WORIA

https://www.lydsy.com/JudgeOnline/problem.php?id=1023 题意：求仙人掌图的直径（最远两点的最短距离）。 同样，首先考虑树的直径求法。 dp[i]dp[i]dp[i] 表示以 iii 为根的子树中点与 iii 的最远距离。 ansansans 表示树的直径。 dp[u]=max(dp[v]+1,(u,v)∈E)dp[u]=max(dp[v]+1,(u,v)\in E) dp[u]=max(dp[v]+1,(u,v)∈E) ans=max(dp[u]+dp[v]+1,(u,v)∈E)ans=max(dp[u]+dp[v]+1,(u,v)\in E) ans=max(dp[u]+dp[v]+1,(u,v)∈E) 根据套路，还是把环单独拿出来处理。 考虑怎么扫一遍环求出所有与环上点有关的直径。 对于环上两点 u,vu,vu,v，经过这两点的最长路径为 dp[u]+dis[u][v]+dp[v]=dp[u]+dp[v]+min(abs(depth[v]−dep[u]),C−abs(depth[v]−depth[u]))dp[u]+dis[u] ...

https://atcoder.jp/contests/arc105/tasks C - Camels and Bridge   题意：有一座桥，分为 m 部分，每部分长度为 l[i]l[i]l[i]，最大承重为 v[i]v[i]v[i]，有 n 个骆驼，每个重量为 w[i]w[i]w[i]，所有骆驼从桥的一头开始按照某个顺序依次过桥，且相互距离保持不变，每部分桥上的重量不能超过这部分的最大承重，每部分桥两端点的重量不算。要安排过桥顺序和相互的距离，使得桥不塌，且首尾两个骆驼的距离最小，输出最小距离。 枚举+贪心 n 很小，可以枚举排列。所以现在需要在给定排列下，求最短长度。 贪心使得每个骆驼与它前一个的距离最小。 对于一只骆驼，它前面所有骆驼的距离都确定了，需要检查它与前面的所有骆驼，保证如果它们在一个部分，它们的重量之和不超过承重。但不好算距离。 所以考虑对一些骆驼，如果它们重量和为 sum，它们首尾最短需要保持的长度。这可以通过预处理桥的每一部分得到。 这样就可以枚举骆驼的区间，计算当前骆驼与前一只最小要的距离。 123456789101112131415161718192021 ...

https://atcoder.jp/contests/arc104/tasks C - Fair Elevator   题意：在 1 到 2n 的数轴上给定 nnn 个区间，定义一组合法的区间集合：所有端点恰被使用一次，交叉的区间长度必须相同。给定的区间中有 -1 表示数据缺失，问给定的区间集合是否有可能为合法的区间集合。 区间dp 合法区间的形式显然是如上图这样的。要么是能分成左右两部分都是合法区间，要么自己是一个最小的合法区间。 最小的合法区间：区间长度为偶数，且左半区间只有左端点，右半部分只有右端点，且所有区间长度都为总长度的一半。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <bits/stdc++.h>using namespace std;#define ll long long#define debug(x) cout << #x < ...

https://atcoder.jp/contests/agc049/tasks B - Flip Digits   题意：给定两个长为n的01串s，t，每次操作对于s串，选择一个为1的位置，并同时翻转该位置和左边一位，问最少操作次数使得两串相同。 贪心 画几个能发现每次操作相当于把1往左移动一位。 从左向右遍历，当 s 不等于 t 时，找到该位右边最近的1，移动到该位右边，翻转这个1，使得 s 在该位等于 t 。 123456789101112131415161718192021222324252627282930#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define ll long longconst int N = 2e6 + 10;const int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f ...

https://atcoder.jp/contests/agc048/tasks B - Bracket Score   题意：给定A，B数组，要用 ‘(’, ‘)’, ‘[’, ‘]’ 构造出合法的括号序列，若位置 iii 为 ‘(’ 或 ‘)’，则该位置贡献 AiA_iAi​，否则贡献 BiB_iBi​，求最大总贡献。 贪心 先把所有位置上都放小括号，由于题目规定了 n 为偶数，所以必定合法。 再尝试修改一些位置上为中括号，每次选择两个间隔为偶数，且都为小括号的位置，并修改，这样每对小括号以及每对中括号的长度都为偶数，必定能够构造出合法序列。 所以只要贪心地每次选择一对修改后贡献最大的位置变为中括号。 123456789101112131415161718192021222324252627282930#include <bits/stdc++.h>#define debug(x) cout << ##x << ":\t" << (x) << endl;using namespace std;#def ...

https://atcoder.jp/contests/agc047/tasks A - Integer Product   题意：给定一个实数数列，0<Ai<1040 < A_i < 10^40<Ai​<104，且 AiA_iAi​ 小数点后最多有 9 位，问有几对数相乘得到整数。 由于 AiA_iAi​ 位数有限，因此化为分数后分母上必定是 2p⋅5q2^p\cdot 5^q2p⋅5q，所以如果要相乘得到整数，只需要考虑每个数的 222 和 555 的幂次即可。 由于可能有负幂次，所以要先乘以 10910^9109 确保分母都去掉。乘的过程中又会有误差问题，如果用 (longlong)(longlong)(longlong) 强制转换会有误差，需要用 llround(x⋅1e9)llround(x\cdot 1e9)llround(x⋅1e9). 123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h>#d ...

https://atcoder.jp/contests/agc044/tasks A - Pay to Win   题意：初始有数0，给定目标数字N，1≤N≤10181\le N\le 10^{18}1≤N≤1018，有四种操作：花费 AAA，乘2；花费 BBB，乘3；花费 CCC ，乘5；花费 DDD，加减1。问达到目标数字的最小花费。 考虑从N操作到0，则操作变为除，且必定整除时操作。 操作序列显然是类似DDDDADDBDDDBBDDCC，即一段D然后有ABC，再循环，所以要考虑D到什么时候可能要ABC了，然后dfs下一个状态。 结论是下一个状态为 ⌊N2⌋\lfloor \frac{N}{2}\rfloor⌊2N​⌋ 或 ⌈N2⌉\lceil \frac{N}{2}\rceil⌈2N​⌉，或⌊N3⌋\lfloor \frac{N}{3}\rfloor⌊3N​⌋ 或 ⌈N3⌉\lceil \frac{N}{3}\rceil⌈3N​⌉，或⌊N5⌋\lfloor \frac{N}{5}\rfloor⌊5N​⌋ 或 ⌈N5⌉\lceil \frac{N}{5}\rceil⌈5N​⌉. 下 ...

https://atcoder.jp/contests/agc043 A - Range Flip Find Route 题意：给定一个黑白矩阵，要求从左上角走到左下角，只能向右或者向下走，且只能走白格，每次操作可以选一个矩形区域反转所有颜色，问最小操作数。 dp 每一格可能从上或者从左转移来，如果转移过来的那个格子是白色，那么当前格就要再翻转，否则可以和前一格一起翻转。虽然可能会翻转其他不需要的格子，但是由于限制了只能向右或下走，所以不会有影响。 1234567891011121314151617181920212223242526272829303132333435#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 3e5 + 10;const int INF = 0x3f3f3f3f;int n, m;char mp[110][110];int dp[110][110];int main() { scanf("%d%d", &n, ...

https://atcoder.jp/contests/abc181/tasks F - Silver Woods   题意：二维平面上有上边界 y=100y=100y=100 和下边界 y=−100y=-100y=−100，在两个边界中间还有一些点，有一个圆要从 (−109,0)(-10^9,0)(−109,0) 移动到 (109,0)(10^9,0)(109,0)，可以沿任何方向移动，但是不能穿过点或者边界，问最大可行的圆的半径。 二分+并查集 二分答案。对于一个已知半径的圆，要判断能否成功移动到目标。 在刘汝佳平面图最小割那部分有一道叫动物园啥的题，讲的就是判断能否从起点到达目标点。有一个很妙的方法。 遍历所有点，如果到上边界距离小于圆的直径则该点向上边界连边，下边界类似。对于一对点，如果它们距离小于直径，则连边。 判断如果上边界存在路径到达下边界，则说明这一个带形区域被分割成了两块，这两块完全不互通，那么这个圆就没法到达目标点。 否则一定能够到达，实际上甚至可以到达任意点。 1234567891011121314151617181920212223242526272829303 ...

https://atcoder.jp/contests/abc175/tasks E - Picking Goods   题意：一张nm的网格，有k格里有物品，价值为 viv_ivi​，从左上角走到右下角，只能向下或向右走，可以拿或不拿格子里的物品，问最大价值。 dp 很简单的dp，写这题的题解不是为了怎么记做这题，而是犯的错误太蠢了。 1234for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) for (int x = 0; x <= 3; x++) dp[i][j][k] = -inf; 调了半天的错误就是上面这个，由于题目里有 k，所以第三重循环我这里用了 x，但是在赋值时却还是用了k。 但是！由于第三维大小只有4，所以这样赋值会导致赋值到不知道什么地方去！！也并不是循环的。 赋值还在dp数组里还好，但是如果到了其他地方，比如 a 数组里而那个a又恰好会用到或者后面会用到的地址，那么就会导致错误！！！ 以后再也不能犯这么傻逼的错了！ 下面是正确代码 1234 ...