爱飞鱼的blog

总结：既然不会用python就不要比赛的时候再去查再想着用，chatgpt的思路和题意理解也就看个乐子 https://codeforces.com/contest/1850 1.B题wa了一发，对于vector熟练度不够，导致忘记对于每次一个测试点结束以后，vector没有clear 2.D题:初看想复杂了，发现删除的题目数有单调性，就以为是二分。多看几个样例才发现是一个基于贪心但需要用排序加双指针实现的简单题 3.E题本质上是求解一个一元二次方程的整数解，由于数据量过大，如果普通二分longlong也不够，所以根据题目答案范围做了特判，超过1e18直接结束本轮，更新右端点。 考虑写一个解一元二次方程的模板函数，最好精度比较高 一道题题面如下，时间限制1s,每个测试点有t组样例 (1≤t≤100)，然后n的范围是2e5,假设数据很强，我的算法 时间复杂度n*根号n，根据计算已经1e9所以肯定过不了 还有一个问题就是，如何理解下面这句话？ 保证对于所有的测试用例，n 的总和不超过...

专题班树型dp练习https://ac.nowcoder.com/acm/contest/28260#question 原问题求树上的最大独立集 Solution：仔细读题，一开始以为每次选择的地点是连续的，导致求成最大深度了。实际上是最大独立集。 debug：对于每个儿子的贡献需要累加，叶子节点需要赋初值。 12345678910111213141516171819202122232425vector<int>e[N];int dp[N][2];void dfs(int u,int fa){ dp[u][1]=1;//叶节点赋值和每个点本身贡献 for(auto v:e[u]){ if(v==fa)continue; dfs(v,u); dp[u][1]+=dp[v][0];//有多个叶子，应该是+=，不是+ dp[u][0]+=max(dp[v][1],dp[v][0]); } }void solve(){ int rt;cin>>n>>rt; for(int...

菜鸟教程链接： https://www.runoob.com/cplusplus/cpp-functions.html C++11 提供了对匿名函数的支持,称为 Lambda 函数(也叫 Lambda 表达式)。 Lambda 表达式把函数看作对象。Lambda 表达式可以像对象一样使用，比如可以将它们赋给变量和作为参数传递，还可以像函数一样对其求值。 Lambda 表达式本质上与函数声明非常类似。Lambda...

一些定义和核心性质，对于算法理解有很大帮助,不妨考虑字符串全部为1base1base1base Border:若字符串S的prefix[i]=suffix[i]prefix[i]=suffix[i]prefix[i]=suffix[i]，则称这个前缀或者这个后缀是一个border 周期：对于字符串S，存在整数P满足S[i]=S[i−P]S[i]=S[i-P]S[i]=S[i−P](p<i≤∣S∣)(p<i \le |S| )(p<i≤∣S∣),则P为字符串S的一个周期。这里的周期也常被称为循环覆盖。 循环节：若字符串S的周期P满足p ∣ s.size()p\,|\, s.size()p∣s.size(),则P是S的一个循环节。 理解：周期用循环覆盖理解，就是长度P的周期拼接若干次以后，S一定作为这其中的子串出现。对于循环节来说，循环节拼接若干次以后，恰好能够得到S。 性质： P是S的周期$\Leftrightarrow...

cdq分治

树哈希 一种好写且卡不掉的树哈希 考虑这样一种哈希方式。对于一棵以 𝑎为根的子树，假设儿子是$ v_1, v_2, \cdots, v_k$，定义子树的哈希 h(a)=1+∑1≤i≤kf(h(vi))h(a)=1+\sum_{1\le i\le k} f(h(v_i))h(a)=1+∑1≤i≤k​f(h(vi​))。其中h(vi)h(v_i)h(vi​) 是 viv_ivi​对应子树的哈希，fff 为一个待定函数。 可以证明：如果 fff 为随机函数，这样的哈希在自然溢出下的期望冲突数不超过 O(n2/2w)O(n^2/2^w)O(n2/2w)。只需考虑最深的一对冲突点即可。 上述哈希最大的优势是好写。如果需要换根，第二次 dp 时只需把子树哈希减掉即可。 实践中，我们并不能取一个真正的随机函数当 fff。但事实上，没有特殊性质的 fff 几乎都卡不掉；因为随便找个 fff 大概率很随机。 有一些反例：如果 fff 取多项式，可能因为一直保持 2k2^k2k 同余关系而白给。但是经过我的实验，似乎只要扰动一下改掉这个性质即可。例如下述函数： 1234567ll h(ll...

树上任意两节点之间最长的简单路径即为树的「直径」。 树形 DP的做法 可以在存在负权边的情况下求解出树的直径。 123456789101112131415161718192021222324252627const int N=10010,M=20010;int n,a,b,c,ans;struct edge{int v,w;};vector<edge> e[N];int dfs(int x,int fa){ int d1=0,d2=0; for(auto ed : e[x]){ int y=ed.v, z=ed.w; if(y==fa) continue;//这样就不用开vis数组了，节约空间 int d=dfs(y,x)+z; if(d>=d1) d2=d1,d1=d; else if(d>d2) d2=d; } ans=max(ans,d1+d2); return d1;//返回从u点往下走的最大长度（悬挂在u点上的最长路径的长度）}int...

#scc：极大的强连通子图（两两相互可达） 123456789101112131415161718192021222324252627282930313233343536373839404142const int N=10010;int n,m,a,b;vector<int> e[N]; int dfn[N],low[N],tot;int stk[N],instk[N],top;int scc[N],siz[N],cnt;void tarjan(int x){ //入x时，盖戳、入栈 dfn[x]=low[x]=++tot; stk[++top]=x,instk[x]=1; for(int y : e[x]){ if(!dfn[y]){//若y尚未访问 tarjan(y); low[x]=min(low[x],low[y]);//回x时更新low } else if(instk[y])//若y已访问且在栈中 ...

SDUT 校赛题目 Description 给定正整数 nnn，计算 nnn 个元素的集合 {1,2,⋯ ,n}\{1,2,\cdots,n\}{1,2,⋯,n}，所有非空子集和的乘积取模 998 244 353998 \, 244 \, 353998244353 后的结果。 Input 一个正整数 nnn (1≤n≤200)(1\le n\le200)(1≤n≤200)，代表集合大小。 例如 333 个元素的集合有 777 个非空子集，分别为...

已知一棵包含 NNN 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 1 x y z，表示将树从 xxx 到 yyy 结点最短路径上所有节点的值都加上 zzz。 2 x y，表示求树从 xxx 到 yyy 结点最短路径上所有节点的值之和。 3 x z，表示将以 xxx 为根节点的子树内所有节点值都加上 zzz。 4 x 表示求以 xxx 为根节点的子树内所有节点值之和 输入格式 第一行包含 444 个正整数 N,M,R,PN,M,R,PN,M,R,P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。 接下来一行包含 NNN 个非负整数，分别依次表示各个节点上初始的数值。 接下来 N−1N-1N−1 行每行包含两个整数 x,yx,yx,y，表示点 xxx 和点 yyy 之间连有一条边（保证无环且连通）。 接下来 MMM 行每行包含若干个正整数，每行表示一个操作。 输出格式 输出包含若干行，分别依次表示每个操作 222 或操作 444 所得的结果（对 PPP 取模）。 对于 100%100\%100%...