ryp的博客为了减少完全以刷号为意义的小号出现，并且将线上可能出现的不恰当行为言论与线下相关联，我们决定 任何账号都必须绑定到 QQ 以进行活动。
具体方法：
加入 QQ 群 1061173220，口令是 wyojyydsrypnb
在群中发消息 /bind XXX，其中 XXX 是你的用户名
WyOJ Musume，也就是 WyOJ 的机器人，会回应你的消息。
根据 WyOJ Musume 的指示来完成操作，绑定成功后，你的账号便可用。
注意：
每个账号只能绑定一个 QQ，但一个 QQ 可以绑定最多三个账号。
若某个账号决定被封禁，其对应的 QQ 会被封禁，对应 QQ 下的所有账号也会被封禁。
递推，比正解还麻烦，略。
超级笨蛋博弈论，找规律。
考虑倒推，剩 $1$ 到 $m$ 张是先手有必胜策略，$m+1$ 是后手有必胜策略。
继续，考虑 $m+2$ 到 $2m+1$，先手方可以将纸牌数控制为 $m+1$，使得对方从 $m+1$ 开始取，进而自己有必胜策略；若 $2m+2$，则不论如何取，剩下纸牌在 $[m+2,2m+1]$ 范围内，后手有必胜策略。
归纳可知，若初始纸牌数 $n$ 为 $m+1$ 的倍数，后手有必胜策略，否则先手有必胜策略。
$n\le 10$，乱搞点暴搜之类的东西大概就可以过的吧（其实我也不知道有什么具体的办法）。
$n\le 10^3$，是不加优化的 DP 做法。
问题的一个难解决的地方就在于分组的实质是选数并建立集合，而不是选取某一段。但要使每个集合中的最大值减最小值（集合即每一组，值即体积，下同）尽可能小，每个集合的元素就一定是排序后的数中某连续的一段，于是直接按物品体积进行排序，这样就可以把集合问题转化为分段问题了。
设 $f_i$ 表示将前 $i$ 个物品进行分组的最小“不整齐程度”，起初 $f_0=0$，有如下转移：
$$f_i=\begin{cases}v_i-v_1 & 1\le i< 2k \\\min \limits_{j=0}^{i-k}(f_j+v_i-v_{j+1}) & 2k\le i\le n \end{cases}$$
对于 $2k\le i\le n$ 的情况，枚举每个 $j$，取最小的 $f_j-v_{j+1}$ 进行转移，$f_n$ 即为最终答案。
转移次数 $O(n)$，转移复杂度 $O(n)$，总的时间复杂度为 $O(n^2)$。
考虑对上述 $O(n^2)$ 的做法进行优化。
复杂度高的原因出在每次取 $\min \limits_{j=0}^{i-k}(f_j-v_{j+1})$ 时需要 $O(n)$ 枚举 $j$，而实际上 $\left [0,i-k \right ]$ 是一个左端静止且右边递增的区间，因此可以直接用一个变量维护这个最值（甚至不需要写单调队列）。
现在，转移次数 $O(n)$，转移复杂度 $O(1)$，DP 的时间复杂度为 $O(n)$，由于排序是 $O(n \log n)$ 的，故总的时间复杂度为 $O(n \log n)$，可以通过此题。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e6+5;
const ll inf=1e18;
int n,k;
ll v[N],f[N],mini;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
}
sort(v+1,v+1+n);
for(int i=1;i<=n;i++)
{
if(i<k*2)f[i]=v[i]-v[1];
else
{
mini=min(mini,f[i-k]-v[i-k+1]);
f[i]=v[i]+mini;
}
}
printf("%lld",f[n]);
return 0;
}$O(n^2)$ 求出任意两点之间的边权（即时间，下同），直接从 $1$ 跑最短路。
考虑边权与坐标的关系，若从一点 $i$ 走到 $j$ 的时间是 $|x_i-x_j|$，且存在另一点 $k$ 满足 $x_k$ 在 $x_i,x_j$ 之间，那么边 $(i,j)$ 可被边 $(i,k),(k,j)$ 代替，也即经过 $k$ 不会使时间更长，这是因为：
$$\begin{aligned} dis_{i,j} &= |x_i-x_j| \\ &= |x_i-x_k| + |x_k-x_j| \\ &\ge \min \left\{ |x_i-x_k|,|y_i-y_k| \right\} + \min \left\{ |x_k-x_j|,|y_k-y_j| \right\} \\ &= dis_{i,k} +dis_{k,j} \end{aligned}$$
纵坐标同理。
对此推广，我们得到结论：对所有点按横坐标排序，相邻点连边，然后纵坐标做相同处理，然后跑最短路即可。边数是 $O(n)$ 的，可以通过此题。
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+5;
const ll inf=1e18;
int n;
struct node
{
int num;
ll x,y;
}dot[N];
bool cmp1(node a,node b)
{
return a.x<b.x;
}
bool cmp2(node a,node b)
{
return a.y<b.y;
}
struct edge
{
int v;
ll w;
};
vector<edge>e[N];
priority_queue<pair<ll,int> >q;
ll d[N];
bool vis[N];
void dijkstra()
{
for(int i=1;i<=n;i++)d[i]=inf;
d[1]=0;
q.push(make_pair(0,1));
while(!q.empty())
{
int u0=q.top().second;
q.pop();
if(vis[u0])continue;
vis[u0]=1;
for(int i=0;i<e[u0].size();i++)
{
int v0=e[u0][i].v,w0=e[u0][i].w;
if(d[u0]+w0<d[v0])
{
d[v0]=d[u0]+w0;
q.push(make_pair(-d[v0],v0));
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
dot[i].num=i;
scanf("%lld%lld",&dot[i].x,&dot[i].y);
}
sort(dot+1,dot+1+n,cmp1);
for(int i=1;i<n;i++)
{
int u0=dot[i].num,v0=dot[i+1].num,
w0=dot[i+1].x-dot[i].x;
e[u0].push_back({v0,w0});
e[v0].push_back({u0,w0});
}
sort(dot+1,dot+1+n,cmp2);
for(int i=1;i<n;i++)
{
int u0=dot[i].num,v0=dot[i+1].num,
w0=dot[i+1].y-dot[i].y;
e[u0].push_back({v0,w0});
e[v0].push_back({u0,w0});
}
dijkstra();
printf("%lld",d[n]);
return 0;
}$O(n^3)$ 超级大暴力，略。
容易知道均衡区间不存在，答案全是 $0$。
建 $ST$ 表维护区间 $min$ 和 $\max$，$O(1)$ 判断一个区间是否合法，时间复杂度 $O(n^2)$。
这一档区分出常数太大的 $\log$ 以及一些神秘复杂度，像根号、$\log^2$ 之类的，放到下面讲。
我们考虑位置 $i$ 成为一个均衡区间的左端点需要满足的限制（右端点同理）：
也就是说，$i$ 符合条件需要右端点 $j$ 足够大。
我们做四次单调栈分别预处理出每个 $v_i$ 的左侧和右侧第一个大于或小于 $v_i$ 的数的位置（不存在则用 $0$ 或 $n+1$ 补充）。左侧的两个位置取 $\min$，记为 $L_i$；右侧取 $\max$，记为 $R_i$。
那么 $[i,j]$ 是均衡区间的充要条件是，$j>R_i$ 且 $L_j>i$。
因此，将所有 $(j,L_j)$ 视为平面上的点，$i$ 的答案即平面上符合上述条件的点的个数，离线下来用树状数组做二位数点即可。注意要离散化。
这个做法有 $O(n\log n)$ 的时间复杂度和 $O(n)$ 的空间复杂度。
import os
import hashlib
def hash (path, method=hashlib.md5):
h = method ()
with open (path, 'rb') as f:
while b := f.read (8192):
h.update (b)
return h.hexdigest ()
q = dict ()
for root, _, k in os.walk ('.'):
for d in k:
i = root + '/' + d
print (i)
h = hash (i)
print (h)
if h in q:
print (f'{i} (Cached from {q[h]})')
os.system (f'ln -sf {q[h]} {i}')
else:
print (f'{i} (Uncached)')
q[h] = iT4 的数据有误，已经修好。
经过我一晚的奋战，WyOJ 已经成功加入了一个 UB 检测器！
具体使用，只需要把语言选为 C++17ubsan，然后重新提交！非常简单也非常好用！！！！！！
然后，点击 Runtime Error 的数据点，可以看到 output 区域包含了具体 UB 信息。
具体的实现是，我把 C++17ubsan 语言的 stderr 输出到了输出文件，于是 output 就会包含原先 stderr 的内容。
如果你的 stderr 内容过多，可能导致 UB 信息被挤掉看不到。 这时可以 #define stderr stdout，然后重新提交。
原先 AC 的点会变成 WA
使用检测器后的代码常数会变大不少，所以可能导致 TLE。
比赛期间看不到 output，所以本功能也自然在赛时无用。
同时，Special Judge 和 Hack 功能也已经修好！
鲁ICP备2025150228号