游记 CSP2022-J2/S2

· · 个人记录

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)\}. AK 了，What should i do? ## day 1 noon 在石门会议室吃盒饭，乐。伙食不能说很好，只能说梦回金华。 HY 有人过生日，于是~~牺牲了休息时间~~吃蛋糕。 听到有人说 decode $O(1)$，其实我很想问的是它们怎么判边界呢？你看二分乱搞： ```cpp 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$ 的暴力调出来了：点权算了两次。 ```cpp 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

主要波动：