题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6774题目大意：对于操作：删除一个字符或者添加一个字符给你两个字符串A，B。q次询问，每次询问A串的A[l...r]最少通过多少次操作变成B。 思路：通过序列自动机得到一个数组：net[i][j]:A[i-]后面第一个j字符的位置。然后每次一个DP：f[i][j]:B前i个字符匹配了j个字符的子序列的最近位置。转移：我们推导出：最少操作次数=r-l+m-*LCS #include<bits/stdc++.h> using namespace std; char a[2000005], ...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6756题目大意：有一个n点，m条边的无向图，每个点有一个权值。现在有两个操作：1 x y：把x点的权值修改为y2 x : 查询x的的邻接点的权值中没有出现的最小非负整数。思路：前几天正好补了一个分块的题，今天就遇到了。我们考虑按点的度数进行维护。我们考虑用权值线段树去维护每个点的mex。 对于修改x：我们去遍历它d[y]>sqrt(n)的邻接点,最多有sqrt(n)个，每个在线段树上修改，复杂度:O(sqrt(n) * logn)对于查询x：如果d[u]<=sqrt(n)那么我们暴力每...

题目链接：https://www.luogu.com.cn/problem/P2572题目大意：思路：珂朵莉树搞一搞，好像数据加强了，只能30分，会T。 #include <bits/stdc++.h> #define ll long long #define sit set<node>::iterator using namespace std; struct node{ int l, r; mutable ll val; int operator<(const node &a) const{ return l&...

题目链接：https://www.luogu.com.cn/problem/CF896C题目大意：这个数据读入有点毒瘤，其他解是模板了。 #include <bits/stdc++.h> #define ll long long #define sit set<node>::iterator using namespace std; struct node{ int l, r; mutable ll val; int operator<(const node &a) const{ return l<a.l; ...

题目链接：https://nanti.jisuanke.com/t/40260题目大意：给两个长度为n的数组，数字大小不超过1e5，求出它们两两相或的数组c，从小到达排序后支持两种操作：0 x ：查询位置为x的数的当前值l r：对[l,r]区间的数开方 思路：我们通过fwt得到c数组。c[i]:i的个数。区间开方肯定用线段树维护。问题是区间长度为n * n。我们考虑对于操作：1 100000000000 5我们真的要建长度为10000000000的线段树吗？其实我们就用到1， 5， 10000000000。3个点。我们肯定考虑离散化。在操作中出现的点保留。开一个2*n的线段树就可以了。 #in...

题目链接：https://ac.nowcoder.com/acm/problem/19810题目大意：思路：我们定义DP[i]:i个节点形成的树的最大花费。我们知道重儿子是一个费用的影响因素：那么我们枚举重儿子的节点个数为x。因为除了重儿子，其他节点到根都有费用。DP[i]=max(DP[i], DP[x]+DP[i-x-1]+i-x-1)这个DP[i-x-1]是有问题的。因为重儿子的节点树必须小等于x。我们定义：f[i][j]:i个节点组成的森林(多个树)，（因为和根断开后，这些都是子树），并且最大的那棵树节点数<=i的最大代价。 那么上面的方程为DP[i]=max(DP[i], D...

题目链接：https://ac.nowcoder.com/acm/problem/16645题目大意： 思路：我们可以看出，每行是独立的，那么对每行直接dp就可以了。f[i][j]:取完区间[i, j]的数能够获得的最大值。枚举取左还是右就可以了。 #include <bits/stdc++.h> #define LL long long #define _int __int128 using namespace std; inline __int128 read(){ __int128 x=0,f=1; char c=getchar(); while...

题目链接：https://ac.nowcoder.com/acm/problem/14254题目大意： 思路：参考大佬的思路： #include <bits/stdc++.h> using namespace std; map<int, int> mp[1005]; int cloer[1005][1005]; int vis[2005]; void dfs(int x, int y, int c1, int c2){ int to=cloer[y][c1]; cloer[x][c1]=y, cloer[y][c1]=x;//强行把x-y染成c1。...

题目链接：https://ac.nowcoder.com/acm/problem/13950题目大意：树上有k个帮派，每个帮派会占据一些城市。他们控制的点除了自己占领的点。还有再加上这些城市两两之间路径上的所有城市。 有时帮派之间会结盟，这样联盟的点集为这些帮派的点集的并集。他们控制的点除了自己占领的点。还有再加上这些城市两两之间路径上的所有城市。 现在有Q个询问。每次询问选择一个点作为首都。和一些帮派。我们只考虑这些被选择的帮派，并且他们结盟。首都离联盟控制的点最近距离为多少？ 思路：我们先对所有的帮派求一个LCA。保存在LCA[i]。每次询问的帮派x1, x2, ...., xm。对L...

题目链接：https://ac.nowcoder.com/acm/problem/19814题目大意：思路：m最大为n+100，并且连通。我们可以假设开始一棵树。有q个查询u-v的最短路。然后添加了100条边。那么最短路可以发生变化的一定经过了这些边。假设这些边为x-y。那么经过了x点。我们以x为起点跑一个最短路，那么a-b的最短路可能为ans[i]=min(ans[i], dis[a]+dis[b])。当然对于每个查询我们不能去枚举一次100条边。而是用100条边上的点跑完最短路都去更新下q个查询。复杂度O(100qlogn) #include <bits/stdc++.h> #...

题目链接：https://ac.nowcoder.com/acm/contest/5666题目大意：给你一个n,m和m条有向边ai->bi和费用ci。每次询问u/v。回答把每条边的费用修改为u/v时。从1流一个流量到n的最小费用。如果无法流到输出NaN。其实就是把所以边容量修改为u。从1流v的流量到n的费用/v。 思路：对于每次询问我们不能跑一次费用流。因为容量一样。你们我们根据费用流的算法流程。在每次寻找增广路SPAF()时。都会找到流量为1的路。我们统计下每个流量下的费用sum[i]和第i条增广路的费用s1[i]。那么我们在出来询问时。判断最大流*u<v就NaN，否则就选择前...

题目链接：https://ac.nowcoder.com/acm/contest/5666/I题目大意：有一个n个点,m条边的图 ，给出每个点的度数，问是否可以成为该图的子图。给定样例：4 41 2 1 01 23 42 31 4

题目链接：https://codeforces.com/problemset/problem/1009/F题目大意：给你一颗树，用d(x, k)表示x在第k层的儿子（自己为根节点）的节点数量。现在希望你输出每个点取得最大d(x, k)的k，如果多个层相同，取k最小的。思路；长链剖分的模板题：我们先熟悉一下长链剖分。 解释合并的时候再计算一下答案。 #include <bits/stdc++.h> using namespace std; vector<int> G[1000005]; int len[1000005], son[1000005]; int tmp[1...

题目链接：https://codeforces.com/problemset/problem/208/E题目大意：有一棵森林。每个节点一个姓名。每次询问x k:x的k级祖先处于deep[x]的儿子有多少个名字不同的节点思路：和上题一样，只是把数组换成了map。 #include <bits/stdc++.h> using namespace std; vector<int> G[200005]; int id[200005]; int ans[200005], vis[200005]; map<string, int> mp; map<int, in...