Codeforces Round #717 (Div. 2)

A. Tit for Tat

图片说明

思路：
(从最高位开始)高位不断减一、最底位不断加一，直到高位都为 $0$ 或者操作了 $k$ 次

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=2e5+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
inline void solve() {
    int n,k;
    cin>>n>>k;
    vector<int>a(n+1);
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<n;++i) {
        if(k>a[i]) {
            k-=a[i];
            a[n]+=a[i]; 
            a[i]=0;
        }
        else {
            a[i]-=k;
            a[n]+=k;
            break;
        }
    }
    for(int i=1;i<=n;++i) cout<<a[i]<<' ';
    cout<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--) solve();
}

B. AGAGA XOOORRR

图片说明

思路:
题目说了只能合并相邻的。
如果可以将数组中元素合成值相等的元素，假设该值为 $x$
如果前 $n$ 项的异或和为 $0$ ，那么一定有 $k$ 使得 $a_1\oplus a_2...\oplus a_{k},a_k\oplus a_{k+1}...\oplus a_{n}$ 相等，即 $x\oplus x=0$ 。
如果前 $n$ 项的异或和不为 $0$ ，那么只能合成奇数个相等的元素，并且根据异或的性质， $x_{1}\oplus x_{2}...\oplus x_{2m+1}$ ，对原数组求前 $n$ 项的异或和时 $x$ 会出现 $m+1$ 次，即至少两次。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=2e5+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
inline void solve() {
    int n,x(0);
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;++i) {
        cin>>a[i];
        x^=a[i];
    }
    if(!x) {
        cout<<"YES\n";
        return;
    }
    int y(0),cnt(0);
    for(int i=1;i<=n;++i) {
        y^=a[i];
        if(y==x) {
            cnt+=1;
            y=0;
        }
    }
    if(cnt>=2) cout<<"YES\n";
    else cout<<"NO\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

C. Baby Ehab Partitions Again

图片说明

思路：
如果原数组不能分成两堆和相同的数就不用删掉某些数了，直接输出 $0$ ；
设 $sum$ 是数组 $a$ 的和，如果 $sum$ 是奇数就不能分成两堆和相同的数，反之这个问题可以转化为数组 $a$ 能否凑出 $sum/2$ ，这个是 $0/1$ 背包的应用；

如果能分成两堆和相同的数，常见的套路是只要删一个就可以了，可以往这个方向想；
首先删掉一个奇数， $sum$ 就变成了奇数
如果没有奇数，可以肯定对每个数进行 $/2$ 操作对问题的求解没有影响，所有对数组 $a$ 的划分的大小关系都不会被改变，那么我们可以一直进行 $/2$ 操作直至出现奇数。从二进制角度看，其实就是删掉二进制从右往左第一个1出现最早的那个数，可以使用 $\_\_builtin\_ctz$ 函数来辅助。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=2e5+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
bool bad(vector<int>v,int s) {
    bitset<200005>b;
    b=1;
    for(auto i:v)
        b|=(b<<i);
    return b[s/2];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,s(0);
    cin>>n;
    vector<int>v(n);
    for(auto &i:v) {
        cin>>i; s+=i;
    }
    if((s&1)||!bad(v,s)) cout<<"0\n";
    else {
        pair<int,int>mn(20,0);
        for (int i=0; i<n; i++)
            mn=min(mn,make_pair(__builtin_ctz(v[i]),i+1));
        cout<<"1\n"<<mn.second<<'\n';
    }
}
/*
6
8 10 4 6 10 6
*/

D. Cut

图片说明

思路：
这个问题转化到树上会简单点
可以想到是每个点 $i$ 向它右边第一个非互质点 $j$ 连边，也就是 $fa[j]=i$ ，表示 $i$ 和 $j$ 不能在同一个区间内，又由区间的连续性知道 $i$ 和 $k(k>j)$ 也不能在同一个区间内，所以必须满足 $fa[j+1]>=fa[j]$ 。
这样连边后就可以得到一颗树，这颗树的性质有：深度小的点编号小，同一层的点编号是连续的，边上的两个点不能在同一个区间。
那么问题就可以转为求 $[l,r]$ 在树中最大的层数，因为只要将树中的每一层划分为一个区间就能保证区间内的元素互质且是连续的。 $[l,r]$ 在树中的第一层和第二层也可能合成一个区间，如果第一层的点编号都大于第二层点父亲的编号，那么可以合并。所以答案是 $d[r]-d[l]+1$ 或者 $d[r]-d[l]$ ，前者表示将树中的每一层划分为一个区间，后者表示 $[l,r]$ 在树中的第一层和第二层合成为一个区间。由这颗树的性质可以知道，如果 $r$ 和 $l$ 在同一层的祖先编号小于 $l$ ，那么答案是 $d[r]-d[l]$ ，反之为 $d[r]-d[l]+1$ 。这一步骤可以用倍增来实现。

这题用线段树来写可能会更好懂些，先求每个点 i 为左端点时，满足区间内数两两互质的最远右端点 + 1，然后用倍增快速查询。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=1e4+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int pre[maxn],pri[maxm],b[maxm];
int head[maxn],Next[maxn*30],to[maxn*30],tot;
inline void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
inline void init() {
    for(int i=2,tot=0; i<maxn; ++i) {
        if(!pre[i]) {
            pri[++tot]=i;    pre[i]=tot;
        }
        for(int j=1; j<=tot; ++j) {
            if(i*pri[j]>=maxn)break;
            pre[i*pri[j]]=j;
            if(i%pri[j]==0)break;
        }
    }
}
int t,f[maxn][20],fa[maxn],d[maxn];
void bfs() {
    queue<int>q;
    q.emplace(0);
    int x;
    while(q.size()) {
        x=q.front(); q.pop();
        for(int i=head[x],y=to[i];i;i=Next[i],y=to[i]) {
            f[y][0]=x;
            d[y]=d[x]+1;
            for(int j=1;j<=t;++j) f[y][j]=f[f[y][j-1]][j-1];
            q.push(y);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,Q;
    init();
    cin>>n>>Q;
    t=(int)log2(n)+1;
    for(int i=1,x,y; i<=n; ++i) {
        cin>>x;
        fa[i]=fa[i-1];
        while(x!=1) {
            y=pre[x];
            do x/=pri[y]; while(x%pri[y]==0);
            fa[i]=max(fa[i],b[y]);
            b[y]=i;
        }
        add(fa[i],i);
    }
    bfs();
    int l,r,x;
    while(Q--) {
        cin>>l>>r;    x=r;
        for(int i=t;~i;--i) if(f[x][i]>=l) x=f[x][i];
        cout<<d[r]-d[x]+1<<'\n';
    }
    return 0;
}