2026 年中国传媒大学程序设计大赛

比赛传送门

A

不难发现,在已有"CUC"上,增加一个"UC"即可使"CUC"子串的数量 $+1$

Code

void solve() {
    int n;
    cin >> n;
    cout <<"CUC";
    for (int i=2;i<=n;i++) cout <<"UC";
    cout <<el;
}

B

简单dp
记 $dp_{i,j}$ , $i$ 表示当前走到第几阶, $j$ 表示是否有过一次走两步的行为

$$dp_{i,1}=dp_{i-2,1}+dp_{i-2,0} $$

$$dp_{i,0}=dp_{i-1,0} $$

注意预处理,否则会超时

Code

const int  N=1e5+4;const int mod=998244353;
vector<vector<int>> dp(N,vector<int>(2));
void init() {
    dp[0][0]=dp[1][0]=1;
    for (int i=2;i<N;i++) {
        dp[i][1]=(dp[i][1]+dp[i-2][0]+dp[i-2][1])%mod;
        dp[i][0]=dp[i-1][0];
    }
}

void solve() {
    int n;
    cin >> n;
    cout << (dp[n][1]+dp[n][0])%mod<<el;
}

C

给面积求 $c$ ,可以想到定积分求面积,那么需要知道零点来确定区间范围

$$x=\frac{b\pm\sqrt{b^2+4c}}{2} $$

于是可以确定左右零点$x0,x1$
先对 $y$定积分一下,得到:

$$S=-\frac{1}{3}x^3\biggr|_{x0}^{x1}+\frac{b}{2}x^2\biggr|_{x0}^{x1}+cx\biggr|_{x0}^{x1} $$

可以发现面积和 $c$ 是有单调关系的,考虑二分
补充:为什么说有单调关系?
因为 $c$ 越大, $x1$ 越靠右, $x0$ 越来越靠左,因此面积也就越大
另外要注意, $x0$ 最小只能取 $0$

Code

void solve() {
    int b,s;
    cin >> b >> s;
    auto check=[&](double c)->double {
        double x=(b+sqrt(b*b+4*c))/2.0;
        double t1=(-1.0/3)*x*x*x+(1/2.0)*b*x*x+c*x;
        double x2=max((b-sqrt(b*b+4*c))/2.0,0.0);
        double t2=(-1.0/3)*x2*x2*x2+(1/2.0)*b*x2*x2+c*x2;
        return t1-t2;
    };
    double left=-1e7,right=1e7;
    for (int i=0;i<10000;i++) {
        double mid=left+(right-left)/2;
        double t=check(mid);
        if (t>s) right=mid;
        else left=mid;
    }
    cout << left<<el;
}

D

$0,1$ 互换位置是没有代价的,也就是你只要数量刚好,代价就可以是 $0$
数量不刚好怎么办?
两个相邻的相同数可以转置变成另一种,一次可以转 $2$ 个
也就是如果两个矩阵相差数量为偶数,代价为 $0$
相差数量为奇数,代价为 $1$

Code

void solve() {
    int n,m;
    cin >> n >> m;
    vector<string> a(n),b(n);
    for (int i=0;i<n;i++) cin >> a[i];
    for (int i=0;i<n;i++) cin >> b[i];
    int cnt=0;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (a[i][j]=='1') cnt++;
        }
    }
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (b[i][j]=='1') cnt--;
        }
    }
    cout << (abs(cnt)%2)<<el;
}

E

$x,y$ 都小于 $10$ 时自己算一下判断,此时开ll是不会爆的
都大于 $10$ 的情况下,$x+y$和$x*y$ 都太弱了
指数函数增长速度比幂函数大
所以比较一下 $x$ 和 $y$ 的大小,哪个大,对应为指数的就是最大的数
注意特判 $x=1$ || $y=1$ 的情况

Code

int fastpow(int base,int exp) {
    int res=1;
    while (exp >0) {
        if (exp &1) res=(res*base);
        base=(base*base);
        exp>>=1;
    }
    return res;
}

void solve() {
    int x,y,p;
    cin >> x >> y>>p;
    if ((x<=10 && y<=10 )|| (x==1 || y==1)) {
        int a1=x+y;
        int a2=x*y;
        int a3=fastpow(x,y);
        int a4=fastpow(y,x);
        vector<int> a={a1,a2,a3,a4};
        int mx=*max_element(all(a));
        if (a[p-1]==mx) cout <<"Yes"<<el;
        else cout << "No"<<el;
    }
    else {
        if (x>y) {
            if (p==4) cout << "Yes"<<el;
            else cout <<"No"<<el;
        }
        else if (x==y) {
            if (p==3 || p==4) cout <<"Yes"<<el;
            else cout <<"No"<<el;
        }
        else {
            if (p==3) cout <<"Yes"<<el;
            else cout <<"No"<<el;
        }
    }
}

F

感觉是本场最难的题之一
先看看小数据的情况:
对于 $1-7$和 $9$ 和 $11$ 无法分,先手直接输
对于 $8$ 分一个 $4$ 出来,后手输
对于 $10$ 分一个 $4$ 出来,后手输
注意到,只要将 $n$ 分为 $4,6,9$ 和另一个合数,后手直接输掉
证明:对于$n≥12$ ,$n-4,n-6,n-9$中至少有一个是合数
$n-6$ 和 $n-9$ 至少有一个是偶数,且由于$n≥12$,那么该偶数肯定为合数

Code

void solve() {
    int n;
    cin >> n;
    if (n<=7 || n==9 || n==11) {
        cout <<"yukari"<<el;
        return;
    }
    else cout <<"kou" <<el;
}

G

dp
注意到,只能选 $3,6,9$ 长度的子数组
记$dp_{i}$为以 $i$ 为结尾的最大染色数
用前缀和快速求前 $3,6,9$ 子数组中的 $1,2,3$ 的个数
如果都相等就转移

$$dp_{i}=dp_{i-3}+3 $$

$$dp_{i}=dp_{i-6}+6 $$

$$dp_{i}=dp_{i-9}+9 $$

Code

void solve() {
    int n;
    cin >> n;
    vector<int> pre1(n+1),pre2(n+1),pre3(n+1),dp(n+1),a(n+1);
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        pre1[i]=pre1[i-1]+ (a[i]==1?1:0);
        pre2[i]=pre2[i-1]+(a[i]==2?1:0);
        pre3[i]=pre3[i-1]+(a[i]==3?1:0);
    }
    for (int i=3;i<=n;i++) {
        dp[i]=dp[i-1];
        if (i>=3) {
            int cnt1= pre1[i]-pre1[i-3];
            int cnt2= pre2[i]-pre2[i-3];
            int cnt3= pre3[i]-pre3[i-3];
            if (cnt1==cnt2 && cnt3==cnt1) dp[i]=max(dp[i],dp[i-3]+3);
        }
        if (i>=6) {
            int cnt1= pre1[i]-pre1[i-6];
            int cnt2= pre2[i]-pre2[i-6];
            int cnt3= pre3[i]-pre3[i-6];
            if (cnt1==cnt2 && cnt3==cnt1) dp[i]=max(dp[i],dp[i-6]+6);
        }
        if (i>=9) {
            int cnt1= pre1[i]-pre1[i-9];
            int cnt2= pre2[i]-pre2[i-9];
            int cnt3= pre3[i]-pre3[i-9];
            if (cnt1==cnt2 && cnt3==cnt1) dp[i]=max(dp[i],dp[i-9]+9);
        }
    }
    cout << dp[n]<<el;
}

H

已无言
存所有连续 $0$ 子数组的左端点和右端点到 $multiset$,方便二分修改
记录所有连续 $0$ 子数组长度子数组对应的个数,方便查询答案
是否会超时???
修改时间复杂度$O(logn)$
查询时间复杂度$O(\sqrt{n})$ ,因为所有长度集齐了最多也就这么多
讲一下大致操作吧,实现我写成石了
0->1:
看一下有没有覆盖到某一连续 $0$ 段,有的话说明该操作将其分为两段
1->0:
连接左段和右段
或者单开一段

Code

void solve() {
    int n,Q;
    cin >> n >>Q;
    string s;
    cin >> s;
    s=" "+s;
    multiset<array<int,2>> st;
    map<int,int> mp;
    for (int i=1;i<=n;i++) {
        if (s[i]=='1') continue;
        int j=i+1;
        while (j<=n && s[j]=='0') j++;
        st.insert({i,j-1});
        mp[j-i]++;
        i=j-1;
    }
    while (Q--) {
        int op,x;
        cin >> op >> x;
        if (op==1) {
            if (s[x]=='0') {
                auto l=st.upper_bound({x,n+1});
                s[x]='1';
                if (l!=st.begin()) {
                    l--;
                    auto [ll,rr]=*l;
                    if (rr>=x && ll<=x) {
                        int front=x-ll;
                        int back=rr-x;
                        if (!--mp[rr-ll+1]) mp.erase(rr-ll+1);
                        st.erase(l);
                        if (front>0) {
                            st.insert({ll,x-1});
                            mp[front]++;
                        }
                        if (back>0) {
                            st.insert({x+1,rr});
                            mp[back]++;
                        }
                    }
                }
            }
            else {//1->0
                auto r=st.upper_bound({x,n+1});
                if (r!=st.end()) {
                    if (r!=st.begin()) {
                        auto l=prev(r);
                        auto [ll,rr]=*l;
                        auto [tl,tr]=*r;
                        if (rr+1==x) {
                            if (tl-1==x) {
                                mp[tr-ll+1]++;
                                if (!--mp[tr-tl+1]) mp.erase(tr-tl+1);
                                if (!--mp[rr-ll+1]) mp.erase(rr-ll+1);
                                st.erase(l); st.erase(r);
                                st.insert({ll,tr});
                            }
                            else {
                                mp[x-ll+1]++;
                                if (!--mp[rr-ll+1]) mp.erase(rr-ll+1);
                                st.erase(l);
                                st.insert({ll,x});
                            }
                        }
                        else {
                            if (tl-1==x) {
                                mp[tr-x+1]++;
                                if (!--mp[tr-tl+1]) mp.erase(tr-tl+1);
                                st.erase(r);
                                st.insert({x,tr});
                            }
                            else {
                                mp[1]++;
                                st.insert({x,x});
                            }
                        }
                    }
                    else {
                        auto [ll,rr]=*r;
                        if (ll==x+1) {
                            mp[rr-x+1]++;
                            if (!--mp[rr-ll+1]) mp.erase(rr-ll+1);
                            st.erase(r);
                            st.insert({x,rr});
                        }
                        else {
                            mp[1]++;
                            st.insert({x,x});
                        }
                    }
                }
                else {
                    if (st.empty()) {
                        mp[1]++;
                        mp.insert({x,x});
                    }
                    else{
                        auto l=prev(r);
                        auto [ll,rr]=*l;
                        if (rr+1==x) {
                            mp[x-ll+1]++;
                            if (!--mp[rr-ll+1]) mp.erase(rr-ll+1);
                            st.erase(l);
                            st.insert({ll,x});
                        }
                        else {
                            mp[1]++;
                            st.insert({x,x});
                        }
                    }
                }
                s[x]='0';
            }
        }
        else {
            int ans=0;
            for (auto &[len,cnt]:mp) if (len>0)ans+=(len/x)*cnt;
            cout << ans<<el;
        }
    }
}

I

爆搜所有排列,$set$去重一下即可

Code

void solve() {
    int n;
    cin >> n;
    vector<int> a(n+1),b(n+1);
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=n;i++) cin >> b[i];
    set<vector<int>> ans;
    vector<int> path;
    auto dfs=[&](auto self,int ia,int ib)->void {
        if (path.size()==2*n) {
            ans.insert(path);
            return;
        }
        if (ia<=n) {
            path.pb(a[ia]);
            self(self,ia+1,ib);
            path.pop_back();
        }
        if (ib<=n) {
            path.pb(b[ib]);
            self(self,ia,ib+1);
            path.pop_back();
        }
    };
    dfs(dfs,1,1);
    cout <<ans.size()<<el;
    for (auto &v:ans) {
        for (auto &x:v) {
            cout << x<<" ";
        }
        cout <<el;
    }
}

J

最优先处理的肯定是,可以直接让字符种类一次变成 $3$ 的
讨论其他的:
分长度讨论,无论$1,2,≥3$,加一个种类,给答案加的值都一样,但是给 $≥3$ 加有潜在收益,肯定优先加
于是得出结论,长度大的优先加,同样大的,种类数最多的优先加,优先队列实现即可
当然,注意特判一下修改没效果的
依旧石山

Code

void solve() {
    int n,k;
    cin >> n >> k;
    int ans=0;
    vector<string> a(n);
    pq<array<int,2>>q;
    for (int i=0;i<n;i++)cin >>a[i];
    for (int i=0;i<n;i++) {
        int sz=a[i].size();
        set<char> s;
        for (auto x:a[i]) s.insert(x);
        if (s.size()<=2)ans+=(int)s.size();
        else ans+=4;
        if (sz==s.size()) continue;
        if (sz>=3) {
            if (s.size()==2) {
                k--;
                if (k<0) continue;
                ans+=2;
            }
            else q.push({sz,(int)s.size()});
        }
        else q.push({sz,(int)s.size()});
    }
    while (!q.empty()) {
        auto [x,y]=q.top();
        q.pop();
        if (x==3) {
            if (y==2) {
                k--;
                if (k<0) break;
                ans+=2;
            }
            else if(y==1) {
                k--;
                if (k<0) break;
                ans++;
                k--;
                if (k<0) break;
                ans+=2;
            }
            else {
                k--;
                if (k<0) break;
                ans++;
                k--;
                if (k<0) break;
                ans++;
                k--;
                if (k<0) break;
                ans+=2;
            }
        }
        else {
            if (x==1) {
                k--;
                if (k<0) break;
                ans++;
            }
            else {
                if (y==1) {
                    k--;
                    if (k<0) break;
                    ans++;
                }
                else {
                    k--;
                    if (k<0) break;
                    ans++;
                    k--;
                    if (k<0) break;
                    ans++;
                }
            }
        }
    }
    cout <<ans<<el;
}

K

扩展域并查集,将每一个朋友 $i$ 分为两个逻辑阵营 $A(i),B(i+n)$
给出 $(x,y)$ 为敌人(即不同阵营) :
$fa(x)=fa(y)$ 或者 $fa(x+n)=fa(y+n)$ 说明俩人不是敌人,矛盾
否则,说明该声明正确,将不同阵营的 $x和y$ 合并(敌人的敌人是朋友):

$$merge(x,y+n) $$

$$merge(y,x+n) $$

Code

const int N=4e5+5;
vector<int> father(N);;
void init() {
    for (int i=0;i<N;i++)father[i]=i;
}
int find(int x) {
    if (father[x]!=x) father[x]=find(father[x]);
    return father[x];
}
void merge(int a,int b) {
    int aa=find(a);
    int bb=find (b);
    if (aa!=bb) father[aa]=bb;
}

void solve() {
    int n,m;
    cin >> n >> m;
    vector<int> en(n+1);
    for (int i=0;i<m;i++) {
        int u,v;
        cin >> u >> v;
        int xa=u,xb=u+n;
        int ya=v,yb=v+n;
        if (find(xa)==find(ya) || find(xb)==find(yb)) cout<<0;
        else {
            cout <<1;
            merge(xa,yb);
            merge(xb,ya);
        }
    }
    cout <<el;
}