Codeforces Round 886 (Div. 4)20230722
title: Codeforces Round 886 (Div. 4)20230722 categories: ICPC tags: null abbrlink: 22d7386e date: 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组样例...
树形dp刷题
title: 树形dp刷题 categories: ICPC tags: null abbrlink: ‘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...
Lambda 函数(也叫 Lambda 表达式)。
title: Lambda 函数(也叫 Lambda 表达式)。 categories: ICPC tags: null abbrlink: 4a233e3d date: 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: ICPC tags: null abbrlink: aff110d8 date: 2023-02-22 00:00:00 一些定义和核心性质，对于算法理解有很大帮助,不妨考虑字符串全部为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\,|\,...
cdq分治
title: cdq分治 categories: ICPC tags: null abbrlink: b55b4eb8 date: 2023-02-19 00:00:00 cdq分治
树哈希
title: 树哈希 categories: ICPC tags: null abbrlink: d32ec61e date: 2023-02-16 00:00:00 树哈希 一种好写且卡不掉的树哈希 考虑这样一种哈希方式。对于一棵以 𝑎为根的子树，假设儿子是$ 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≤kf(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...
树的直径——树形dp求法
title: 树的直径——树形dp求法 categories: ICPC tags: null abbrlink: de14d9c9 date: 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: ICPC tags: null abbrlink: 4b4a3d7 date: 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: ICPC tags: null abbrlink: ‘3207e856’ date: 2023-02-03 00:00:00 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 个非空子集，分别为...
树链剖分
title: 树链剖分 categories: ICPC tags: null abbrlink: ‘7e454910’ date: 2023-01-29 00:00:00 已知一棵包含 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...