依旧是好一场烂一场.
依旧是那么菜.
依旧是难止颓废.
依旧是在此方仰望, 幻想?
上面这段中二的东西是为了防止 Parisb 说我的标题与内容无关而 diss 我莫名其妙 115 的语文.
但是菜是的确是菜...
这次没改题就来写博是因为考场心态稍炸, 想稍微写一下.
考前日常毒奶:
我看了下总刷题排行榜, Dybala699,Mr_zkt598.
我想让他们凑个整, 我就说 zkt 要 A2 个, Dybala 要 A1 个.
然后两个都说中了... 我并不知道这次 T2 可以那样 AC.
然后我就被 Dybala 良心谴责了 (他 T2 小问题打飞了本来能 AC 的) 啊啊啊我没脸我错了
然而反正我自己也就 A 了一个...
回归正题:
上来看题, 都不会.
然后 T1 可以打表找规律, 26 分钟搞定, 高精数组开的 20,WA60.
然后看 T2, 不会, 看了一个小时, 不会, 去厕所, 听 Parisb 说 Dybala 切题好快, 心态稍炸.
突然发现自己电脑底下的有 3 盒空的百醇, 以及一大堆零食袋子, 心烦.
又怕自己被冤枉于是这次考试很短时间就去了 3 次厕所, 每次都用演算纸包着零食的盒子怕被其他老师看见.
往厕所运了 3 次之后总算清干净了, 舒坦一些, 然后关上柜子, 忽然又一盒空百醇掉到了我的脚上.
后来又运了一趟...
另外我这一个小时没碰鼠标键盘, 而 Yu-shi 在我旁边一直码一直码码了一个半小时... 心态更崩了.
打了半个正解, TLE40.
然后这边的人开始问 T3 的样例的时, 坐在角落听不清他们在说什么, 只听到 T3balabalaT3balabala
意思就是他们都进 T3 了, 我 T2 动还没动呢
心理压力更大了.
然后又看了一个小时, 想到了题解里的那个正解 (不是 bitset) 但不会证明, 把 int 数组写成 char 数组, RE30.
其实复杂度算错了, 一看 n3 会死就又没想 bitset. 一直在想 n2.
然后自己不会证也没什么想法, 进 T3, 样例锅了, 发大样例.
大样例暴力跑不出来, 小样例暴力输出不对.
这是考场心态.
然后 T3 乱打暴力就扔了, 过会 T1 发现数组锅了, 改正. 结束.
算复杂度时要考虑 bitset 的 1/32 的常数.
稳住心态! 稳住心态! 稳住心态! 尽量不要受周围人的干扰.
按照自己的步调来, 不管什么分数都是自己考的, 没有人为你负责.
抗干扰能力还是要练, 至少现在不会被 LNC*** 键盘而干扰过甚.(虽然能听出来他要 AK 了)
但是问题还是很多. 环境的改变不是理由因为你的确不能改变 csp 的考场...
啊... 收到一个信息奥赛三调进步奖, 真是讽刺.
从好变菜再变得稍微不那么菜就能拿进步奖...
算了吧.
稳住心态.
加油吧...
T1: 棋盘
打表找到的式子, 还不会证:
f[i]=f[i-1]*i+(-1)i
- #include<cstdio>
- struct bigint{
- int ws,a[10000];
- void operator++(){
- a[1]++;
- for(int i=1;a[i]>=10000;++i)a[i]-=10000,a[i+1]++;
- if(a[ws+1])ws++;
- }
- void operator--(){
- a[1]--;
- for(int i=1;a[i]<0;++i)a[i]+=10000,a[i+1]--;
- if(!a[ws])ws--;
- }
- void operator*=(int k){
- for(int i=1;i<=ws;++i)a[i]*=k;
- for(int i=1;i<=ws;++i)a[i+1]+=a[i]/10000,a[i]%=10000;
- if(a[ws+1])ws++;
- }
- void print(){
- printf("%d",a[ws]);
- for(int i=ws-1;i;--i)printf("%04d",a[i]);
- puts("");
- }
- }ans;
- int main(){
- int n;scanf("%d",&n);
- if(n==1){puts("0");return 0;}
- for(int i=2;i<=n;++i){
- ans*=i;
- if(i&1)--ans;
- else ++ans;
- }
- ans.print();
- }
- View Code
T2: 传递
用 bitset 的做法我就不说了. 虽然我考场上没想到.
题解的结论仅在竞赛图下成立:
考虑两个点 u,v.
如果 P 中存在路径由 u 到 v, 那么就必须有一条 P 边由 u 到 v
1)如果同时 Q 中存在路径由 v 到 u, 那么就必须有一条 Q 边由 v 到 u, 与上面矛盾.
此时 PQ 的边都建出来的话会形成经过 uv 的环.
2)如果同时 Q 中存在路径由 u 到 v, 那么就必须有一条 Q 便又 u 到 v, 与上面矛盾
此时 P 与 Q 的反边都建出来的话也会形成经过 uv 的环.
所以只要把 P 所有边建出来, Q 边正着建后判个环, Q 边反着建后再判个环, 就好了.
拓扑. 数组不要开成 char.
因为是竞赛图, 所以每两个点之间都有一条单向边, 所以上述判断条件就是充分必要条件了.
- #include<cstdio>
- int n,deg[2019],q[2019];char m[2019][2019];
- int main(){
- int t;scanf("%d",&t);
- while(t--){
- scanf("%d",&n);char T=1;
- for(int i=1;i<=n;++i)scanf("%s",m[i]+1);
- for(int i=1;i<=n;++i)deg[i]=0;
- for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(m[i][j]!='-')deg[i]++;
- int t=0;
- for(int i=1;i<=n;++i)if(!deg[i])q[++t]=i;
- for(int h=1;h<=t;++h)for(int i=1;i<=n;++i)if(m[i][q[h]]!='-'){
- deg[i]--;
- if(!deg[i])q[++t]=i;
- }
- if(t!=n){T=0;goto output;}
- for(int i=1;i<=n;++i)deg[i]=0;t=0;
- for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
- if(m[i][j]=='P')deg[i]++;
- else if(m[i][j]=='Q')deg[j]++;
- //for(int i=1;i<=n;++i)printf("%d",deg[i]);
- for(int i=1;i<=n;++i)if(!deg[i])q[++t]=i;
- for(int h=1;h<=t;++h)for(int i=1;i<=n;++i)if(m[i][q[h]]=='P'||m[q[h]][i]=='Q'){
- deg[i]--;//printf("%d->%d\n",q[h],i);
- if(!deg[i])q[++t]=i;
- }
- if(t!=n)T=0;
- output:puts(T?"T":"N");
- }
- }
- View Code
T3: 异或
不会. 注意 d 要小于 min(ai)而不是小于等于.
[考试反思]1010csp-s 模拟测试 66: 依旧
来源: http://www.bubuko.com/infodetail-3232637.html