WORIA

http://acm.hdu.edu.cn/contests/contest_show.php?cid=881 1007 - Tokitsukaze and Rescue   题意：n 个点的完全无向图，要求删掉k条边，使得剩下的图上的从 1 到 n 的最短路最长。(3≤n≤50,1≤k≤min(n−2,5))(3≤n≤50,1≤k≤min(n−2,5))(3≤n≤50,1≤k≤min(n−2,5)) 杭电似乎有道题是删掉 1 条边，要最短路最长，需要先求出最短路，再遍历最短路上所有边，比较删掉哪个后新的最短路最长。 本题也类似，只是要dfs k 次，每次都求最短路，再删最短路上边。 但是这样复杂度就是 O(n2ck)O(n^2c^k)O(n2ck) （Dij完全图 n2n^2n2 求最短路）。 其实说白了就是暴搜，所以复杂度是个问题。 出题人大佬说：假设一条路长度A，另一条长 B，A > B，然而 A 成为最短路，说明 A 上所有边权和 sumAsum_AsumA​ 大于 B 上所有边权和 sumBsum_BsumB​，而 sumA=∑i=1Arand(),sumB=∑i=1B ...

http://acm.hdu.edu.cn/contests/contest_show.php?cid=880 1001 - Total Eclipse   题意：给定一张无向图，每点有点权，每次操作选一个联通子图，每点点权-1，问最少多少次操作后所有点点权都为 0 . 并查集+贪心 贪心地每次选择最大地联通子图，所有点权-1，直到有些点权为 0，再选择分裂开的新的联通子图，直到所有点权都为 0. 这样就要分治，每次找到分裂点，时间不够。所以点权减少行不通就要逆向考虑。 考虑在全是 0 的图上加点权。 按照点权从大到小排序，点权最大的先放进图里，以后每次操作一定都会选它。 加入一个新点时，要把新图上的所有点的点权都+1，由于每个联通块算作一次操作，所以操作数就是加上图上加入新点后的联通块个数。 由于点权可能不是连续的，所以每加入一个点，操作数还要乘上新点权和上一个点权的差值。 用并查集维护联通块合并，同时为了动态记录联通块个数，还要一个set，每次旧点向新点合并，并把旧点删掉，加入新点。 1234567891011121314151617181920212223242526272829 ...

http://acm.hdu.edu.cn/contests/contest_show.php?cid=888 1004 - Permutation Counting   题意：有一个大小为 n 的排列，给定了相邻元素的大小关系，问合法排列的个数。 dp dp[i][j]dp[i][j]dp[i][j] 表示到第 i 位，第 i-1 位为 j，合法的排列数。 如果当前位比前一位大： dp[i][j]=∑k=1j−1dp[i−1][k]dp[i][j]=\sum_{k=1}^{j-1}dp[i-1][k]dp[i][j]=∑k=1j−1​dp[i−1][k]。 如果当前为比前一位小：dp[i][j]=∑k=ji−1dp[i−1][k]dp[i][j]=\sum_{k=j}^{i-1}dp[i-1][k]dp[i][j]=∑k=ji−1​dp[i−1][k]。 用 sum 记录和。 其实把dp的意义变为 到第 i 位，第 i-1 位为前 i-1 个数中第 j 大的数 更容易理解。 因为只要大小关系不变，数字改变，结果仍然不变。比如最大的数从10变为1000，合法排列个数仍然不变。 把数 j ...

http://acm.hdu.edu.cn/contests/contest_show.php?cid=879 1005 - Fibonacci Sum   题意：给定 N，C，K，(1≤N,C≤1018,1≤K≤105)(1≤N,C≤10^{18},1≤K≤10^5)(1≤N,C≤1018,1≤K≤105)，FiF_iFi​ 为斐波那契数列的第 i 项。求 (F0)K+(FC)K+(F2C)K+⋯+(FNC)Kmod  1000000009(F_0)^K+(F_C)^K+(F_{2C})^K+\cdots+(F_{NC})^K \mod 1000000009(F0​)K+(FC​)K+(F2C​)K+⋯+(FNC​)Kmod1000000009。 二次剩余 几乎是原题了，ZOJ3774 先看原题，求前 N 个斐波那契数的 K 次方和。 数据很大没法矩阵快速幂，只能用通项公式求。 Fi=15[(1+52)i−(1−52)i]F_i=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^i-(\frac{1-\sqrt{5}}{2})^i] Fi​=5​1​ ...

B. Number Circle   题意：环形排列给定的数列，使得每个数小于 它相邻的两个数之和。 先安排好最大的数，只有在它两边放第二，第三大的数才可能满足。接着把整个数列剩下的数从大到小放就好了，由于每个数一定与某个比它大的数相邻，所以一定满足条件。 1234567891011121314151617181920212223#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<ll, ll> pii;const int INF = 0x3f3f3f3f;const int maxn = 1e5 + 10;int n;int a[maxn];int main() { scanf("%d", &n); for (int i = 0; i < n; i++)scanf("%d", &a[i]); sort(a, a + n); swap(a[n-1], a[n-2]); for (int i = ...

https://codeforces.com/gym/102979 F. Find the XOR   题意：给定一张带边权无向图，定义一条路径的长度等于路径上所有边的异或和，定义 d(u,v)d(u,v)d(u,v) 为所有 uuu 到 vvv 的路径中最长的路径长度（不需要是简单路径），多次询问，每次给定 l,rl,rl,r，问对所有 l≤i<j≤rl\le i<j\le rl≤i<j≤r，d(i,j)d(i,j)d(i,j) 的异或和。 线性基 [WC2011] 最大Xor路径 的增强版 给定 u,vu,vu,v，求 d(u,v)d(u,v)d(u,v) 的方法与WC2011相同，先dfs找出一些环，放进线性基里，任意找一条 u,vu,vu,v 的路径，通过找到与环的最大异或和。 设 D[u]D[u]D[u] 表示 uuu 到 1 的路径长度，则 d(u,v)=D[u]⊕D[v]⊕Maxd(u,v)=D[u]\oplus D[v]\oplus \text{Max}d(u,v)=D[u]⊕D[v]⊕Max，其中 Max\text{Max}Max 为线性基中与 d( ...

http://codeforces.com/gym/103049 J. Joint Excavation 题意：给定一张连通的无向图，要求给出一条链，把链从图上去掉，把图切成若干个连通块，给每个连通块分配颜色 1 或 2，要求两种颜色的点数相同。给出链以及颜色划分。 dfs 很妙的dfs题。 下面称颜色 1 的点集为 A，颜色 2 的点集为 B，链的点集为 C。   初始把所有点分到点集 A。 任选一点开始dfs，遇到之前没有访问过的点则把该点从 A 去掉，分到点集 C，即链上。 当对一个节点的访问结束后，把该点再从点集 C 中去掉，分到点集 B。 期间检查当 A，B 大小相同时exit。   可以发现这三个点集分别对应dfs中的不同状态：A 表示为访问状态，B 表示访问结束，C 表示正在访问。 dfs中访问结束的点必定不会与未访问的点相邻，否则一定会先去访问那个未被访问的点。 而正在访问的点也一定是一条链，这也正是深度优先搜索的特性。 访问结束的点是可能与多个正在访问的点相邻的，但这些正在访问的点一定构成一条链。 12345678910111213141516171819202122 ...

http://codeforces.com/contest/1468 H. K and Medians   题意：给定 n,kn,kn,k，数列 aaa 初始为 1−n1-n1−n 的排列，每次操作选择长为 kkk 的子序列，除中位数外全部删去，问能否变为给定的数列 bbb。 思维 考虑最后一次删除，一定是选择以 bib_ibi​ 为中位数的某个序列，现在先把这个序列补上去，则 bib_ibi​ 左边需要被删除的数的个数为 ⌊k2⌋\lfloor\frac{k}{2}\rfloor⌊2k​⌋，右边需要被删除的数的个数为 ⌊k2⌋\lfloor\frac{k}{2}\rfloor⌊2k​⌋。现在要看能否从倒数第二次删除前的数列得到最后一次删除前的数列。 假设倒数第二次删除前的数列中在 bib_ibi​ 左边的需要被删除的数的个数大于 2×⌊k2⌋2\times\lfloor\frac{k}{2}\rfloor2×⌊2k​⌋，则右边需要被删除的数的个数小于 2×⌊k2⌋2\times\lfloor\frac{k}{2}\rfloor2×⌊2k​⌋，则在倒数第二次删除操作中可以从 bib_i ...

http://codeforces.com/contest/1510 B. Button Lock   题意：给定n个长度为d的01串，一个初始全为 0 的串S，要S的对于1到d每个位置按照一定顺序置为1，使得对于每个01串，存在某一时刻S等于该串，‘R’ 操作可以将S串全部置0，要求给出最短的操作序列。 最小路径覆盖+贪心 每个01串作为一个节点，若 u 为 v 的子集，则 u，v 连边，每有一条路径就相当于有一个 ’R‘ 操作，则问题变为最小化 路径数+每条路径的代价。一条路径的代价等于这条路径上最大的点包含的 1 的个数，这个最大的点一定是这条路径的一个端点。 最小路径覆盖要转化为二分图匹配。匈牙利算法就是每次尝试把新点加入匹配，要注意只会调节已配对的对象，而不会减少已配对的个数。 又因为一定是从含 1 多的点开始更优（含1多的总是能走到含1少的），所以把所有点按照包含 1 的个数排序后，贪心地从大到小遍历尝试加入匹配。 最后输出路径。 123456789101112131415161718192021222324252627282930313233343536373839404 ...

https://codeforces.com/contest/1425 E. Excitation of Atoms   题意：有n个原子，可以选任意个激活，每个原子有激活后得到的能量与激活需要花费的能量，还有这个原子指向的另一个原子的编号，初始时所有原子指向它后一个，最后一个原子不能指向。如果一个原子处于激活状态，它所指向的原子也会自动处于激活状态，如此链式反应。要求改变K个原子的指向，问最大能净获得的能量。(4≤N≤105,0≤K<N)(4 \le N \le 10^5, 0 \le K < N)(4≤N≤105,0≤K<N) 贪心+模拟 很恶心的细节题，对着数据改程序才勉强过0.o 如果K=0，就是选一个最大的后缀。 如果K=2，激活任一点，都可以遍历所有点，设激活x，则x->1，x-1->x+1。所以只要枚举所有点作为手动激活的那个点。 如果K>2，总可以浪费掉多出的几次机会，变为K=2，如K=3时，可以x->2,x->1,x-1>x+1。 如果K=1，分两种情况：从1进入，由于K=1，所以必须跳过后面某个点，直接枚举。从后 ...