考试 开考看题，秒了 T1，感觉 T2 是简单 dp，T3 有点神秘不知道，T4 一眼有一个 \(\mathcal O(n^2)\)。于是顺序开题。T1 很快写了，T2 看了一个小时还是不会有点难崩，当时是很快想到一个 dp，设 \(f_{i,j,0/1}\) 表…

今天是10月28号，上了铁道技术认知。

P8269 [USACO22OPEN] Visits S 题解题目传送门 博客传送门 首先，每头牛牛都只有一个拜访对象，所以如果考虑图论建模的话，相当于每个点出度都是 1。这相当于图是个基环树森林（注意不只有一棵基环树），而且每个基环…

联合猫国 去年模拟赛做过一道几乎一模一样的题，于是一眼秒了。 本题的一个结论：最终可合并的区间数为 \(\bm{O(n\log n)}\) 级别。 证明可以考虑构造出可合并区间数最多的序列，显然是所有数都相同时的区间数，可以取…

pre { white-space: pre !important; word-wrap: normal !important; overflow-x: auto !important; display: block !important; font-family: "Consolas", "Monaco", "Courier New", …

10.28 （虽然但是下发文件NOIP?）10.28 CSP-S 前倒数第二场模拟赛，直接一道都没切出来。。。 再不放信心赛真要没信心了。 t1 dp题。 显然对于每一次行动都是一个背包dp。 变种在于背包更换，更换后容量重新计算。 所…

T1 code #include<bits/stdc++.h> using namespace std; const int N=5e4+5,M=1e3+5; int n,m,ans=0; char s[N],t[M]; int nxt[M]; int f[N][M]; int g[M][30]; void getnxt(){nxt[1]=0;int j=0;for(int i=2;i&…

CSP-S模拟41 A. 数轴取物(axis) 显然可以有一个 \(O(n^3)\) 的背包 dp，设 \(dp[i][j][k]\) 表示选区间 \([i,j]\)，背包容量为 \(k\) 时可获得的最大价值。每次枚举固定左端点从小到大枚举右端点，发现 \(dp[i][j]\) …