Codeforces Round 900 (Div. 3)
A. How Much Does Daytona Cost?
解题思路:
可取一个元素作为子数组，数组中存在\(k\)即可。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
int n;
int k;
void solve()
{
scanf("%d %d",&n,&k);
vector<int> a(n + 1);
bool st = false;
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i] == k)
{
st = true;
}
}
if(st)
{
puts("YES");
}
else
{
puts("NO");
}
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
}
B. Aleksa and Stack
解题思路:
构造一 ：从\(1e9\)开始自减，从左放到右，放\(n\)个即可。
构造二：\(1,3,5,7,...,2n - 1\).其中,\(a[i]为奇数，(a[i-1]+a[i-2]) * 3 为偶数\)。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
int n;
int k;
void solve()
{
scanf("%d",&n);
vector<ll> a(n + 1);
ll res = 1e9;
int cnt = 0;
for(int i = n;i;i--)
{
a[i] = (res - cnt);
cnt ++;
}
for(int i = 1;i<=n;i++)
{
// if((3 * a[i]) % (a[i-1] + a[i-2]) == 0)
// {
// puts("NO");
// return;
// }
printf("%lld ",a[i]);
}
puts("");
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
}
C. Vasilije in Cacak
解题思路:
下界：\(l = \sum_\limits{i = 1}^ka_i\)。
上界:\(r = \sum_\limits{i = n - k + 1}^na_i\)。
如果\(l \leq x \leq r\),那么就是\(YES\).
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
ll n, k, x;
void solve()
{
scanf("%lld %lld %lld", &n, &k, &x);
ll d = k * (k + 1) / 2;
ll u = (2 * n - k + 1) * k / 2;
if (x >= d && x <= u)
{
puts("YES");
}
else
{
puts("NO");
}
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
}
D. Reverse Madness
解题思路：
根据题意:\(l_i \leq r_i < l_{i + 1} < r_{i + 1}\)。
所以对于一个\(x\)，他的\(l_i \leq x \leq r_i\)是唯一的。
我们设\(x = l_i + k\)。带入题目中给的式子。
\[\begin{align*}
a &= min(x,r_i + l_i - x)\\
&= min(l_i + k,r_i - k)\\
b &= max(x,r_i + l_i - x)\\
&= max(l_i + k,r_i - k)
\end{align*}
\]
所以对于给定的\(x\),他翻转的范围一定是从一个\(l,r\)中心，向左右等距离的扩展。
那么，对于一个区间\(l_i,r_i\),我们只要根据给出的\(x\)进行一个类似差分数组的修改。等全部修改完之后，进行一个前缀和就可以得知每个位置被修改的次数。
对于同一个位置，偶数次翻转等于没操作。所以每个位置至多操作一次。
实现方法一：异或前缀和\(O(n)\)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, k;
void solve()
{
scanf("%d %d", &n, &k);
vector<int> l(k + 1), r(k + 1);
string s;
cin >> s;
for (int i = 1; i <= k; i++)
{
scanf("%d", &l[i]);
l[i]--;
}
for (int i = 1; i <= k; i++)
{
scanf("%d", &r[i]);
r[i]--;
}
int m;
scanf("%d", &m);
vector<int> cnt(n + 1, 0);
while (m--)
{
int x;
scanf("%d", &x);
x--;
cnt[x] ^= 1;
}
for (int i = 1; i <= k; i++)
{
int st = 0;
for (int j = l[i]; j < r[i] + l[i] - j; j++)
{
st ^= cnt[j] ^ cnt[r[i] + l[i] - j];
if (st)
{
swap(s[j], s[r[i] + l[i] - j]);
}
}
}
cout << s << endl;
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
}
实现方法二：二分+普通前缀和\(O(qlog(k) + (k + n))\)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, k;
void solve()
{
scanf("%d %d", &n, &k);
vector<int> l(k + 1), r(k + 1);
string s;
cin >> s;
for (int i = 1; i <= k; i++)
{
scanf("%d", &l[i]);
l[i]--;
}
for (int i = 1; i <= k; i++)
{
scanf("%d", &r[i]);
r[i]--;
}
int m;
scanf("%d", &m);
vector<int> cnt(n + 10, 0);
while (m--)
{
int x;
scanf("%d", &x);
x--;
int ll = 1;
int rr = k + 1;
while (ll + 1 < rr)
{
int mid = ll + rr >> 1;
if (l[mid] <= x)
{
ll = mid;
}
else
{
rr = mid;
}
}
int idx = ll;
int a = min(x, l[idx] + r[idx] - x);
int b = max(x, r[idx] + l[idx] - x);
cnt[a]++;
cnt[b + 1]--;
}
for (int i = 1; i <= n; i++)
{
cnt[i] += cnt[i - 1];
}
for (int i = 1; i <= k; i++)
{
for (int j = l[i]; j <= l[i] + r[i] - j; j++)
{
if (cnt[j] & 1)
{
swap(s[j], s[r[i] + l[i] - j]);
}
}
}
cout << s << endl;
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
}
实现方法三:\(splay\)翻转
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register
#define inf 0x7f7f7f7f
#define maxn 325000
#define int ll
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c<='9'&&c>='0')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0)
{
x=-x;
putchar('-');
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int t,n,k,a[maxn],b[maxn],q;
string s;
int q_l[maxn],q_r[maxn];
int ch[maxn][3];//ch[x][0] 代表x节点的左儿子 ch[x][1]代表x节点的右儿子
int val[maxn];//val[x] 代表x这个点的点权值
int cnt[maxn];//cnt[x] 代表有多少个与x这个点权值相同的点
int par[maxn];//par[x] 代表x的父亲节点
int siz[maxn];//siz[x] 代表x的子树(包括它自己在内)有多少个点,包括cnt[x](重复的点)
int root;//这棵树的根
int ncnt;//当前这课树的节点个数(不算权值相同的重复节点)
int rev[maxn];//反转数组 1--表示需要反转 0--表示不需要
inline int find_dir(int x)//查看x这个节点是其父亲节点的左儿子还是右儿子
{
return ch[par[x]][1]==x;
}
inline void pushup(int x)//更新x节点的siz值
{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];
}
inline void rotate(int x)//splay最重要的操作旋转 是保持整颗树平衡的关键
{
int father=par[x];//找到x的父亲
int grandfather=par[father];//找到x的爷爷
int dir=find_dir(x);//找到x与其父亲的关系 dir==1 x为右儿子 dir==0 x为左儿子
int son=ch[x][dir^1];//找到x的儿子(与x和x父亲关系刚好相反,所以^取反)
ch[father][dir]=son,par[son]=father;//将x的儿子与x的父亲连边
ch[grandfather][find_dir(father)]=x,par[x]=grandfather;//将x的爷爷与x连边 其中x的方向与其父亲节点的方向相同(x它爸是它爷爷的什么节点,它也是)
ch[x][dir^1]=father,par[father]=x;//将x与其父亲节点连边 两者方向与原来相反,所以取反
pushup(father),pushup(x);//更新siz,注意从小往上更新,所以先更新father,再是x,整个过程不会影响其爷爷节点的siz,所以不用更新
}
inline void splay(int x,int goal=0)//伸展操作 将x这个节点一路旋转,成为目标节点(goal)的儿子 此处goal如果不传参,则默认将x旋成根
{
//如果该节点、该父节点和该爷爷节点「三点一线」,那么应该先旋转父节点. 只有这样才能维持二叉的模样,保证时间复杂度
while(par[x]!=goal)//当x不为goal的儿子时就一直旋转
{
int father=par[x];//找爸爸
int grandfather=par[father];//找爷爷
if(grandfather!=goal)//当爷爷也不为目标节点时
{
if(find_dir(father)==find_dir(grandfather))//当三点一线时
{
rotate(father);//先旋父亲
}
else rotate(x);//否则直接旋儿子
}
rotate(x);
}
if(!goal) root=x;//如果目标节点不是根节点,就把x设为根
}
inline void find(int x)//辅助节点 将最大的小于等于x的节点rotate到根节点来 (此时的x并不是节点编号,而是一个具体的值)
{
// if(root==0) return;//root=0说明不成一棵树
int cur=root;
while(ch[cur][x>val[cur]]&&x!=val[cur])//如果x大于cur,就往cur的右儿子去找(x>val[cur]==1),否则就去找它的左儿子,当存在val[cur]==x时,此时cur就是找的那个点,结束循环直接伸展
{
cur=ch[cur][x>val[cur]];//根据cur与x的大小来决定往哪个方向继续找
}
splay(cur);
}
inline void insert(int x)//插入大小等于x的点 如果存在相同的值,则cnt++,否则新建一个大小为x的点
{
//ps:因为新建节点时可能会拉出一条链,所以新建节点后需要将该节点splay到根节点.
//沿途的rotate操作可以使平衡树恢复平衡.
int cur=root,p=0;
while(cur!=0&&x!=val[cur])
{
p=cur;
cur=ch[cur][x>val[cur]];//根据cur与x的大小来决定往哪个方向继续找
}
//上面这个while会因为两种情况而停止
//1.cur!=0,说明找到大小与x相同的点
if(cur!=0) cnt[cur]++;//这种时候直接++即可
else//cur==0,说明没有找到大小与x相同的点,需要新建一个大小与x相同的节点
{
cur=(++ncnt);
if(p>=1) ch[p][x>val[p]]=cur;//经过一致讨论,if(p>=1)可以不要,不过加上也不算错 这一步目的是确定x是p的什么儿子
//以下操作是对新节点cur进行初始化
ch[cur][0]=ch[cur][1]=0;//cur作为叶子节点,它压根没儿子
siz[cur]=cnt[cur]=1;
par[cur]=p;
val[cur]=x;
}
splay(cur);//将它转到根节点
}
inline void pushdown(int x)//整体思路与线段树打标记类似
{
if(rev[x]!=0)//如果x的左右子树需要翻转
{
swap(ch[x][0],ch[x][1]);//翻转左右子树
rev[ch[x][0]]^=1;//同时往下继续打标记
rev[ch[x][1]]^=1;
rev[x]=0;//清楚x节点所标记号
}
}
inline int k_th(int k)//询问整棵树中 第k小的点
{
int cur=root;
while(1)
{
pushdown(cur);
if(ch[cur][0]!=0&&siz[ch[cur][0]]>=k)//如果当前节点存在左儿子,同时左子树总节点个数是不下于K的,那么优先找左边
{
cur=ch[cur][0];//找当前节点的左儿子
}
else if(k>siz[ch[cur][0]]+cnt[cur])//如果左子树的节点个数包括这个节点本身都不满足第k小(即他们之和小于k)
{
k-=siz[ch[cur][0]]+cnt[cur];//那么可以将问题给缩小
//变成:在当前节点的右子树中寻找第(k-siz[ch[cur][0]]+cnt[cur])的点
cur=ch[cur][1];//找当前节点的右儿子
}
else
{
return cur;//找到了
}
}
}
inline int pre(int x)//查找前驱 (此处的x为值,而不是节点编号) 前驱定义:前驱节点val值小于该节点val值并且值最大的节点
{
find(x);//find x 后,直接查看左子树最大的树就是它的前驱(即整个左子树最右边的数)
//ps:有一点需要注意,find所找的是最大的小于等于x的节点,而前驱定义是最大的小于x的节点
//两者的差异在于find有等于 前驱没有等于
//那么可能会有一种情况,如果find找到的节点本身就是小于x的节点,那么这个节点就是x的前驱
//但是此时这个节点又被设置成了整棵树的根
//所以我们此时就不能返回这个节点的左子树的最大值,而是直接返回这个根节点
if(val[root]<x) return root;//这一步的目的就在这里
else//否则的话find就是把大小等于x的节点设置成了根节点,那么小于根节点的最大值根据二叉树的定义可得位于左子树的最右边
{
int cur=ch[root][0];//左儿子
while(ch[cur][1]>=1)//这个循环就是来找前驱的
{
cur=ch[cur][1];
}
return cur;
}
}
inline int succ(int x)//查找后继 原理与方法与查找前驱相同 后继定义:后继节点val值大于该节点val值并且值最小的节点
{
find(x);//
if(val[root]>x) return root;
else
{
int cur=ch[root][1];
while(ch[cur][0]>=1)
{
cur=ch[cur][0];
}
return cur;
}
}
inline void remove(int x)//删除操作 将x这个点删除
{
int next=pre(x);//前驱
int last=succ(x);//后继
splay(next);//将前驱splay到根
splay(last,next); //将后继splay成前驱的儿子,一定是右儿子
int del=ch[last][0];//此时后继的左儿子就是x
if(cnt[del]>1)//要特判下cnt大于1的情况
{
cnt[del]--;
splay(del);
}
else
{
ch[last][0]=0;//否则就直接置为0
}
}
inline void reverse(int l,int r)
{
int x=k_th(l),y=k_th(r+2);//x--l-1 y--r+1
splay(x),splay(y,x);
rev[ch[y][0]]^=1;//对于r+1的左子树进行反转
}
inline void out_put(int x)
{
pushdown(x);
if(ch[x][0]!=0) out_put(ch[x][0]);//自上往下递归
if(val[x]!=0&&val[x]<=n)
{
printf("%c",s[val[x]]);
}
if(ch[x][1]!=0) out_put(ch[x][1]);
}
signed main()
{
t=read();
while(t--)
{
n=read(),k=read();
cin>>s;
s=" "+s;
for(rg int i=0;i<=n+2;++i) insert(i);
for(rg int i=1;i<=k;++i) a[i]=read();//l1=1
for(rg int i=1;i<=k;++i) b[i]=read();//rk=n li<=ri li=ri-1+1
q=read();//a=min(x,ri+li-x) b=max(x,ri+li-x)
vector<pair<int,int>>cg;
while(q--)
{
int x=read();
int l=-1,r=k;
while(l+1<r)
{
int mid=(l+r)/2;
if(b[mid]>=x) r=mid;
else l=mid;
}
reverse(min(x,a[r]+b[r]-x),max(x,a[r]+b[r]-x));
}
out_put(root);
putchar('\n');
for(rg int i=0;i<=n+15;++i)
{
q_l[i]=q_r[i]=val[i]=cnt[i]=par[i]=siz[i]=rev[i]=0;
ch[i][0]=ch[i][1]=ch[i][2]=0;
}
root=ncnt=0;
}
}
E. Iva & Pav
解题思路一:
\[f(l,r) = a_l \&a_{l + 1}\&...\&a_r
\]
显然，固定左端点，右端点右移，答案只会减小不会变大，具有单调性。二分。
定义:\(nxt[i][j]为从第1个到第i个元素中，二进制表示，数位第j位为1的个数\)。即前缀和。
对于固定的\(l\)，寻找到最远的\(r\)满足\(res = \sum_\limits{i = 0}^{30}(nex[r][i] - nxt[l-1][i] == (r-l + 1)) * (2^i),res \geq k\)。
代码\(O(30(qlog(n) + n))\):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, k, m;
void solve()
{
scanf("%d", &n);
vector<int> a(n + 1);
vector<vector<int>> s(n + 10, vector<int>(32, n + 1));
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++)
{
s[i] = s[i - 1];
for (int j = 0; j < 30; j++)
{
if (a[i] >> j & 1)
{
s[i][j]++;
}
}
}
scanf("%d", &m);
while (m--)
{
int idx, x;
scanf("%d %d", &idx, &x);
int l = idx - 1;
int r = n + 1;
auto check = [&](int mid)
{
int res = 0;
for (int i = 0; i < 30; i++)
{
if (s[mid][i] - s[idx - 1][i] == mid - idx + 1)
{
res += 1 << i;
}
}
if (res < x)
{
return false;
}
return true;
};
while (l + 1 < r)
{
int mid = l + r >> 1;
if (check(mid))
{
l = mid;
}
else
{
r = mid;
}
}
if (l < idx)
{
printf("-1 ");
}
else
{
printf("%d ", l);
}
}
puts("");
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
}
解题思路二：
从高数位向低数位遍历。
对于\(k\)而言，我们用\(res\)记录最远的\(r\)使得\(f(l,r) = k\)。
我们设\(k_j表示k的从小到大的第j个二进制位\)。举例:\(k= 3,那么，k_1=1，k_0=1\)
对于\(k_j == 1\),我们用来更新\(res\).
对于\(k_j == 0\),我们寻找最长的连续的\(a_j == 1\),使得该\((l,r)\)的\(f(l,r)_j == 1\)。
举例：
\(a_1 = 0100,a_2 = 0110,a_3 = 0100\)
询问\(l = 1,k = 0010\)
显然，\(res = 2\)不是答案，答案为\(3\).
这就是因为，从高数位开始遍历，\(k_3 = 0\),但是第\(3\)位如果取到\(1\),\(f(l,r)\)一定大于\(k\)。所以优先级高于最终的\(res\)。
但记住，这里的优先级是低于当时的\(res\)的。我们在看第\(3\)位的时候，\(res= 3\).
如果越过\(res\)取1,那么更高位一定会有0，使得答案小于\(k\)。
举例：
\(a_1 = 1100,a_2 = 1110,a_3 = 0100\)
询问\(l = 1,k = 1010\)
这里答案就是\(2\)了。但第三位的1明显能顺延到\(a_3\).
如果我们顺延到\(a_3\),答案确实是包含\(2^2\)最远的位置，但是我们更大的\(2^3\)就会丢失。
所以这里的最远要和\(res\)取个最小值。
\(ans = max(ans,min(res, nxt[l][j] - 1))\)。
我们可用\(nxt\)数组预处理出从第\(i\)个元素开始，往后第一个第\(j\)位为0的元素下标为多少，这样我们找最远距离就可以\(O(1)\)了。
代码\(O(30(n + q))\):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, k, m;
void solve()
{
scanf("%d", &n);
vector<int> a(n + 1);
vector<vector<int>> ne(n + 10, vector<int>(32, n + 1));
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = n; i; i--)
{
ne[i] = ne[i + 1];
for (int j = 29; j >= 0; j--)
{
if (~a[i] >> j & 1)
{
ne[i][j] = i;
}
}
}
scanf("%d", &m);
while (m--)
{
int l, x;
scanf("%d %d", &l, &x);
int res = n;
int ans = 0;
for (int i = 29; i >= 0; i--)
{
if (x >> i & 1)
{
// res是等于x的最远位置
res = min(res, ne[l][i] - 1);
}
else
{
// 这里res不用更新
// res是等于x的最远位置，这里的ne[l][i]是大于res的尽量远的位置
ans = max(ans, min(res, ne[l][i] - 1));
}
}
ans = max(res, ans);
if (ans < l)
{
printf("-1 ");
}
else
{
printf("%d ", ans);
}
}
puts("");
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
}
F. Vasilije Loves Number Theory
解题思路:
\(gcd(a,n) = 1\)意味着二者互质，没用相同的质因子。
所以,\(d(n \cdot a) = d(n) \cdot d(a)\)
因为，\(d(n \cdot a) = n\),所以,\(d(a) = \frac n {d(n)}\)。
若，\(n \% d(n) \neq 0\),则无解。
由于本题中\(q\)很小，所以询问内部操作\(O(q)\)也可。
本题中，主要是\(n\)在过程中可能很大，需要考虑处理。而\(d(n)\)全程不超过\(10^9\)，所以可以直接跟进处理得到。
设\(d\)为当前\(d(n)\)，若我们执行操作1，\(d\)的变化为，若\(n\)中的质数\(p_i\)的数量从\(a \rightarrow b\),那么\(d \rightarrow \frac d a * b\)。
所以，我们实时记录\(n\)中每个质数的数量，当乘以\(x\)的时候，实时拆分\(x\)更新质数数量即可。\(O(logx)\)每次更新\(d\)。
那么，有了\(d\),怎么求\(n \% d\)呢。
\(n\)太大了，我们可以将过程中乘以的\(x\)都记录下来(假设都装到\(v\)中)，然后遍历所有的内容\((n,x \leq 10^6)\)
\[n = \prod v_i (mod\ d)
\]
即\(O(q)\)求取最终的模数。
对于操作2，我们同样\(O(qlog(x))\)删除\(v\)中的所有\(x\)即可，其中每次反向更新\(d\)为\(O(logx)\).
时间复杂度:\(O(q^2log(x))\)。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
ll n,k,x;
vector<int> primes,minp;
const int N = 1e6 + 10;
//ÓÃÀ´¼Ç¼ÿ¸öÖÊÊý³öÏÖÁ˶àÉÙ´Î
vector<int> cnt(N);
void sieve(int n)
{
minp.assign(n + 10,0);
primes.clear();
for(int i = 2;i<=n;i++)
{
if(minp[i] == 0)
{
minp[i] = i;
primes.push_back(i);
}
for(auto p : primes)
{
if(i * p > n)
{
break;
}
minp[i * p] = p;
if(p == minp[i])
{
break;
}
}
}
}
void solve()
{
ll q = 0;
scanf("%lld %lld",&n,&q);
//ÓÃÀ´¼Ç¼µ±Ç°n³ËÁËÄÄЩx
vector<int> s;
//¼Ç¼µ±Ç°d(n)
ll d = 1;
auto add = [&](ll val,ll t = 1)
{
while(val > 1)
{
int p = minp[val];
d /= cnt[p] + 1;
cnt[p] += t;
d *= cnt[p] + 1;
val /= p;
}
};
add(n);
s.push_back(n);
while(q--)
{
scanf("%lld",&k);
if(k == 1)
{
scanf("%lld",&x);
add(x);
s.push_back(x);
ll res = 1;
for(auto v : s)
{
res = (res * v) % d;
}
if(res)
{
puts("NO");
}
else
{
puts("YES");
}
}
else
{
//»Ö¸´n£¬ÄǾÍÖ»ÁôÒ»¸ön
while(s.size() > 1)
{
add(s.back(),-1);
s.pop_back();
}
}
}
while(s.size())
{
add(s.back(),-1);
s.pop_back();
}
puts("");
}
int main()
{
int t = 1;
sieve(N);
scanf("%d",&t);
while(t--)
{
solve();
}
}