posted on 2022-10-28 22:41:08 | under 日志 | source
GD 已经有代码了！游记写在代码里，搬过来吧。
2022.10.29。
GD-J00015 / GD-S00013。
FS 石门中学。
震惊：两个编号如此接近！
day 0
在 SS 机房颓废。
CMB 画饼：FS 初中生第一。
day 1 morning J
8:30
好困啊！！！
8:47
pow 一眼 AC，注意到特判 \(a=1\) 之后最多跑 \(O(\log b)\) 次所以是暴力题。
9:30
decode AC，做法是找一个二次函数的零点，三份求最高点，再在左边二分。
9:45
由于实在担心 decode 挂掉所以打了两个对拍，一个有解一个无解。
10:00
发现，上厕所要监考员跟着去，什么玩意？？？
去年在广大附中还是押身份证的。
10:30
expr AC。数据太难造了，不拍了。就是建出一棵表达式树然后 dfs。因为有那个优先级的问题，要把表达式反过来建，前后加一对括号，很稳。
另外能不能解释一下 GDB 不可用的问题？？？
11:00
point AC。
排序一下，DP，和隔壁 LIS 一样：
\[f_{i,k}=\max_j\{f_{j,k-dist(i,j)+1}+dist(i,j)\}. \]\(dist(i,j)\) 是两点的曼哈顿距离，中间不够的用虚点填满。
AK 了，What should i do?
day 1 noon
在石门会议室吃盒饭，乐。伙食不能说很好，只能说梦回金华。
HY 有人过生日，于是牺牲了休息时间吃蛋糕。
听到有人说 decode \(O(1)\)，其实我很想问的是它们怎么判边界呢？你看二分乱搞：
LL n,e,d,s;
LL f(LL p){
return p*s-p*p-n;
}
LL ternary(LL l,LL r){
while(r-l>10){
LL d=(r-l)/3;
if(f(l+d)<f(r-d)) l+=d;
else r-=d;
}
LL ans=l;
for(LL i=l;i<=r;i++) if(f(ans)<f(i)) ans=i;
return ans;
}
LL binary(LL l,LL r){
LL ans=-1;
for(LL mid=(l+r)>>1;l<=r;mid=(l+r)>>1){
if(f(mid)<0) l=mid+1;
else ans=mid,r=mid-1;
}
return ans;
}
int mian(){
s=n-e*d+2;
if(s<0) return puts("NO"),0;
LL ans1=binary(1,ternary(1,1e9)),ans2=s-ans1;
if(1<=ans1&&1<=ans2&&f(ans1)==0&&f(ans2)==0){
if(ans1>ans2) swap(ans1,ans2);
printf("%lld %lld\n",ans1,ans2);
}else puts("NO");
return 0;
}
好吧我承认我不会一元二次方程。
day 1 afternoon S
14:30
背包放错考场了，差点进了上午的考场。
就我的意思是，上午在电脑 2 室考，下午找准考证时看错了。
同一桌竟然是同校的 @Sunny郭 。
进行一个题目的看。
15:00
B 有点思路？是不是把 \(\min,\max_{<0},0,\min_{>0},\max\) 都拎出来跑一遍就行了，不是很确定。
15:27
B AC，机房 cmd 不能运行程序，说是缺少一个什么 .dll，可见准备之仓促。
写了 8 个 STable，然后枚举两个人共 25 种决策……
反正复杂度很对，不会超时，对吗？
15:30
发现 A,D 好像是同一个东西。。。今天图论专场是吧？？？
A 首先 \(O(nm)\) 最短路（BFS 谢谢喵），然后呢？暴力枚举两个点？
如何求出 \(f_{u,v}\) 表示 \(\max_{to_{u,k}\land to_{k,v}} v_k\)？
枚举 \(k\) 然后更新 或者 枚举 \(u,v\) 去找 \(k\)。
那么是不是说把两者结合呢？
\(k=0\) 是【模板】无向图三元环计数！ 说明这个题可做。
16:00
枚举景区 B,C，那么只会用到 \(f_{1,u}\)，复杂度 \(O(n^2+nm)\)。
笑。
16:05
SB gdb 竟然有查看数组容量限制！！！
于是决定进行一个输出调试。
16:20
A AC。开始进行一个 C 的看。
考场通知：C 题样例解释中最后一个“第 \(5\) 次”改为“最终”。
16:30
C 两个限制分别为 \(out_u=1\) 和有环。
线段树分治。用并查集，如果 \(query(u,v)=\textbf{true}\) 那就有环出现。
假的！
17:30
写了很久终于干掉了 C 的暴力 20pts，期望很快吧。观察到需要重新跑 tarjan 的次数可以很少，我只在所有 \(out_u=1\) 的时候跑 tarjan 缩点。
还有一个小时想写 D。
性质：
- \(k=1\) 是树上前缀和；
- \(k=2\) 必然会沿着路径走，一个 DP；
- \(k=3\) 最多走到一个儿子那里，不会走更深的地方。
先写树剖吧。
特殊性质就是说深度很小，可以把链拉出来跑暴力。
感觉可以点分治！写不写？？？
其实一直有矩阵乘法优化 DP 的冲动（我是说动态 DP），但是，先写暴力吧。。。
18:24
\(k=3\) 挂了。不知道怎么挂的，大样例错两个。
今天到此为止。感觉非常不舒服（心理上的），没有写出 \(k=3\) 的情况，我感觉我的 D 都快接近正解了，但我没时间写了！！！
18:27
CSP2022-S，再见！
目测 \(100+100+20+30\)。提高一等没啥问题吧，但是 CMB 画的饼可能有大问题。谁知道呢。等个七天再说。
day 1 evening
学校教练太强了，已经有代码了。J/S 都有的那种，可惜不知道怎么发到 luogu 上。
J 组 AK！同校的 @Lucky9568 、@Prominence 也都 AK 了，我直接 Orz。
luogu：\(S=100+100+?+56\)。
终于发现了，C 题如果每个点都连出一条出边，是必然有环的（不然给个反例？），所以只需要维护 \(out\)，还不是很会接下来怎么做。
D 题一直没有算到底多少分，luogu 给了 \(56\) 分。没有 TLE 是没有想到的。
day 2
INFOJ：\(100+100+40+44=284\)。
C 题算错分了，原来是 8 个测试点。
D 题 \(k=3\) 的暴力调出来了：点权算了两次。
LL dp3(int u,int v){
int cnt=split(u,v);
f[0][0]=f[0][1]=f[1][1]=1e18,f[1][0]=a[pos[1]];
for(int i=2;i<=cnt;i++){
f[i][0]=f[i][1]=1e18;
if(i>=3) f[i][0]=f[i-3][0]+a[pos[i]];
// ^~~~~~~~~
f[i][0]=min({f[i][0],f[i-1][0],f[i-1][1],f[i-2][0],f[i-2][1]})+a[pos[i]];
// ^~~~~~~ ^~~~~~~~~
int j=minx[pos[i]][0]==pos[i-1]?minx[pos[i]][1]:minx[pos[i]][0];
f[i][1]=min({f[i-1][0],f[i-1][1],f[i-2][0]})+a[j];
}
return min(f[cnt][0],f[cnt][1]+a[v]);
}
写对了就 76 分了！
jisuanke：\(100+100+60+44=304\)，A 题数据造错（\(m\leq 10^5\)）我也没办法，当它过了吧。
score
J 不用看了 AK
S：
- luogu \(100+100+60+56=316\)
- infoj \(100+100+40+44=284\)
- jisuanke \([85,100]+100+60+44=[289,304]\)
- youdao \(100+100+40+44=284\)
主要波动：
- jisuanke A 数据多了个 0，TLE
- T3 memset bool 数组的时候写了 sizeof(int)，infoj 提示 dangerous system calls
- T4 希望草多一点 k=2 的分