原题链接

前言

隔天考试食不食油饼。

感受：

难度还是佛如 C 组。

T1 用 1.5 h 想出正解，是道比较好想的博弈论。

T2 一开始居然想的树剖（脑子抽了），实际可能比 T1 更简单？暴力甚至挂了。

T3 没看。

T4 打了 30分暴力，用 ST 表卡了下内存。

挂分情况：

T2 暴力奇怪的挂了 -30。

T1 博弈

关键点在于谁先破开一个环。

显然，先破开环的人被动。

有两个特殊性质：

• 被破开的有 3 个绳结的绳子必定被一次取完，且取得人要再破开一个环。

• 被破开的有 4 个绳结的绳子可以被劈成 2，2，此时下一人必定会取完并破开下一个环。

考虑到取完要破一个环，贪心的想，肯定先按绳结排序。

注意到被破开的大于等于 4 个绳结的绳子是个很关键的点，此轮的人要么留 4 个取走其他，要么取走全部并破开下一个环，令自己被动。

注意被破开的有 3 个绳结的绳子无法保留，只能取完闭并破环，应特殊处理。

现在假设只有大于等于 4 个绳结的绳子。

定义 \(f(i,t,x,y)\) 表示取到第 \(i\) 个绳子，当前是 先手（0）/后手（1） 拿，此时先手有 \(x\) 个，后手有 \(y\) 个，当前拿的人能拿到的最大值。

定义 \(s\) 为 \(a\) 的前缀和数组。

那么此时要么取走 \(s_n-s_{i-1}-4\cdot (n-i)\)，要么取完 \(a_i\)，并让另一个人主动。

据此，不难写出 \(f\) 的递归式。

时间复杂度 \(O(n \log n)\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,c,x,y,t,ans;
int a[105],s[105];

int f(int i,int t,int x,int y)
{
    if(i==n) return (t?y:x)+a[n];
    return max((t?y:x)+s[n]-s[i-1]-4*(n-i),s[n]-f(i+1,t^1,x+a[i]*(!t),y+a[i]*t));
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++) if(a[i]==3) c++;
    if(c&1) x+=c/2*3,y+=c/2*3+3,t=0;
    else x+=c/2*3,y+=c/2*3,t=1;
    if(c<n) ans=f(c+1,t,x,y);
    else ans=x;
    if(t) ans=s[n]-ans;
    cout<<ans<<' '<<s[n]-ans<<'\n';
}

T2 齿轮

据 s.f.s.l.，齿轮转速只和两个齿轮有关（还说这是常识），被薄纱了。

的确，化简式子后发现只和给定的齿轮 \(x,y\) 的齿轮数相关。

可以用并查集维护。扩展域 \(x+n\) 为与 \(x\) 方向相反的齿轮。

这题就完了。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,m,a[N],fa[N*2];
inline int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}

inline int rd()
{
    int x=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    return x;
}

int main()
{
    n=rd(),m=rd();
    for(int i=1;i<=n;i++) a[i]=rd();
    for(int i=1;i<=n*2;i++) fa[i]=i;
    while(m--)
    {
        int op=rd(),x=rd(),y=rd(),v;
        if(op==1) a[x]=y;
        else if(op==2)
        {
            if(x==y) continue;
            fa[find(x+n)]=find(y);
            fa[find(y+n)]=find(x);
        }
        else
        {
            v=rd();
            if(fa[find(x)]==fa[find(y)]&&fa[find(x+n)]==fa[find(y)]) {puts("0");continue;}
            if(fa[find(x)]!=fa[find(y)]&&fa[find(x+n)]!=fa[find(y)]) {puts("0");continue;}
            long long A=1ll*a[x]*v,B=a[y],g=__gcd(A,B);A/=g,B/=g;
            if(fa[find(x+n)]==find(y)) A=-A;
            printf("%lld/%lld\n",A,B);
        }
    }
}

T3

题意可简化为构造一个不下降序列 \(a,|a|=n\)，使 \(a_n\) 最小，且满足 \(\prod\limits_{i=1}^{n}(a_i-i+1)=c\)，\(c \leq 10^9\)。

令 \(A_i=a_i-i+1\)，则 \(A_i-1 \leq A_i\)。显然 \(A_i \mid c\)。

根据因数个数公式，\(10^9\) 范围内的数因数个数大约在 \(1500\) 个以内。

\(1\) 是个很好用的构造数字，可以用来补位置。

于是贪心地想，构造时要让构造的序列尽可能短。

歪解（别急着走，万一是 100pts 还贼简单呢）

枚举 \(a_n\)，每次往前贪心地选最大满足条件的因数，如此构造。

把所有因数丢进一个 set 即可。复杂度 \(O(n\log d)\)，\(d\) 为因数个数。

#include<bits/stdc++.h>
using namespace std;

int T,n,c;
set<int> d;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)
    {
        d.clear();
        cin>>n>>c;
        for(int i=1;i*i<=c;i++) if(c%i==0) d.insert(i),d.insert(c/i);
        for(int i:d)
        {
            vector<int> p;
            p.push_back(i);
            int _c=c/i;
            while(p.size()<n&&_c!=1)
            {
                auto it=d.upper_bound(*p.rbegin());
                while(it!=d.begin()&&(*it-1>*p.rbegin()||_c%*it!=0)) --it;
                if(*it==1) break;
                p.push_back(*it);_c/=*it;
            }
            if(_c!=1) continue;
            reverse(p.begin(),p.end());
            int cnt=n-p.size();
            // 补 0
            for(int i=1;i<=cnt;i++) cout<<i<<' ';
            for(int i=0;i<p.size();i++) cout<<p[i]+cnt+i<<' ';
            cout<<'\n';
            break;
        }
    }
}

正解

为什么是歪解？

来看一组反例。

比如要得到 \(12113374=2\times 7 \times 13 \times 19 \times 31 \times 113\)，此时要求选的数 \(\leq 266\)。

如果按歪解的方案：就是 \(266\times 113\times 31\times 13\)，需要 \(4\) 个数，

但实际只需要 \(3\) 个数：\(247\times 226\times 217\)。

但这种数据实在太难构造，所以没有。

事实上，贪心地想，答案序列可以表示为如此的形式 ：\(...,y,y-1,y-2,...,x\)。

其中前半段最大值 \(\leq y\)。因为对 \(A_i\) 的限制为 \(A_i-1 \leq A_i\)，这样的形式能让 \(x\) 尽可能小。注意 \(y,y-1,...\) 这类值还可以在前面出现，显然也合法，只是上述形式更方便计算。

考虑枚举 \(x\)，递增地枚举 \(y\)，记 \(f(i,j)\) 为使用 \(\leq d_i\) 的因数构造出 \(d_j\) 值的最小长度。（\(d\) 是 \(c\) 的因数数组）。

此时就能 \(O(1)\) 判断当前 \(x,y\) 是否合法。

转移方程还是写一下：

\(\begin{cases} f(i,j)=f(i-1,j)\qquad d_i \nmid d_j \\ f(i,j)=\min\{f(i-1,j),f(i,k)+1\}\qquad d_i \mid d_j \end{cases}\)

其中 \(k\) 为因数 \(d_j/d_i\) 的下标，这个可以用哈希表维护。

注意还要记录路径。

#include<bits/stdc++.h>
using namespace std;

const int N=1500;
int T,n,c,k;
int d[N],f[N][N];
pair<int,int> g[N][N];//路径数组
unordered_map<int,int> mp;//哈希表

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)
    {
        k=0;
        cin>>n>>c;
        for(int i=1;i*i<=c;i++) if(c%i==0) d[++k]=i,d[++k]=c/i;
        if(d[k-1]==d[k]) --k;
        sort(d+1,d+1+k);
        for(int i=1;i<=k;i++) mp[d[i]]=i;
        for(int i=0;i<=k;i++) for(int j=0;j<=k;j++) f[i][j]=1e9;
        f[0][1]=0;
        for(int i=1;i<=k;i++)
            for(int j=1;j<=k;j++)
            {
                f[i][j]=f[i-1][j];
                g[i][j]={i-1,j};
                if(d[j]%d[i]==0)
                {
                    int k=mp[d[j]/d[i]];
                    if(f[i][k]+1<f[i][j]) f[i][j]=f[i][k]+1,g[i][j]={i,k};
                }
            }
        int ti,tj;
        vector<int> p;
        for(int i=1;i<=k;i++)
        {
            int x=d[i],_c=c/x,flag=0;
            //特判 y=x 的情况
            if(f[i][mp[_c]]+1<=n) {p.push_back(x),ti=i,tj=mp[_c];break;}
            for(int j=i+1;j<=k&&d[j]-d[j-1]<=1&&_c%d[j]==0;j++)
            {
                _c/=d[j];
                if(f[j][mp[_c]]+j-i+1<=n)
                {
                    for(int k=i;k<=j;k++) p.push_back(d[k]);
                    ti=j,tj=mp[_c],flag=1;
                    break;
                }
            }
            if(flag) break;
        }
        while(ti&&tj)
        {
            auto [_ti,_tj]=g[ti][tj];
            if(_ti==ti) p.push_back(d[ti]);
            ti=_ti,tj=_tj; 
        }
        reverse(p.begin(),p.end());
        int cnt=n-p.size();
        // 补 0
        for(int i=1;i<=cnt;i++) cout<<i<<' ';
        for(int i=0;i<p.size();i++) cout<<p[i]+cnt+i<<' ';
        cout<<'\n';
    }
}

T4 简单的数据结构题

放在 T4，雀食简单。

如果刻意去研究完全平方数性质，那你就被骗到了。

考虑 \(x\) 与运算上一些数，值的变化不会超过 \(\log x\) 次（把所有位的 1 变为 0 后就不会变化了）。

如果固定左端点，把所有使值变化的位置处理出来，就能得到 \(\log\) 级别个区间，每个区间值是相同的。

判断当前值是否是完全平方数，就能统计答案。

对于询问，是典型的二维偏序问题，离线下来，排个序，统计答案用线段树维护即可。

处理区间带个 \(\log\)，每次用线段树统计答案带个 \(\log\)，总复杂度 \(O(n\log n \log v+q \log n)\)，其中 \(v\) 为值域。

也就调了一个小时。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+5;
int _,n,m,a[N],ans[N*5],nxt[N][30];
struct node{int l,r,id;} q[N*5];
struct SegmentTree{
    #define mid ((l+r)>>1)
    int sum[N<<2],add[N<<2];
    inline void clear() {for(int i=1;i<=n*4;i++) sum[i]=add[i]=0;}
    inline void pushdown(int k,int l,int r)
    {
        if(!add[k]) return;
        add[k<<1]+=add[k],add[k<<1|1]+=add[k];
        sum[k<<1]+=(mid-l+1)*add[k],sum[k<<1|1]+=(r-mid)*add[k];
        add[k]=0;
    }
    void upd(int x,int y,int v,int k=1,int l=1,int r=n)
    {
        if(l>=x&&r<=y) {sum[k]+=(r-l+1)*v,add[k]+=v;return;}
        pushdown(k,l,r);
        if(x<=mid) upd(x,y,v,k<<1,l,mid);
        if(mid<y) upd(x,y,v,k<<1|1,mid+1,r);
        sum[k]=sum[k<<1]+sum[k<<1|1];
    }
    int qsum(int x,int y,int k=1,int l=1,int r=n)
    {
        if(l>=x&&r<=y) return sum[k];
        int res=0;
        pushdown(k,l,r);
        if(x<=mid) res+=qsum(x,y,k<<1,l,mid);
        if(mid<y) res+=qsum(x,y,k<<1|1,mid+1,r);
        return res;
    }
}T;

inline int rd()
{
    int x=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    return x;
}

signed main()
{
    //判断是否为完全平方数
    auto check=[](int x) {return (int)sqrt(x)*sqrt(x)==x;};
    _=rd();
    while(_--)
    {
        n=rd(),m=rd();
        T.clear();
        for(int i=1;i<=n;i++) a[i]=rd();
        for(int i=1;i<=m;i++) q[i]={rd(),rd(),i};
        sort(q+1,q+1+m,[&](node a,node b){return a.l>b.l;});
        vector<int> t(31,-1);
        for(int i=n;i>=1;i--) for(int j=0;j<30;j++) nxt[i][j]=t[j],t[j]=((a[i]>>j)&1)?t[j]:i;
        for(int i=n,j=1;i;i--)
        {
            vector<pair<int,int>> pos;
            for(int j=0;j<30;j++) if(((a[i]>>j)&1)&&nxt[i][j]!=-1) pos.emplace_back(nxt[i][j],j);
            sort(pos.begin(),pos.end());
            int l=i,now=a[i];
            //值相同的区间是左闭右开（EarthMessenger 狂喜）
            for(int j=0;j<pos.size();j++)
            {
                int tmp=now;
                now^=(1<<pos[j].second);
                //当前可能有多个位进行了变化
                while(j+1<pos.size()&&pos[j].first==pos[j+1].first) now^=(1<<pos[++j].second);
                if(check(tmp)) T.upd(l,pos[j].first-1,1);
                l=pos[j].first;
            }
            if(check(now)) T.upd(l,n,1);
            while(j<=m&&q[j].l==i) ans[q[j].id]=T.qsum(i,q[j].r),++j;
            
        }
        for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    }
}