"NOIP"算是“恢复”了，在CSP-S大概一个月后，NOIP 2020在12月5日（星期六），也终于迎来了。
刚好学校的段二在周三、四、五，时间上几乎是挤在了一起。最后一个周五的时候，从下午放学到晚上晚修结束回到宿舍，一直在纠结——考虑该把重心放在哪个上面。然后反复纠结，一开始想着还是段考吧（NOIP算个*），中午打电话给父母，他们也这么想，结果到了晚上，他们又觉得NOIP更重要……
当时有种在十字路口做生死选择似的感觉，纠结、迷茫、又害怕。现在回想起来，那个选择其实也没有这么重要。
那晚霞超好看！！
那个周末选择了在学校留宿（因为是段考前一周周末），其实也就是周六中午之后到周日下午，时间并不是多。
我似乎把它们都看得太重了，换上以月或者是季度为单位的广角镜头，段考和NOIP，也不过只是件事罢了。别让自己把这些事情看得太重啊。
另外还要做核酸检测，CCF要求7天之内的核酸检测报告阴性证明。趁着周一下午的体育/自习/自习/自习的迷之课表，就去了趟医院，感觉挺快的，取样的时候我都没反应过来就已经搞定了。
做完之后顺便回了趟家。也就两周（一周半？）没回家，进到自己房间看到床上整齐的被铺莫名有些想念、有些伤感。
回到家里趁着WIFI把《使徒行者3》的一些幕后花絮也缓存了，哦对了，《使徒行者3》的大结局是在那个留宿的周六晚上在寒风中看完的……有些急促，却又有些突然，就这样结束了，还来不及细细回味。
段考申请了延考，心情挺复杂的。看着全班人都在对着桌面上的一本又一本的书复习，自己走向电脑室。其实也还好，不过回到宿舍，就……心态完全都不一样，舍友还高低给你整两句。当然还有晚上兴奋地回到宿舍讲今天的段考题怎么样怎么样，数学哪里又炸了……
那几天就在一套又一套的套题、题解中度过了，中间还有高一、高三的学生来上课，反复被打断思路。在这种奇怪的感觉中，就这样，三天过去了。
周五下午匆匆忙忙的回到班里，上了一节申子靖的班会课，很有感觉。后来他说，在我们班上效果不如在实验班的时候好，其中他讲了“考上一所好大学——以北大为例”，我想，可能是对于他们来说，梦想就在眼前不远的地方；而对于大多数的我们而言，那个梦想还要努力奔跑，才能看得见希望。
周五晚上在电脑室待了一会儿就走了，有点无所适从的感觉。打开C++ STL文档，基本会用的都会了，打开隔壁电脑的Windows 7下的DEV C++，突然感觉也没啥好打的。大概8点就回家了，考前一定要念一遍的《考前叮嘱》也没听（刚好在临走之前，有点尴尬），念来念去都是那样，没啥必要又浪费时间，自己看（理一遍坑）一遍还更快。
回到家中，准备完东西躺在床上已经是21:30了。
学校要求是6:20到学校南区集中，从家里出发，至少也得5:30起床。尽管第二天要这么早起床，但想到明天的比赛，心情还是难以平复，甚至是有些亢奋。
十点半多才入睡。
5：30
醒来的时候没有太多感觉，机械似的穿衣服、刷牙、洗脸……很冷，直到坐到车上去学校的时候，感觉整个人还是冰凉的，手超级冰。
握着热的咖啡和鸡肉卷（香肠鸡蛋卷？，麦当劳），感觉才好了些。凌晨的麦当劳其实也还是有人的。
到学校门口，一下车，迎面刮过来的寒风，刮得我的手生疼。
在保安那里登记的时候，发现飞哥的名字就在我下一个，只差了1分钟离校。
早上真的好冷好冷。
广州感觉其实也不是很远，路上迷迷糊糊地带着耳机睡了近一个小时就差不多到了。
正文
早上感觉手真的很凉，看上去都是苍白的，加上洗个手简直是雪上加霜。进了考场我不停地搓手，希望能好些。
这次的解压密码终于是有点规律的了。
T1
看了一遍题感觉能做，细想了一下应该没问题，于是就是开始打了。打完的时候差不多过了80分钟了，感觉思考占的时间还是有点长。
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector<int> a[100100];
bool el[100100]; //是否为路由终结点
struct bfun
{
long long p,q; //p/q表示体积
//int num; 当前节点编号
};
inline bfun gcd(const bfun a) //约分
{
long long x=a.p,y=a.q,z;
z=x%y;
while (z!=0)
{
x=y;
y=z;
z=x%y;
}
bfun t;
t.p=a.p/y;
t.q=a.q/y;
return t;
}
inline bfun sum(const bfun a,const bfun b)
{
long long m; //分母
m=a.q*b.q;
long long s; //分子
s=a.p*b.q+b.p*a.q;
long long x=s,y=m,z;
z=x%y;
while (z!=0)
{
x=y;
y=z;
z=x%y;
}
bfun ans;
ans.p=s/y;
ans.q=m/y;
return ans;
}
bfun b[100100];
void dfs(int x)
{
if (el[x]) return;
bfun s;
s.p=b[x].p;
s.q=b[x].q*a[x].size();
s=gcd(s);
for (vector<int>::size_type j=0;j<a[x].size();++j)
{
const int next=a[x][j];
b[next]=sum(b[next],s);
dfs(next);
}
b[x].p=0;
}
int main()
{
int n,m,di,i,j,next;
scanf("%d%d",&n,&m);
memset(el,false,sizeof(el));
for (i=1;i<=n;++i)
{
scanf("%d",&di);
for (j=1;j<=di;++j)
{
scanf("%d",&next);
a[i].push_back(next);
}
if (di==0) el[i]=true;
}
//令n+1为超级源点，将其与各个接收口连接。
for (i=1;i<=m;++i)
a[n+1].push_back(i);
b[n+1].p=m,b[n+1].q=1; //初始化污水
for (i=1;i<=n;++i)
b[i].p=0,b[i].q=1;
dfs(n+1);
for (i=1;i<=n;++i)
if (el[i])
{
b[i]=gcd(b[i]);
printf("%lld %lld\n",b[i].p,b[i].q);
}
return 0;
}想了想会不会数组越界、MLE、long long溢出。虽然说题目限制污水不会经过超过10个节点，但是还是想试试一条链的情况，结果发现系统栈太小……会爆，尝试NOI LINUX（就是UBUNTU 14 LTS），未果，当时有点担心常数的问题。还有打算写个随机生成数据的，结果发现考场上的电脑没有Pascal……回去痛思，一定要好好学下C++的随机生成数据。（当然利用CTIME和RAND()也能生成，不过不太熟，也没这个必要了。
写了个10层二叉树，又手算了一遍10层二叉+三叉发现int不狗用，确实要long long，就改了改，过去了。心想：不会要高精度吧，CCF没必要吧，就算高精度也不太值得写啊，skip。
噢还有细节，用unsigned long long，先gcd得到最小公倍数再乘。
结果就被卡成了80pts。。
T2
看到S=(AB)^i C 这种字符串，数据量高达2^20
没有想到太好的做法，于是就果断暴力
比赛的时候KMP记得不太清楚，只好写暴力判断是否循环节了……
被卡常数……预计时间O(T*N*N)，结果常数太大，N<=1000的时候就要2.3s多了。同样是O(T*N*N)的另一个同学，大样例0.5s就过了……
更讽刺的是赛前两星期还写过KMP……看来自己对KMP的理解还是不够到位。
后来眼看时间不多了，看到只有一种字符的情况，想骗个8pts，写了，但是没有拿到。
期望56pts，实际32pts。
T3
看到SPJ的题目，知道不好做。
考场上说明了自定义比较器需要开启C++11标准编译，不会告诉选手怎么用……然而尽管知道我还是不会做。不超过820000步都是合法的，感觉是比较开放的思路，不一定要盯着最小步数也能完成部分测试点。
碍于比较麻烦，最后10pts的也没有写出来。
T4
时间不多的情况下毫不犹豫选择了30pts——模拟一步步走。
想尝试优化，发现把n步合并起来之后做空间向量，但是不保证中间溢出边界，就没有多想了。
对于-1的特殊判断，每个维度位移都为0就是-1，但是要考虑n步之内会不会溢出。比赛的时候没有考虑到n步的问题，但是100%数据O(N)跑一遍我都要TLE了。
赛后发现第13个测试点是属于前者的-1，但是当时写code的时候也没想着-1的数据点会放这么后来骗分。只开了10^5，100%是5*10^5，血亏5分？
SUMMARY
80+32+0+30=142pts
吐槽
考场上的电脑真的干净……别的能用的编辑器只找到个被删掉快捷方式的subline text 3，里面居然还藏着个Python 3的包！
陈兆锋
于2020年12月
Comments | NOTHING