CF Round 562

CF1168 A~C

A Increasing by Modulo

这个我们操作 $k$ 次就是至多给一个数字 + k ，所以直接二分一下 $k$ 就好了。

cpp

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 300006
#define P 998244353
int Pow( int x , int a ) {
    int cur = x , ans = 1;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}
int n , m;
int A[MAXN];
bool chk( int x ) {
    int base = 0;
    for( int i = 1 ; i <= n ; ++ i ) {
        if( A[i] + x >= m ) {
            int t = ( A[i] + x ) % m;
            if( t >= base ) continue;
        }
        if( A[i] + x >= base && A[i] <= base ) continue;
        else if( A[i] + x >= base ) base = A[i];
        else return false;
    }
    return true;
}
int main() {
    cin >> n >> m;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%d",A+i);
    int l = 0 , r = m;
    while( l <= r ) {
        int m = l + r >> 1;
        if( chk( m ) ) r = m - 1;
        else l = m + 1;
    }
    cout << l << endl;
}

B Good Triple

开始看了好久硬是不知道怎么做。。后来 zzh 说了一下，考虑一个位置左右第一个相等的位置其实期望情况下很近啊？然后想想，貌似卡不掉。。于是直接拿最近的位置暴力就行了。原理是一个显然的贪心，如果以一个位置坐中心可以更近地得到两边相同就肯定不会去找远的。

cpp

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 300116
#define P 998244353
int Pow( int x , int a ) {
    int cur = x , ans = 1;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}
int n , m;
char ch[MAXN]; int ans[MAXN];
int main() {
    scanf("%s",ch);
    n = strlen( ch );
    int cur = -1; long long res = 0;
    for( int i = 0 ; i < n ; ++ i ) {
        for( int j = i - 1 ; j >= 0 ; -- j ) {
            if( ch[i] == ch[j] && ch[j] == ch[i + i - j] ) {
                ans[i + ( i - j )] = max( ans[i + i - j] , j + 1 );
                break;
            }
        }
    }
    int re = 0;
    for( int i = 0 ; i < n ; ++ i ) re = max( re , ans[i] ) , res += re;
    cout << res << endl;
}

C And Reachability

同时把一个数字看成它所代表的二进制代表的集合。

首先，如果 $A[x]$ 与 $A[y]$ 有交，显然可以一步到达。

否则，我们希望通过中间的数字使得 $A[x]$ 变得和 $A[y]$ 有交。

然后考虑这个过程在做什么，在从左往右走，如果和这个数字有交，就可以将当前数变成这个数字。但是我们可以感性理解一下拿和不拿这两种状态是可以任意决定的，所以其实你到达这里之后当前的数字就可以或上这个数。

也就是说，当我们到达一个数，如果和这个数有交，就把当前数字变成和它的或，看到达 $y-1$ 时是否与 $A[y]$ 有交就行了。

怎么优化这个过程？我们考虑在线段树上处理，对于每个线段树上的节点维护一下，如果某个位是 1 到达这个节点并离开这个节点时会或上什么东西，因为或运算满足结合律。于是就可以 $O(n\log^2n)$ 解决问题。

cpp

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 300016
#define P 998244353
int Pow( int x , int a ) {
    int cur = x , ans = 1;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}
int n , q;
int A[MAXN];
 
int T[MAXN << 2][20], w;
 
void pu(int rt) {
    for( int i = 0 ; i < 20 ; ++ i ) {
        T[rt][i] = T[rt << 1][i];
        int v = T[rt << 1][i];
        for( int j = 0 ; j < 20 ; ++ j ) if( v & ( 1 << j ) )
            T[rt][i] |= T[rt << 1 | 1][j];
        T[rt][i] |= T[rt << 1 | 1][i];
    }
}
 
void build(int rt, int l, int r) {
    if (l == r) {
        for( int w = 0 ; w < 20 ; ++ w ) if (A[l] & (1 << w))
            T[rt][w] = A[l];
        return;
    }
    int m = l + r >> 1;
    build(rt << 1, l, m), build(rt << 1 | 1, m + 1, r);
    pu(rt);
}
 
int fr , to;
bool que(int rt, int l, int r, int L, int R) {
    if( fr & to ) return true;
    if (L <= l && R >= r) {
        int re = 0;
        for( int w = 0 ; w < 20 ; ++ w ) if( fr & ( 1 << w ) )
            re |= T[rt][w];
        fr |= re;
        return fr & to;
    }
    int m = l + r >> 1, re = 0;
    if (L <= m) re |= que(rt << 1, l, m, L, R);
    if (R > m) re |= que(rt << 1 | 1, m + 1, r, L, R);
    return re;
}
 
 
int main() {
    cin >> n >> q;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%d",A + i);
    build( 1 , 1 , n );
    int x , y;
    while( q --> 0 ) {
        scanf("%d%d",&x,&y);
        if( x + 1 == y ) { puts( ( A[x] & A[y] ) ? "Shi" : "Fou" ); continue; }
        fr = A[x] , to = A[y];
        puts(que( 1 , 1 , n , x + 1 , y - 1 ) ? "Shi" : "Fou");
    }
}