信息工程大学第五届超越杯程序设计竞赛（同步赛）题解

比赛传送门

博客园传送门

c++ 模板框架

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second 
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define MEM(a,x) memset(a,x,sizeof(a))
#define lowbit(x) ((x)&-(x))
inline int Ls(int p){return p<<1;}
inline int Rs(int p){return p<<1|1;}
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int N=1e3+10;
inline void Solve()
{
}
int main()
{
        #ifndef ONLINE_JUDGE
                freopen("1.in","r",stdin);
                freopen("1.out","w",stdout);
        #endif
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int _=1;
        //cin>>_;
        while(_--){
                Solve();
        }
        return 0;
}

A.遗失的旋律

把加一操作和乘二操作分开看，某一个位置出现了0表示加一，后面所有出现的1都会乘2，也就是说如果用cnt表示这个0后面1的个数，它对答案的贡献就是 $2^{cnt}$

对于一个给定的一个字串，答案就可以写成所有0产生的贡献之和，再加上 $x \cdot 2^{cnt}$

其中cnt表示整个区间1的个数。比如 010110 就可以写成 $2^3 +2^2 +2^0 + x \cdot 2^3$

用线段树维护区间1的个数和区间所有0对答案贡献的总和，分别用s1和s0表示。左右合并时s0就可以用左树s0乘上右树s1，再加上右树的s0。

const int N=1e5+10,M=998244353;
char s[N];
inline int qp(int a,int b)
{
        int res=1;
        while(b){
                if(b&1) res=1ll*res*a%M;
                a=1ll*a*a%M;
                b>>=1;
        }
        return res%M;
}
struct sg_tree{
        int l,r;
        int s0,s1;
}T[8*N];
inline void up(int p)
{
        T[p].s1=T[Ls(p)].s1+T[Rs(p)].s1;
        T[p].s0=(1ll*T[Ls(p)].s0*qp(2,T[Rs(p)].s1)%M+T[Rs(p)].s0)%M;
}
inline sg_tree up(sg_tree L,sg_tree R)
{
        sg_tree t;
        t.s1=L.s1+R.s1;
        t.s0=(1ll*L.s0*qp(2,R.s1)%M+R.s0)%M;
        return t;
}
inline void build(int p,int l,int r)
{
        if(l==r){
                T[p]={l,r,s[l]=='0',s[l]=='1'};
                return;
        }
        T[p]={l,r};
        int mid=l+r>>1;
        build(Ls(p),l,mid);build(Rs(p),mid+1,r);
        up(p);
}
inline void upd(int p,int x)
{
        int &l=T[p].l,&r=T[p].r;
        if(l>x||r<x) return;
        if(l==r){
                s[l]=!(s[l]-'0')+'0';
                T[p].s0=(s[l]=='0');T[p].s1=(s[l]=='1');
                return;
        }
        upd(Ls(p),x);upd(Rs(p),x);
        up(p);
}
inline sg_tree qy(int p,int l,int r)
{
        sg_tree t={0,0,0,0},lt=t,rt=t;
        if(T[p].l>r||T[p].r<l) return t;
        if(T[p].l>=l&&T[p].r<=r) return T[p];
        if(T[Ls(p)].r>=l) lt=qy(Ls(p),l,r);
        if(T[Rs(p)].l<=r) rt=qy(Rs(p),l,r);
        return up(lt,rt);
}
inline void Solve()
{
        int n,m;
        cin>>n>>m>>s+1;
        build(1,1,n);
        while(m--){
                int op,x,l,r;cin>>op;
                if(op==1){
                        cin>>x;upd(1,x);
                }else{
                        cin>>x>>l>>r;
                        sg_tree t=qy(1,l,r);
                        cout<<(t.s0+1ll*x*qp(2,t.s1)%M)%M<<endl;
                }
        }
}

B.时间的礼物

有很多方法可以求得方案数为： $\binom{n+m-1}{m-1}$

首先可以将整数划分问题转换为隔板法问题：有n个球，m-1个隔板方案相当于是把n个数分解为m个大于0的数方案，题目要求可以等于0，n个球的左右两边可以插入隔板，这里可以增加两个球，对于隔板并在一起的情况可以在隔板之间插入球，增加了m-2个球，等价于n+m个球插入m-1个隔板的方案数，所以总方案数为： $\binom{n+m-1}{m-1}$

从另外一个角度，考虑整数划分方案中0的个数为i，剩下的相当于是n个球，插入m-i-1个隔板方案数，总方案可以表示成 $\sum_{i=0}^{m-1}\binom{m}{i}\cdot \binom{n-1}{m-i-1}$ ，这个式子也等价于共有m+n-1个球，先从前面m个中选择i个，再从后面的n-1个球中选择m-i-1个，一共选择m-1个球。这个方案数也等价于直接在n+m-1个球中选m-1个方案数。

直接计算可能会存在逆元不存在的情况，可以先用素数筛找出 $2*10^6$ 内的素数（式子中m+n数量级可能会达到2e6），可以计算每个素数在阶乘中出现的次数，进一步算出每个素数在答案中的阶乘。

const int N=2e6+10;
int n,m,p;
int cnt,pr[N];
bool st[N];
inline void INIT()
{
    rep(i,2,N){
        if(!st[i]) pr[++cnt]=i;
        for(int j=1;j<=cnt&&i*pr[j]<=N-1;++j){
            st[i*pr[j]]=1;
            if(i%pr[j]==0) break;
        }
    }
}
inline int Qp(int a,int b)
{
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%p;
        a=1ll*a*a%p;
        b>>=1;
    }
    return res%p;
}
inline int Cal(int a,int b)
{
    int res=0;
    while(a){
        res+=a/b;
        a/=b;
    }
    return res;
}
inline void Solve()
{
    INIT();
    cin>>n>>m>>p;
    int ans=1;
    rep(i,1,cnt+1){
        int t=Cal(n+m-1,pr[i])-Cal(m-1,pr[i])-Cal(n,pr[i]);
        ans=1ll*ans*Qp(pr[i],t)%p;
    }
    cout<<ans<<endl;
}

C.财政大臣

用一个数组记录变化的值，修改只需要改变单个点的值，最后从根节点做一遍dfs，记录前面节点变化值的和加到子节点上。最后答案就是变化的值加上初始的值。

const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],idx;
int a[N];
LL b[N];
inline void add(int a,int b)
{
    e[++idx]=b;ne[idx]=h[a];h[a]=idx;
}
void dfs(int u,int fa,int s)
{
    for(int i=h[u];i;i=ne[i]){
        int v=e[i];
        if(v==fa) continue;
        dfs(v,u,b[u]+s);
    }
    b[u]+=s;
}
inline void Solve()
{
    int n,m;
    cin>>n>>m;
    rep(i,0,n-1){
        int a,b;cin>>a>>b;
        add(a,b);add(b,a);
    }
    rep(i,1,n+1) cin>>a[i];
    while(m--){
        int op,u,x;
        cin>>op>>u>>x;
        if(op==1) b[u]+=x;
        else b[u]-=x;
    }
    dfs(1,0,0);
    rep(i,1,n+1) cout<<a[i]+b[i]<<" ";
}

D.实验室有多少人

用数对维护信息，开始时间对应1，表示增加1个人，结束时间对应-1，表示减少一个人。把所有数对按时间从小到大排序，相同时间的把-1的放在前面，最后遍历更新答案即可。

const int N=1e6+10;
pii a[2*N];
inline void Solve()
{
    int n,x,y,m=0;
    cin>>n;
    rep(i,0,n){
        cin>>x>>y;
        a[++m]={x,1};a[++m]={y,-1};
    }
    sort(a+1,a+1+m);
    int ans=0,nw=0;
    rep(i,1,m+1){
        nw+=a[i].se;
        ans=max(ans,nw);
    }
    cout<<ans<<endl;
}

E.在雾中寻宁静

先对树做一遍dfs，记录节点进入的时间L和出去的时间R，L到R就包含了该节点以及其子树节点（dfs序）。
问题转换为区间染色，因为后面的染色会覆盖前面的染色，可以考虑逆向操作，每一次只染没有染过色的点，跳过已经染过色的点。可以用并查集维护下一个未染色的点。
代码说明：

a数组表示dfs序。
L[i]和R[i]分别表示进入和出去时刻。
s[i]表示i指向下一个没有填色的位置。

const int N=2e5+10,M=2*N;
int h[N],e[N],ne[N],idx;
int a[M],L[N],R[N];
int n,cnt,s[M];
pii op[N];
inline void add(int a,int b)
{
    e[++idx]=b;ne[idx]=h[a];h[a]=idx;
}
void dfs(int u)
{
    L[u]=++cnt;
    for(int i=h[u];i;i=ne[i]) dfs(e[i]);
    R[u]=++cnt;
}
int Find(int u)
{
    if(s[u]==u) return u;
    else return s[u]=Find(s[u]);
}
inline void Solve()
{
    cin>>n;
    rep(i,1,n){
        int x;cin>>x;
        add(x,i+1);
    }
    dfs(1);
    int q;cin>>q;
    rep(i,0,q){
        int x,y;cin>>x>>y;
        op[i]={x,y};
    }
    rep(i,1,2*n+2) s[i]=i;
    per(i,q-1,-1){
        int l=L[op[i].fi],r=R[op[i].fi],c=op[i].se;
        for(int k=Find(l);k<=r;k=Find(k)){
            a[k]=c;s[k]=Find(k+1);
        }
    }
    rep(i,1,n+1) cout<<a[L[i]]<<" ";
}

F.不规则的轮回

注意到x,y的规模不大，对n个数对暴力求出所有数对最多枚举 $10^7$ 左右，时间上可以接收，空间上只需要存储询问中的数对，然后计算出的数对在询问中就算上贡献，c++用map即可。

const int N=2e3+10;
pii a[N],b[N];
inline void Solve()
{
        int n,m;
        set<pii>q;
        map<pii,int>mp;
        cin>>n;
        rep(i,0,n) cin>>a[i].fi>>a[i].se;
        cin>>m;
        rep(i,0,m) cin>>b[i].fi>>b[i].se,q.insert({b[i].fi,b[i].se});
        rep(i,0,n){
                int &x=a[i].fi,&y=a[i].se;
                while(x!=y){
                        if(q.count({x,y})) ++mp[{x,y}];
                        if(x>y) x-=y;
                        else y-=x;
                }
                if(q.count({x,y})) ++mp[{x,y}];
        }
        rep(i,0,m) cout<<mp[{b[i].fi,b[i].se}]<<endl;
}

G.完美数字

根据算术基本定理将数字分成素数乘积，除了素数2和5结合对末尾0有贡献，其他素数乘积都不会产生新的末尾0，末尾的0个数就取决于2的幂次和5的幂次中较小的一个。
将每个数2的幂次和5的幂次计算出来，分别求前缀和。然后枚举左端点 L，找到第一个较小的段和大于等于 k 的右端点 R，对答案产生 n-R+1 的贡献。注意到 L 往右移动时，R 只能右前移，不能回退(双指针算法)。

const int N=2e5+10;
int a[N],b[N];
inline int A(int x,int k)
{
    int rt=0;
    while(x%k==0){
        x/=k;++rt;
    }
    return rt;
}
inline void Solve()
{
    int n,m;
    cin>>n>>m;
    rep(i,1,n+1){
        cin>>a[i];
        b[i]=A(a[i],2);a[i]=A(a[i],5);
    }
    rep(i,1,n+1) a[i]+=a[i-1],b[i]+=b[i-1];
    LL ans=0;
    int r=1;
    rep(l,1,n+1){
        while(r<=n&&min(a[r]-a[l-1],b[r]-b[l-1])<m) ++r;
        if(r<=n) ans+=n-r+1;
    }
    cout<<ans<<endl;
}

H.春天与花儿

如果只改变一个数，将 ai 加到 k 的倍数即可。
对于 k=4 的情况，还有可能是把两个不同的数加到能被2整除。
对于 k=6 的情况，还有可能是把一个数加到能被2整除，另外一个加到能被3整除。

const int N=1e6+10;
int a[N],n,b[N];
inline int calc(int x,int k)
{
        return (k-x%k)%k;
}
inline pii Find01(int *a)
{
        int m1=100,m2=100;
        rep(i,0,n){
                if(a[i]<=m1){
                        m2=m1;
                        m1=a[i];
                }else if(a[i]<m2) m2=a[i];
        }
        return {m1,m2};
}
inline int Find0(int *a)
{
        int pos=0;
        rep(i,1,n){
                if(a[i]<a[pos]){
                        pos=i;
                }
        }
        return pos;        
}
inline void Solve()
{
        int k,ans=6;
        cin>>n>>k;
        rep(i,0,n){
                cin>>a[i];
                ans=min(ans,calc(a[i],k));
        }
        if(k==4&&n!=1){
                rep(i,0,n) a[i]=calc(a[i],2);
                auto rt=Find01(a);
                ans=min(ans,rt.fi+rt.se);
        }
        if(k==6&&n!=1){
                rep(i,0,n) b[i]=calc(a[i],3),a[i]=calc(a[i],2);
                int p1=Find0(a),p2=Find0(b);
                if(p1!=p2){
                        ans=min(ans,a[p1]+b[p2]);
                }else{
                        auto r1=Find01(a),r2=Find01(b);
                        ans=min({ans,r1.fi+r2.se,r1.se+r2.fi});
                }
        }
        cout<<ans<<endl;
}

I.孤独与追求

为了避免偶数回文串的情况，先对原字符串做填充处理。然后枚举中点，可以用二分长度+字符串哈希求出以这个点为中点的最长回文串。预处理出值的前缀和数组a，根据回文串对称性，对于中点是 m，右端点是 r 的回文串，只需要求出 $\max_{m \le i \le r} a[i]-a[m]$ ，用线段树维护区间最大值即可。

const int N=2e6+10;
int n,mp[27];
char s[N];
LL a[N];
ULL h[N],rh[N],p[N];
namespace Segment_tree{
    struct sg_tree{
        int l,r;
        LL mx;
    };
    inline void up(sg_tree *t,int p){
        t[p].mx=max(t[Ls(p)].mx,t[Rs(p)].mx);
    }
    inline void Build(sg_tree *t,LL *a,int p,int l,int r){
        t[p]={l,r};
        if(l==r){
            t[p].mx=a[l];
            return;
        }
        int mid=l+r>>1;
        Build(t,a,Ls(p),l,mid);Build(t,a,Rs(p),mid+1,r);
        up(t,p);
    }
    inline LL Qy(sg_tree *t,int p,int l,int r){
        if(t[p].l>r||t[p].r<l) return -1e18;
        if(t[p].l>=l&&t[p].r<=r) return t[p].mx;
        LL res=-1e18;
        if(t[Ls(p)].r>=l) res=max(res,Qy(t,Ls(p),l,r));
        if(t[Rs(p)].l<=r) res=max(res,Qy(t,Rs(p),l,r));
        return res;
    }
}
namespace Str_Algorithm{
        ULL Str_Hash(char *s){
                ULL p=131,h=0;
                int n=strlen(s);
                rep(i,0,n) h=h*p+s[i];
                return h;
        }ULL Str_Hash(string s){
                ULL p=131,h=0;
                rep(i,0,s.size()) h=h*p+s[i];
                return h;
        }
        void Build_lhash(char *s,ULL *h){
                int n=strlen(s+1);
                int p=131;h[0]=0;
                rep(i,1,n+1) h[i]=h[i-1]*p+s[i];
        }void Build_lhash(string s,ULL *h){
                int n=s.size()-1;
                int p=131;h[0]=0;
                rep(i,1,n+1) h[i]=h[i-1]*p+s[i];
        }
        void Build_rhash(char *s,ULL *h){
                int n=strlen(s+1);
                int p=131;h[n+1]=0;
                per(i,n,0) h[i]=h[i+1]*p+s[i];
        }void Build_rhash(string s,ULL *h){
                int n=s.size()-1;
                int p=131;h[n+1]=0;
                per(i,n,0) h[i]=h[i+1]*p+s[i];
        }
        ULL Get_lhash(int l,int r,ULL *h,ULL *p){return h[r]-h[l-1]*p[r-l+1];}
        ULL Get_rhash(int l,int r,ULL *h,ULL *p){return h[l]-h[r+1]*p[r-l+1];}
        void Manacher(char *s,int *p,int n){
                int r=0,c;
                rep(i,1,n){
                        if(i<r) p[i]=min(p[(c<<1)-i],p[c]+c-i);
                        else p[i]=1;
                        while(s[p[i]+i]==s[i-p[i]]) ++p[i];
                        if(p[i]+i>r) r=p[i]+i,c=i;
                }
        }
}
inline void Init(char *s,int &n)
{
    per(i,n,0) s[2*i-1]=s[i];
    n=2*n-1;
    for(int i=2;i<=n;i+=2) s[i]='z'+1;
}
Segment_tree::sg_tree T[4*N];
inline void Solve()
{
    using namespace Str_Algorithm;
    using namespace Segment_tree;
    cin>>n;
    rep(i,0,26) cin>>mp[i];
    cin>>s+1;
    Init(s,n);
    rep(i,1,n+1) a[i]=a[i-1]+mp[s[i]-'a'];
    p[0]=1;
    Build(T,a,1,1,n);
    rep(i,1,n+1) p[i]=p[i-1]*131;
    Build_lhash(s,h);Build_rhash(s,rh);
    LL ans=-1e18;
    rep(i,1,n+1){
        int l=0,r=min(n-i,i-1);
        while(l<r){
            int mid=l+r+1>>1;
            if(Get_lhash(i-mid,i,h,p)==Get_rhash(i,i+mid,rh,p)) l=mid;
            else r=mid-1;
        }
        ans=max(ans,2*(Qy(T,1,i,i+l)-a[i])+mp[s[i]-'a']);
    }
    cout<<ans<<endl;
}

J.最后的星光

如果用两个字符串相同位置个数来表示一个状态，最终状态就是字符串长度 n，发现问题转换成广搜。
如果当前状态是 t ，采用第一种方法可以枚举选了 i 个相同的位置，状态就转移到了 t-i+m-i。注意需要满足不相等的位置足够选： $m-i \leq n-t$ 。采用第二种方法，假设在相等的位置中有 i 个在 a 中，j 个在 b 中，相同位置增加了a-i个，又减少了j个，状态转移到了 t+a-i-j。直接枚举 i+j 的值，上界就是 $i+j \leq t,a+b$ ，下界要保证不相等的位置足够选： $n-t \geq a+b-(i+j)$
时间复杂度为 $O(n^2)$

const int N=2010;
char s1[N],s2[N];
int d[N];
inline void Solve()
{
    int a,b,m;
    cin>>s1>>s2>>a>>b>>m;
    int n=strlen(s1),ct=0;
    rep(i,0,n) if(s1[i]==s2[i]) ++ct;
    MEM(d,-1);d[ct]=0;
    queue<int>q;q.emplace(ct);
    while(q.size()){
        int t=q.front();q.pop();
        rep(i,max(0,m-n+t),t+1){
            if(t+m-2*i<0) break;
            if(d[t+m-2*i]==-1){
                q.emplace(t+m-2*i);
                d[t+m-2*i]=d[t]+1;
            }
        }
        rep(i,max(0,a+b-n+t),min(t,a+b)+1){
            if(t+a-i<0) break;
            if(d[t+a-i]==-1){
                q.emplace(t+a-i);
                d[t+a-i]=d[t]+1;
            }
        }
    }
    cout<<d[n]<<endl;
}

K.天使的拼图

结论是矩形满足3|n且4|m，或12|n且m>=7都合法，其中n,m可以互换。
假设n是行，m是列，由于n，m可交换，下面证明只说明一种。
考虑把两个Tenshi图块拼在一起，覆盖要求中间不能有空，只有两个拼法：

由于其他的拼法会导致中间有空隙不合法，问题就可以转换用上面两种图形经过旋转翻转覆盖矩形。
两个图形都是12块单位，如果能覆盖则一定有 12|nm
分类讨论：

3|n且4|m，此时显然能被上面第一个3 * 4的矩形图覆盖。
12|n，3|m或者4|m同1。下面考虑12|n，3和4都不能整除m，由上面两个图可知m>=3，得到m>=5。可验证m=5的情况无法覆盖。对于其他情况，如果m=3k+4,k>=1，使用第一个图，可以先把第一个3 * 4的图先横着放满，这时m=3k，后面都竖着放。如果m=3k+8,k>=1，横着放两次m就变成了 3k，也可以覆盖。
12|mn，m和n都不能被4整除。可知m和n都必须是偶数。将n * m的矩形分成单位正方形，将行和列分别标上号码1,2,…,n及1,2,…,m。给单位正方形(i,j)按如下方式赋值:值为i,j中能被4整除的数的个数(因此值可以为0,1,2)。这样所有的方格数字之和是偶数：考虑某个行i能被4整除产生贡献为m，对于能被4整除的列产生贡献为n，而m和n都是偶数。按照这个方法写一个程序打表，可以发现两个图不管如何放，贡献都是奇数。所以覆盖图形的个数也是偶数个，就有24|mn，则8|mn，m，n都为偶数，一定有一个被4整除，与前提矛盾，这种情况不存在。

bool ok(LL n,LL m)
{
    if(n%3==0&&m%4==0) return true;
    if(n%12==0&&m>=7) return true;
    return false;
}
inline void Solve()
{
    LL n,m;cin>>n>>m;
    if(ok(n,m)||ok(m,n)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

L.擅长搞事的高木同学

如下图所示，假设要从A点走到对角E点。首先可以发现A到E最后一定是偶数步，且至少4步。

用 $f_a(n),f_c(n),f_g(n)$ ，分别表示点 A,C,G到E的方案数。

注意到对称性，可知 $f_c(n)=f_g(n)$

我们可以对 $f_a(n)$ 进行划分，从A开始走两步，可以到达A，C，G，于是有了下式（注意到达A是A->B->A和A->H->A两种不同的走法）：

$f_a(n)=2f_a(n-2)+f_c(n-2)+f_g(n-2)=2f_a(n-2)+2f_c(n-2)$

再对 $f_c(n)$ 进行划分，从C开始走两步，可以到达C，A，于是有了下式：

$f_c(n)=f_a(n-2)+2f_c(n-2)$

边界： $f_a(2)=0,\, f_c(2)=1$

写成矩阵形式用快速幂即可：

$\begin{bmatrix} f_a(n) \\ f_c(n) \end{bmatrix} = \begin{bmatrix} 2 & 2 \\ 1 & 2 \end{bmatrix}^{\frac{n}{2}-1 } \begin{bmatrix} f_a(2) \\ f_c(2) \end{bmatrix} = \begin{bmatrix} 2 & 2 \\ 1 & 2 \end{bmatrix}^{\frac{n}{2}-1 } \begin{bmatrix} 0 \\ 1 \end{bmatrix}$

const int N=1e3+10,M=1e9+7;
struct mat{
        int a[2][2];
        mat operator*(const mat& b) const{
                mat c={0,0,0,0};
                rep(i,0,2) rep(j,0,2) rep(k,0,2) c.a[i][j]+=1ll*a[i][k]*b.a[k][j]%M,c.a[i][j]%=M;
                return c;
        }
};
inline int Qp(LL n)
{
        mat res={1,0,0,1},A={2,2,1,2},a={0,0,1,0};
        while(n){
                if(n&1) res=res*A;
                A=A*A;
                n>>=1;
        }
        res=res*a;
        return res.a[0][0]%M;
}
inline void Solve()
{
        LL n;
        cin>>n;
        if((n&1)||n<=3){
                cout<<0<<endl;
        }else cout<<Qp(n/2-1)<<endl;
}

M.Monika's game

用f(n)表示n的最大值。无论用什么策略，最大值始终是 $\frac{n(n-1)}{2}$

证明：

对于n=1该式子成立。

对于 $n \ge 2$ ，假设比n小的规模都满足上式，则有：

$f(n)=f(n-r)+f(r)+r(n-r)=\frac{(n-r)(n-r-1)}{2} + \frac{r(r-1)}{2} + r(n-r) = \frac{n(n-1)}{2} , 1 \le r \le n-1$

故对于 $n \ge 2$ ，上式也成立。

inline void Solve()
{
    int n;
    cin>>n;
    cout<<1ll*n*(n-1)/2<<endl;
}