CSP-S 2020游记
NXYorz
2020-11-08 15:21:36
### $Day\ 0$
早晨起晚了$qwq$，不过应该没有太大关系吧毕竟没有人查。穿好衣服之后强忍想要出门的欲望站在屋子里想是否忘了什么事情，没有想起来就出门了，到了机房，高二的被教导员喊走了，就剩下我一个人。过了一会，$zzh$进门的一瞬间，我就想起来忘了给我妈说发健康码的事情了。等到$zp$一来，我就去给我妈打电话了$emmm$。
$9:00$准时出发，和$zhs$坐在了一起$qwq$，有一点晕车，所以大部分时间不是吃就是睡，$zp$说$5h$就可以到日照了，结果到了下午$5:00$才刚进酒店(由于疫情的原因，宿舍不让用了$emmm$，只好集体住酒店喽$qwq$，$zp$和$yp$去找了大约$15min$才回来，他们说是新开的，还没有挂牌，~~淦！~~ 当时我脑海里浮现出来的画面只有那种路边开的，环境卫生很差的偏远小宾馆，结果我被狠狠的打脸了，~~好爽。~~ 酒店非常棒！学$OI$的两年以来，第一次住这么好的宾馆，让我不禁怀疑这到底是不是$140$一晚上的两人标准间：
房间在顶楼， ~~刚开始觉得很安静~~ 一进门，巨大的落地窗映入眼帘(夜景一定超级棒)，落地窗旁边有一个长长的小沙发，感觉也很棒，沙发旁有一台电脑桌(不过没有电脑)，还有一把看上去不怎么专业的电竞椅?桌子上有插头和花，还有一个神秘的需要扫码的~~小~~盒子。里面装了什么？我不知道，隐约看到了$DLS$，~~咱也不知道，咱也不敢问。~~ 卫生间很干净。
收拾完，$zp$把我们叫过去了，他就在$715$，我在$727$，我们对面。说了一些注意事项。$yp$突然说电视别看太晚，结果$zp$直接说不准看电视，$9:30$睡觉，明天$8:00$起床。
回到房间，发现还有抽烟机和洗衣机？！$zhs$趴在窗户旁边不知道在看些什么，只听见他说:
>唔！看对面有一个小女孩在跳舞!
>
>跳得不错！
>
>她在对着镜子自己跳。
>
>不对，她妈妈在教她。
>
>此女必成大器
>
>跳的不错qwq
过了一会,$zy$来了，臭小子竟然想霸弓硬上王？$zy$说:"插头里面可能有摄像头啊！"把正在从壁画里找摄像头的$zhs$说了一愣(细思极恐)，他是怎么知道的，~~咱也不知道，咱也不敢问~~。
快睡觉的时候，和$zhs$下了几盘五子棋，~~好玩~~。
还是很紧张，复习去了。
### $Day\ 1$
下午要考试了，紧张...心里一直默默回顾自己的作战计划:
>2:30~2:50读题
>
>2:50~4:00打暴力
>
>4:00~6:20优化暴力
>
>6:20~6:30检查
醒来去洗漱，没想到水龙头是有热水的，满足$qwq$，昨天晚上睡得不太好，醒了好几次。$8:10$的时候，$zp$喊我们吃饭，腿有点酸$emmm$昨晚和$zhs$聊了好久，没想到这个家伙睡觉打呼噜。
吃完饭，$zp$说不能睡觉现在，等吃完午饭再睡，昏昏欲睡的我只好去看书，发现了很多以前忽视但实质上是最重要的东西——思维。书里会给你提供一些做题的思路，但以前急功近利的我却忽视了这些东西，现在说什么都已经晚了。
他们几个说宾馆隔音效果不太好，可以听到奇怪的声音，具体是什么，~~咱也不知道，咱也不敢问~~。
吃完饭，应该去睡一会了，还是很紧张...
呼,考完了，崩了，$T1$是一个模拟，赶紧打完暴力，好像会超时，不过没管，按照计划先把暴力打完再去优化，$T2$先写了暴力，$T3$发现是一个$DAG$，想跑拓扑排序，但是优先级的问题貌似有些难处理，于是先打了暴力。$T4$看着像博弈论，果断放弃，回去调$T1$,$T2$了。当时已经$4:30$了，发现$T1$可以分段讨论，讨论完之后稀里糊涂的过了大样例，~~大样例真水啊~~。事后发现好多边界没有判，甚至把十月当成了三十天来算都没出错。$T1$对拍上来就已经$5:30$了，接着看$T2$，发现可以按位讨论，每一位只有$2$或者$1$两种情况，容斥一下过了大样例。对拍时出了一点锅，发现暴力数组开小了，处理完已经$6:20$了。~~事后发现数组$a_i$忘了开```ull```，含泪60$points$~~，不甘心啊！但转念一想，如果交暴力，也许$20points$也没有，心里就好受了很多了。
剩下$10min$去检查文件名了。
晚上出来之后，发现大家都崩了，心里就不是那么难受了，回酒店的路上，发现了找了好久的万达广场，原来它在东面，于是就决定去那里吃饭，在四楼吃了自助餐，$axy$说这是提前欢迎我们回归文化课，欠揍。终于吃完了之后，在下楼的路上发现了电玩城，$zy$，$sjy$等人像饿狼一般扑了上去，我本不想去，可$zhs$说要不要...给她抓一个娃娃？于是立马就把我说服了，一共买了$80RMB$的游戏币,结果...铩羽而归，很遗憾。从万达出来时，已经快$10:00$了，于是八个人向疯子一样狂奔。突然$szz$大吽了一声，所有人都笑了。$wqy$说了一句什么，我没听清，$zzh$开始狂笑。
也许，这才是学$OI$该有的样子叭。
### $Day\ 2$
老实点，回家了。
依稀记得昨晚和$zhs$玩了三局旗，很开心。然后看黑豹，由于我看过所以看了一半睡着了，$zhs$说他看完了，~~(漫威真香)~~
晚上快吃饭的时候，源代码下来了，从洛谷民间数据测了一下:$90+65+25+5=185$。$T1$忘了开$ll$了啊含泪$90pts$，$T2$果不其然爆炸了。$T3$按照$20pts$打的没想到多过了一个点...挂了$45pts$，感觉很难受。
牛客:$90+95+25+0=210$，貌似没卡我？
-----
### $For\ a\ long\ time$
官方成绩:$90+60+25+0=175$,$SD\ rk81$
屑代码：
$T1$
```cpp
#include<cstdio>
using namespace std;
const int d1 = 365;//平年
const int d2 = 366;//闰年
const int T = 1461;
int q;
bool v[13];
bool pd(int x)
{
if(x <= 1582)
{
if(x > 0 && x % 4 == 0)
return true;
if(x < 0 && (x + 1) % 4 == 0)
return true;
}
if(x > 1582 && ((x % 400 == 0) || (x % 4 == 0 && x % 100 != 0))) return true;
return false;
}
void cl(int ri , int &month , int &day , int &year)
{
for(year;;)
{
if(year == 0) year++;
if(pd(year))
{
if(ri >= d2) ri -= d2 , year++;
else break;
}
else
{
if(year != 1582)
{
if(ri >= d1) ri -= d1 , year++;
else break;
}
else
{
if(ri >= d1 - 10) ri -= d1 - 10 , year++;
else break;
}
}
if(ri == 0) break;
}
if(year == 0) year++;
for(month;;)
{
if(month == 2)
{
if(pd(year))
{
if(ri >= 29) ri -= 29 , month++;
else break;
}
else
{
if(ri >= 28) ri -= 28 , month++;
else break;
}
}
else
{
if(v[month])
{
if(ri >= 30) ri -= 30 , month++;
else break;
}
else
{
if(year != 1582 || month != 10)
{
if(ri >= 31) ri -= 31 , month++;
else break;
}
else
{
if(ri >= 21) ri -= 21 , month++;
else break;
}
}
}
if(ri == 0) break;
}
if(year == 1582 && month == 10 && ri >= 4)
day = ri + 11;
else day = ri + 1;
}
void work()
{
int ri; scanf("%d",&ri);
if(ri <= 1721424) //[-4713 , -1]
{
int year = -4713 , day = 1 , month = 1;
int k = ri / T , r = ri % T;
year += k * 4;
cl(r , month , day , year);
if(year == 0) year++;
if(year < 0) printf("%d %d %d BC\n",day , month , -year);
else printf("%d %d %d\n",day , month , year);
}
else
{
ri -= 1721424;
if(ri < 577095)//[1 , 1580]
{
int year = 1 , day = 1 , month = 1;
int k = ri / T , r = ri % T;
year += k * 4;
cl(r , month , day , year);
if(year < 0) printf("%d %d %d BC\n",day , month , -year);
else printf("%d %d %d\n",day , month , year);
}
else
{
ri -= 577095;
if(ri <= 365 * 2 - 10)
{
int year = 1581 , day = 1 , month = 1;
cl(ri , month , day , year);
if(year < 0) printf("%d %d %d BC\n",day , month , -year);
else printf("%d %d %d\n",day , month , year);
}
else
{
int year = 1583 , day = 1 , month = 1;
ri -= 365 * 2 - 10;
int k = ri / 146097 , r = ri % 146097;
year += k * 400;
cl(r , month , day , year);
if(year < 0) printf("%d %d %d BC\n",day , month , -year);
else printf("%d %d %d\n",day , month , year);
}
}
}
}
int main()
{
freopen("julian.in","r",stdin);
freopen("julian.out","w",stdout);
v[4] = v[6] = v[9] = v[11] = 1;
scanf("%d",&q);
while(q--)
work();
return 0;
}
```
$T2$
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 1e6 + 1;
const int M = 1e8 + 1;
const int Bit = 64;
int n,m,c,k;
unsigned long long ans = 1;
int a[N];
bool v[Bit],b[Bit];
void cl(int x)
{
int bit = 0;
while(x)
{
if((x & 1) && b[bit])
v[bit] = 1;
x >>= 1;bit++;
}
}
int main()
{
freopen("zoo.in","r",stdin);
freopen("zoo.out","w",stdout);
scanf("%d %d %d %d",&n,&m,&c,&k);
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
for(int i = 1; i <= m; i++)
{
int pi,qi; scanf("%d%d",&pi,&qi);
b[pi] = 1;
}
for(int i = 1; i <= n; i++)
cl(a[i]);
for(int i = 0; i < k; i++)
{
if(!v[i] && b[i]) ans *= 1;
else ans *= 2;
}
cout<<ans - n;return 0;
}
```
$T3$
```cpp
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 2e4 + 10;
const int mod = 998244353;
ll cj = 1;
int n,m,q,sum;
int first[N];
ll a[N];
struct E
{
int next;
int to;
void add(int x , int y)
{
next = first[x];
to = y;
first[x] = sum;
}
}e[N];
struct NO
{
int ti;
int p,v;
}Node[N];
struct Sig
{
int l;
int r;
int w;
int lazy;
};
void dfs(int x)
{
if(Node[x].ti == 1 || Node[x].ti == 2)
{
if(Node[x].ti == 1)
{
for(int i = 1; i <= n; i++)
a[i] = (a[i] * cj) % mod;
a[Node[x].p] += Node[x].v; a[Node[x].p] %= mod;
cj = 1;
}
else cj = (cj * Node[x].v) % mod;
}
else
{
int b[N];b[0] = 0;
for(int i = first[x]; i ; i = e[i].next)
{
int to = e[i].to;
b[++b[0]] = to;
}
for(int i = b[0]; i >= 1; i--)
dfs(b[i]);
}
}
int main()
{
freopen("call.in","r",stdin);
freopen("call.out","w",stdout);
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%lld",&a[i]);
scanf("%d",&m);
for(int i = 1; i <= m; i++)
{
int op,pi,vi,ci; scanf("%d",&op);
switch(op)
{
case 1:
scanf("%d%d",&pi,&vi);
Node[i] = (NO){op,pi,vi};
break;
case 2:
scanf("%d",&vi);
Node[i] = (NO){op,0,vi};
break;
case 3:
scanf("%d",&ci);
for(int j = 1; j <= ci; j++)
{
int ui; scanf("%d",&ui);
e[++sum].add(i , ui);
}
Node[i] = (NO){op,0,0};
break;
break;
}
}
scanf("%d",&q);
for(int i = 1; i <= q; i++)
{
int fi; scanf("%d",&fi);
dfs(fi);
}
for(int i = 1; i <= n; i++)
a[i] = (a[i] * cj) % mod;
for(int i = 1; i <= n; i++)
printf("%lld ",a[i]);
return 0;
}
```
经过小修小补，很快就把$T1,T2$的锅修好了emmmm。
现在终于把$T3$调过了。
修改之后的代码：
$T1$
```cpp
#include<cstdio>
using namespace std;
const int d1 = 365;//平年
const int d2 = 366;//闰年
const int T = 1461;
int q;
bool v[13];
bool pd(int x)
{
if(x <= 1582)
{
if(x > 0 && x % 4 == 0)
return true;
if(x < 0 && (x + 1) % 4 == 0)
return true;
}
if(x > 1582 && ((x % 400 == 0) || (x % 4 == 0 && x % 100 != 0))) return true;
return false;
}
void cl(int ri , int &month , int &day , int &year)
{
for(year;;)
{
if(year == 0) year++;
if(pd(year))
{
if(ri >= d2) ri -= d2 , year++;
else break;
}
else
{
if(year != 1582)
{
if(ri >= d1) ri -= d1 , year++;
else break;
}
else
{
if(ri >= d1 - 10) ri -= d1 - 10 , year++;
else break;
}
}
if(ri == 0) break;
}
if(year == 0) year++;
for(month;;)
{
if(month == 2)
{
if(pd(year))
{
if(ri >= 29) ri -= 29 , month++;
else break;
}
else
{
if(ri >= 28) ri -= 28 , month++;
else break;
}
}
else
{
if(v[month])
{
if(ri >= 30) ri -= 30 , month++;
else break;
}
else
{
if(year != 1582 || month != 10)
{
if(ri >= 31) ri -= 31 , month++;
else break;
}
else
{
if(ri >= 21) ri -= 21 , month++;
else break;
}
}
}
if(ri == 0) break;
}
if(year == 1582 && month == 10 && ri >= 4)
day = ri + 11;
else day = ri + 1;
}
void work()
{
long long ri; scanf("%lld",&ri);
if(ri <= 1721424) //[-4713 , -1]
{
int year = -4713 , day = 1 , month = 1;
int k = ri / T , r = ri % T;
year += k * 4;
cl(r , month , day , year);
if(year == 0) year++;
if(year < 0) printf("%d %d %d BC\n",day , month , -year);
else printf("%d %d %d\n",day , month , year);
}
else
{
ri -= 1721424;
if(ri < 577095)//[1 , 1580]
{
int year = 1 , day = 1 , month = 1;
int k = ri / T , r = ri % T;
year += k * 4;
cl(r , month , day , year);
if(year < 0) printf("%d %d %d BC\n",day , month , -year);
else printf("%d %d %d\n",day , month , year);
}
else
{
ri -= 577095;
if(ri <= 365 * 2 - 10)
{
int year = 1581 , day = 1 , month = 1;
cl(ri , month , day , year);
if(year < 0) printf("%d %d %d BC\n",day , month , -year);
else printf("%d %d %d\n",day , month , year);
}
else
{
int year = 1583 , day = 1 , month = 1;
ri -= 365 * 2 - 10;
int k = ri / 146097 , r = ri % 146097;
year += k * 400;
cl(r , month , day , year);
if(year < 0) printf("%d %d %d BC\n",day , month , -year);
else printf("%d %d %d\n",day , month , year);
}
}
}
}
int main()
{
// freopen("julian.in","r",stdin);
// freopen("julian.out","w",stdout);
v[4] = v[6] = v[9] = v[11] = 1;
scanf("%d",&q);
while(q--)
work();
return 0;
}
```
$T2$
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int Bit = 101;
const unsigned long long inf = 18446744073709551615;
int n,m,c,k;
unsigned long long a[N];
ll ans = 1;
bool v[Bit] , b[Bit] ,flag;
void cl(unsigned long long x)
{
int bit = 0;
while(x)
{
if(x & 1) v[bit] = 1;
x >>= 1; bit++;
}
}
int main()
{
// freopen("aa.in","r",stdin);
scanf("%d %d %d %d",&n,&m,&c,&k);
for(int i = 1; i <= n; i++)
cin>>a[i];
for(int i = 1; i <= m; i++)
{
int pi,qi; scanf("%d %d",&pi,&qi);
b[pi] = 1;
}
for(int i = 1; i <= n; i++)
cl(a[i]);
for(int i = 0; i < k; i++)
if(!v[i] && b[i]) ans *= 1 ,flag = 1;
else ans *= 2;
if(!flag && k == 64)
{
if(n == 0)
printf("18446744073709551616");
else cout<<inf - n + 1;
}
else cout<<ans - n;
return 0;
}
```
$T3$
```cpp
#include<cstdio>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 998244353;
typedef long long ll;
int n,m,q,sum;
int f[M],first[M],inn[M];
ll a[N],mult,_mult[N],Add[N];
bool v[N];
struct NO
{
int ty;
int p;
int v;
ll mul;
ll w;
}Node[M];
struct E
{
int next;
int to;
void add(int x , int y)
{
next = first[x];
to = y;
first[x] = sum;
}
}e[M * 2];
struct queue
{
int head,tail;
int a[M];
void clear()
{head = tail = 0;}
void push(int x)
{a[tail++] = x;}
void pop()
{head++;}
int front()
{return a[head];}
bool empty()
{return head == tail ? true : false;}
}qu;
void in(int &x)
{
x = 0; char ee = getchar();
while(ee < '0' || ee > '9') ee = getchar();
while(ee >= '0' && ee <= '9') x = (x << 1) + (x << 3) + ee - '0' , ee = getchar();
}
void dfs(int x)
{
if(Node[x].ty == 1 || Node[x].ty == 2)
{
if(Node[x].ty == 2)
_mult[x] = Node[x].v;
return;
}
for(int i = first[x]; i ; i = e[i].next)
{
int to = e[i].to;
if(!v[to]) dfs(to) , v[to] = 1;
_mult[x] *= _mult[to] , _mult[x] %= mod;
}
}
void topo_sort()
{
for(int i = 1; i <= m; i++)
if(!inn[i]) qu.push(i);
while(!qu.empty())
{
int now = qu.front(); qu.pop();
if(Node[now].ty == 1) Add[Node[now].p] += Node[now].v * Node[now].w , Add[Node[now].p] %= mod;
ll k = Node[now].w;
for(int i = first[now]; i ; i = e[i].next)
{
int to = e[i].to;
inn[to]--; if(!inn[to]) qu.push(to);
Node[to].w += k , Node[to].w %= mod;
k *= _mult[to] , k %= mod;
}
}
}
int main()
{
// freopen("aa.in","r",stdin);
// freopen("aa.out","w",stdout);
in(n);
for(int i = 1; i <= n; i++) scanf("%lld",&a[i]);
in(m);
for(int i = 1; i <=m; i++)
{
int tye; in(tye); _mult[i] = 1;
switch(tye)
{
int pi , vi , ci;
pi = 0 , vi = 0 , ci = 0;
case 1:
in(pi);in(vi);
Node[i] = (NO){tye,pi,vi,1,0};
break;
case 2:
in(vi);
Node[i] = (NO){tye,pi,vi,1,0};
break;
case 3:
in(ci);
for(int j = 1; j <= ci; j++)
{
int gi; in(gi);
inn[gi]++;
Node[i] = (NO){tye,pi,vi,1,0};
e[++sum].add(i , gi);
}
break;
break;
}
}
in(q);mult = 1;
for(int i = 1; i <= q; i++)
in(f[i]);
for(int i = 1; i <= m; i++)
if(!inn[i]) dfs(i);
for(int i = q; i >= 1; i--)
{
int id = f[i];
if(Node[id].ty == 1) Node[id].w += mult;
else if(Node[id].ty == 2) mult *= _mult[id] , mult %= mod;
else Node[id].w += mult , mult *= _mult[id] , mult %= mod;
}
topo_sort();
for(int i = 1; i <= n; i++)
printf("%lld ",((a[i] * mult) % mod + Add[i] % mod) % mod);
return 0;
}
```
---------
吐槽：$T1$卡```int```,$T2$卡```ull```，不愧是你。$CCF$。