题意 n个点m条边的有向图，给出边的单位流量费用，q次询问，每次询问有有u,v两个整数，表示所有边的容量为u/v，对于每次询问，输出从1到n流量为1时的最小费用，流量达不到1时，输出“NaN”. 题解 每条边的容量是相同的，如果边的容量为1的时候流量为maxflow，那么边的容量为u/v时，流量就是u* maxflow/v。所以，只要将所有边按容量为1跑最小费用最大流，将每次增广的流量和费用存下来，按费用从小到大排序，对于每次询问，假定边容量为u，那么最大流就是u*maxflow，按费用从小到大加到将流量凑到v，得到的费用再除以v，就是流量为1时的费用了。 代码 #include <bi...

题意 n个点m条边的无向图，每条边有一个权值，-1,0,1，表示这条边的染色情况，-1表示没有染色，0,1表示染的颜色。需要对没有染色的边进行染色（0和1两种），求满足所有环的边异或和为0的染色方案数。 题解  直接对边赋值很难搞，那么考虑对点赋值，再转换为边的赋值，边的值就是两个端点的异或值，这样的好处就在于，在环中的一个点的权值会被相邻边的异或两次，两个相同的数异或就为0，这样就可以保证环的边异或和为0. 考虑这样赋值的方案数，每个点可以有两种选择，在n个点连通的情况下，n个点就有2^n种方案，那么边的方案是多少呢，两个相邻点(x,y)，[x权值为1，y权值为0]和[x权值为0，y权值为1...

题意 n个人排成一排，分成两组，第i个人属于a[i]组，每个人有一个能力值b[i]，从左往右每个人在第i秒执行一次动作，可以把前面不属于自己组的且能力值小于自己的消灭。同时有m次操作c[i]，可以在第c[i]秒后把所有前面的人包括自己的能力值增加一，求第n秒后的存活人数。 题解 要找出每个人能消灭前面的人数有多少个很难，那么我们考虑第i个人会不会被消灭。做这种题首先要分析清楚随着时间的变化什么是不变的。走两个样例可以看出，如果第j个人在第j秒能消灭第i个人，那么无论第j秒后，他俩的能力值怎么变化，能力值的差值一定是不变的，换句话说，如果第j个人能消灭第i个人，那么在第j秒后，第j个人还是可以消...

F Infinite String Comparision 题意 对于字符串x，定义 为字符串x重复无限次形成的字符串。给定字符串a,b，比较 和 的字典序大小。 题解 重复无限次肯定是不行的，多举几个样例发现，将长一点的字符串重复一次，短的字符串去和它去比较，不够则重复，直到重复了一次的长的字符串比完，就能得出结果。这虽然能过，但不会证。正确解法根据一个定理，只需要比较a,b字符串的前 len(a)+len(b)-gcd(len(a),len(b)) 就行。 代码 #include <bits/stdc++.h> using namespace std; #define INF ...

Who Gets the Most Candies? 题目 N children are sitting in a circle to play a game. The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from the K-th child, who tells all the others the integer on his card and ...

康托展开——全排列的本质 参考链接 X=a[n]* (n-1)!+a[n-1] * (n-2)!+…+a[i] * (i-1)!+…+a[1]*0! 1.求一个排列是原排列的按字典序的第几个排列。 #include<cstdio> #include<iostream> using namespace std; int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; // 阶乘 int cantor(int *a, int n) { int x = 0; for (int i = 0; i < n; ...

hdu4027题解——线段树 题意： n个数，m次询问： 0 l r ：将[l, r]内的数取根号并向下取整。 1 l r ：输出[l, r]区间和。 思路：线段树，维护区间和。 坑点：l 可能会大于 r，需要剪枝，否则直接TLE，当值为1时不需要再取根号了，剪枝后500ms左右。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 10; const int MAXN = 4 * N; struct node { ll l, r, val; }t[MAXN]...

hdu3974题解——线段树，dfs构建结构 题意：一个公司有N个人，编号1-n，除公司老总外，每个人都有一个上司，每个成员都有若干个或0个下属（一个成员的下属的下属还是他的下属），形成树结构，为公司的人分配任务i，若分配给成员x（可以是老总），则x和他的下属的任务都变为i；m次询问，两种情况，情况一询问某个成员的任务，情况二将成员x和他的下属的任务更改为y； 解法：将树结构构建为线性结构，用dfs求出成员x的下属区间（dfs可以用来求该节点管理的区间范围），然后就直接用线段树解。 dfs建立线性结构的时候可以先找到根结点，从根结点开始dfs，这样每个结点就只访问一次，可以减少时间和内存，但这...

洛谷P4315 //Change k w：将第k条树枝上毛毛果的个数改变为w个。 //Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。 //Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问： //Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。 //这题的重点在两个标记的同步问题和边权变点权问题，当改变权值时，要把节点的加的lazy置为0，增加 加的操作时lazy直接加 //pushdown的时候先操作置换的标记再操作加法的标记 //然后是边权改点权，因为只有N- 1条边，所以就把边的...

洛谷P4949 最短距离 给出一个 n 个点 n 条边的无向连通图。 你需要支持两种操作： 修改 第 x 条边的长度为 y ； 查询 点 x 到点 y 的最短距离。 共有 m 次操作。 思路 n个点n条边的无向连通图（简单图），如果少一条边就是形成一棵树，就是一道LCA题，这题多了一条边，就要用相应的方法处理这条边。 考虑剔除的边是(uu,vv)，权值为w，那么 (u,v) 的最短距离就是 min(dis(u,v),dis(u,uu)+dis(v,vv)+w,dis(u,vv)+dis(v,uu)+w)。 dis(u, v)=dis(root, u) + dis(root, v) - 2 * ...

树上主席树 在树上根据dfs序建立主席树。 题目 给定一棵 n 个节点的树，每个点有一个权值。有 m 个询问，每次给你 u,v,k，你需要回答 u xor last 和 v 这两个节点间第 k 小的点权。 其中 last是上一个询问的答案，定义其初始为 0，即第一个询问的 u 是明文。 维护主席树，每个节点代表这个下标的数出现的次数。 用u点的主席树+v点的主席树-lca(u,v)的主席树-lca(u,v)父节点的主席树，在这样产生的主席树上查找第k小的排名。 注意 在dfs的时候就建立主席树，这样求的前缀和就是按照从根到该节点的值（用dfn数组建立的树是错的，太菜不知道为什么，也许是什么地方...

题目链接 询问区间内不同数的个数 做法一：树状数组做法：离线处理，将以r从小到大排序，一个标记数组记录数出现的位置，树状数组里只记录当前所有相同的数的最右位置，这样一个数就只会被加一次。  #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 7; #define lowbit(i) i&(-i) int sum[maxn]; int n, m; void add(int x, int C) { for (int i = x; i <= n; i += lowbit(i)) sum[i...

题目链接 题意 给出一个序列，问区间[l, r]中所有不同元素出现的第一个位置（取最左）组成的序列中的第k/2个，k是区间不同数的个数。 第i个询问区间依赖于第i-1个询问的答案，所以是强制在线的。 思路 区间第k个，显然是主席树，和查询区间不同数的个数一样，都是相同的数只取一个，但这个是取相同数的最前面一个，所以在建树的时候倒过来建就可以满足要求，然后要查询位置第k/2的数的位置，所以先求出这个区间[l,r]内不同数的个数，然后直接询问区间第k/2就可以。 #include <bits/stdc++.h> using namespace std; const int maxn =...

题目链接 题意 给n个石头的坐标，要求从一个石头到另一个石头路径上石头之间的长度的最小最大距离。 思路 最短路的变形，dijkstra算法是有一个核心条件，d[v] > d[u] + cost[u][v]则替换，因为到v的距离有更小的，这里可以用d[v] > max(d[u], cost[u][v])，表示的意思是到v节点如果存在到u节点路径中的最长距离小于到v节点路径中的最长距离，就替换掉，至于加一个max是因为(u,v)这条边也在到v的这条路径上，所以要取最大值。 #include <iostream> #include <cstdio> #includ...