wiki 说明 mt19937 是一个随机数生成器类，效用同 rand()，随机数的范围同 unsigned int 类型的取值范围。 其优点是随机数质量高（一个表现为，出现循环的周期更长；其他方面也都至少不逊于 rand()），且速度比 rand() 快很多。使用时需要 #include<random>。 mt19937 基于 32 位梅森缠绕器，由松本与西村设计于 19...

Code.cpp // -std=c++17 -lm -O2 -Wall -Wl,-stack=2147483647 // #pragma GCC optimize(3, "Ofast", "inline") #include <bits/stdc++.h> using namespace std; #define F(i, a, b) for(int i = a, i##e...

比赛传送门 E. Rendez-vous de Marian et Robin 题意：有边权无向图，两人从两个起点出发，在某些节点有使自己速度加倍的道具（永久生效），求两人碰头的最短时间。$n,m\leq 2\times 10^5$。保证边权为偶数。 显然是分层图，在这些特殊节点向下层连一条有向边，下层的边权减半。 跑两遍 Dijkstra，枚举节点计算答案最小值。 $w_i\le...

比赛传送门 CDE 写不出来真是给他烂完了。更多的蔬菜。 A. Zhan’s Blender 题意：一个栈每秒最多可以弹出 $x$ 个数，我每秒可以最多往栈里放 $y$ 个数，求栈弹出 $n$ 个数最短时间。 显然我使劲往里面放就行了，栈使劲弹出就行了。 [ans=\left\lceil\dfrac{n}{\min(x,y)}\right\rceil] Code ans = n...

比赛传送门 A. Simple Palindrome 题意：构造一个长度为 $n$ 仅含 aeiou 的字符串，最小化回文子串的数量。 显然尽可能让 aeiou 均摊 $n$。 那么显然接下来要么扎堆要么挨个排。 如果挨个排，那么扎堆自己组成的回文串依然存在，并且会新增其他的回文串；而自己扎堆只会产生关于自己的回文串。所以我们有理由断言，应该扎堆排。 Code int n, s...

0x01 P10287 最长不下降子序列 题意：求出在 DAG 上的最长不下降子序列。$n,m\leq 10^5,1\leq A_i \leq 10$。 首先，最长不下降子序列怎么求？ 设计状态： $f_i$ 表示到点 $i$，最长不下降子序列的最长长度。 不行。每条边转移一次，更新一次的时间复杂度为 $O(n)$，总的时间复杂度为 $O(nm)$，TLE。 注意 $1 \...

比赛传送门 A. Dora’s Set 题意：在 $[l,r]$ 的整数中选择三个两两互质的数删掉，要求尽可能多删，求最多的删除次数。 和质数相关，考虑奇偶性。 显然三个数至多有一个偶数（否则gcd不小于2，矛盾）。 为了尽可能利用 $[l,r]$ 中更多的数字，考虑使用连着的数字：$ a=2n - 1, b=2n, c=2n + 1$，设 $d = \max {\gcd(a,b),...

A* (A-Star) 是一种搜索算法，对于有多个节点的路径求出最低通过成本。 过程 定义： $g$ ：初始状态到当前状态的距离函数； $h$ ：当前状态到最终状态的距离函数（估计）； $h^{\ast}$ ：当前状态到最终状态的距离函数（精确）； $f = g + h$ ：每个点的评估函数。 条件： 如果 $h \leq h^{\ast}$ 恒成...

题目背景 请选手注意，即使你曾经游玩过与题目中提到的游戏类似的其他游戏，也请你仔细阅读题目描述，否则任何因题目阅读不仔细而导致的失分将不予申诉。 $awa$ 最近在玩一款名叫 “昨夜圆车” 的手机游戏。作为一款优秀的手机游戏，它的游戏数值必然是令人称赞的。最近，她在观看 “皿狠皮车” 的直播间时，不时传出 “超大杯！”“超小杯！” 等声音。这不神奇吗，细看主播原来在拿 Excel...

当 $n$ 不太大，又不能直接爆搜的情况下，我们使用 meet in the middle 的搜索技巧。 过程是，取一个 $mid$，对前后两端分别搜索，如果两端的结果拼接后满足题意，则可以计入答案。 这个方法可以将 $O(2^n)$ 的复杂度降为 $O(2^{n/2})$。 P2962 [USACO09NOV] Lights G 题意： $n$ 点 $m$ 边无向图，每个点初始状态...