Codeforces Round 886 (Div. 4)20230722
title: Codeforces Round 886 (Div. 4)20230722categories: - ICPCtags: - nullabbrlink: 22d7386edate: 2023-02-27 00:00:00总结：既然不会用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,假设数据很强，我的算法...
树形dp刷题
title: 树形dp刷题categories: - ICPCtags: - nullabbrlink: ‘1e240034’date: 2023-02-24 00:00:00专题班树型dp练习https://ac.nowcoder.com/acm/contest/28260#question原问题求树上的最大独立集Solution：仔细读题，一开始以为每次选择的地点是连续的，导致求成最大深度了。实际上是最大独立集。debug：对于每个儿子的贡献需要累加，叶子节点需要赋初值。vector<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...
Lambda 函数(也叫 Lambda 表达式)。
title: Lambda 函数(也叫 Lambda 表达式)。categories: - ICPCtags: - nullabbrlink: 4a233e3ddate: 2023-02-23 00:00:00菜鸟教程链接：https://www.runoob.com/cplusplus/cpp-functions.html C++11 提供了对匿名函数的支持,称为 Lambda 函数(也叫 Lambda 表达式)。Lambda 表达式把函数看作对象。Lambda 表达式可以像对象一样使用，比如可以将它们赋给变量和作为参数传递，还可以像函数一样对其求值。 Lambda 表达式本质上与函数声明非常类似。Lambda...
字符串border系列学习笔记
title: 字符串border系列学习笔记categories: - ICPCtags: - nullabbrlink: aff110d8date: 2023-02-22 00:00:00一些定义和核心性质，对于算法理解有很大帮助,不妨考虑字符串全部为$1base$ Border:若字符串S的$prefix[i]=suffix[i]$，则称这个前缀或者这个后缀是一个border 周期：对于字符串S，存在整数P满足$S[i]=S[i-P]$$(p<i \le |S| )$,则P为字符串S的一个周期。这里的周期也常被称为循环覆盖。 循环节：若字符串S的周期P满足$p,|, s.size()$,则P是S的一个循环节。 理解：周期用循环覆盖理解，就是长度P的周期拼接若干次以后，S一定作为这其中的子串出现。对于循环节来说，循环节拼接若干次以后，恰好能够得到S。 性质： P是S的周期$\Leftrightarrow...
cdq分治
title: cdq分治categories: - ICPCtags: - nullabbrlink: b55b4eb8date: 2023-02-19 00:00:00cdq分治
树哈希
title: 树哈希categories: - ICPCtags: - nullabbrlink: d32ec61edate: 2023-02-16 00:00:00树哈希 一种好写且卡不掉的树哈希考虑这样一种哈希方式。对于一棵以 𝑎为根的子树，假设儿子是$ v_1, v_2, \cdots, v_k$，定义子树的哈希 $h(a)=1+\sum_{1\le i\le k} f(h(v_i))$。其中$h(v_i)$ 是 $v_i$对应子树的哈希，$f$ 为一个待定函数。 可以证明：如果 $f$ 为随机函数，这样的哈希在自然溢出下的期望冲突数不超过 $O(n^2/2^w)$。只需考虑最深的一对冲突点即可。 上述哈希最大的优势是好写。如果需要换根，第二次 dp 时只需把子树哈希减掉即可。 实践中，我们并不能取一个真正的随机函数当 $f$。但事实上，没有特殊性质的 $f$ 几乎都卡不掉；因为随便找个 $f$ 大概率很随机。 有一些反例：如果 $f$ 取多项式，可能因为一直保持 $2^k$...
树的直径——树形dp求法
title: 树的直径——树形dp求法categories: - ICPCtags: - nullabbrlink: de14d9c9date: 2023-02-12 00:00:00树上任意两节点之间最长的简单路径即为树的「直径」。 树形 DP的做法 可以在存在负权边的情况下求解出树的直径。const 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; } ...
强连通分量
title: 强连通分量categories: - ICPCtags: - nullabbrlink: 4b4a3d7date: 2023-02-10 00:00:00#scc：极大的强连通子图（两两相互可达） const 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已访问且在栈中 ...
贡献法+经典背包+费马小定理
title: 贡献法+经典背包+费马小定理categories: - ICPCtags: - nullabbrlink: ‘3207e856’date: 2023-02-03 00:00:00SDUT 校赛题目 Description给定正整数 $n$，计算 $n$ 个元素的集合 ${1,2,\cdots,n}$，所有非空子集和的乘积取模 $998 , 244 , 353$ 后的结果。 Input一个正整数 $n$ $(1\le n\le200)$，代表集合大小。 例如 $3$ 个元素的集合有 $7$ 个非空子集，分别为...
树链剖分
title: 树链剖分categories: - ICPCtags: - nullabbrlink: ‘7e454910’date: 2023-01-29 00:00:00已知一棵包含 $N$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 1 x y z，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。 2 x y，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。 3 x z，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。 4 x 表示求以 $x$ 为根节点的子树内所有节点值之和 输入格式第一行包含 $4$ 个正整数 $N,M,R,P$，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。 接下来一行包含 $N$ 个非负整数，分别依次表示各个节点上初始的数值。 接下来 $N-1$ 行每行包含两个整数 $x,y$，表示点 $x$ 和点 $y$ 之间连有一条边（保证无环且连通）。 接下来 $M$...