2024中国计算机学会CSP-S认证提高组第二轮解析

Randle

2024的CSP-S刚刚落幕，有申诉需求的同学们抓紧了中国计算机学会官方申诉链接
个人觉得这次主办方出题很有区分度，甚至有出题人可以猜到做题人心思的感觉
本贴是鄙人的代码和思路，有什么问题欢迎各位指出
T1

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N = 1e5 + 5;
int a[N];
queue<int> q;
int main(){
        int n;scanf("%d",&n);
        for(int i = 0; i <= n-1; i++){
                scanf("%d",&a[i]);
        }
        sort(a,a+n);
        for(int i = 0; i <= n-1; i++){
                if(q.empty()){
                        q.push(a[i]);
                }else{
                        if(q.front() < a[i]){
                                q.pop();
                        }
                        q.push(a[i]);
                }
        }
        printf("%d",q.size());
        return 0;
}

我一看先贪心算法，因为无后效性就直接贪，用一个队列queue，更清楚
核心代码是判断后入的是否大于队首，若大于则弹出队首，不大于就直接插队尾，最后输出队列长度就是答案

T2

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int csy[N];
int zjcsy[N];
struct cifmt{
        int dx;
        int stv;
        int a;
}car[N];
int main(){
        freopen("detect.in","r",stdin);
        freopen("detect.out","w",stdout);
        memset(zjcsy,0,sizeof(zjcsy));
        int t;cin>>t;
        int n,m,l,v;
        for(int i = 1; i <= t; i++){
                cin>>n>>m>>l>>v;
                int col = 0;int sum;
                int bsum = 0;
                for(int j = 1; j <= n; j++){
                        cin>>car[j].dx>>car[j].stv>>car[j].a;
                }
                for(int k = 1; k <= m; k++){
                        cin>>csy[k];
                }
                for(int ddq = 1; ddq <= n; ddq++){
                        if(car[ddq].a == 0 && car[ddq].stv > v){
                                col++;
                                for(int ppq = 1; ppq <= m; ppq++){//注意判断这时候dx是不是刚好是一个csy
                                        if(csy[1] == car[ddq].dx){
                                                zjcsy[1]++;
                                        }else if(csy[ppq] == car[ddq].dx ){
                                                zjcsy[ppq]++;
                                                
                                                cout<<zjcsy[ppq]<<endl;
                                                break;
                                        }else if(csy[ddq] < car[ddq].dx && car[ddq].dx < csy[ppq+1]){
                                                zjcsy[ppq+1]++;
                                                
                                                cout<<zjcsy[ppq+1]<<endl;
                                                break;
                                        }
                                }
                        }else if(car[ddq].a > 0){
                                if(car[ddq].stv > v){
                                        if(car[ddq].dx <= csy[m]){
                                                col++;
                                                for(int jsx = 1; jsx <= m; jsx++){
                                                        if(csy[jsx] == car[ddq].dx){
                                                                zjcsy[jsx]++;
                                                                
                                                                cout<<zjcsy[jsx]<<endl;
                                                                break;
                                                        }else if(csy[jsx] < car[ddq].dx && car[ddq].dx < csy[jsx+1]){
                                                                zjcsy[jsx+1]++;
                                                                
                                                                cout<<zjcsy[jsx+1]<<endl;
                                                                break;
                                                        }
                                                }
                                        }
                                }else if(car[ddq].stv == v){//注意这里如果进的时候的dx刚好是csy里的一个
                                        if(car[ddq].dx < csy[m]){
                                                col++;
                                                for(int ccf = 1; ccf <= m; ccf++){
                                                        if(csy[ccf] < car[ddq].dx && car[ddq].dx < csy[ccf+1]){
                                                                zjcsy[ccf+1]++;
                                                                
                                                                cout<<zjcsy[ccf+1]<<endl;
                                                                break;
                                                        }
                                                }
                                        }
                                }else if(car[ddq].stv < v){
                                        sum = ((v*v) - (car[ddq].stv * car[ddq].stv)) / (2*car[ddq].a);
                                        if(car[ddq].dx + sum < csy[m]){
                                                col++;
                                                for(int xr = 1; xr <= m; xr++){
                                                        if(csy[xr] < car[ddq].dx && car[ddq].dx < csy[xr+1]){
                                                                zjcsy[xr+1]++;
                                                                
                                                                cout<<zjcsy[xr+1]<<endl;
                                                                break;
                                                        }
                                                }
                                        }
                                }
                        }else if(car[ddq].a < 0){
                                if(car[ddq].stv > v){
                                        sum = ((v*v) - (car[ddq].stv*car[ddq].stv)) / (2*car[ddq].a);
                                        for(int lrz = 1; lrz <= m; lrz++){
                                                if(car[ddq].dx <= csy[lrz] && csy[lrz] <= (car[ddq].dx+sum)){
//                                                        cout<<car[ddq].dx<<" "<<csy[lrz]<<" "<<car[ddq].dx+sum<<endl;
                                                        col++;
                                                        zjcsy[lrz]++;
                                                        
                                                        cout<<zjcsy[lrz]<<endl;
                                                        break;
                                                }
                                        }
//                                        cout<<sum<<endl;
                                }
                        }
                }
                cout<<col<<" ";
                for(int sy = 1; sy <= m; sy++){
                        if(csy[sy] != 1){
                                bsum++;
                        }
                }
                cout<<bsum<<endl;
        }
}

结构体起手
car数组结构体用来记录车的数量
dx是小车进来的位置
stv是小车初始速度
a是小车加速度
接下来分a==0,a<0,a>0三种情况讨论，看是否超速
1、a=0初速度也小于等于标准速度
2、a<0初速度也小于等于标准速度
3、位移段不跨测试点
均不用判断，因为他们不会超速或超速的那段也测不进去
测试仪用csy数组记录，最后保留一下测试仪个数
有的人可能想每个测试仪都存在数组里，每个加过去
1、每个加过去分类讨论4个5个还硬的过来，10000个呢？更多呢？模不过来
2、有的人考虑为0的，没用的删掉，那有很多大于0的，比如1个、2个也有可能没用的，我注释了“刚好是标准”就是有风险出现这种情况的
所以我们分析下2种情况：
1、我a>0，在某个地方增加达到标准速度，那么这个地方后面所有点肯定超，留最先的测试仪就行
2、我a<0，在某个地方降速达到标准速度，那么这个地方前面至起始位置所有点肯定超，留最后的测试仪就行
最后扫一遍zjcsy就可以得到要留的测试仪
T3

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
#define PII pair<int,int>
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define cl(f,x) memset(f,0x3f,sizeof(f))
using ll = long long;
using namespace std;
const int N=2e5+5,M=1e6+5;
int a[N],suf[N],last[M],n;
ll pre[N],f[N];
void solve() {
        scanf("%d",&n);
        rep(i,1,n) {
                scanf("%d",&a[i]);
                last[a[i]]=n+1;
                pre[i]=pre[i-1]+(a[i]==a[i-1])*a[i];
        }
        per(i,n,1) {
                suf[i]=last[a[i]];
                last[a[i]]=i;
        }
        suf[0]=n+1;
        rep(i,1,n)
                f[i]=0;
        ll mx=0;
        rep(i,1,n) {
                chkmax(f[i],mx+pre[i-1]);
                int p=suf[i-1];
                if(p<=n)
                        chkmax(f[p],f[i]+pre[p-1]-pre[i]+a[i-1]);
                chkmax(mx,f[i]-pre[i]);
        }
        printf("%lld\n",mx+pre[n]);
}
int main() {
//    freopen("color.in","r",stdin);
//    freopen("color.out","w",stdout);
    int testcase=1;
    scanf("%d",&testcase);
    while(testcase--)
        solve();
    return 0;
}

第三题动态规划
状态转移方程：
dp[1][0] = max(dp[1][0], dp[i - 1][j][1] + (a == a[i - j - 1] ? a : 0));
dp[1][1] = max(dp[1][1], dp[i - 1][j][0] + (a == a[i - j - 1] ? a : 0));
dp[j][0] = dp[i - 1][j - 1][0] + (a == a[i - 1] ? a : 0);
dp[j][1] = dp[i - 1][j - 1][1] + (a == a[i - 1] ? a : 0);
我们最优策略是隔一个选一个，比如5252
我们可以把5都染红2都染蓝，最大权就是7
分析左右染色块推状态转移方程，有数位DP和插头DP的味道
有的同学场下跟我说红黑树后缝个普通DP，维护平衡代码我就不放了，同学们可以自己试试

T4

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PII pair<int,int>
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define cl(f,x) memset(f,0x3f,sizeof(f))
using ll = long long;
using namespace std;
const int N=1e6+5,M=20;
inline int read() {
        int x=0,f=1;
        char ch=getchar();
        while(!isdigit(ch)) {
                if(ch=='-')
                        f=-1;
                ch=getchar();
        }
        while(isdigit(ch))
                x=x*10+ch-48,ch=getchar();
        return x*f;
}
#define ls(k) (k<<1)
#define rs(k) (k<<1|1)
#define pa(k) (k>>1)
#define sonid(k) (rs(pa(k))==k)
#define bro(k) (k^1)
vector<int> op[M];
int n,m,k,l,ta[N],a[N],b[N],opp[N],pos[N],p[N],f[N],g[N],t[N];
void dfs(int u,int d) {
        ++p[d];
        if(d==k) {
                t[p[d]]=u;
                pos[u]=p[d];[/u]
[u]                return;[/u]
[u]        }[/u]
[u]        opp=op[d][p[d]];[/u]
[u]        dfs(ls(u),d+1);[/u]
[u]        dfs(rs(u),d+1);[/u]
[u]}[/u]
[u]char s[N];[/u]
[u]void init() {[/u]
[u]        n=read();[/u]
[u]        m=read();[/u]
[u]        rep(i,1,n)[/u]
[u]                ta[i]=read();[/u]
[u]        rep(i,1,m)[/u]
[u]                b[i]=read();[/u]
[u]        l=1; k=0;[/u]
[u]        while(l<n)[/u]
[u]                l<<=1,++k;[/u]
[u]        per(i,k-1,0) {[/u]
[u]                scanf("%s",s+1);[/u]
[u]                int len=strlen(s+1);[/u]
[u]                op[i].resize(len+1);[/u]
[u]                rep(j,1,len)[/u]
[u]                        op[i][j]=s[j]-48;[/u]
[u]        }[/u]
[u]        dfs(1,0);[/u]
[u]}[/u]
[u]void dfs1(int u,int d) {[/u]
[u]        if(d==k) {[/u]
[u]                f=pos;[/u]
[u]                g=pos-1;[/u]
[u]                return;[/u]
[u]        }[/u]
[u]        dfs1(ls(u),d+1);[/u]
[u]        dfs1(rs(u),d+1);[/u]
[u]        if(!opp) {[/u]
[u]                if(a[f[ls(u)]]>=k-d) {[/u]
[u]                        f=f[ls(u)];[/u]
[u]                        g=g[ls(u)];[/u]
[u]                } else {[/u]
[u]                        f=f[rs(u)];[/u]
[u]                        g=g[rs(u)];[/u]
[u]                }[/u]
[u]                chkmax(g,g[ls(u)]);[/u]
[u]        } else {[/u]
[u]                if(a[f[rs(u)]]>=k-d) {[/u]
[u]                        f=f[rs(u)];[/u]
[u]                        g=g[rs(u)];[/u]
[u]                } else {[/u]
[u]                        f=f[ls(u)];[/u]
[u]                        g=g[ls(u)];[/u]
[u]                }[/u]
[u]                chkmax(g,g[rs(u)]);[/u]
[u]        }[/u]
[u]}[/u]
[u]int tc[4];[/u]
[u]ll ans[N];[/u]
[u]void upd(int _l,int _r,int val) {[/u]
[u]        chkmin(_r,l);[/u]
[u]        if(_l>_r)[/u]
[u]                return;[/u]
[u]        ans[_l]+=val;[/u]
[u]        ans[_r+1]-=val;[/u]
[u]}[/u]
[u]void solve() {[/u]
[u]        rep(i,0,3)[/u]
[u]                tc[i]=read();[/u]
[u]        rep(i,1,n)[/u]
[u]                a[i]=ta[i]^tc[i%4];[/u]
[u]        rep(i,n+1,l)[/u]
[u]                a[i]=INF;[/u]
[u]        dfs1(1,0);[/u]
[u]        rep(i,0,l)[/u]
[u]                ans[i]=0;[/u]
[u]        rep(i,1,l) {[/u]
[u]                int u=t[i],d=0,val=l;[/u]
[u]                // c >= i[/u]
[u]                if(i==1)[/u]
[u]                        upd(1,1,i);[/u]
[u]                while(u!=1) {[/u]
[u]                        int v=pa(u);[/u]
[u]                        ++d;[/u]
[u]                        if(opp[v]==sonid(u)) {[/u]
[u]                                if(a[i]<d)[/u]
[u]                                        break;[/u]
[u]                        } else {[/u]
[u]                                if(a[f[bro(u)]]>=d)[/u]
[u]                                        chkmin(val,g[bro(u)]);[/u]
[u]                        }[/u]
[u]                        upd(max(i,(1<<(d-1))+1),min(val,1<<d),i);[/u]
[u]                        u=v;[/u]
[u]                }[/u]
[u]                // c < i[/u]
[u]                u=t[i]; d=0; val=l;[/u]
[u]                while(u!=1) {[/u]
[u]                        int v=pa(u);[/u]
[u]                        ++d;[/u]
[u]                        if(opp[v]!=sonid(u)) {[/u]
[u]                                if(a[f[bro(u)]]>=d)[/u]
[u]                                        chkmin(val,g[bro(u)]);[/u]
[u]                        }[/u]
[u]                        if(i<=(1<<d)) {[/u]
[u]                                upd((1<<(d-1))+1,min(val,i-1),i);[/u]
[u]                                break;[/u]
[u]                        }[/u]
[u]                        u=v;[/u]
[u]                }[/u]
[u]        }[/u]
[u]        rep(i,1,l)[/u]
[u]                ans[i]+=ans[i-1];[/u]
[u]        ll res=0;[/u]
[u]        rep(i,1,m)[/u]
[u]                res^=i*ans[b[i]];[/u]
[u]        printf("%lld\n",res);[/u]
[u]}[/u]
[u]int main() {[/u]
[u]//        freopen("arena.in","r",stdin);[/u]
[u]//    freopen("arena.out","w",stdout);[/u]
[u]        init();[/u]
[u]    int testcase=read();[/u]
[u]    while(testcase--)[/u]
[u]        solve();[/u]
[u]    return 0;[/u]
[u]}

T4是全国决赛级别的题
差分思想，部分贪心后接DFS，深搜接树形DP
缝缝补补有超时点，各位同学有生log的做法可以在下方留言

最后祝各位rp++，Noip见

苏紫方璇

用markdown不能直接粘贴，得套上代码标记

Randle

苏紫方璇 发表于 2024-11-3 23:43
用markdown不能直接粘贴，得套上代码标记

谢谢谢谢！！

StarMax

Thanks1！