All Your Paths are Different Lengths 题目链接：https://atcoder.jp/contests/arc102/tasks/arc102_b 题解： 构造题有技巧，如果题目中要求了20和60，那就从这里入手好了。 发现没法入手因为太平凡了.... 但是，他要求了每种值只出现了一次，容易联想到弄出来$log$个$2$的幂次。 诶？想到这里发现，$20$好像差不多就是$log$大小。 我们就放$20$个点，第$i$个点指向第$i + 1$个点两条边，$2^{i - 1}$和$0$。 发现不能放20个因为有可能爆，那就放恰好$log$个就...

[Poi2012]Tour de Byteotia 题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3060 题解： 这类题有一个套路，就是他不要求的点可以随便搞。 我们只需要保证前$k$个点是对的就行。 因此，如果一条边的有至少一个是关键点的端点，我们设当前边是关键边。 有结论：只删关键边一定是最优的。 然后枚举就行了。 代码： #include <bits/stdc++.h> #define N 1000010 using namespace std; char *p1, *p2, ...

[Poi2012]Tour de Byteotia 题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3060 题解： 这类题有一个套路，就是他不要求的点可以随便搞。 我们只需要保证前$k$个点是对的就行。 因此，如果一条边的有至少一个是关键点的端点，我们设当前边是关键边。 有结论：只删关键边一定是最优的。 然后枚举就行了。 代码： #include <bits/stdc++.h> #define N 1000010 using namespace std; char *p1, *p2, ...

动物园zoo 题目大意：https://www.lydsy.com/JudgeOnline/problem.php?id=1151 题解： 我们发现每个点只会往右延伸$5$个，这个数非常小。 再加上每个动物只有选和不选，很容易想到把每个点后面$5$个给状压到一起。 想到这里就好办了，随便弄个数组搞一搞就好。 代码： #include <bits/stdc++.h> #define N 50010 using namespace std; int n, c, f[N][35], bu[N][35], last, ans; char *p1, *p2,...

Do Not Duplicate 题目链接：https://atcoder.jp/contests/agc036/tasks/agc036_b 题解： 首先最后肯定至多只有$n$个数。 我们想处理出来每个点下一个一样的数的下一个数。 有点绕口....处理出来了之后，暴力找环然后暴力跳就好。 代码： #include <bits/stdc++.h> #define N 200010 using namespace std; typedef long long ll; int a[N], pre[N], nxt[N], val[N]; char *p...

Triangle 题目链接：https://atcoder.jp/contests/agc036/tasks/agc036_a 题解： 我开始的时候以为是$Millar-Rabin$加$Pollard-Rho$快速分解质因数。 结果啊.... 要是$S$是个质数啥的咋办..... 所以啊，我们换一种思考问题的方式。 首先，一定可以存在一个点是$(0,0)$，就假设三号点是原点好了。 那么面积的等式可以用三角形的叉积被表示为$X_1Y_2 - X_2Y_1 = S$。 设$X1=10^9$，$Y1=1$即可。 代码： #include <bits/stdc+...

[JLOI2013]地形生成 题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3193 题解： 这种求总排列的题，一种常规做法就是所有的元素按照某种排列方式然后一个一个往里插。 这个题就是从大到小排序这样，对后面的元素没有影响。 现在有一些相等的元素我们怎么弄？ 如果是标号序列的话，就是瞎$jb$排就行了。 如果是等高线序列的话，只要按照$a$作为第二关键字就好。 代码： #include <bits/stdc++.h> #define N 1010 using namespace std...

火花灿灿 题目：   数据范围： 题解： 这个题真的是个神仙题。 我们对于每块石头维护一个$01$串。 这个$01$串的长度是操作次数。 如果$01$串的当前位是$1$，表示这次操作中当前石子被划分到了贡献当中，就是被划分到了$b_i$中。 那么如果所有的石子都单独一堆，必定是所有的$01$串都互不相同。 而且有一个限制就是每一列最多$m$个。 显然$01$的长度具有单调性。 故此二分答案之后考虑怎么验证。 我们相当于在一个$n\times mid$的棋盘上添$1$使得满足要求。 首先有一个贪心，就是对于每一行来讲，能添$k$个数绝对不填$k + 1$个...

「LibreOJ NOIP Round #1」旅游路线 题目链接：https://loj.ac/problem/539 题解： 这个题就很神奇 首先大力$dp$很好想，因为可以把一维放到状态里以取消后效性。 然后就能倍增了...因为就是个**$dp$ 我没想出来/px 代码： #include <bits/stdc++.h> #define N 110 #define M 1010 #define K 30 #define inf 0x3f3f3f3f using namespace std; int g[N][N][K], p[N],...

「SDOI2017」相关分析 题目链接：https://loj.ac/problem/2005 题解： 把上面的式子拆掉，把下面的式子拆掉。 发现所有的东西都能用线段树暴力维护。 代码： #include <bits/stdc++.h> #define N 100010 #define ls p << 1 #define rs p << 1 | 1 using namespace std; typedef double db; typedef double ll; ll sum[N << 2], tagx1[...

独钓寒江雪 题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3162 题解： 首先，如果没有那个本质相同的限制这就是个***题。 直接树形dp就好。 那么如果加上那个限制呢？ 我们发现，无论最后怎么本质相同，树的重心一定不变。 故此，从重心开始去重即可。 参考：https://www.cnblogs.com/zhoushuyu/p/9295759.html 代码： #include <bits/stdc++.h> #define N 500010 using namespace std;...

[HEOI2012]旅行问题 题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2746 题解： 这个是讲课时候的题。 讲课的时候都在想怎么后缀自动机.... 当然是能做啦，$SAM$这么强。 实际上是个$AC$自动机，按照题目模拟就行了。 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1 << 20 ; const int mod = 100000000...