Randle 发表于 2024-11-3 17:09

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

本帖最后由 Randle 于 2024-11-6 20:39 编辑

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

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

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

T2

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int csy;
int zjcsy;
struct cifmt{
      int dx;
      int stv;
      int a;
}car;
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.dx>>car.stv>>car.a;
                }
                for(int k = 1; k <= m; k++){
                        cin>>csy;
                }
                for(int ddq = 1; ddq <= n; ddq++){
                        if(car.a == 0 && car.stv > v){
                              col++;
                              for(int ppq = 1; ppq <= m; ppq++){//注意判断这时候dx是不是刚好是一个csy
                                        if(csy == car.dx){
                                                zjcsy++;
                                        }else if(csy == car.dx ){
                                                zjcsy++;
                                                
                                                cout<<zjcsy<<endl;
                                                break;
                                        }else if(csy < car.dx && car.dx < csy){
                                                zjcsy++;
                                                
                                                cout<<zjcsy<<endl;
                                                break;
                                        }
                              }
                        }else if(car.a > 0){
                              if(car.stv > v){
                                        if(car.dx <= csy){
                                                col++;
                                                for(int jsx = 1; jsx <= m; jsx++){
                                                      if(csy == car.dx){
                                                                zjcsy++;
                                                               
                                                                cout<<zjcsy<<endl;
                                                                break;
                                                      }else if(csy < car.dx && car.dx < csy){
                                                                zjcsy++;
                                                               
                                                                cout<<zjcsy<<endl;
                                                                break;
                                                      }
                                                }
                                        }
                              }else if(car.stv == v){//注意这里如果进的时候的dx刚好是csy里的一个
                                        if(car.dx < csy){
                                                col++;
                                                for(int ccf = 1; ccf <= m; ccf++){
                                                      if(csy < car.dx && car.dx < csy){
                                                                zjcsy++;
                                                               
                                                                cout<<zjcsy<<endl;
                                                                break;
                                                      }
                                                }
                                        }
                              }else if(car.stv < v){
                                        sum = ((v*v) - (car.stv * car.stv)) / (2*car.a);
                                        if(car.dx + sum < csy){
                                                col++;
                                                for(int xr = 1; xr <= m; xr++){
                                                      if(csy < car.dx && car.dx < csy){
                                                                zjcsy++;
                                                               
                                                                cout<<zjcsy<<endl;
                                                                break;
                                                      }
                                                }
                                        }
                              }
                        }else if(car.a < 0){
                              if(car.stv > v){
                                        sum = ((v*v) - (car.stv*car.stv)) / (2*car.a);
                                        for(int lrz = 1; lrz <= m; lrz++){
                                                if(car.dx <= csy && csy <= (car.dx+sum)){
//                                                      cout<<car.dx<<" "<<csy<<" "<<car.dx+sum<<endl;
                                                      col++;
                                                      zjcsy++;
                                                      
                                                      cout<<zjcsy<<endl;
                                                      break;
                                                }
                                        }
//                                        cout<<sum<<endl;
                              }
                        }
                }
                cout<<col<<" ";
                for(int sy = 1; sy <= m; sy++){
                        if(csy != 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

#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,suf,last,n;
ll pre,f;
void solve() {
      scanf("%d",&n);
      rep(i,1,n) {
                scanf("%d",&a);
                last]=n+1;
                pre=pre+(a==a)*a;
      }
      per(i,n,1) {
                suf=last];
                last]=i;
      }
      suf=n+1;
      rep(i,1,n)
                f=0;
      ll mx=0;
      rep(i,1,n) {
                chkmax(f,mx+pre);
                int p=suf;
                if(p<=n)
                        chkmax(f,f+pre-pre+a);
                chkmax(mx,f-pre);
      }
      printf("%lld\n",mx+pre);
}
int main() {
//    freopen("color.in","r",stdin);
//    freopen("color.out","w",stdout);
    int testcase=1;
    scanf("%d",&testcase);
    while(testcase--)
      solve();
    return 0;
}

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

T4
#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;
int n,m,k,l,ta,a,b,opp,pos,p,f,g,t;
void dfs(int u,int d) {
      ++p;
      if(d==k) {
                t]=u;
                pos=p;
                return;
      }
      opp=op];
      dfs(ls(u),d+1);
      dfs(rs(u),d+1);
}
char s;
void init() {
      n=read();
      m=read();
      rep(i,1,n)
                ta=read();
      rep(i,1,m)
                b=read();
      l=1; k=0;
      while(l<n)
                l<<=1,++k;
      per(i,k-1,0) {
                scanf("%s",s+1);
                int len=strlen(s+1);
                op.resize(len+1);
                rep(j,1,len)
                        op=s-48;
      }
      dfs(1,0);
}
void dfs1(int u,int d) {
      if(d==k) {
                f=pos;
                g=pos-1;
                return;
      }
      dfs1(ls(u),d+1);
      dfs1(rs(u),d+1);
      if(!opp) {
                if(a]>=k-d) {
                        f=f;
                        g=g;
                } else {
                        f=f;
                        g=g;
                }
                chkmax(g,g);
      } else {
                if(a]>=k-d) {
                        f=f;
                        g=g;
                } else {
                        f=f;
                        g=g;
                }
                chkmax(g,g);
      }
}
int tc;
ll ans;
void upd(int _l,int _r,int val) {
      chkmin(_r,l);
      if(_l>_r)
                return;
      ans+=val;
      ans-=val;
}
void solve() {
      rep(i,0,3)
                tc=read();
      rep(i,1,n)
                a=ta^tc;
      rep(i,n+1,l)
                a=INF;
      dfs1(1,0);
      rep(i,0,l)
                ans=0;
      rep(i,1,l) {
                int u=t,d=0,val=l;
                // c >= i
                if(i==1)
                        upd(1,1,i);
                while(u!=1) {
                        int v=pa(u);
                        ++d;
                        if(opp==sonid(u)) {
                              if(a<d)
                                        break;
                        } else {
                              if(a]>=d)
                                        chkmin(val,g);
                        }
                        upd(max(i,(1<<(d-1))+1),min(val,1<<d),i);
                        u=v;
                }
                // c < i
                u=t; d=0; val=l;
                while(u!=1) {
                        int v=pa(u);
                        ++d;
                        if(opp!=sonid(u)) {
                              if(a]>=d)
                                        chkmin(val,g);
                        }
                        if(i<=(1<<d)) {
                              upd((1<<(d-1))+1,min(val,i-1),i);
                              break;
                        }
                        u=v;
                }
      }
      rep(i,1,l)
                ans+=ans;
      ll res=0;
      rep(i,1,m)
                res^=i*ans];
      printf("%lld\n",res);
}
int main() {
//      freopen("arena.in","r",stdin);
//    freopen("arena.out","w",stdout);
      init();
    int testcase=read();
    while(testcase--)
      solve();
    return 0;
}

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

最后祝各位rp++,Noip见

苏紫方璇 发表于 2024-11-3 23:43

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

Randle 发表于 2024-11-4 17:07

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

谢谢谢谢!!

StarMax 发表于 2024-11-6 01:42

Thanks1!
页: [1]
查看完整版本: 2024中国计算机学会CSP-S认证提高组第二轮解析