本题是一道细节巨多的操作分块题。 踩坑记录 一个块中有可能多次修改一条边（个人认为是本题最难部分）。 set的erase会直接删除所有不大于且不小于传入变量的键值，所以一定要好好写 operator 使其可以匹配唯一键值。 变量多了一定要打注释，在这方面一定不要相信你的大脑。 即使你很确定错误在哪，也要看看别的地方，不要像我瞪了半小时才知道错误在屏幕外。 AC 代码 自己都觉得又臭又长 #include<bits/stdc++.h>#define fru(i,j,k) for(int i=j;i<=k;i++)#define frd(i,j,k) for(int i=j;i>=k;i--)#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);using namespace std;using ll = long long;char c=' ';int in( ...

因为这玩意没什么好当板子的，就作为题解来写 思路 前人之述备矣。 补充几点： 开始一直以为复杂度是错的，后来写了个暴搜发现长度在 131313 以内的合法串只有 450004500045000 左右，完全是够的。 主要注意： “((” 的情况应找最近未被匹配的括号。 代码 #include<bits/stdc++.h>#define fru(i,j,k) for(int i=j;i<=k;i++)#define frd(i,j,k) for(int i=j;i>=k;i--)#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);using namespace std;using ll = long long;char c=' ';int in(void){ int x=0;bool f=false; while(!isdigit(c))& ...

CSP2023 提前开坑~~ “DAY 0” 为开始考试第一天，其余以此类推。 初赛 DAY -2 今天啥都没准备，就看了一个复赛题的题解，还没看懂…… DAY -1 今天搞了半张卷子（不是，这些模拟卷都这么难吗？！！） DAY 0 早上，CSP-J，水。 下午，CSP-S，跳过了约 5 题，如果线没有比 70 还高应该没事……吧？ DAY 7 出分了，提高的线只有 40 就离谱。 结果普及高 40 分过线，提高高 35 分过线，初赛圆满完结。 复赛 DAY -2 今天发现学的好多东西在纲里所谓“NOI 级”的部分，而在“提高级”里的平衡树和高斯消元却根本不会，感觉药丸…… 主要工作：背以前的模板以及摆烂。 DAY -1 继续背板子，学习 pb_ds 以及摆烂。 加油！ DAY 0 考试开始~ 早上 J 组： T1：开始还在推每个位置是啥时候被删掉的，退不出来，然后突然发现只要求 nnn 的答案，于是使用第一次删掉最后一个数的时间。水之，期望 100100100。 T2：看了看，写了一个贪心，让每次的车都直接创到第一个比当前加油站便宜的加油站，因为如果到达一个加油站，油箱里却 ...

题面 弱化版题面（甚至那题很多题解都过不去这题） 推导相当简单，只要等比数列求和一代入，就结束了。 但特判有三个，还很隐蔽…… a==1 \\会使推导过程分母为0a==0 \\会出现0的0次方/*分母*/%p==0 \\逆元不存在 代码 #include<iostream>#include<cstdio>#include<iomanip>#include<cstdlib>#include<algorithm>#include<random>#include<ctime>#include<cmath>#include<cstring>#include<queue>#include<map>#include<unordered_map>#define fru(i,j,k) for(int i=j;i<=k;i++)#define frd(i,j,k) for(int i=j;i>=k;i--)#def ...

T1 相信你们都查到了的原题：CF468A 签到题，考的是出题人如何写SPJ。 1,2,31,2,31,2,3：显然无解 4,54,54,5：显然有解，手工构造就行了。 1 * 2 = 22 * 3 = 66 * 4 = 24 1 + 5 = 62 * 6 = 123 * 4 = 1212 + 12 = 24 >5>5>5：每次输出 n - (n-1) = 11 * 1 = 1 就可以使得 n,(n−1)n,(n-1)n,(n−1) 两数字凭空消失，此时只剩 111 到 (n−2)(n-2)(n−2)，可以看做 nnn 减少了 222。 不断减下去，直到 nnn 为 444 或 555，输出构造的答案就可以了。 T2 相信你们都查到了的原题：P2224 DP，设 fif_ifi​ 表示左手劳累度为 iii 时右手劳累度最小值。 最后计算 max⁡{fi,i}\max\{f_i,i\}max{fi​,i} 即可。 其实上面的思想有了，转移十分简单，实在推导不出来就看 luogu 题解吧。 T3 相信你们都查到了的近似题：P5656 傍一写了个十分正确的东西 ...

快读快写 1.0： char c=' ';ll in(void){ ll x=0;bool bl=false; while(!isdigit(c)) { bl^=c=='-'; c=getchar(); } while(isdigit(c)) { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return bl?-x:x; }template<typename t>void out(t x){ if(x<0)pc('-'),x=-x; if(x>9)out(x/10); pc(x%10+48);} 2.0（仅适用于文件读写）： char buf[1 << 23], *p1 = buf, *p2 = buf;#define getcha ...

高精度板子，会在做题时完善，目前有： 高精减高精 高精乘低精 高精除低精 struct nd{ int len,nl[maxn]; nd() { len=0; memset(nl,0,sizeof nl); } bool operator<(nd y) { if(len<y.len)return true; if(len>y.len)return false; frd(i,len-1,0) if(nl[i]<y.nl[i])return true; else if(nl[i]>y.nl[i])return false; return false; } nd operator-(nd y) { nd as; as.len=len; fru(i,0,len-1) { ...

字符串哈希 模数： 比较弱：101926081710192608171019260817 强得离谱：212370440130137957212370440130137957212370440130137957 （不要问我为啥放这）hash 表模数：194910011949100119491001 const ll mod=/*mod*/,bs=/*base*/;inline ll gths(int l,int r){return ((hs[r]-hs[l-1]*pow(bs,r-l+1))%mod+mod)%mod;}//mainl=str.size();fru(i,0,l-1)hs[i+1]=(hs[i]*bs+str[i])%mod; KMP 算法 看毛片 设字符串为 sss（下标从0开始），dcdcdc 为当前模式串 sss 判断的下标，preliprel_ipreli​ 为 s[0,i]s[0,i]s[0,i] 中最长前缀后缀相等长度，当匹配失败时正好需要会退到下标 predc−1pre_{dc-1}predc−1​。 简单来说，匹配过的总长 ...

快速幂&取余运算 O(log⁡2b)O(\log_2{b})O(log2​b) 求 abmod⁡pa^b \operatorname{mod} pabmodp。 ll qp(ll a,ll b,ll p){ ll ans=1; while(b) { if(b&1)ans=(ans*a)%p; a=(a*a)%p; b>>=1; } return ans;} 乘法逆元 快速幂 模数是质数版：qp(a,p-2,p) 模数仅满足 gcd⁡(a,p)=1\gcd(a,p)=1gcd(a,p)=1 版：qp(a,phi(p)-1,p) exGCD版 如下： ll inv(ll a,ll p){ ll tx,ty;exgcd(a,p,tx,ty); return (tx%p+p)%p;} 线性预处理 比较懒，直接贺了 oiwiki 的代码 inv[1] = 1;for (int i = 2; i <= n; ++i) &# ...

第二道黑题，想了一周终于想出来了，小激动。 main 主要思路：根据字典序定义，从小到大把每个数往小里放就一定行，于是从每个数开始搜索，找编号最小的合法终点。 补充一些细节： 只要确定了每个点的出边删除顺序，就一定有合法解。 在任何有至少一条边的状态中，设 nnn 为点数，eee 为边数，一定有 e⩽n−1e\leqslant{n-1}e⩽n−1，于是一定有两个点都把连接他们的边当做他们第一个要删的边，最终删的一边不剩。 code #include<iostream>#include<iomanip>#include<cstdlib>#include<cstdio>#include<string>#include<cstring>#include<cmath>//75760209#include<ctime>#include<climits>#include<random>#include<algorithm>#include<map> ...