Codeforces round 900 (Div.3)（G未补）

目录

A. How Much Does Daytona Cost?

B. Aleksa and Stack

C. Vasilije in Cacak

D. Reverse Madness

E. Iva & Pav

1，线段树+二分

2，前缀按位与+二分

3，ST表+二分

F. Vasilije Loves Number Theory

G. wxhtzdy ORO Tree

A. How Much Does Daytona Cost?

题意大概是给定一个长度为n的序列a和一个数k，问我们是否能在序列a中找到一个子序列，使得子序列中出现次数最多的数是k

因为没有要求子序列的长度，也就是说，只要序列中出现了k，我们就可以找到长度为1的子序列，这个子序列只包括k，那么这就找到一个符合题意的解了

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 1e5 + 10;int main()
{int t;scanf("%d",&t);while(t--){int n,k;scanf("%d%d",&n,&k);bool flag=false;for(int i=0;i<n;i++){int x;scanf("%d",&x);if(x==k)flag=true;}if(flag)puts("YES");else puts("NO");}return 0;
}

B. Aleksa and Stack

题意大概是，给定一个n，要求我们构造一个序列，使得对于每个下标i，都满足3*ai+2%（ai + ai+1)!=0 (1≤i≤n−2).

那么我们可以发现，如果序列中全是奇数的话，奇数+奇数=偶数，奇数*3=奇数，偶数是不可能整除奇数的，因此就找到一个满足题意的构造了

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 2e5 + 10;int a[N];int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1,j=1;i<=n;i++,j+=2)printf("%d ",j);printf("\n");}return 0;
}

C. Vasilije in Cacak

题意大概是给定一个n，有一个长度为1~n的序列，在给定一个k和x，问是否能在序列中挑选k个不同的数相加起来恰好等于x

首先，我们可以对序列预处理求前缀和，这样就可以求出来，用k个数能凑出来的最小值和最大值，如果x不在这个最小值到最大值的区间中，显然我们是不可能凑出来的，如果x在这个范围中，那么就一定能凑出来，证明如下

首先我们可以取前k个数，也就是1 ，2，3……k，当我们想让这k个数凑出来的数+1的话，只需要不选第k个数而选择第k+1个数，同理，想加2的话可以在不选第k-1个数，选择第k个数，如此往复，肯定能凑出来最小值到最大值这个范围的所有数

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 2e5 + 10;ll sum[N];int main()
{for(int i=1;i<=N;i++)sum[i]=sum[i-1]+i;//因为有多组询问，我们可以预处理出来N的前缀和int t;                 //如果这题n很大的话，我们可以不求前缀和，用等差数列的求和公式求最小值和最大值scanf("%d",&t); while(t--){int n,k;ll x;scanf("%d%d%lld",&n,&k,&x);if(x>=sum[k]&&x<=sum[n]-sum[n-k])puts("YES");else puts("NO");}return 0;
}

D. Reverse Madness

题意大概是给一个长度为n的字符串s，然后给两个长度为k的左边界数组，和右边界数组，并且满足l1=1，rk=k，对于任意i，满足li<=ri,且li=ri-1+1，接下来有q个操作，每个操作给定一个x，找到一个x满足li<=x<=ri，因为有上面的条件，这样的区间一定是唯一的，然后

• Let a=min(x,ri+li−x) and let b=max(x,ri+li−x)
• 翻转字符串s中下标从a到b的这个子串，输出经过q次操作后的s

 这题看似是一个模拟题，如果暴力去模拟的话，肯定是会超时的。暴力模拟的过程是，首先我们要找到x所在的区间，然后计算a和b，在翻转a到b的这个子串，这样下来加上q次询问，时间复杂度最坏会达到O（qN），一定会超时的，就算我们用二分查找x所在的区间，翻转子串时最坏同样会达到O（N）的时间复杂度，时间复杂度还是O（qN）的，因为我们的目的就是看是否能将翻转这步操作优化一下。

首先对于所有的l【i】~r【i】,每个区间是互不影响的，然后我们模拟几个样例会发现，每次翻转都是对称的，具体可以看一下这个样例

10 1

aghcdegdij

1

10

5

1 2 3 4 2

我们会先翻转1~n，然后翻转2~n-1，然后翻转3~n-2……，我们会发现，对于任何一个位置，如果这个位置翻转次数位偶数，等价于没有翻转，如果是奇数，就需要跟以区间中心堆成的点交换位置，例如，如果我们进行了前两次操作，那么得到的结果就是 jghcdegdia，中间的八个字符等于没变，左右端点的两个字符交换了一下位置，因此我们可以得到结论，如果一个位置操作了奇数次，等价于将这个位置和以其所在区间的中心的对称位置交换位置，如果为偶数次，等价于没有操作

因此，结合模拟的过程，我们首先二分查找x所在的区间，然后将a到b这个区间中的每个位置需要的操作数+1，这里可以用一个差分来优化区间修改，记录完后求一遍差分数组的前缀和就是所有点的操作次数，接着我们要遍历每个给定的区间，因为我们并不知道如果一个位置需要操作，他是跟谁换位置，所以要遍历每个区间，找到需要操作的位置所在的区间，然后进行操作，要注意一点，枚举区间时一定是枚举区间的左半边，因为我们对整个区间进行了区间修改，且区间是对称的，所以如果需要操作的位置为奇数，与他对称的位置也一定是奇数，如果枚举了整个区间，那我们就操作了两次，又等于没有操作了

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 2e5 + 10;int n,k,q;
int l[N],r[N],c[N];
char str[N];int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);for(int i=0;i<=n;i++)c[i]=0;scanf("%s",str+1);for(int i=1;i<=k;i++)scanf("%d",&l[i]);for(int i=1;i<=k;i++)scanf("%d",&r[i]);scanf("%d",&q);while(q--){int x;scanf("%d",&x);int left=1,right=k;//二分查找x所在的区间while(left<right){int mid =left+right>>1;if(l[mid]<=x&&x<=r[mid]){left=mid;break;}if(x<l[mid])right=mid;else left=mid+1;}int id=left;int L=min(x,l[id]+r[id]-x),R=max(x,l[id]+r[id]-x);//计算a和bc[L]++,c[R+1]--;//差分}for(int i=1;i<=n;i++)c[i]+=c[i-1];//差分数组求前缀和for(int i=1;i<=k;i++){for(int j=l[i];j<=(l[i]+r[i])/2;j++)//这里一定是枚举左半边区间，因为是对称的{if(c[j]&1)//如果出现了奇数次，就交换swap(str[j],str[r[i]+l[i]-j]);//以区间中点对称交换}}printf("%s\n",str+1);}return 0;
}

E. Iva & Pav

题意大概是定义一个函数为f（l，r）=al&al+1&al+2&……ar

给定一个长度为n的序列a和q个询问，每个询问给定一个l，k，要求找到最大的r满足f（l，r）>=k

这题的解法很多，最简单直观的肯定是线段树，因为题目要求我们维护一个区间，只有区间查询，没有区间修改，所以我们只需要写一个只有查询操作的线段树，很好写，我们二分枚举区间长度，配合线段树的区间查询，注意一下按位与的问题细节问题就好l

1，线段树+二分

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 2e5 + 10;int n;
int a[N];
struct Node
{int l, r;int sum;//当前区间的异或和
} tr[N * 4];void pushup(int u)//用子节点更新父节点信息
{tr[u].sum = tr[u << 1].sum & tr[u << 1 | 1].sum;
}
void build(int u, int l, int r)//建立线段树
{if (l == r)tr[u] = {l, r, a[l]};else{tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);}
}
int query(int u, int l, int r)//区间查询
{if (tr[u].l >= l && tr[u].r <= r)//如果当前区间被查询区间完全覆盖，就返回当前区间异或和return tr[u].sum;else{int ans = 0;int mid = tr[u].l + tr[u].r >> 1;if (l <= mid)ans = query(u << 1, l, r);//这里要注意，是赋值=，不能用0按位与，0跟任何数按位与都是0if (r > mid){if (ans || l <= mid)//如果跟左儿子有交集，说明左儿子异或和有值或者为0，这时才跟右儿子按位与ans &= query(u << 1 | 1, l, r);else//否则是赋值，不是按位与ans = query(u << 1 | 1, l, r);}return ans;}
}
int main()
{int t;scanf("%d", &t);while (t--){scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);build(1, 1, n);int q;scanf("%d", &q);while (q--){int l, k;scanf("%d%d", &l, &k);int L = 1, R = n - l + 1;//二分枚举长度while (L < R){int mid = L + R + 1 >> 1;if (query(1, l, l + mid - 1) >= k)L = mid;else R = mid - 1;}if (query(1, l, l + R - 1) >= k)printf("%d ", l+R-1);//查询完了也要最判断一下是否满足条件else printf("-1 ");//不满足输出-1}printf("\n");}return 0;
}

2，前缀按位与+二分

我们用二位数组f[i][j]表示从第1位到第i位数中的第j位二进制中1出现的个数，我们首先处理出来前n个数的中每一位二进制中1出现的次数，同时已经固定好了左边界，因此我们可以用二分枚举右边界，f[r][j]-f[l-1][j]就表示第l个数到第r个数的第j为二进制中1出现的次数，如果等于区间长度，那么二进制都为说明区间中每个数的第k位二进制都为1，异或起来还是1，对答案贡献1<<j，如此往复遍历完每一位二进制，最终就可以得到第l个数一直按位与到第r个数的值，然后二分判断即可

同时，对于给定的l，如果a[l】<k，那么就不可能找到一个右边界，因为按位与只会越来越小

代码如下：

#include <iostream>
#include <algorithm>using namespace std;const int N = 2e5 + 10;int n;
int a[N], f[N][30];void get_prefix()
{for (int i = 1; i <= n; i++)//遍历每个数{for (int j = 0; j < 30; j++)//遍历每个数的每一个二进制位{if (a[i] & (1 << j))//为1的话数量加1f[i][j] = f[i - 1][j] + 1;else//否则不变f[i][j] = f[i - 1][j];}}
}
int main()
{int t;scanf("%d", &t);while (t--){scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);get_prefix();//求前缀按位与，求出前缀中每一位二进制中1出现的次数int q;scanf("%d", &q);while (q--){int l, k;scanf("%d%d", &l, &k);if (a[l] < k)//说明不可能找到答案了{printf("-1 ");continue;}int left = l, right = n;//二分枚举右边界while (left < right){int mid = left + right + 1 >> 1;int num = 0;for (int i = 0; i < 30; i++)//要遍历二进制的每一位，找到区间的异或值{if (f[mid][i] - f[l - 1][i] == mid - l + 1)num += (1 << i);}if (num >= k)left = mid;else right = mid - 1;}printf("%d ", right);}printf("\n");}return 0;
}

3，ST表+二分

要想一个题能用ST表来做，那么该问题得是可重复贡献问题，且只有查询操作，没有修改操作，对于这一类问题，用ST表的效率要高于线段树。如何解释这类问题呢，例如，对于给定一序列，我们要查询子序列的最大值或者最小值，我们可以求出其中一段的最大值和其中另外一段的最大值，如果这两段有重复也不会影响答案，最后取一个max，就可以得到整个区间的最大值。但是如果我们求的是区间和，如果有区间重复了，就会影响答案，对于这样的求区间和的问题就不是可重复贡献问题，对于求区间最大值最小值这类问题，就是可重复贡献问题。简单来说就是，如果相同的数出现在两个区间中，不影响正确答案，就是可重复贡献问题。

接着我们看按位与，如果两个区间中有相同的数，相同的数按位与上相同的数，得到的答案为自身，即X&X=X，所以这个题满足可重复贡献

类似于求区间最大值的st表做法，我们用一个二维数组f[i][j]表示以第i个数开始连续2^j个数的按位与的值，例如f[1][0]即为从第一个数开始连续1个数的按位与的值，就是a[1]自己，f[1][1]即为a[1]&a[2]，f[1][2]即为a[1]&a[2]&a[3]&a[4]

那么我们可以得到f[i][j]=f[i][j-1]&f[i+(1<<(j-1))][j-1]

对于每次询问，我们二分枚举右边界，然后查表就可以快速得到答案，时间复杂度是O（1）的

代码如下：

#include<iostream>
#include<algorithm>using namespace std;const int N = 2e5 + 10;int n;
int a[N],st[N][20];int query(int l,int r)
{int z=0;while((1<<z+1)<=r-l+1)z++;//找到合适的区间长度return st[l][z]&st[r-(1<<z)+1][z];
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);st[i][0]=a[i];//首先要确定边界}for(int j=1;j<=20;j++)//先枚举jfor(int i=1;i+(1<<j)-1<=n;i++)//再枚举每一个数a[i]st[i][j]=st[i][j-1]&st[i+(1<<(j-1))][j-1];//预处理出来st表int q;scanf("%d",&q);while(q--){int l,k;scanf("%d%d",&l,&k);int left=l,right=n;//二分枚举右边界while(left<right){int mid = left + right + 1 >> 1;if(query(l,mid)>=k)left = mid;else right = mid - 1; }if(query(l,right)>=k)printf("%d ",right);//查询完了也要判断一下，最后得到的答案是否满足条件else printf("-1 ");//不满足就输出-1}printf("\n");}return 0;
}

F. Vasilije Loves Number Theory

题意很简单，大概意思是给定一个整数n，定义d（n）为n的约数个数，给定q个操作，操作1 为给定一个x，让n=n*x，问是否能找到一个a，满足gcd（a，n）=1，d（a*n）=n。操作2为将n变回最初给定的n。要注意的时，每次执行操作1后不会将n变回最初的n

先给出结论：如果d（n）能整除n，即n%d（n）==0那么就能找到一个a，否则不能.

证明：根据唯一分解定理，任何一个数n都能被表示成n=,p表示n的质因数，b表示该质因数出现的次数。n的约数个数就等于那么如果想要找到一个a满足gcd（a,d）=1，那么一定要满足a分解质因数后得到的每个质因数都与n得到的质因数不同。假设我们已经找到一个满足条件的a，且a分解质因数的结果是pk+1^bk+1 * pk+2^bk+2 ,那么a的约数个数就为,记为X，那么a*n= *，那么同理d（a*n）=*,因此题目就转换成了d（a*n）=d（n）*X=n,要想使这个等式成立，X的取值很好找，如果d（n）=n，那么我们X取1，只要找到一个不是n的质因数的质数m，那么就是a的值，如果d（n）！=n，只要d（n）能整除n，那么,我们只要找到一个不是n的质因数的一个质数m，那么就是a的值。因此只要满足d(n)能整除n，我们就可以找到一个满足条件的a

但是这题中n可能会非常大，可能会爆longlong，因此我们不能直接求出来每次操作1过后的n，再求n的约数个数，然后直接判断，我们可以换一种思路，将n分解成质因数，用唯一分解定理来表示n，这样同时我们可以算出来n的约数个数，最后如果d（n）能整除n的话，那么d（n）一定跟n有相同的质因数，且对于这个相同的质因数，n中这个质因数出现的次数b一定大于等于d（n）中这个质因数出现的次数b，例如2能整除12，2的唯一分解后为2=2^1,12的唯一分解后为12=2^2*3^1，相同的质因数为2，且2中2出现的次数小于12中2出现的次数，那么如果能用n把d（n）的相同的质因数消除，d(n)的值就会变成1，就说明d（n）能整除n，即我们只需要消去以后判断d（n）是否为1即可。

同时，处理时有一个小优化，我们可以预处理出来1~1e6中每个数的最小质因数，这样就可以快速的求出来每个数的质因数以及质因数出现的次数（具体操作看代码），这一步可以用线性筛法快速求出。同时，对于操作1，每次乘上一个x，等价于增加n中已经有的质因数的出现的次数或者是增加质因数的个数，对于每个操作1，我们要先将n的约数个数除去n与x共有的质因数在n中出现的次数，重新统计加上x中该质因数出现的次数，再乘上这个质因数出现的总次数

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 1e6 + 10;int n, q, cnt;
int v[N], minp[N], prime[N];
//v[i]表示i是否被筛过，minp[i]表示i的最小质因数，prime记录下1~1e6中所有的质数void oula()//线性筛
{for (int i = 2; i <= N; i++)//线性筛的下标要从2开始{if (!v[i]){prime[cnt++] = i;minp[i] = i;//如果这个数是质数，他的最小质因数就是自己}for (int j = 0; prime[j] <= N / i; j++){v[i * prime[j]] = 1;minp[i * prime[j]] = prime[j];//通过prime[j]被筛掉的数的最小质因数就是prime[j]if (i % prime[j] == 0)break;}}
}
int main()
{oula();//首先预处理出来1~1e6中所有数的最小质因数int t;scanf("%d", &t);while (t--){scanf("%d%d", &n, &q);map<int, int> mp;//存储n的质因数出现的次数ll number = 1;//记录n的约数个数while (n > 1)//将n分解质因数{int p = minp[n];//n的最小质因数while (n % p == 0){mp[p]++;n /= p;}number *= (mp[p] + 1);//记算n的约数个数}auto init_number = number;//初始时n的约数个数auto init_mp = mp;//初始时n的质因数以及质因数出现的次数while (q--){int op, x;scanf("%d", &op);if (op == 1){scanf("%d", &x);while (x > 1)//将x分解质因数{int p = minp[x];//x的最小质因数number /= (mp[p] + 1);//要先减去n的这个质因数出现的次数，重新统计这个质因数出现的次数while (x % p == 0){mp[p]++;x /= p;}number *= (mp[p] + 1);//重新统计了重复质因数出现的次数后，重新计算n的约数个数}//判断d（n）是否能整除nll c = number;for (auto [a, b] : mp){while (c % a == 0 && b){c /= a;b--;}}if (c == 1) printf("YES\n");else printf("NO\n");}else//恢复成初始状态{number = init_number;mp = init_mp;}}puts(" ");}return 0;
}

G. wxhtzdy ORO Tree