【题解】 Codeforces 1168 Round #562 (Div. 1)

【题解】 Codeforces 1168 Round #562 (Div. 1)

心态爆炸，掉紫了。

总结

1. 二分答案是非常常见和好用的操作
2. 要有暴力直觉，检查暴力是否可行。
3. 需要训练dp

A. Increasing by Modulo
给出n,m(3e5)，然后给出长度为n的在0到m-1之间的数字序列，每次可以选择任意个数让它们在模m意义下加一，问最少几次操作可以得到一个不下降子序列。

二分答案ans，检查时维护当前最大值，如果当前值小于最大值并且ans不足以让它增加到最大值，则失败。如果当前值大于最大值，检查能否让当前值先到m再到最大值，如果不能，最大值设置为当前值。

int n, m;
int save[M];
bool check(int k)
{int mx = 0;for(int i=1; i<=n; ++i){int now = save[i];if(now<mx){if(mx-now>k){return 0;}}else{if(m-now+mx>k)mx = now;}}return 1;
}
int main(void)
{n = read(), m=read();for(int i=1; i<=n; ++i)save[i] = read();int lef = 0, rig = m;while(lef<=rig){int mid = (lef+rig)>>1;if(check(mid)) rig = mid-1;else lef = mid+1;}printf("%dn",lef );return 0;
}

B. Good Triple
给一个长为n(3e5)的01串s，问有多少个(l,r)满足

1. 1 &lt; = l &lt; = r &lt; = n 1&lt;=l&lt;=r&lt;=n 1<=l<=r<=n
2. 有 ( x , k ) 使 得 l &lt; = x &lt; x + 2 k &lt; = r , 有(x,k)使得l&lt;=x&lt;x+2k&lt;=r, 有(x,k)使得l<=x<x+2k<=r, 此时 s x = s x + k = s x + 2 k s_x=s_{x+k}=s_{x+2k} sx​=sx+k​=sx+2k​

题解说，任何一个长为9以上的01串都会有这样的(x,k)出现，打表验证如下，确实9以上的01串全会存在这样的(x,k)对:

bool check(int n) //检测长为i的串是否有不存在xk的情况
{for(int mask=0; mask<(1<<n); ++mask){int flag = 1;for(int i=0; i<n; ++i){for(int j=i+1; j<n; ++j) if(2*j-i<n){int a = mask>>i&1, b = mask>>j&1, c = mask>>(2*j-i)&1;if(a==b && a==c)flag = 0, i = n;}}if(flag)return 1;}return 0;
}
int main(void)
{for(int i=1; i<=20; ++i)cout << check(i) << endl; return 0;
}

所以只需要对每个l，暴力查找最先出现的r即可。

char save[M];
bool check(int l, int r)
{for(int i=l; i<=r; ++i){for(int j=i+1; j<=r; ++j) if(2*j-i<=r){if(save[i]==save[j] && save[i]==save[2*j-i])return 1;}}return 0;
}
int main(void)
{scanf("%s",save);int n = strlen(save);ll ans = 0;for(int l=0; l<n; ++l){int r;for(r=l+1; r<n; ++r)if(check(l,r))break;ans += n-r;}cout << ans << endl;return 0;
}

C. And Reachability
给定n,q(3e5)，然后给定长为n的数字序列A(3e5)，随后是q个查询，每次给出两个数x和y，问在A中能否找到一个从x开始，结束于y的子序列，且子序列的相邻两项按位与的结果不为0.

二进制问题自然想到按位分解，3e5内的数字最多只有18位。题解的做法是从后往前扫一遍，维护一个数组 d i , j d_{i,j} di,j​，表示i位置上的数能访问到的最早的第j位为1的数是多少。要做到这个，需要再维护一个数组 g i , j g_{i,j} gi,j​，表示i位置上的数之后的最早的第j位为1的数是多少，这个数组可以在扫的时候自然维护。
当访问到第i个数时，扫描它的每一位，如果第j位为1，那么 d i , j = i d_{i,j}=i di,j​=i，否则 d i , j = m i n { d k , j } , k 为 i 能 通 过 g i , j 访 问 的 数 字 。 d_{i,j}=min{d_{k,j}}, k为i能通过g_{i,j}访问的数字。 di,j​=min{dk,j​},k为i能通过gi,j​访问的数字。

判断(x,y)的答案时，对于y的每一个为1的位j，判断 d i , j &lt; = y d_{i,j}&lt;=y di,j​<=y是否成立，只要成立一个，就可达。

服务器好像炸了，未提交验证

int save[M], dp[M][17], lst[M][17];
int main(void)
{memset(dp, -1, sizeof(dp));memset(lst, -1, sizeof(lst));int n = read(), q = read();for(int i=1; i<=n; ++i)save[i] = read();for(int i=n; i; --i){for(int j=0; j<18; ++j){if(save[i+1]>>j&1)lst[i][j] = i+1;elselst[i][j] = lst[i+1][j];}}for(int i=n; i; --i){for(int j=0; j<18; ++j){if(save[i]>>j&1)dp[i][j] = i;else{int x = -1;for(int kj=0; kj<18; ++kj) if(dp[i][kj]!=-1){int k = dp[i][kj];if(dp[k][j]!=-1 && (x==-1||dp[k][j]<x))x = dp[k][j];}dp[i][j] = x;}}}while(q--){int x=read(), y=read(), suc=0;for(int j=0; j<18; ++j) if((save[y]>>j&1) && dp[x][j]<=y){suc = 1;break;}printf("%sn",suc?"Shi":"Fou" );}return 0;
}