第36次CCF CSP计算机软件能力认证记录
本次应该是我最后一次参加CSP了，明年就毕业了。遗憾的是这次也仅仅只是拿了300分。需要走的路还很远很远。
今天去官网看见能把代码下载下来了，就记录一下。
然而这并不是完整的题解，只是我自身心路历程的记录。如果想看完整的题解的话我推荐这篇博客
第一题
简单模拟签到题。
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
| #include<bits/stdc++.h>
using namespace std;
const int mxlen = 200;
int n,k;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int types(char c){
if(c=='f') return 0;
if(c=='b') return 1;
if(c=='l') return 2;
if(c=='r') return 3;
}
void walk(int startx,int starty,string s){
for(int i=0;i<s.size();i++){
int tempx = startx+dx[types(s[i])];
int tempy = starty+dy[types(s[i])];
if(tempx<=0||tempx>n||tempy<=0||tempy>n) continue;
startx = tempx;
starty = tempy;
}
cout<<startx<<" "<<starty<<endl;
}
void work(){
string temp="";
int x,y;
for(int i=1;i<=k;i++){
cin>>x>>y>>temp;
walk(x,y,temp);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
while(T--){
cin>>n>>k;
work();
}
return 0;
}
|
第二题
没有想出来正解，暴力算出来每个位置b变成0时需要的最少w。看别人的做法应该是用求和公式写不等式然后用前缀和做。出题人的仁慈，暴力有80分。
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
| #include<bits/stdc++.h>
using namespace std;
const int mxlen = 1e5+10;
int n;
int a[mxlen],b[mxlen];
int needE[mxlen];
int work(int x){
int originE = 0;
int temp = 0;
for(int i=0;i<=n;i++){
if(i!=x) temp+=b[i];
temp-=a[i];
if(temp<0) {
originE+=-temp;
temp = 0;
}
}
return originE;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
while(T--){
cin>>n;
for(int i=0;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
cout<<work(i)<<" ";
}
}
return 0;
}
|
第三题
模拟Cache，（学过计组的有福了）。但是最后应该是因为直接用二维数组暴力维护最近使用的内存所以TLE了一个点，只拿了90分。赛后想起来如果用deque声明数组做把排序操作时间复杂度降下来应该就能过了。
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
| #include<bits/stdc++.h>
using namespace std;
const int mxlen = 10000;
int n,N;
struct node{
int id;
bool changed;
};
node v[mxlen][mxlen];
void init(){
for(int i=0;i<N;i++){
for(int j=0;j<n;j++){
v[i][j].id=-1;
}
}
}
void wirte(int id){
cout<<1<<" "<<id<<endl;
}
void read(int id){
cout<<0<<" "<<id<<endl;
}
bool findInCache(int id){
int i=(id/n)%N;
for(int j=0;j<n;j++){
if(v[i][j].id==-1)break;
if(v[i][j].id==id) return true;
}
return false;
}
void loadCache(int id){
int i=(id/n)%N;
node qw;
qw.id = id;qw.changed=0;
bool ok = 0;
for(int j=0;j<n;j++){
if(v[i][j].id==-1){
v[i][j].id=qw.id;
v[i][j].changed = qw.changed;
ok=1;
break;
}
}
if(ok) {read(id);;return;}
if(v[i][n-1].changed) wirte(v[i][n-1].id);
v[i][n-1].id = qw.id;
v[i][n-1].changed = qw.changed;
read(id);
}
void wirteCache(int id){
int i=(id/n)%N;
int pos = 0;
for(int j=0;j<n;j++){
if(v[i][j].id==id){
pos = j;
v[i][j].changed = 1;
break;
}
}
node temp;
temp.id = v[i][pos].id;
temp.changed = v[i][pos].changed;
for(int j=pos;j>0;j--){
v[i][j].id = v[i][j-1].id;
v[i][j].changed = v[i][j-1].changed;
}
v[i][0].id = temp.id;
v[i][0].changed = temp.changed;
}
void readInCache(int id){
int i=(id/n)%N;
int pos = 0;
for(int j=0;j<n;j++){
if(v[i][j].id==id){
pos = j;
break;
}
}
node temp;
temp.id = v[i][pos].id;
temp.changed = v[i][pos].changed;
for(int j=pos;j>0;j--){
v[i][j].id = v[i][j-1].id;
v[i][j].changed = v[i][j-1].changed;
}
v[i][0].id = temp.id;
v[i][0].changed = temp.changed;
}
void work(){
init();
int T;
cin>>T;
while(T--){
int type,a;
cin>>type>>a;
if(type==0){
if(findInCache(a)){
readInCache(a);
continue;
}else {
loadCache(a);
readInCache(a);
}
}else {
if(findInCache(a)){
wirteCache(a);
}else {
loadCache(a);
wirteCache(a);
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
while(T--){
cin>>n>>N;
work();
}
return 0;
}
|
第四题
这道题更是没有思路。正解应该是DP。赛场上只想到了把所有能到的点用边长为1的边连接，然后dijkstra求最短路，只拿了30分。
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
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxlen = 2e6+10;
int n;
int a[mxlen],k[mxlen];
struct Edge{
ll v,w,next;
}G[mxlen];
ll head[mxlen],cnt;
void add(ll u,ll v,ll w){
cnt++;
G[cnt].w=w;
G[cnt].v=v;
G[cnt].next = head[u];
head[u] = cnt;
}
struct node {
ll d,u;
bool operator<(const node& t)const {
return d>t.d;
}
};
ll dis[mxlen];
void work(){
memset(dis,0x3f,sizeof(dis));
dis[1] = 0;
priority_queue<node> q;
q.push((node){0,1});
while(!q.empty()){
node temp = q.top();
q.pop();
ll u =temp.u;
ll d = temp.d;
if(d!=dis[u]) continue;
for(int i=head[u];i;i=G[i].next){
ll v=G[i].v,w=G[i].w;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
q.push((node){dis[v],v});
}
}
}
if(dis[n]==dis[0]) printf("-1");
else printf("%d",dis[n]);
}
int main(){
int T=1;
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&k[i]);
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=min(n,i+k[i]);j++){
add(i,j-a[j],1);
}
}
work();
}
return 0;
}
|
总结
最后时间不够了，也没有时间去分析最后一题了，看了一眼根本没看懂呜呜呜。
