参考笔记
2024-10-13 12:07:33
发布于:浙江
T1
题目大意
题目会给出个学生,每个学生必定属于两个集合当中的一员,两个集合分别为与。
每个学员还会有一个朋友圈的集合,范围为从自身开始一直到个同学为一个朋友圈。
领袖筛选资格:
- 朋友圈包含所有同社团同学
- 包含另一个社团的领袖。
题目要求我们求出有多少对人员可以符合这个要求。
思路分析
部分分思维
在1~10的数据范围当中,n的取值始终是小于等于3000的,这就意味着的做法可以通过这部分的数据样例点。
暴力枚举
- 枚举出朋友圈包含G集合的所有人
- 枚举出朋友圈包含H集合的所有人
- 判断这些人之间是否存在着朋友关系 统计对数
for(int i = 1 ; i <= n ; i ++ )
{
for(int j = 1 ; j <= n ; j ++ )
{
//统计选中i和j所覆盖的朋友圈是否包含HG集合的所有人
}
}
但是观察到总体的的范围为,因此在这里只有或者才可以通过。
-
根据题目需求,一个学生被选择为首领条件只有 包含另一个种类的领袖 包含同种类的所有同学。
在两个领袖当中最多只有一个能够满足其中第一个条件。并且满足第二个要求的从左至右的第一个某种类的学生。
*两个满足第一个条件的学生也能凑成一对
-
找出从左到右的第一个当前种类的学生。判断他是否也满足条件2
-
枚举所有的学生,可以去判断它是否包含另一个种类满足条件二的学生,如果有说明符合条件的对数多了一对。
/* Zhiyu_
*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN (200000 + 10)
typedef long long ll;
typedef double dd;
int n, arr[MAXN];
int a[MAXN]; // 判断当前学生的状态是G还是H
int gmax, hmax;
int b[MAXN]; // 当前学生包含的部分
int max_g, max_h, ans;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
char op;
cin >> op;
if (op == 'G') { // 如果当前位置为G则标记为1,最后一个G出现的位置实时更新
a[i] = 1, gmax = i;
} else { // 如果当前位置为H则标记为0,最后一个H出现的位置实时更新
a[i] = 0, hmax = i;
}
}
for (int i = 1; i <= n; i++) cin >> b[i];
// 当前这一名学生包含了其他的所有的同类学生的情况,那么只需要找出第一名学生
// (那么我们在输入的时候则需要加上我们的最远位置的统计)
// 只要第一名学生所涵盖的范围是大于最后一名学生出现的位置,我们记录一下
// 找满足第一条件的学生
for (int i = 1; i <= n; i++) {
if (a[i] == 1) { // 找到第一名G类型的学生
if (b[i] >= gmax) // 该学生所包含的范围超出了最远的一个G学生的位置,更新在max_g
max_g = i;
break; // 第二名学生就不符合情况了
}
}
// 同理找出H类型学生的情况
for (int i = 1; i <= n; i++) {
if (a[i] == 0) { // 找到第一名H类型的学生
if (b[i] >= hmax) // 该学生所包含的范围超出了最远的一个H学生的位置,更新在max_h
max_h = i;
break; // 第二名学生就不符合情况了
}
}
// cout << hmax << " " << gmax << " " << max_g << " " << max_h << endl;
// 枚举满足第二条件的学生,我们的条件二其记录的名单上记录了另一类型学生的"领导者"。
for (int i = 1; i <= n; i++) {
// 出现G类型学生的领导者(通过一条件出现),并且这个领导者在H类型学生包含范围内,那么也是一个情况
// 当前学生在G的领导者之前出现,并且它所涵盖的范围包含了G类型学生
if (max_g && a[i] == 0 && i < max_g && b[i] >= max_g)
ans++;
// 出现H类型学生的领导者(通过一条件出现),并且这个领导者在G类型学生包含范围内,那么也是一个情况
// 当前学生在H的领导者之前出现,并且它所涵盖的范围包含了H类型学生
if (max_h && a[i] == 1 && i < max_h && b[i] >= max_h)
ans++;
}
// H和G类型学生都是自己群体的领导者,如果先出现的领导者并没有把另外一个领导者包含进去
// 那么出现一个特殊情况,每一个领导者管自己的群体,管不到另外一个群体 例:GGGGGHHHHHH
if (max_g && max_h && b[min(max_g, max_h)] < max(max_g, max_h))
ans++;
cout << ans << endl;
return 0;
}
T2
题目意思
在一个二维矩阵当中,题目会给出一个只包含上下左右的边连接的一个正多边形。
然后会给出对起点与终点,求解每一对起点到达终点的最小步数。(可以顺时针或者逆时针进行行走)
思路分析
1. 暴力枚举
- 记录每一个格子的前后坐标
- 每当进行一次提问,那么就从起点正反走到终点,累计步数。
struct Node{
int next_x,next_y; //保存当前顶点下一步的坐标
int pre_x,pre_y; // 保存当前顶点上一步的坐标
}mp[1005][1005];
int n,q;
cin >> n >> q;
int last_x,last_y;
cin >> last_x >> last_y;
for(int i = 2 ; i <= n ; i ++ )
{
cin >> x >> y;
// 保存每一个坐标的前一个节点和后一个节点。
while(last_x < x ){
mp[last_x][last_y].next_x = last_x + 1;
mp[last_x][last_y].next_y = last_y;
last_x ++ ;
mp[last_x][last_y].pre_x = last_x - 1;
mp[last_x][last_y].pre_y = last_y;
}
while(last_y < y){
mp[last_x][last_y].next_y = last_y + 1;
mp[last_x][last_y].next_x = last_x;
last_y ++ ;
}
while(last_x > x)
{
....
}
while(last_y > y)
{
....
}
}
while(q -- )
{
int stx,sty,edx,edy;
cin >> stx >> sty >> edx >> edy ;
int count = 0;
int count2 = 0 ;
while(stx != edx && sty != edy) // 正走
{
int tx = mp[stx].next_x;
int ty = mp[sty].next_y;
stx = tx;
sty = ty;
count ++ ;
}
while(stx != edx && sty != edy) //反走
{
int tx = mp[stx].pre_x;
int ty = mp[sty].pre_y;
stx = tx;
sty = ty;
count2 ++ ;
}
}
cout << min(count1,count2) << endl;
在部分数据当中 还是可以过的
在全部数据当中,他的具体运算时间大致为⬇️
约等于
具体超时的原因还是在每次查询问题的时候 ,超出了时间。
我们最终要去求的还是行走的步数,有没有一种办法可以快速的算出某一段区间的总和呢?
以上核心代码的时间复杂度最多为,一旦出现路线覆盖整个地图,则必然超时。
但是转变思路,路线虽为竖横,正向负向行走,但是我们可以将正向的路线其视为是一条线段,其中的第个顶点的坐标可以视为在第步所能到达的位置,具体如下:
那么我们将正向的路线视为是一条线段,通过在地图当中记录下走到当前格子的步数,每当给出起点与终点坐标时,我们就可以通过直接得到正向行走的步数。
而负向只需要将总步数 - 正向步数即可获得。
通过这样的方式,每次回答的时间复杂度为,最后时间复杂度为最高为
参考代码
#include<bits/stdc++.h>
using namespace std;
int mp[1005][1005];
int main()
{
int n,p;
cin >> p >> n;
int sx,sy,nx,ny;
cin >> sx >> sy;
n--;
int x=sx;
int y=sy;
int cnt = 0; // 统计总步数
while(n--)// 将步数累计在地图当中的每一格
{
cin >> nx >> ny;
while(x < nx)mp[++x][y] = ++ cnt;
while(x > nx)mp[--x][y] = ++ cnt;
while(y < ny)mp[x][++y] = ++ cnt;
while(y > ny)mp[x][--y] = ++ cnt;
}
nx=sx; //形成闭环 再走一次
ny=sy;
while(x < nx)mp[++x][y] = ++ cnt;
while(y < ny)mp[x][++y] = ++ cnt;
while(x > nx)mp[--x][y] = ++ cnt;
while(y > ny)mp[x][--y] = ++ cnt;
while(p--)
{
int ex,ey;
cin >> x >> y >> ex >> ey;
int temp = abs(mp[x][y] - mp[ex][ey]); // 正向行走
cout << min (temp,cnt-temp) << endl; // 跟负向取最小值则为答案
}
return 0;
}
T3
题目大意
给出两个数字,需要使其通过两种操作变为相等。
- 给进行+1操作
- 当为偶数,可以除2或者乘2
每次执行视为一次操作,最少几次操作让其变为一致?
思路解析
为了尽可能让a与b接近,在只能对a进行操作的情况下,我们需要不停的将其缩小,也就是通过/2与+1的操作使其变小。
-> or
若出现2*a < b 的情况下,如果我们直接去累加1的话,可能会出现漏掉部分a/=2或者a+=1的操作使得次数更小的情况。
但是很麻烦的事情是,你没有办法去判断a的取值到达多少才比较合适,因为他的浮动过大,边界难以去限定。
那么我们换一个思路,我们只是为了求解最少次数,b的操作是否存在一些与a的操作等价的情况?
例如 b = 10 a = 20 ,操作为a /= 2 ;
换算成等价公式,也可以视为 b*= 2;
那么在面对2*a的情况下,我们不对a进行操作,因为边界值无法确定,但是我们可以通过等价的换算对b进行同等的价值操作。
也就是
$ a*2 < b$ :
假如:
只能执行+1的操作,使其变为b 并不正确。
这时候,a有可能通过*2的操作变为大于b的情况,在通过+1的操作变为b的倍数在除2刚好变为距离b更接近的数字,操作次数刚好比直接+1更小。
这种情况下,操作次数是没有办法确定一个方案一定可以得到最值的,我们就需要把这个范围的操作次数全部枚举出来,但是只对a进行这样的操作范围太广了,几乎无法确定具体的边界。
因此,我们可以将a*=2 和a+=1的操作 等价转换为b /=2 和 b-=1的操作,将a和b同时进行/=2的+1,-1的操作,枚举完a和b逐渐变为1的情况,最后选择出现过的操作次数。
特殊样例
answer = 15
若a=110,且b=200,count代表当前情况下通过+1和之前/2的操作次数使其相等的次数
- a = 110 b = 200 count = 90
- a = 55 , b = 100 , count = 47
- a = 28 , b = 50 count = 29
- a = 14 , b = 25 count = 18
- a = 7 , b = 12 count = 15
- a = 4 , b = 6 count = 15
- a = 2 ,b = 3 count = 16
取其出现的最小值15作为答案。
直接输出
操作步骤
- 使 a>b -> a< b
- 使 2*a < b -> 2*a > b
- 枚举在2*a < b范围当中a和b的所有取值求最小值操作次数
#include<iostream>
using namespace std;
typedef long long ll;
ll a,b;
int a_b() // 让a>b -> a<b
{
ll count = 0 ;
while(a > b)
{
if(a&1)a++,count ++ ;
a /= 2;
count ++ ;
}
return count ;
}
int get_b1() // 让2*a < b -> 2 * a > b
{
int count = 0 ;
while(b >= 2*a)
{
if(b&1)count ++ ; // b变为偶数 a+1等价为b-1
b /= 2;
count ++ ;
}
return count ;
}
int b_a() // 枚举2*a > b 情况下 ab相等的所有取值
{
if(a == b)return 0 ;
int count = 0 ;
ll last_sum = b - a; // 统计+1的操作次数
while(a)
{
if(a&1)a++,count ++ ;
if(b&1)count ++ ;
b/=2;
a/=2;
count += 2;
ll it_sum = b - a + count ;
if(b < a || last_sum <= it_sum)
{
break;
}else last_sum = it_sum;
if(a == b){
last_sum = it_sum ;
break;
}
}
return last_sum;
}
void solve()
{
std::cin >> a >> b;
ll count = a_b();
count += get_b1();
count += b_a();
std::cout << count << endl;
}
int main()
{
int n;
std::cin >> n;
while(n--)
{
// std::cout << n << endl;
solve();
}
return 0;
}
T4
给出一字符串,字符串只有字符COW
。
其中任意一个字符可以转换为另外两个字符,并且排列顺序随意排列
例C
-> OW
任意两个不同的字符排在一起,可以转换为另一个与这两个字符都不同的字符
例 ‘OW’ -> 'C'
然后我们就可以发现一个非常好玩的性质 逆向操作
我们可以把任意两个不同的字符排列,视为另外一个不同的字符的等价
例: 'C' ->'OW' ->'C' , 'OW'就可以视为是一个C
两个相同的字符可以对消
例:CC
-> '' 删除相临相同的字符
题目目的:通过两种操作也没有可能把字符串的某一个子串变为只剩下C
的情况。
思路解析
Q1:是否有可能通过无线的扩展延伸,让字符变为只剩下一个C的字符?
例:'COW' -> 'OWOW' -> 'CWWOW' ...
A1: 我们可以通过题目给出来的条件,得到等价公式 任意两个不同的字符排列 等价于 另一个完全不同的字符 因此假若这个字符串本身就是合法的,那么一定有办法,假如本身就不合法,就不可能通过无线的拓展操作变为字符串C
。
问题就转换为了,如何判断这个字符串本身是合法的?难道输入这个字符串本身就决定了是否能变为字符串C
。
例'COWC' 输入本身如此那么他就必然不合法吗?其实并不是。
关键性质:任意两个不同的字符可以 交换位置
例: 'OW' -> 'WCCO' -> 'WO'
也就是说,字符串本身的字符排列顺序是可以变为类似于冒泡排序的相临字符交换位置。
那么,刚才的例子‘COWC’ -> 'COCW' -> 'CCOW' -> 'OW' -> 'C' 合法!
那么,剩下来的问题,就变为统计字符WCO
的个数,判断是否能够只剩下C即可
对于COW的字符个数做一个前缀和数组,在获取子串范围的时候,通过O(1)的时间复杂度计算出子串内的字符个数。
#include<iostream>
using namespace std;
const int MAXN = 2e5+7;
int q;
int C[MAXN],W[MAXN],O[MAXN];
int main()
{
string s;
cin >> s;
cin >> q;
s = ' ' + s;
for(int i = 1 ; i < s.size() ; i ++ )
{
C[i] = C[i-1] + (s[i] == 'C');
W[i] = W[i-1] + (s[i] == 'W');
O[i] = O[i-1] + (s[i] == 'O');
}
while(q--)
{
int l,r;
cin >> l >> r;
int Ccnt = C[r] - C[l-1];
int Wcnt = W[r] - W[l-1];
int Ocnt = O[r] - O[l-1];
// cout << Ccnt << " " << Wcnt << " " << Ocnt << endl;
if((Ccnt & 1) && !(Wcnt&1) && !(Ocnt&1)){
cout << "Y" ;
}else if (!(Ccnt & 1) && (Wcnt&1) && (Ocnt&1)){
cout << "Y" ;
}else {
cout << "N" ;
}
}
return 0;
}
这里空空如也
有帮助,赞一个