Codeforces Round 769 (Div. 2)(Dgcd st表+二分 or 分解因数 C 位运算分类讨论)

A - ABC

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
int sum[1<<16];

void solve()
{
    cin>>n;
    string s;cin>>s;
    if(s=="1"||s=="0"||s=="01"||s=="10"){
        cout<<"YES\n";
    }
    else cout<<"NO\n";
}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

B - Roof Construction

首先最大值肯定存在n里面最大的二进制的1的最高位

然后还有个结论是相邻的异或和最小，尽量是连续的数

所以直接在二进制的1的最高位的左边接个0断开就行了

其他连续就行

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];

void solve()
{
   cin>>n;
   int mx=0;
   for(int i=0;i<n;i++){
       if((1<<i)<n){
           mx=1<<i;
       }
       else break;
   }
   for(int i=1;i<mx;i++){
       cout<<i<<" ";
   }
   cout<<"0 ";
   for(int i=mx;i<n;i++) cout<<i<<" ";
   cout<<"\n";
}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

C - Strange Test

操作题先想操作性质

第三个操作使得 (a|b)>=max(a,b)

这个时候操作a已经没用了，只能让b增加到（a|b）

所以分类讨论

1先加a 然后或运算 然后让b增加

2.b增加 然后或运算 然后让b增加

因为b总和<=1e6 所以直接枚举操作增加多少次即可

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];

void solve()
{
    int a,b;
    cin>>a>>b;
    int res=b-a;
    for(int i=a;i<=a+b-a;i++)
    {
        if(i==b)
        {
            res=min(res,i-a);
        }
        else
        {
            res=min(res,1+i-a+(i|b)-b);
        }
    }  
    for(int i=b;i<=b+b-a;i++)
    {
        res=min(res,i-b+1+(i|a)-i);
    }
    cout<<res<<"\n";
}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

D：

gcd没思路就从因子身上出发

首先有个共同的点是，如果当前端点存在和前面点构成不合法区间

怎么办

修改当前端点为一个很大质数这样前面gcd都是1

又因为区间长度大于1所以前面的区间都不用管

维护一个pre 表示1到pre的区间都不用管了

先讲因子思路

每个数最多有logn个因子

所以直接枚举每个因子的开始区间和结束区间，

然后暴力枚举每个因子是否存在不合法的情况即可

假设因子开始区间是 l 结束区间是r

当前点是 i,因子是x

不合法就是 i-y+1=x

y=i-x+1

如果y在l到r则不合法

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
int f[N][22];
int gcd(int a, int b)  // 欧几里得算法
{
    return b ? gcd(b, a % b) : a;
}

void init(){
    for (int j = 0; j < 20; j ++ )
        for (int i = 1; i + (1 << j)-1<=n; i ++ )
            if (!j) f[i][j] = a[i];
            else f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int query(int l,int r){
    int len=r-l+1;
    int k=log(len)/log(2);
    return gcd(f[l][k],f[r-(1<<k)+1][k]);
}
void solve()
{
   cin>>n;
   for(int i=1;i<=n;i++) cin>>a[i];
    int res=0;
    int pre=0;
    vector<array<int,3>> st;
    for(int i=1;i<=n;i++){
        for(auto&t:st){
            t[2]=gcd(t[2],a[i]);
        }
        st.push_back({i,i,a[i]});
        vector<array<int,3>> f;
        for(int j=0;j<st.size();j++){
            if(f.empty()){
                f.push_back(st[j]);
            }
            else if(f.back()[2]==st[j][2]){
                f.back()[1]=st[j][1];
            }else f.push_back(st[j]);
        }
        swap(f,st);
        for(auto&t:st){
            int at=i-t[2]+1;
            if(t[0]<=at&&at<=t[1]){
                if(at>pre){
                    res++;
                    pre=i;
                }
            }
        }
        cout<<res<<" ";
    }
}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
   // cin>>t;
    while(t--) solve();
}

第二思路：

因为gcd是单调递减

上面的式子

i-y+1=x

i+1=x+y

因为y和x都是递减的

所以越靠左x+y越小，但是i+1是定值

满足二分

所以用个二分+st表查询区间gcd即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
int f[N][22];
int gcd(int a, int b)  // 欧几里得算法
{
    return b ? gcd(b, a % b) : a;
}

void init(){
    for (int j = 0; j < 20; j ++ )
        for (int i = 1; i + (1 << j)-1<=n; i ++ )
            if (!j) f[i][j] = a[i];
            else f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int query(int l,int r){
    int len=r-l+1;
    int k=log(len)/log(2);
    return gcd(f[l][k],f[r-(1<<k)+1][k]);
}
void solve()
{
   cin>>n;
   for(int i=1;i<=n;i++) cin>>a[i];
   
   init();
   int pre=1;
   int res=0;
   for(int i=1;i<=n;i++){
       if(a[i]==1) res++,pre=i+1;
       else{
           int l=pre,r=i;
           while(l<r){
               int mid=l+r>>1;
               if(query(mid,i)>=i-mid+1) r=mid;
               else l=mid+1;
           }
           if(query(l,i)==i-l+1){
               res++;
               pre=i+1;
           }
       }
       cout<<res<<" ";
   }
}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
   // cin>>t;
    while(t--) solve();
}