首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 茶余饭后
    3. 发新帖
[原创]CSP-S
发表于: 3天前 398

[原创]CSP-S

屑云 活跃值
3天前
398

2024的CSP-S刚刚落幕
个人觉得这次主办方出题很有区分度，甚至有出题人可以猜到做题人心思的感觉
本贴是鄙人的代码和思路讲解，有什么问题欢迎各位指出
T1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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[i][1][0] = max(dp[i][1][0], dp[i - 1][j][1] + (a[i] == a[i - j - 1] ? a[i] : 0));
dp[i][1][1] = max(dp[i][1][1], dp[i - 1][j][0] + (a[i] == a[i - j - 1] ? a[i] : 0));
dp[i][j][0] = dp[i - 1][j - 1][0] + (a[i] == a[i - 1] ? a[i] : 0);
dp[i][j][1] = dp[i - 1][j - 1][1] + (a[i] == a[i - 1] ? a[i] : 0);
我们最优策略是隔一个选一个，比如5252
我们可以把5都染红2都染蓝，最大权就是7
分析左右染色块推状态转移方程，有数位DP和插头DP的味道
有的同学场下跟我说红黑树后缝个普通DP，维护平衡代码我就不放了，同学们可以自己试试

T4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#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=p[d];
                return;
        }
        opp=op[d][p[d]];
        dfs(ls(u),d+1);
        dfs(rs(u),d+1);
}
char s[N];
void init() {
        n=read();
        m=read();
        rep(i,1,n)
                ta[i]=read();
        rep(i,1,m)
                b[i]=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[i].resize(len+1);
                rep(j,1,len)
                        op[i][j]=s[j]-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[f[ls(u)]]>=k-d) {
                        f=f[ls(u)];
                        g=g[ls(u)];
                } else {
                        f=f[rs(u)];
                        g=g[rs(u)];
                }
                chkmax(g,g[ls(u)]);
        } else {
                if(a[f[rs(u)]]>=k-d) {
                        f=f[rs(u)];
                        g=g[rs(u)];
                } else {
                        f=f[ls(u)];
                        g=g[ls(u)];
                }
                chkmax(g,g[rs(u)]);
        }
}
int tc[4];
ll ans[N];
void upd(int _l,int _r,int val) {
        chkmin(_r,l);
        if(_l>_r)
                return;
        ans[_l]+=val;
        ans[_r+1]-=val;
}
void solve() {
        rep(i,0,3)
                tc[i]=read();
        rep(i,1,n)
                a[i]=ta[i]^tc[i%4];
        rep(i,n+1,l)
                a[i]=INF;
        dfs1(1,0);
        rep(i,0,l)
                ans[i]=0;
        rep(i,1,l) {
                int u=t[i],d=0,val=l;
                // c >= i
                if(i==1)
                        upd(1,1,i);
                while(u!=1) {
                        int v=pa(u);
                        ++d;
                        if(opp[v]==sonid(u)) {
                                if(a[i]<d)
                                        break;
                        } else {
                                if(a[f[bro(u)]]>=d)
                                        chkmin(val,g[bro(u)]);
                        }
                        upd(max(i,(1<<(d-1))+1),min(val,1<<d),i);
                        u=v;
                }
                // c < i
                u=t[i]; d=0; val=l;
                while(u!=1) {
                        int v=pa(u);
                        ++d;
                        if(opp[v]!=sonid(u)) {
                                if(a[f[bro(u)]]>=d)
                                        chkmin(val,g[bro(u)]);
                        }
                        if(i<=(1<<d)) {
                                upd((1<<(d-1))+1,min(val,i-1),i);
                                break;
                        }
                        u=v;
                }
        }
        rep(i,1,l)
                ans[i]+=ans[i-1];
        ll res=0;
        rep(i,1,m)
                res^=i*ans[b[i]];
        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见

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！

收藏
免费 ・0
支持
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//