CSP-S2020题目整理
T1 儒略日
这道题目在考场上卡爆我
然后我就废了
这道题实际上就是考察一个对于闰年和平年的研究
我们可以先预处理前四百年的情况，然后对于在1582年之前的和1582年之后的分类讨论一下，然后这样就可以直接加减了
用一个函数来返回月份的天数似乎比较方便
参考代码
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define int long long
using namespace std;
const int maxn=146097;
int q;
int y[maxn],m[maxn],d[maxn];
int r,tmp;
int calc(int year,int month)
{
if(month==2)
{
if(year%4!=0) return 28;
else
{
if(year%100!=0) return 29;
else
{
if(year%400!=0) return 28;
else return 29;
}
}
}
if(month==4||month==6||month==9||month==11)
return 30;
else return 31;
}
signed main()
{
m[0]=d[0]=1;
for(int i=1;i<maxn;i++)
{
d[i]=d[i-1]+1;
m[i]=m[i-1];
y[i]=y[i-1];
if(d[i]>calc(y[i],m[i]))
{
m[i]++,d[i]=1;
}
if(m[i]>12)
{
y[i]++;
m[i]=1;
}
}
cin>>q;
while(q--)
{
cin>>r;
if(r>2299160)
{
r-=2159351;
tmp=r/maxn*400+1200;
r%=maxn;
}
else
{
tmp=r/1461*4-4712;
r%=1461;
}
cout<<d[r]<<" "<<m[r]<<" ";
if(tmp+y[r]>0)
cout<<tmp+y[r];
else
cout<<(1-tmp-y[r])<<" BC";
cout<<'\n';
}
return 0;
}
|
T2 动物园
这道题目我当年在考场看到之后直接就没有去做，没错是的
然后我就光荣爆零了
现在看来，实际上就只是一个位运算的应用，然后题目看起来比较可怕罢了，然后我们的对于这道题
可以用一个数字来记录一下动物的数量，然后需要买的饲料的情况，用二进制就好了
然后我们统计所有的情况，用容斥原理，减去不能怨的动物的数量，剩下的就是还能选的动物的数量啦
注意用一个unsigned long long 和特判
参考代码
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define int unsigned long long
using namespace std;
int n,m,c,k;
int ans,dw,ls;
signed main()
{
cin>>n>>m>>c>>k;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
dw|=x;
}
for(int i=1;i<=m;i++)
{
int p,q;
cin>>p>>q;
ls|=1ull<<p;
}
for(int i=0;i<k;i++)
if(!((ls>>i)&1)||((dw>>i)&1))
ans++;
if(ans==64&&n==0)
cout<<"18446744073709551616"<<'\n';
else
{
if(ans==64)
cout<<-n<<'\n';
else
cout<<(1ull<<ans)-n<<'\n';
}
return 0;
}
|
T3 函数调用
在赛场上我一度认为这道题目是最简单的
但是不是
这道题目看到标签说要用拓扑排序来着
然后拓扑排序一下
实际上对于每个操作进行处理，对于操作2，实际上我们可以看成若干个操作1，然后操作3也可以转化一下，然后我们就可以建一个函数调用关系的有向图，进行拓扑排序，看函数调用的顺序，然后我们对于每一个加法和乘法，看他们对于总的答案的贡献是多少，然后就可做了
参考代码
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int maxn=100005;
const int mod=998244353;
int n,m,q;
int cnt[maxn];
int a[maxn];
int type[maxn],mul[maxn],add[maxn],pos[maxn];
int out1[maxn],out2[maxn];
vector<int> g1[maxn],g2[maxn];
void topo1()
{
queue <int> q;
for(int i=0;i<=m;i++)
{
out1[i]=g2[i].size();
if(out1[i]==0)
q.push(i);
}
while(q.size())
{
int x=q.front();
q.pop();
for(int i=0;i<g1[x].size();i++)
{
int e=g1[x][i];
mul[e]=1ll*mul[e]*mul[x]%mod;
out1[e]--;
if(out1[e]==0)q.push(e);
}
}
}
void topo2()
{
queue <int> q;
for(int i=0;i<=m;i++)
{
out2[i]=g1[i].size();
if(out2[i]==0)
q.push(i);
}
while(q.size())
{
int x=q.front();
int tag=1;
q.pop();
for(int i=g2[x].size();i>0;--i)
{
int e=g2[x][i-1];
cnt[e]=(cnt[e]+1ll*cnt[x]*tag)%mod;
tag=1ll*tag*mul[e]%mod;
out2[e]--;
if(out2[e]==0)
q.push(e);
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>m;
mul[0]=1;
for(int i=1;i<=m;i++)
{
cin>>type[i];
if(type[i]==1)
{
mul[i]=1;
cin>>pos[i]>>add[i];
}
if(type[i]==2)
cin>>mul[i];
if(type[i]==3)
{
mul[i]=1;
int c;
cin>>c;
for(int j=0;j<c;++j)
{
int e;
cin>>e;
g1[e].push_back(i);
g2[i].push_back(e);
}
}
}
cin>>q;
cnt[0]=1;
while(q--)
{
int x;
cin>>x;
g1[x].push_back(0);
g2[0].push_back(x);
}
topo1();
topo2();
for(int i=1;i<=n;i++)
a[i]=1ll*a[i]*mul[0]%mod;
for(int i=1;i<=m;i++)
{
if(type[i]==1)
a[pos[i]]=(a[pos[i]]+1ll*cnt[i]*add[i])%mod;
}
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
|
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=1000005;
const int inf=1e9;
int T,n,a[maxn];
pair <int,int> q1[maxn],q2[maxn];
int l1,r1,l2,r2;
pair <int,int> get_max()
{
if(r1==l1)
return q2[l2++];
else if(r2==l2)
return q1[--r1];
else if(q2[l2]>q1[r1-1])
return q2[l2++];
else return q1[--r1];
}
pair <int,int> get_min()
{
if(l1==r1)
return q2[--r2];
else if(r2==l2)
return q1[l1++];
else if(q2[r2-1]<q1[l1])
return q2[--r2];
else return q1[l1++];
}
pair <int,int> Min(pair <int,int> x,pair <int,int> y)
{
return x<y?x:y;
}
inline void solve()
{
l1=r1=l2=r2=0;
for(int i=1;i<=n;++i)
q1[r1++]=make_pair(a[i],i);
int flag=0,cnt=0,alf=0;
while(1)
{
cnt++;
pair <int,int> x=get_min(),y=get_max();
pair <int,int> z=Min((l1<r1?q1[l1]:make_pair(inf,-inf)),(l2<r2?q2[r2-1]:make_pair(inf,-inf)));
y.first-=x.first;
if(y>z||cnt==n-1)
{
if(flag)
{
cout<<n-(flag-(alf&1))<<'\n';
return ;
}
if(cnt==n-1)
{
cout<<1<<'\n';
return ;
}
q2[r2++]=y;
}
else
{
alf++;
if(!flag)
flag=cnt;
q2[r2++]=y;
}
}
}
int main()
{
cin>>T;
T--;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
solve();
while(T--)
{
int k;
cin>>k;
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
cin>>a[x];
}
solve();
}
return 0;
}
|
