膜拜博弈论带我上 Rank1。Rank
诶 好像把7咕了，那就咕吧。
A. 基础的生成函数练习题（gf）
先给 \(a\)，\(b\)，\(c\) 按升序排个序，求出相邻两数之差。
若较小的两数之差（\(a\) 和 \(b\)）为奇数，先操作 \(\lfloor{\frac{b-a}{2}}\rfloor\) 次使 \(a=b-1\)，再操作 \(c-b\) 次使 \(a=c-1\)，\(b=c\)，再操作两次让 \(a+=2\)，\(b,c+=1\)即可，共需要 \(\lfloor{\frac{b-a}{2}}\rfloor+(c-b)+2\) 次操作。
若差为偶数，先操作 \(\frac{b-a}{2}\) 次使 \(a=b\)，再操作 \(c-b\) 次使 \(a=b=c\) 即可，共需要 \(\frac{b-a}{2}+(c-b)\) 次操作。
太简单，不放码了。
B. 简单的拉格朗日反演练习题（lagrange）
原[CF1706E] Qpwoeirut and Vertices
恼了，只打出 \(20pts\) 暴力，看我狂补最小生成树。
但正解可以不用最小生成树。我继续了上午并查集的思想，发现维护好的话是可行的。
首先，题目可以翻译成：按给出的顺序，最少在图中连几条边之后满足 \(\left[l,r\right]\) 内所有点都在同一联通块内。
设 \(min_i\) 为最少加了多少边之后满足 \(i\) 与 \(i+1\) 在同一连通块内。这样的话答案就转化成了求 \(\max_{i=l}^{r-1} min_i\) 的值。
求 \(min_i\) 的值时考虑用启发式合并，判断给出边的两个端点是否在同一连通块内，若否则将小的联通块合并到大的上，按顺序求出每个点的 \(min_i\) 值。
查询方面，已经确定了是区间找最大值，那么直接献出我最爱的线段树。
复杂度不知道是多少，大概在 \(\mathcal{O(nlogn)}\) 左右，请大佬们指正。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx int
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=2e5+5;
int n,m,q;
int fx[N];
int tre[N<<2],minn[N];
int siz[N];
vector<int>G[N];
namespace Wisadel
{
int Wfind(int x)
{
if(fx[x]==x) return x;
return fx[x]=Wfind(fx[x]);
}
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
void Wpushup(int rt)
{
tre[rt]=max(tre[ls],tre[rs]);
}
void Wbuild(int rt,int l,int r)
{
if(l==r)
{
tre[rt]=minn[l];
return;
}
Wbuild(ls,l,mid),Wbuild(rs,mid+1,r);
Wpushup(rt);
}
int Wq(int rt,int l,int r,int x,int y)
{
if(x>y) return 0;
if(x<=l&&r<=y) return tre[rt];
int res=0;
if(x<=mid) res=max(res,Wq(ls,l,mid,x,y));
if(y>mid) res=max(res,Wq(rs,mid+1,r,x,y));
return res;
}
short main()
{
n=qr,m=qr,q=qr;
fo(i,1,n) G[i].clear(),G[i].push_back(i),fx[i]=i,siz[i]=1,minn[i]=1e9;
fx[n+1]=n+1;
fo(i,1,m)
{
int a=qr,b=qr;
a=Wfind(a),b=Wfind(b);
if(a==b) continue;
if(siz[a]>siz[b]) swap(a,b);
siz[b]+=siz[a];fx[a]=b;
for(int j=0;j<G[a].size();j++)
{
int v=G[a][j];
if(Wfind(v)==Wfind(v+1)) minn[v]=min(i,minn[v]);
if(Wfind(v)==Wfind(v-1)) minn[v-1]=min(i,minn[v-1]);
G[b].push_back(v);
}
G[a].clear();
siz[a]=0;
}
Wbuild(1,1,n-1);
while(q--)
{
int a=qr,b=qr;
printf("%d\n",Wq(1,1,n-1,a,b-1));
}
return Ratio;
}
}
int main(){return Wisadel::main();}
对了，还有一个疑问，这样改有什么必要性吗。
C. 容易的多元拉格朗日反演练习题（multi）
没想到是黑啊。
直接挂我中午写的题解了。
D. 朴素的抽象代数题（algebra）
一点也不朴素好吧，题目还没搞清楚，%%% HDK 赛时打出 25pts 暴力。
挂个抽象玩意。
点击查看高级背景
题面高级，但感觉不如 Delov 主题的。
完结撒花~
