题号 题目 通过率 A Clam and Fish 1453/4902 B Classical String Problem 1547/6542 C Operation Love 1431/5631 D Points Construction Problem 548/2238 E Two Matchings 943/4141 F Fraction Construction Problem 1034/6445 G Operating on a Graph 972/4259 H Sort the Strings Revision 200/767 I Sorti...

题号 题目 通过率 A B-Suffix Array 789/4347 B Infinite Tree 264/1005 C Domino 24/288 D Quadratic Form 167/551 E Counting Spanning Trees 75/149 F Infinite String Comparision 1918/6403 G BaXianGuoHai, GeXianShenTong 38/190 H Minimum-cost Flow 766/3901 I 1 or 2 1031/5289 J Easy Integration...

题号 标题 通过率 A All with Pairs 750/2822 B Boundary 1394/11796 C Cover the Tree 1256/5537 D Duration 1552/1883 E Exclusive OR 323/844 F Fake Maxpooling 1867/8124 G Greater and Greater 576/1500 H Happy Triangle 499/2857 I Interval 287/1633 J Just Shuffle 725/2372 K Keyboard Free 370...

模板题 P3806 【模板】点分治1 题目描述 给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。 详讲 关于点分治具体内容可以看这个这里主要是详细讲讲代码：getrt是用来求重心，我们利用树型dp的思维来做，即找到该节点所有的子树，找到最大的哪一颗即可 void getrt(int u,int pa)//求重心 { size[u]=1; maxp[u]=0; for(int i=head[u];i;i=E[i].nxt) { int v=E[i].v; if(v==pa||vis[v]) continue; ...

@[toc] 介绍： 将原问题分解成若干相同形式，相互独立的子问题，各个击破一般用来解决有关树上路径的统计和询问 题目： P4178 Tree给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。 做法： 暴力做法；(O(n^2^))点分治做法：选择一个点作为分治中心，令其为rt做dfs。对于一条路径path(u,v)，其要么经过rt(即lca(u,v) = = rt)，要么在某个子树sub(son[rt])中把问题形式化为： solve(T,rt) = 统计T树中经过rt且长度<=k的路径数量 对T数进行分治work(T)的步骤：1.找到一个分治中心rt2....

P4178 Tree 题意： 给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。 题解： 点分治的模板题是求等于K的路径条数本题是求小于等于K的路径条数，我们只需要改变统计答案即可原本统计答案是对一个路劲长度len，判断K-len在之前的子树中出现多少次，用f数组来记录，直接查看f[k-len]等于多少即可现在统计答案是对一个路径长度len，判断小于等于K-len的数在之前的子树中出现多少次，统计区间数量，我们可以用树状数组来实现，对于每个len我们插入数组f[]其中，然后求1~K-len的区间查询 代码： 详细看代码 #include<bits/stdc...

P4381 [IOI2008]Island 题意： 给你一棵基环树森林，求出基环树的直径之和. 题解： 对于基环树,我们将环看作根,那么直径有两种情况:: 1.不经过环,也就是环上某个点的子树内部,对于这种情况,直接在子树内部处理直径,更新答案即可; 2.经过环,答案就是i的子树内长度+j的子树内长度+i和j之间的距离，我们预处理出环上每个点到其子树上的最长距离,在预处理一个环上前缀和,ans=max{sondis[i]+sondis[j]+sumcircle[i]-sumcircle[j]},更新答案即可.sondis[i]记录环上的第i个点到其子树的最远距离;sumcircle[]记录环上...

P2607 [ZJOI2008]骑士 题意： n个点n个边，每个点都有权值，相邻的点不能同时选择，问如何选择能使得权值最大 题解： 这个题很有P1352 没有上司的舞会这个题的感觉，唯一的区别是那个题保证是树，而本题肯定不是树，而是基环树也就是本题中，每一个连通块有且只有一个环，所以我们找到这个环并剪短，这样就形成一颗树，断口的两个端点x和y，我们认为分开对于一棵树，这不就是P1352 没有上司的舞会这个题吗 注意有可能存在很多连通块，记得所有连通块的答案要累加 代码： #include <cstdio> #include <iostream> #include &lt...

P1352 没有上司的舞会 题意： 给你一个树，每个点都有权值，选择一些点使得权值和最大，要求父亲节点和子节点不能同时选择 题解： 经典树形dpdp[x][0]表示以x为根的子树，且x不参加舞会的最大快乐值dp[x][1]表示以x为根的子树，且x参加了舞会的最大快乐值则dp[x][0] = ∑{ max(dp[y][0],dp[y][1]) } (y是x的儿子)dp[x][1] = ∑{ dp[y][0] } + a[x] (y是x的儿子)找到唯一的树根rootans=max(dp[root][0],dp[root][1]) 代码： #include<bits/stdc++.h>...

P5049 [NOIP2018 提高组] 旅行 题意： 一棵树(可能是基环树)，从1出发，每到达一个新的点就记录下编号。求一种走法使得记录下来的编号字典序最小。 1≤n≤500000 m=n−1 或 m=n 题解： 如果不是基环树，那直接每次走字典序小的点即可对于基环树：第一个方法：暴力删边将基环树变为一颗普通的树，然后计算答案，复杂度是O(n * n)这个方法好像只能过P5022 [NOIP2018 提高组] 旅行 这个没加强数据的题，P5049过不了第二个方法：参考题解对于基环树，我们在环上跑到一半，另一半通过回溯到你刚到这个环的起点，接着DFS就可以了例如下图，我们从1开始，走3走2然...

@[toc]参考博客 概念 基环树 = n个点n条边的图 = 1棵树 + 1个环无向树(N点N边无向图) 外向树(每个点入度=1) 内向树(每个点出度=1) 以上三种树有十分优秀的性质，就是可以直接将环作为根。就可以对每个环的子树进行单独处理，最后再处理环 找环 拓扑排序 处理无向图 可以找出环上的所有点 入度大于等于2的点就是环上的点 code void topsort(){ int l=0,r=0; for (int i=1;i<=n;i++) if(in[i]==1) q[++r]=i; while(l<r) { in...

P3992 [BJOI2017]开车 题意： 题解： 我们要先将问题转换圈是车，x是加油站。红色部分为车移动的路线数组a是车数量的前缀和数组b是加油站的前缀和而a[i]与b[i]的差的绝对值就是对应的红色路被走的次数现在车发生位置移动，b数组没有影响，a数组i到j这段整体减一现在我们要做的就是维护a序列，支持区间+1/-1，询问∑| a[i] - b[i] |线段树不能实现用分块实现实现过程：按照下标分块，每块按照a[i] - b[i] 排序 代码： 代码为借鉴 #pragma optimize("Ofast") #include<bits/stdc++.h> #define M...

P4135 作诗 题意： 给定 n 个不大于 c 的正整数 a1...an 和 m 组询问，每次问 [l,r] 中有多少个数出现正偶数次。对于每次询问：设上一个询问的答案为 ans（第一个询问时 ans=0），令L=(l+ans)mod n+1，R=(r+ans)mod n+1，若L>R，交换 L 和 R，则本次询问为[L,R]。 题解： 第一反应是莫队，但是题目明确说了是强制在线当这种区间问题想不到什么好方法时，分块暴力就是最好的方法首先预处理前i块内颜色为j的出现几次sum[i][j]ans[i][j]表示第i块到第j块内有多少数出现了偶数次cnt[i]表示i颜色出现次数（cnt每次...

题意： 长度为n的字符串S，现在要找出k个不同的子序列，使得这些序列的总价值最低一个序列的价值等于删去的字符长度（空串也算子序列）1≤n≤100,1≤k≤10^12^ 题解： 一看就是dp，我们先想想串a可以有多少不同的子序列dp[i][j]表示前i个字符构造出来的长度为j的子序列数量转移方程不难得到：dp[i][j]=dp[i-1][j-1]+dp[i-1][j]，（也就是选第i个和不选第i个）但是这样做是存在重复的比如satwt,按照上面的方法，st和at就会重复出现，那么怎么才能避免？因为t是重复的，我们只需要取最近的t就行对于j<i且aj = = ai时，前j-1个字符形成的子序...