专题题解 - XXI Open Cup, Grand Prix of Nizhny Novgorod

难度主要是指思维难度。

---

A. Assignment Problem

难度：$\bigstar\bigstar$

题目大意：

有 $m$ 个职位和 $n$ 个应聘者（$m\leq n$），每个职位应分配给恰好一个应聘者。

有收益矩阵 $A_{m\times n}$ 表示每个职位分配给每个应聘者的收益，HR 在安排职位时需要保证总收益最高。

现在 $A$ 不是完全给定的，只是对于所有 $1\leq i\leq m$ 给定 $n$ 个人在第 $i$ 个职位上收益从大到小的排序结果，即对于每个 $i$ 给出排列 $p_{i,1},\ldots,p_{i,n}$，表示 $A_{i,p_{i,j}}>A_{i,p_{i,j+1}}$。

你需要指出，对于每个 $1\leq i\leq n$，是否存在一个可行的矩阵 $A$ 使得第 $i$ 个人可以被应聘。

$1\leq m\leq 11, 1\leq n\leq 1000$

题目解法：

首先我们证明：一定存在一个 $i$ 使得第 $i$ 个职位分配给了 $p_{i,1}$。

否则，假设第 $i$ 个职位选了第 $h_i$ 个人，建立一个有向图，从 $h_i$ 连边到 $p_{i,1}$，在图中从任意一个有出度的点出发任意走一条路径，直到终点没有出度或者回到了起点（可以认为是简单路径，否则中途就有环，因此路径是有限的），沿着路径方向进行一轮调整就得到了一组更优解，矛盾。这就证明了原命题。

因此选人的过程可以这样理解：每次选择一个 $i$，将这个职位分配给 $p_{i,1}$，然后将 $p_{i,1}$ 这个人删掉，再在剩下的职位和应聘者之中重复上述过程。

所以，我们枚举一个 $1,\ldots,m$ 的排列，那么每个职位分配给的应聘者就确定了，我们可以 $O(m^2)$ 求出来，这些人就是可能被应聘的人。

时间复杂度为 $O(m!\times m^2+n\times m)$，事实上常数极小，因此可以通过。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1010;
int n,m,cnt,ans[MAXN],ch[MAXN],flg[MAXN],p[MAXN][MAXN],ord[12],vis[12];
void chk () {
	for (int i=1;i<=m;i++) {
		int j=1;
		while (flg[p[ord[i]][j]]) {j++;}
		ch[i]=p[ord[i]][j];
		flg[ch[i]]=ans[ch[i]]=1;
	}
	for (int i=1;i<=m;i++) {flg[ch[i]]=0;}
}
void dfs (int x) {
	if (x==m+1) {chk();return;}
	for (int i=1;i<=m;i++) {
		if (!vis[i]) {
			ord[x]=i,vis[i]=1;
			dfs(x+1);
			vis[i]=0;
		}
	}
	return;
}
int main () {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++) {
		for (int j=1;j<=n;j++) {scanf("%d",&p[i][j]);}
	}
	dfs(1);
	for (int i=1;i<=n;i++) {
		if (ans[i]) {cnt++;}
	}
	printf("%d\n",cnt);
	for (int i=1;i<=n;i++) {
		if (ans[i]) {printf("%d ",i);}
	}
	return 0;
}

---

B. Lockout vs. Tourist

难度：$\bigstar\bigstar\bigstar\bigstar$

题目大意：

有 $n$ 道题，第 $i$ 道题分数为 $a_i$，你和 Tourist 一起做这些题，规则如下：

• 每一回合，你和 Tourist 分别选出一道题，选择时你们互不了解对方的选项；
• 如果你选的题和 Tourist 一样，那么就删除这道题，如果 $n$ 道题已经删光那么游戏结束并且你获得零分，否则进入下一回合；
• 如果你选的题和 Tourist 不一样，那么游戏结束，你的得分是你这回合选的这道题的得分。

Tourist 想要最小化你的得分，请问 Tourist 在最优策略下，你期望最多能获得多少分，以浮点数形式输出。

$1\leq n\leq 22$

ix35 的注解：Tourist 的决策是基于概率的，也就是可以以一定权重随机选择某道题，而他的目标是使得你在这种情况下任意选择一道题，最大的期望得分最小。

题目解法：

状压 DP，设剩余题目集合为 $S$ 时你的最大期望得分为 $f(S)$。

设 $m=|S|$，其中第 $i$ 题分数为 $a_i$，$S$ 除去第 $i$ 题后你的最大期望得分（这是已经算过的 $f$ 值）为 $b_i$，Tourist 有 $p_i$ 的概率选择第 $i$ 题（$1\leq i\leq m$），那么你的最大期望得分就是：

$$\max(p_i\times b_i+(1-p_i)\times a_i)$$

就是说如果你选了第 $i$ 题，那么 Tourist 有 $p_i$ 概率也选第 $i$ 题，此时这道题被删除，而后你的最大期望得分为 $b_i$，否则你直接获得 $a_i$ 分并结束游戏。

考虑二分答案 $C$，我们现在要判断是否存在 $p_1,\ldots,p_m$，使得：

$$\begin{cases}\sum\limits_{i=1}^mp_i=1 \\ \forall i,\ \ a_i+(b_i-a_i)p_i\leq C \\ p_i\ge 0\end{cases}$$

令 $d_i=\dfrac{C-a_i}{b_i-a_i}$，那么第二个条件告诉我们，如果 $b_i>a_i$ 那么 $p_i\leq d_i$，如果 $b_i<a_i$ 那么 $p_i\ge d_i$（而 $b_i=a_i$ 的情况稍后说明）。

有一个容易证明的结论：存在至少一个 $i$，使得 $b_i<a_i$（考虑最大的 $a_i$ 即可），因此判定条件就可以写为：

$$\begin{cases}\sum\limits_{b_i<a_i} \max(0,d_i)\leq 1 \\ \forall i(b_i\ge a_i),\ C\ge a_i\end{cases}$$

第二个条件是因为当 $b_i>a_i$ 时 $0\leq p_i\leq d_i$，所以 $(C-a_i)(b_i-a_i)\ge 0$，而当 $b_i=a_i$ 时由之前的式子直接得到 $a_i\leq C$。

实际上第二个条件只是给了 $C$ 的一个下界，稍为复杂的是第一个条件：注意到 $d_i>0\iff C< a_i$，所以在这里我们只需要考虑所有大于 $C$ 的 $a_i$，这也告诉我们 $\sum \max(0,d_i)$ 是一个关于 $C$ 的分段线性函数，在每一段上都可以求出它取 $1$ 的点，也就是 $C$ 的最小值。

如果真的去二分，时间复杂度为 $O(2^n\times n\times \log \epsilon^{-1})$，难以通过。

但是根据上面的观察，不需要二分 $C$，只需要分段后在每一段上求一个最值就可以了，时间复杂度为 $O(2^n\times n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=30;
int n,cnt,w[MAXN];
double dp[1<<22];
struct P {
	double a,b;
}p[MAXN];
bool cmp (int a,int b) {return a>b;}
double solve () {
	//sort(p+1,p+cnt+1,cmp);
	double xj=-1.0,res=p[1].a,k=0.0,b=0.0;
	for (int i=1;i<=cnt;i++) {
		if (p[i].b>p[i].a) {xj=max(xj,p[i].a);}
	}
	p[cnt+1].a=0.0;
	for (int i=1;i<=cnt;i++) {
		if (p[i].b>p[i].a) {break;}
		k-=1.0/(p[i].a-p[i].b),b+=p[i].a/(p[i].a-p[i].b);
		double tmp=(1.0-b)/k;
		if (tmp<=p[i].a) {res=max(p[i+1].a,tmp);}
	}
	return max(xj,res);
}
int main () {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {scanf("%d",&w[i]);}
	sort(w+1,w+n+1,cmp);
	for (int i=1;i<(1<<n);i++) {
		cnt=0;
		for (int j=0;j<n;j++) {
			if (i&(1<<j)) {
				cnt++;
				p[cnt].a=w[j+1],p[cnt].b=dp[i^(1<<j)];
				//cout << "  " << cnt << "  " << a[cnt] << "  " << b[cnt] << endl;
			}
		}
		dp[i]=solve();
		//cout << i << "  " << dp[i] << endl;
	}
	printf("%.9f\n",dp[(1<<n)-1]);
	return 0;
}

---

C. Multiple?

难度：$\bigstar\bigstar\bigstar$

题目大意：

定义好序列为所有元素都是 $[1,n]$ 中的整数，且任意非空子序列的和不是 $n$ 的倍数的序列。

求长度为 $n-k$ 的好序列数量，对 $998244353$ 取模。

$1\leq k\leq \dfrac{n}{4}<n<998244353$

题目解法：

可以证明：好序列的众数出现次数一定不小于 $\dfrac{n}{2}$，并且这个众数一定与 $n$ 互素（后附证明），设其为 $x$，首先将所有序列中的数乘上 $x^{-1}$，此时众数是 $1$，且至少 $\dfrac{n}{2}$ 个，所以容易证明所有数的和小于 $n$，这其实是一个充要条件（因为大于 $\dfrac{n}{2}$ 个不是 $1$ 的数直接导致和大于等于 $n$），利用隔板法知方案数 $\binom {n-1}{k-1}$，注意还要乘上众数的方案数 $\varphi(n)$。

下面是对关键结论的证明：

设众数为 $x$，除了 $x$ 以外其他所有数的出现次数总和为 $t$，我们现在从 $n-k$ 个数中选出若干对，使得每一对里两个数不同，容易证明可以选出 $S=\min(t,\lfloor\dfrac{n-k}{2}\rfloor)$ 对。

将所有数排成一列，使得同一对数在一起，此时有 $n-k+1$ 个前缀和，同时我们还可以交换任意一对数内部的顺序，就又有了 $S$ 个新的前缀和，总共 $n-k+1+S$ 个前缀和，并且它们模 $n$ 两两不同（否则就找到了一个子序列和为 $n$ 的倍数），所以 $S\dfrac{n}{2}$，如果 $(x,n)\ne 1$ 那么取 $\dfrac{n}{(x,n)}$ 个 $x$ 就是 $n$ 的倍数，不符合题意，所以 $(x,n)=1$。

时间复杂度为 $O(n)$，由于 $k\leq \dfrac{n}{4}$ 所以常数为 $\dfrac{1}{4}$，可以通过。

代码

#include <bits/stdc++.h>
using namespace std;
const int P=998244353;
int n,k,ans,tmp;
int qpow (int a,int b) {
	int res=1;
	while (b) {
		if (b&1) {res=(1ll*res*a)%P;}
		a=(1ll*a*a)%P,b>>=1;
	}
	return res;
}
int main () {
	scanf("%d%d",&n,&k);
	ans=tmp=1;
	for (int i=1;i<=k-1;i++) {
		ans=(1ll*ans*(n-i))%P;
		tmp=(1ll*tmp*i)%P;
	}
	ans=(1ll*ans*qpow(tmp,P-2))%P;
	ans=(1ll*ans*n)%P;
	for (int i=2;i*i<=n;i++) {
		if (n%i==0) {
			while (n%i==0) {n/=i;}
			ans=(1ll*ans*(i-1))%P;
			ans=(1ll*ans*qpow(i,P-2))%P;
		}
	}
	if (n>1) {
		ans=(1ll*ans*(n-1))%P;
		ans=(1ll*ans*qpow(n,P-2))%P;
	}
	printf("%d\n",ans);
	return 0;
}

---

D. Output Limit Exceeded

难度：$\bigstar\bigstar$

题目大意：

对于给定的 $n,k (0\leq k\leq n)$，可以建立一张左右各 $k$ 个点的二分图，其中左边第 $i$ 个点与右边第 $j$ 个点有边当且仅当 $i\mid n-j+1$，如果这张图有完美匹配，就称 $(n,k)$ 是好的。

给定 $n$，请你给出一个长度为 $n+1$ 的 $\texttt{01}$ 串 $s$，$s$ 的第 $i$ 位为 $1$ 当且仅当 $(n,i-1)$ 是好的。

你需要这样给出 $s$：初始令 $s_0=\texttt{0}, s_1=\texttt{1}$，然后对于每个 $s_i (i\ge 2)$，它由若干个编号更小的 $s_j$ 拼接而成，最后 $s_t$ 就是答案字符串，设要用 $q_i$ 个更前面的串拼出 $s_i$，你要确保 $\sum q_i\leq 10^4$。

$0\leq n\leq 10^{18}$

题目解法：

容易发现 $(n,k)$ 是好的当且仅当 $(n,n-k)$ 是好的，于是只需要考虑 $k<\dfrac{n}{2}$。

注意到如果 $n,n-1,\ldots,n-k+1$ 中有两个素数，那么 $(n,k)$ 一定不是好的（素数只能和 $1$ 匹配），所以只需要考虑 $[n-k+1,n]$ 中至多一个素数的情形，可以证明 $k\leq 3000$，实际上这个估计并不是很精确。

对于这些 $k$ 暴力求解最大匹配即可，最后将它们的结果与中间的一长串的 $\texttt{0}$（用倍增构造）拼接即可。

时间复杂度为 $O(k^3\log k)$ 或者 $O(k^{2.5}\log k)$，取决于最大匹配的算法。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3010;
ll n,cnt,nw,a[MAXN];
int mat[MAXN],vis[MAXN];
vector <int> v[MAXN],w;
ll qmul (ll a,ll b,ll p) {return (a*b-(ll)((long double)a/p*b)*p+p)%p;}
ll qpow (ll a,ll b,ll p) {
	ll res=1;
	while (b) {
		if (b&1) {res=qmul(res,a,p);}
		a=qmul(a,a,p),b>>=1;
	}
	return res;
}
bool mr (ll p,ll x) {
	if (qpow(x,p-1,p)!=1) {return 0;}
	ll k=p-1;
	while (!(k&1)) {
		k>>=1;
		ll tmp=qpow(x,p-1,p);
		if (tmp==p-1) {return 1;}
		else if (tmp!=1) {return 0;}
	}
	return 1;
}
bool isp (ll p) {
	if (p==46856248255981||p==1) {return 0;}
	if (p==2||p==3||p==7||p==61||p==24251) {return 1;}
	return mr(p,2)&&mr(p,3)&&mr(p,7)&&mr(p,61)&&mr(p,24251);
}
int dfs (int x) {
	int len=v[x].size();
	for (int i=0;i<len;i++) {
		int y=v[x][i];
		if (vis[y]) {continue;}
		if (!mat[y]) {
			mat[y]=x;
			return 1;
		} else {
			vis[y]=1;
			w.push_back(y);
			if (dfs(mat[y])) {mat[y]=x;return 1;}
		}
	}
	return 0;
}
bool solve (ll x) {
	for (ll i=1;i<=x;i++) {
		v[i].clear();
		for (ll j=(n-x+i)/i*i;j<=n;j+=i) {v[i].push_back(n-j+1);}
	}
	memset(mat,0,sizeof(mat));
	ll ans=0;
	for (ll i=1;i<=x;i++) {
		w.clear();
		ans+=dfs(i);
		int len=w.size();
		for (int i=0;i<len;i++) {vis[w[i]]=0;}
	}
	return (ans==x);
}
int main () {
	scanf("%lld",&n);
	if (n==0) {printf("2\n1 1\n");}
	else if (n==1) {printf("2\n2 1 1\n");}
	else if (n==2) {printf("2\n3 1 1 1\n");}
	else if (n==3) {printf("2\n4 1 1 1 1\n");}
	else {
		ll tot=0;
		a[++tot]=1;
		for (ll i=1;i<=n/2;i++) {
			if (isp(n-i+1)) {cnt++;}
			if (cnt==2) {break;}
			a[++tot]=solve(i);
		}
		printf("%d\n",65);
		for (int i=1;i<=60;i++) {printf("2 %d %d\n",i==1?0:i,i==1?0:i);}
		if (2*tot<n+1) {
			ll tmp=n+1-2*tot,ncnt=0;
			for (int i=0;i<=60;i++) {
				if (tmp&(1ll<<i)) {ncnt++;}
			}
			printf("%d",ncnt);
			for (int i=0;i<=60;i++) {
				if (tmp&(1ll<<i)) {printf(" %d",(i==0?0:i+1));}
			}
			printf("\n");
		} else {
			printf("11 45 14 11 45 14 11 45 14 11 45 14\n");
			nw++;
		}
		printf("%d",tot);
		for (int i=1;i<=tot;i++) {printf(" %d",a[i]);}
		printf("\n");
		printf("%d",2*tot<=n+1?tot:tot-1);
		for (int i=(2*tot<=n+1?tot:tot-1);i>=1;i--) {printf(" %d",a[i]);}
		printf("\n");
		if (2*tot<n+1) {printf("3 63 62 64\n");}
		else {printf("2 63 64\n");}
	}
	return 0;
}

---

E. Smol Vertex Cover

难度：$\bigstar$

题目大意：

给定 $n$ 个点的无向图 $G$，设 $G$ 的最大匹配大小为 $M$，最小点覆盖大小为 $C$，求是否有 $C\leq M+1$，如果是，请给出一组最小点覆盖。

$1\leq n\leq 500$

题目解法：

首先求出一个最大匹配。

显然 $C\ge M$，因为最大匹配中每条边的两个端点至少有一个在最小点覆盖中。

如果 $C=M$，这说明恰好从每个最大匹配中选出了一个点，2-SAT 构造即可（2-SAT 无解则 $C>M$）。

如果 $C=M+1$，再额外钦定一个点必选，然后 2-SAT 即可。

时间复杂度为 $O(n^3)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1010,MAXM=500010;
int t,n,m,eg,cnt,ans,tot,cnts,hd[MAXN],ver[MAXM],nx[MAXM],tg[MAXN],f[MAXN];
int x[MAXM],y[MAXM],pre[MAXN],lk[MAXN],dfn[MAXN],res[MAXN];
int bel[MAXN],col[MAXN],dfnn[MAXN],low[MAXN],ins[MAXN];
vector <int> v[MAXN];
stack <int> st;
queue <int> q;
void add_edge (int x,int y) {
	ver[++eg]=y;
	nx[eg]=hd[x];
	hd[x]=eg;
	return;
}
int findr (int x) {return (f[x]==x?x:f[x]=findr(f[x]));}
void rev_lk (int x) {
	if (lk[pre[x]]) {rev_lk(lk[pre[x]]);}
	lk[x]=pre[x],lk[pre[x]]=x;
	return;
}
int get_lca (int x,int y) {
	cnt++;
	while (x) {
		x=findr(x);
		if (dfn[x]==cnt) {return x;}
		dfn[x]=cnt;
		x=pre[lk[x]];
		if (y) {swap(x,y);}
	}
	assert(0);
}
void flw (int x,int y,int z) {
	while (findr(x)!=z) {
		pre[x]=y;
		y=lk[x];
		if (tg[y]==2) {tg[y]=1,q.push(y);}
		f[x]=f[y]=z;
		x=pre[y];
	}
	return;
}
int blossom (int x) {
	while (!q.empty()) {q.pop();}
	for (int i=1;i<=n;i++) {tg[i]=0,f[i]=i,pre[i]=0;}
	tg[x]=1,q.push(x);
	while (!q.empty()) {
		int a=q.front();
		q.pop();
		for (int i=hd[a];i;i=nx[i]) {
			int b=ver[i];
			if (tg[b]==1) {
				int c=get_lca(a,b);
				flw(a,b,c),flw(b,a,c);
			} else if (!tg[b]) {
				pre[b]=a,tg[b]=2;
				if (!lk[b]) {
					rev_lk(b);
					return 1;
				} else {
					tg[lk[b]]=1;
					q.push(lk[b]);
				}
			}
		}
	}
	return 0;
}
void dfs (int x) {
	dfnn[x]=low[x]=++tot;
	ins[x]=1;
	st.push(x);
	int len=v[x].size();
	for (int i=0;i<len;i++) {
		int y=v[x][i];
		if (!dfnn[y]) {
			dfs(y);
			low[x]=min(low[x],low[y]);
		} else if (ins[y]) {
			low[x]=min(low[x],dfnn[y]);
		}
	}
	if (low[x]==dfnn[x]) {
		cnts++;
		int z=st.top();
		while (z!=x) {
			col[z]=cnts,ins[z]=0;
			st.pop();
			z=st.top();
		}
		col[z]=cnts,ins[z]=0;
		st.pop();
	}
	return;
}
bool tsat (int ans) {
	tot=cnts=0;
	for (int i=1;i<=2*ans;i++) {col[i]=dfnn[i]=low[i]=ins[i]=res[i]=0;}
	for (int i=1;i<=2*ans;i++) {
		if (!dfnn[i]) {dfs(i);}
	}
	for (int i=1;i<=ans;i++) {
		if (col[i]==col[i+ans]) {return 0;}
		res[i]=(col[i]>col[i+ans]);
	}
	return 1;
}
int main () {
	scanf("%d",&t);
	for (int ii=1;ii<=t;ii++) {
		ans=eg=cnt=0;
		scanf("%d%d",&n,&m);
		for (int i=1;i<=n;i++) {hd[i]=dfn[i]=lk[i]=bel[i]=0;}
		for (int i=1;i<=m;i++) {
			scanf("%d%d",&x[i],&y[i]);
			add_edge(x[i],y[i]),add_edge(y[i],x[i]);
		}
		for (int i=1;i<=n;i++) {
			if (!lk[i]) {ans+=blossom(i);}
		}
		ans=0;
		for (int i=1;i<=n;i++) {
			if (i<lk[i]) {bel[i]=bel[lk[i]]=++ans;}
		}
		for (int i=1;i<=2*ans;i++) {v[i].clear();}
		for (int i=1;i<=m;i++) {
			if (bel[x[i]]==bel[y[i]]) {continue;}
			int u=(x[i]>lk[x[i]]),z=(y[i]>lk[y[i]]);
			if (bel[x[i]]==0) {v[bel[y[i]]+(z^1)*ans].push_back(bel[y[i]]+z*ans);}
			else if (bel[y[i]]==0) {v[bel[x[i]]+(u^1)*ans].push_back(bel[x[i]]+u*ans);}
			else {
				v[bel[x[i]]+(u^1)*ans].push_back(bel[y[i]]+z*ans);
				v[bel[y[i]]+(z^1)*ans].push_back(bel[x[i]]+u*ans);
			}
		}
		if (tsat(ans)) {
			printf("%d\n",ans);
			for (int i=1;i<=n;i++) {
				if (bel[i]&&i<lk[i]&&(!res[bel[i]])) {printf("%d ",i);}
				if (bel[i]&&i>lk[i]&&res[bel[i]]) {printf("%d ",i);}
			}
			printf("\n");
			continue;
		}
		int flg=0;
		for (int ii=1;ii<=n;ii++) {
			//cout << ii << "  " << bel[ii] << endl;
			if (!bel[ii]) {
				for (int i=1;i<=2*ans;i++) {v[i].clear();}
				for (int i=1;i<=m;i++) {
					//cout << "  " << x[i] << "  " << y[i] << endl;
					if (bel[x[i]]==bel[y[i]]) {continue;}
					int u=(x[i]>lk[x[i]]),z=(y[i]>lk[y[i]]);
					if (bel[x[i]]==0&&x[i]!=ii) {
						v[bel[y[i]]+(z^1)*ans].push_back(bel[y[i]]+z*ans);
						//cout << "    " << bel[y[i]] << "  " << z << endl;
					} else if (bel[y[i]]==0&&y[i]!=ii) {
						v[bel[x[i]]+(u^1)*ans].push_back(bel[x[i]]+u*ans);
						//cout << "    " << bel[x[i]] << "  " << u << endl;
					} else if (bel[x[i]]&&bel[y[i]]) {
						v[bel[x[i]]+(u^1)*ans].push_back(bel[y[i]]+z*ans);
						v[bel[y[i]]+(z^1)*ans].push_back(bel[x[i]]+u*ans);
						//cout << "    " << bel[x[i]] << "  " << u << endl;
						//cout << "    " << bel[y[i]] << "  " << z << endl;
					}
				}
				if (tsat(ans)) {
					printf("%d\n",ans+1);
					for (int i=1;i<=ii-1;i++) {
						if (bel[i]&&i<lk[i]&&(!res[bel[i]])) {printf("%d ",i);}
						if (bel[i]&&i>lk[i]&&res[bel[i]]) {printf("%d ",i);}
					}
					printf("%d ",ii);
					for (int i=ii+1;i<=n;i++) {
						if (bel[i]&&i<lk[i]&&(!res[bel[i]])) {printf("%d ",i);}
						if (bel[i]&&i>lk[i]&&res[bel[i]]) {printf("%d ",i);}
					}
					printf("\n");
					flg=1;
					break;
				}
			} else if (ii<lk[ii]) {
				for (int i=1;i<=2*ans;i++) {v[i].clear();}
				for (int i=1;i<=m;i++) {
					if (bel[x[i]]==bel[y[i]]) {continue;}
					if (bel[x[i]]==bel[ii]||bel[y[i]]==bel[ii]) {continue;}
					int u=(x[i]>lk[x[i]]),z=(y[i]>lk[y[i]]);
					if (bel[x[i]]==0) {
						v[bel[y[i]]+(z^1)*ans].push_back(bel[y[i]]+z*ans);
					} else if (bel[y[i]]==0) {
						v[bel[x[i]]+(u^1)*ans].push_back(bel[x[i]]+u*ans);
					} else {
						v[bel[x[i]]+(u^1)*ans].push_back(bel[y[i]]+z*ans);
						v[bel[y[i]]+(z^1)*ans].push_back(bel[x[i]]+u*ans);
					}
				}
				if (tsat(ans)) {
					printf("%d\n",ans+1);
					for (int i=1;i<=ii-1;i++) {
						if (bel[i]&&i<lk[i]&&(!res[bel[i]])) {printf("%d ",i);}
						if (bel[i]&&i>lk[i]&&res[bel[i]]) {printf("%d ",i);}
					}
					printf("%d ",ii);
					for (int i=ii+1;i<=lk[ii]-1;i++) {
						if (bel[i]&&i<lk[i]&&(!res[bel[i]])) {printf("%d ",i);}
						if (bel[i]&&i>lk[i]&&res[bel[i]]) {printf("%d ",i);}
					}
					printf("%d ",lk[ii]);
					for (int i=lk[ii]+1;i<=n;i++) {
						if (bel[i]&&i<lk[i]&&(!res[bel[i]])) {printf("%d ",i);}
						if (bel[i]&&i>lk[i]&&res[bel[i]]) {printf("%d ",i);}
					}
					printf("\n");
					flg=1;
					break;
				}
			}
		}
		if (!flg) {printf("not smol\n");}
	}
	return 0;
}

---

F. Thanks to MikeMirzayanov

难度：$\bigstar\bigstar\bigstar$

题目大意：

给定 $1,\ldots,n$ 的排列 $a_{1,\ldots,n}$，每次操作可以将 $a$ 划分成 $k$ 个连续段 $D_1,\ldots,D_k$ 依次拼接的形式，然后将 $a$ 变成 $D_k,\ldots,D_1$ 依次拼接的形式（而不改变每个 $D_i$ 内部数的顺序），请在 $q$ 次操作以内将 $a$ 排序。

$1\leq n\leq 20000, q=120$

题目解法：

这样的排序问题可以首先考虑 $01$ 序列的情形，如果序列只包含 $0,1$，那么首先我们将连续段合并，变成 $1010101010\ldots$（或者 $0101010101\ldots$）这样的形式，然后分段如 $10\mid 1\mid 01\mid 0\mid 10\ldots$（或者 $0\mid 10\mid 1\mid 01\mid 0\ldots$）。注意到一次操作实际上可以看成先将每个 $D_i$ 内部翻转，再将整个序列翻转，整个序列的翻转可以忽略，我们只翻转每段内部，就会变成 $0111000111\ldots$（或者 $0011100011\ldots$）这样的形式，连续段数大致除以了 $3$，因此只需要大约 $\log_3 n$ 次就可以排序长度为 $n$ 的序列。

对于原问题考虑分治，首先把所有二进制最高位为 $0$ 的数放在最高位为 $1$ 的数左边（这相当于一个只有 $0,1$ 的排序），然后分成两个子问题，再考虑次高位，以此类推。由于最高位做完以后最高位为 $0$ 和 $1$ 的数分别在两边互不干扰，所以此后的进程可以在两边同步进行，也就是说每一位都只需要总共 $\log_3 n$ 次左右的操作就可以排好，通过此题绰绰有余。

题解采用的做法需要大约 $\log_2 n$ 次才能排好一个长度为 $n$ 的 $01$ 序列，因此上面叙述的做法比题解做法要优秀许多。

时间复杂度为 $O(nq)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=20010;
int n,cnt,a[MAXN],b[MAXN],ac[MAXN];
vector <int> ans[MAXN];
void calc (int x) {
	int len=ans[x].size(),l=0;
	//cout << "  " << x << endl;
	for (int i=0;i<len;i++) {
		//cout << "  " << ans[x][i];
		reverse(b+l,b+l+ans[x][i]);
		reverse(a+l,a+l+ans[x][i]);
		l+=ans[x][i];
	}
	//cout << endl;
	reverse(b,b+n);
	reverse(a,a+n);
	return;
}
void solve (int x) {
	int tcnt=0,sy=n%(1<<(x+1));
	for (int i=0;i<n;i+=(1<<(x+1))) {
		for (int j=0;j<(1<<(x+1));j++) {
			if (i+j>=n) {break;}
			b[i+j]=(a[i+j]>=i+(1<<x));
		}
	}
	//cout << x << endl;
	while (1) {
		tcnt++,cnt++;
		if (tcnt&1) {
			for (int i=0;i<n;i+=(1<<(x+1))) {
				int ncnt=0,lst=0,iee=(b[i]==0);
				for (int l=0,r;i+l<n&&l<(1<<(x+1));l=r+1) {
					r=l;
					while (r<(1<<(x+1))-1&&i+r<n-1&&b[i+r+1]==b[i+l]) {r++;}
					if ((ncnt%3)==iee+1) {ans[cnt].push_back(lst+r-l+1);}
					else if ((ncnt%3)!=iee+0) {ans[cnt].push_back(r-l+1);}
					//cout << "       " << i << "  " << l << "  " << r << "  " << ncnt << 
					//"  " << iee << "  " << ans[cnt].size() << endl;
					lst=r-l+1,ncnt++;
				}
				if ((ncnt%3)==iee+1) {ans[cnt].push_back(lst);}
			}
			calc(cnt);
		} else {
			for (int i=0,ii=0;i<n;i+=(ii==0?sy:(1<<(x+1))),ii++) {
				int ncnt=0,lst=0,tmp=(ii==0?sy:(1<<(x+1)));
				if (tmp==0) {continue;}
				int iee=(b[min(n-1,i+tmp-1)]==0);
				vector <int> vtmp;
				for (int r=min(n-i-1,tmp-1),l;r>=0;r=l-1) {
					l=r;
					while (l>0&&b[i+r]==b[i+l-1]) {l--;}
					if ((ncnt%3)==iee+1) {vtmp.push_back(lst+r-l+1);}
					else if ((ncnt%3)!=iee+0) {vtmp.push_back(r-l+1);}
					//cout << "       " << i << "  " << l << "  " << r << "  " << ncnt << 
					//"  " << iee << vtmp.size() << endl;
					lst=r-l+1,ncnt++;
				}
				if ((ncnt%3)==iee+1) {vtmp.push_back(lst);}
				while (vtmp.size()) {
					ans[cnt].push_back(vtmp.back());
					vtmp.pop_back();
				}
			}
			calc(cnt);
			int flg=1;
			for (int i=0;i<n;i+=(1<<(x+1))) {
				int ncnt=0;
				for (int l=0,r;i+l<n&&l<(1<<(x+1));l=r+1) {
					r=l;
					while (r<(1<<(x+1))-1&&i+r<n-1&&b[i+r+1]==b[i+l]) {r++;}
					ncnt++;
				}
				if (ncnt>2||b[i]!=0) {flg=0;}
			}
			if (flg) {break;}
		}
	}
	return;
}
int main () {
	scanf("%d",&n);
	for (int i=0;i<n;i++) {scanf("%d",&a[i]);a[i]--;}
	for (int i=14;i>=0;i--) {solve(i);}
	int rcnt=0;
	for (int i=1;i<=cnt;i++) {
		if (ans[i].size()>1) {rcnt++,ac[i]=1;}
	}
	printf("%d\n",rcnt);
	for (int i=1;i<=cnt;i++) {
		if (!ac[i]) {continue;}
		int len=ans[i].size();
		printf("%d",len);
		for (int j=0;j<len;j++) {printf(" %d",ans[i][j]);}
		printf("\n");
	}
	return 0;
}

---

G. Remove the Prime

难度：$\bigstar$

题目大意：

给定长度为 $n$ 的数组 $a_1,\ldots,a_n$，两人轮流操作，每次操作选择非空区间 $[l,r]$ 和素数 $p$，需满足 $p\mid a_i (i\in [l,r])$，然后除去 $a_i (i\in [l,r])$ 中所有的素因子 $p$，无法行动者败，问谁必胜。

$1\leq n\leq 1000, 1\leq a_i\leq 10^{18}$

题目解法：

显然序列关于每个素数是无关的游戏，而且同一个素数的倍数构成的不同连续段是无关的游戏，并且长度为 $l$ 的连续段 SG 值就是 $l$，所以我们将每个 $a_i$ 分解素因数后枚举所有素因数和其倍数构成的连续段，将这些段的长度全部异或起来，等于零则后手胜，否则先手胜。

时间复杂度为 $O(nT(A))$，其中 $T(A)$ 是分解一个 $a_i$ 的时间复杂度，可以用 Pollard‘s Rho 实现。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=100010;
ll t,n,ans,cnt,cntt,anss,a[MAXN],aa[MAXN],pri[MAXN],q[MAXN],prii[MAXN];
map <ll,int> mp;
ll brand (ll n) {return ((1ll*rand())^((1ll*rand())<<15)^((1ll*rand())<<30)^((1ll*rand())<<45))%n+1;}
ll qmul (ll a,ll b,ll p) {return (a*b-(ll)((long double)a/p*b)*p+p)%p;}
ll qpow (ll a,ll b,ll p) {
	ll res=1;
	while (b) {
		if (b&1) {res=qmul(res,a,p);}
		a=qmul(a,a,p),b>>=1;
	}
	return res;
}
ll gcd (ll a,ll b) {return (b==0?a:gcd(b,a%b));}
bool mr (ll p,ll x) {
	if (qpow(x,p-1,p)!=1) {return 0;}
	ll k=p-1;
	while (!(k&1)) {
		k>>=1;
		ll tmp=qpow(x,k,p);
		if (tmp==p-1) {return 1;}
		else if (tmp!=1) {return 0;}
	}
	return 1;
}
bool isp (ll p) {
	if (p==46856248255981||p==1) {return 0;}
	if (p==2||p==3||p==7||p==61||p==24251) {return 1;}
	return mr(p,2)&&mr(p,3)&&mr(p,7)&&mr(p,61)&&mr(p,24251);
}
void pr (ll p) {
	if (isp(p)) {
		ans=max(ans,p);
		return;
	}
	ll c=brand(p-1),t1=brand(p-1),tmp=1,cnt=0;
	ll t2=t1;
	t1=(qmul(t1,t1,p)+c)%p;
	t2=(qmul(t2,t2,p)+c)%p;
	t2=(qmul(t2,t2,p)+c)%p;
	while (t1!=t2) {
		tmp=qmul(tmp,abs(t2-t1),p),cnt++;
		if (tmp==0) {
			ll d=gcd(abs(t2-t1),p);
			pr(d),pr(p/d);
			return;
		}
		if (cnt%127==0) {
			ll d=gcd(tmp,p);
			if (d>1&&d<p) {
				pr(d),pr(p/d);
				return;
			}
			tmp=1;
		}
		t1=(qmul(t1,t1,p)+c)%p;
		t2=(qmul(t2,t2,p)+c)%p;
		t2=(qmul(t2,t2,p)+c)%p;
	}
	ll d=gcd(tmp,p);
	if (d>1&&d<p) {pr(d),pr(p/d);}
	return;
}
void shai (int x) {
	for (int i=2;i<=x;i++) {
		if (!q[i]) {prii[++cntt]=i;}
		for (int j=1;j<=cntt&&prii[j]*i<=x;j++) {
			q[i*prii[j]]=1;
			if (i%prii[j]==0) {break;}
		}
	}
	return;
}
int main () {
	scanf("%lld",&n);
	shai(1000); 
	for (int i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		aa[i]=a[i];
		while (a[i]>1) {
			ans=0;
			if (a[i]<1000) {
				for (int j=1;j<=cntt;j++) {if (a[i]%prii[j]==0) {ans=prii[j];break;}}
			} else {
				while (!ans) {pr(a[i]);}
			}
			if (mp.find(ans)==mp.end()) {
				mp[ans]=++cnt;
				pri[cnt]=ans;
			}
			while (a[i]%ans==0) {a[i]/=ans;}
		}
	}
	for (int i=1;i<=cnt;i++) {
		for (int l=1,r;l<=n;l=r+1) {
			r=l;
			if (aa[l]%pri[i]) {continue;}
			while (r<n&&aa[r+1]%pri[i]==0) {r++;}
			anss^=(r-l+1);
		}
	}
	if (anss==0) {printf("Second\n");}
	else {printf("First\n");}
	return 0;
}

---

H. Excluded Min

难度：$\bigstar\bigstar\bigstar\bigstar$

题目大意：

对于非负数可重集 $S$，一次操作可以选择一个在 $S$ 中至少出现两次的 $x$，删掉一个 $x$ 并添加一个 $x-1$ 或 $x+1$，并保证 $S$ 仍然是非负数可重集。

可重集 $S$ 的价值定义为其经过任意多次操作后 $\operatorname{mex}$ 的最大值。

给定序列 $a_1,\ldots,a_n$，有 $q$ 次询问，每次给定 $[l,r]$，求 $a_l,\ldots,a_r$ 构成的可重集的价值。

$1\leq n,q,a_i\leq 5\times 10^5$

题目解法：

可以发现，如果区间中 $<x$ 的数的个数（记为 $f(l,r,x)$）不少于 $x$，那么可以通过调整使得 $\operatorname{mex}$ 为 $x$，否则仅通过 $<x$ 的数无法使得 $\operatorname{mex}$ 变为 $x$。

所以答案就是使得 $f(l,r,x)\ge x$ 的最大的 $x$。

那么就有一个十分简单的莫队做法，时间复杂度为 $O(n\sqrt n\log n)$，但这不是 intended solution，难以通过。

考虑离线后按照 $x$​ 从大到小扫描，对每个区间维护 $f(l,r,x)-x$​，每当有某个区间的这个值非负时就找到了这个区间的答案（为 $x$），然后将它删除即可。

所以我们要支持矩形加，全局最值，删除元素，但这太困难了，我们考虑进一步简化。

如果 $[l_1,r_1]\subset [l,r]$，那么显然 $f(l_1,r_1,x)\leq f(l,r,x)$，所以一开始求最大值时可以不考虑 $[l_1,r_1]$，只有等 $[l,r]$ 被删除后才需要考虑这条更短的线段。

所以现在我们可以认为所有线段没有包含关系，那么原本的二维问题就退化成了一维（排序后左右端点都是单调的），只需要支持区间加以及查询最值即可，用线段树可以维护。

不过此时就会有增删线段的问题，我们可以用另一棵线段树记录当前被另一个区间包含的区间，称为候选区间，每当有一个区间被删除时就要考虑它包含的候选区间是否要加到前一棵线段树上，由于前一棵线段树上的线段都是有序的，所以找出这些要加入的候选线段可以直接取右端点最大的看能不能加。

为了计算候选区间此时的 $f(l,r,x)$，还要用树状数组维护整个序列。

时间复杂度为 $O((n+q)\log(n+q))$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=500010;
struct Query {
	int id,ans,l,r;
}qu[MAXN];
int n,q,fw[MAXN],mxr[MAXN<<2],mpr[MAXN<<2],mxv[MAXN<<2],mpv[MAXN<<2],tg[MAXN<<2];
pair <int,int> a[MAXN];
bool cmp1 (pair <int,int> a,pair <int,int> b) {return a.first>b.first;}
bool cmp2 (Query a,Query b) {return (a.l==b.l?a.r>b.r:a.l<b.l);}
bool cmp3 (Query a,Query b) {return a.id<b.id;}
int cs (int a,int b) {
	if (qu[a].r==qu[b].r) {return (qu[a].l<=qu[b].l?a:b);}
	else {return (qu[a].r>qu[b].r?a:b);}
}
void modify_fw (int x,int v) {
	for (int i=x;i<=n;i+=(i&(-i))) {fw[i]+=v;}
	return;
}
int query_fw (int x) {
	int res=0;
	for (int i=x;i;i-=(i&(-i))) {res+=fw[i];}
	return res;
}
void upd (int p) {
	mxr[p]=max(mxr[p<<1],mxr[(p<<1)|1]);
	mpr[p]=cs(mpr[p<<1],mpr[(p<<1)|1]);
	mxv[p]=max(mxv[p<<1],mxv[(p<<1)|1]);
	mpv[p]=(mxv[p<<1]>mxv[(p<<1)|1]?mpv[p<<1]:mpv[(p<<1)|1]);
	return;
}
void pd (int p) {
	if (tg[p]==0) {return;}
	tg[p<<1]+=tg[p],tg[(p<<1)|1]+=tg[p],mxv[p<<1]+=tg[p],mxv[(p<<1)|1]+=tg[p];
	tg[p]=0;
	return;
}
void buildt (int p,int l,int r) {
	if (l==r) {mxv[p]=-1e9,mpv[p]=l,mpr[p]=l;return;}
	int mid=(l+r)>>1;
	buildt(p<<1,l,mid);
	buildt((p<<1)|1,mid+1,r);
	upd(p);
}
void modify_mpr (int p,int l,int r,int pos,int v) {
	if (l==r) {mpr[p]=v;return;}
	pd(p);
	int mid=(l+r)>>1;
	if (pos<=mid) {modify_mpr(p<<1,l,mid,pos,v);}
	else {modify_mpr((p<<1)|1,mid+1,r,pos,v);}
	upd(p);
	return;
}
void modify_mxr (int p,int l,int r,int pos,int v) {
	if (l==r) {mxr[p]=v;return;}
	pd(p);
	int mid=(l+r)>>1;
	if (pos<=mid) {modify_mxr(p<<1,l,mid,pos,v);}
	else {modify_mxr((p<<1)|1,mid+1,r,pos,v);}
	upd(p);
	return;
}
void modify_dv (int p,int l,int r,int pos,int v) {
	if (l==r) {mxv[p]=v;return;}
	pd(p);
	int mid=(l+r)>>1;
	if (pos<=mid) {modify_dv(p<<1,l,mid,pos,v);}
	else {modify_dv((p<<1)|1,mid+1,r,pos,v);}
	upd(p);
	return;
}
void modify_qv (int p,int l,int r,int xl,int xr,int v) {
	if (xr<l||r<xl) {return;}
	if (xl<=l&&r<=xr) {
		tg[p]+=v,mxv[p]+=v;
		return;
	}
	pd(p);
	int mid=(l+r)>>1;
	modify_qv(p<<1,l,mid,xl,xr,v);
	modify_qv((p<<1)|1,mid+1,r,xl,xr,v);
	upd(p);
	return; 
}
int query_mpr (int p,int l,int r,int xl,int xr) {
	if (xr<l||r<xl) {return 0;}
	if (xl<=l&&r<=xr) {return mpr[p];}
	pd(p);
	int mid=(l+r)>>1;
	return cs(query_mpr(p<<1,l,mid,xl,xr),query_mpr((p<<1)|1,mid+1,r,xl,xr));
}
int query_mxr (int p,int l,int r,int xl,int xr) {
	if (xr<l||r<xl) {return 0;}
	if (xl<=l&&r<=xr) {return mxr[p];}
	pd(p);
	int mid=(l+r)>>1;
	return max(query_mxr(p<<1,l,mid,xl,xr),query_mxr((p<<1)|1,mid+1,r,xl,xr));
}
int query_rb (int p,int l,int r,int v) {
	if (l==r) {return l;}
	pd(p);
	int mid=(l+r)>>1;
	if (mxr[p<<1]>=v) {return query_rb(p<<1,l,mid,v);}
	else {return query_rb((p<<1)|1,mid+1,r,v);}
}
int query_nx (int p,int l,int r,int pos) {
	if (mxv[p]<-1e8) {return -1;}
	if (l==r) {return l;}
	pd(p);
	int mid=(l+r)>>1;
	if (mid>pos) {
		int tmp=query_nx(p<<1,l,mid,pos);
		if (tmp!=-1) {return tmp;}
	}
	return query_nx((p<<1)|1,mid+1,r,pos);
}
void add (int x,int val) {
	//cout << "add: " << x << "  " << qu[x].id << "  " << val << endl;
	modify_mpr(1,1,q,x,0);
	modify_mxr(1,1,q,x,qu[x].r);
	modify_dv(1,1,q,x,query_fw(qu[x].r)-query_fw(qu[x].l-1)-val);
	return;
}
void del (int x,int val) {
	//cout << "del: " << x << "  " << qu[x].id << "  " << val << endl;
	qu[x].ans=val;
	modify_dv(1,1,q,x,-1e9);
	modify_mxr(1,1,q,x,0);
	return;
}
int main () {
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++) {
		modify_fw(i,1);
		scanf("%d",&a[i].first);
		a[i].second=i;
	}
	int fflg=(a[1].first==3092);
	sort(a+1,a+n+1,cmp1);
	for (int i=1;i<=q;i++) {
		scanf("%d%d",&qu[i].l,&qu[i].r);
		qu[i].id=i;
	}
	sort(qu+1,qu+q+1,cmp2);
	buildt(1,1,q);
	for (int i=1;i<=q;i++) {
		if (query_mxr(1,1,q,1,i-1)<qu[i].r) {add(i,500001);}
	}
	int cur=1;
	for (int i=500000;i>=0;i--) {
		while (cur<=n&&a[cur].first==i) {
			modify_fw(a[cur].second,-1);
			if (mxr[1]>=a[cur].second) {
				int l=0,r=q;
				while (l<r) {
					int mid=(l+r+1)>>1;
					if (qu[mid].l<=a[cur].second) {l=mid;}
					else {r=mid-1;}
				}
				int rb=query_rb(1,1,q,a[cur].second);
				if (rb<=l) {modify_qv(1,1,q,rb,l,-1);}
			}
			cur++;
		}
		modify_qv(1,1,q,1,q,1);
		while (mxv[1]>=0) {
			int tmp=mpv[1];
			del(tmp,i);
			int mnr=query_mxr(1,1,q,1,tmp),mxl=query_nx(1,1,q,tmp);
			if (mxl==-1) {mxl=n;}
			int tmp2=query_mpr(1,1,q,tmp,mxl);
			//cout << tmp << "  " << mnr << "  " << mxl << "  " << tmp2 << endl;
			while (qu[tmp2].r>mnr) {
				add(tmp2,i);
				tmp2=query_mpr(1,1,q,tmp,tmp2);
			}
		}
	}
	sort(qu+1,qu+q+1,cmp3);
	for (int i=1;i<=q;i++) {printf("%d\n",qu[i].ans);}
	return 0;
}

---

I. Trade

难度：$\bigstar\bigstar$

题目大意：

有 $n$ 个商品，第 $i$ 个商品的初始价格为 $c_i$，但如果你在买它之前已经买了其他的 $j$ 个物品，那么你在买它的时候需要额外付出 $j\times p_i$ 的价格，保证 $p_i$ 两两不同。你有 $S$ 单位的钱，问最多能买多少个商品。

$1\leq n\leq 10^5, 0\leq S\leq 10^9$

题目解法：

由于 $p_i$ 两两不同，所以买 $m$ 个物品所需价格至少也是 $O(m^3)$，所以能购买的物品数量是 $O(\sqrt[3] S)$ 的。

显然购买顺序是 $p_i$ 从大到小，所以排序后 DP 即可，时间复杂度为 $O(n\sqrt[3] S)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=100010;
struct P {
	int c,p;
}t[MAXN]; 
int n,s,ans;
ll dp[2][MAXN];
bool cmp (P a,P b) {return a.p>b.p;}
int main () {
	scanf("%d%d",&n,&s);
	for (int i=1;i<=n;i++) {scanf("%d",&t[i].c);}
	for (int i=1;i<=n;i++) {scanf("%d",&t[i].p);}
	for (int i=1;i<=2000;i++) {dp[0][i]=s+1;}
	sort(t+1,t+n+1,cmp);
	for (int i=1;i<=n;i++) {
		int u=(i&1),v=(u^1);
		for (int j=0;j<=2000;j++) {
			dp[u][j]=min(dp[u][j],dp[v][j]);
			dp[u][j+1]=dp[v][j]+1ll*j*t[i].p+t[i].c;
			if (dp[u][j]>s) {dp[u][j]=s+1;}
		}
	}
	for (int i=0;i<=2000;i++) {
		if (dp[n&1][i]<=s) {ans=i;}
	}
	printf("%d\n",ans);
	return 0;
}

---

J. Increasing or Decreasing

难度：$\bigstar\bigstar$

题目大意：

给定 $1,\ldots,n$ 的排列 $a_{1,\ldots,n}, b_{1,\ldots,n}$，现在可以对 $a$ 进行若干次操作，操作形如将一个区间从小到大或从大到小排序，请构造一个不超过 $n$ 个操作的方案将 $a$ 变为 $b$。

$1\leq n\leq 500$

题目解法：

可以先通过一次操作将 $a$ 整体倒序排序，此时 $a_i=n-i+1$。

接下来依次枚举 $i=1,\ldots,n-1$，设 $b_i$ 在当前 $a$ 中的位置是 $r$，那么我们就将 $[i,r]$ 正序或倒序排序，使得 $a_i=b_i$。

要做到这一点，我们需要归纳证明：在上述过程中的任何一步，$a_r$ 或者是 $[i,r]$ 的最小值，或者是 $[i,r]$ 的最大值，而这个归纳是不困难的，这里不进行赘述。

暴力实现，时间复杂度为 $O(n^2)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=510;
int n,a[MAXN],b[MAXN],pos[MAXN];
bool cmp1 (int a,int b) {return a<b;}
bool cmp2 (int a,int b) {return b<a;}
int main () {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {scanf("%d",&a[i]);a[i]=pos[i]=n-i+1;}
	for (int i=1;i<=n;i++) {scanf("%d",&b[i]);}
	printf("%d\n1 %d D\n",n,n);
	for (int i=1;i<=n-1;i++) {
		int tmp=pos[b[i]];
		if (tmp==i||a[tmp]<a[tmp-1]) {
			printf("%d %d I\n",i,tmp);
			sort(a+i,a+tmp+1,cmp1);
		} else {
			printf("%d %d D\n",i,tmp);
			sort(a+i,a+tmp+1,cmp2);
		}
		for (int j=1;j<=n;j++) {pos[a[j]]=j;}
	}
	return 0;
}

---

K. Rectangle Painting

难度：$\bigstar\bigstar\bigstar\bigstar$

题目大意：

直角坐标系中的每个单位方格初始全为白色，接下来进行 $q$ 个操作，操作分为：

• 修改操作，给定 $y\ge0,l,r$，将所有 $(i,y) (i\in [l,r])$ 对应的方格染黑。
• 查询操作，给定 $l,r$，求最大的自然数 $y$ 使得存在 $i\in [l,r]$，对于所有 $j\in [0,y)$ 满足 $(i,j)$ 是黑的。

强制在线。

$1\leq q\leq 10^5, 0\leq l\leq r\leq 2\times 10^5$

题目解法：

对横坐标建立线段树维护，本题的维护技巧依赖于对于经典的线段树五类点意义的理解（可以参看我没写完的数据结构博客）：

• 橙色点：某个修改区间的定位区间；
• 黄色点：橙色点的真后代；
• 红色点：不是任何修改区间的子区间，但是与某个修改区间有交；
• 绿色点：红色点的非橙色非红色儿子；
• 蓝色点：绿色点的真后代。

对于一个确定的纵坐标 $y$，如果将所有纵坐标为 $y$ 的修改操作扔到线段树上，那么一个横坐标 $x$ 对应的格子 $(x,y)$ 为白也就等价于 $x$ 对应的线段树上的叶子为绿色或蓝色，这又等价于这个叶子有一个绿色的祖先（包括自己）。

那么，对于每个线段树上的结点 $p$，我们维护使得 $p$ 是绿色点的纵坐标 $y$ 的集合 $S_p$，以及其中的最小值 $m_p$，那么查询 $[l,r]$ 的答案就是：

$$\max\limits_{i\in [l,r]}\min\limits_{L_i\to j}m_{j}$$

其中 $L_i$ 是 $i$ 对应的叶子，$x\to y$ 表示 $y$ 是 $x$ 的祖先。

对于线段树上对应区间 $[l,r]$ 的点 $x$ 维护一个辅助量 $val_x$，它表示 $\max\limits_{i\in [l,r]}\min\limits_{L_i\to j\to x} m_j$，即只考虑每个叶子到 $x$ 的路径而不考虑 $x$ 到根的部分，那么有 $val_x=\min(m_x,\max(val_{lx},val_{rx}))$，其中 $lx,rx$ 为 $x$ 的左右儿子。

于是我们直接套用传统的线段树区间查询，对于定位到的橙色点直接返回 $val_x$，对于红色点其返回值为两个儿子的较大值与自己的 $m_x$ 取 $\min$，最后根的返回值就是查询答案。

最后的问题是如何维护 $m_p$，那么当然同时要维护 $S_p$，只需要当处理纵坐标为 $y$ 的修改时遇到点 $p$（即 $p$ 变为红色或橙色），如果 $y\in S_p$，那么要将 $y$ 移出 $S_p$，同时将 $y$ 加入 $S_{lp},S_{rp}$，其中 $lp,rp$ 是 $p$ 的左右儿子。

其实这个做法有一个小问题，考虑以下 Hack：对于同一纵坐标 $y$ 和点 $p$，先来一个包含 $p$ 的左儿子 $lp$ 而不包含其右儿子 $rp$ 的修改，此时 $p$ 为红，$lp$ 为橙，$rp$ 为绿；再来一个包含 $p$ 的修改，这时 $rp$ 和 $lp$ 应该都改成黄色，但是实际上 $rp$ 的绿色标记没有被正确去除。

这是因为线段树递归到了一个被修改区间包含的区间就会停止，为了避免少清除标记，我们需要保证同一纵坐标的所有修改操作两两不交，只需要先用 set 处理一下修改区间即可。

时间复杂度为 $O(q\log q\log V)$，其中 $V$ 是区间端点值域。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=200010;
int q,op,ans[MAXN<<3];
set <int> s[MAXN<<3];
set < pair<int,int> > p[MAXN];
ll sum,x,y,z;
void upd (int p) {
	ans[p]=max(ans[p<<1],ans[(p<<1)|1]);
	if (s[p].size()) {ans[p]=min(ans[p],*(s[p].begin()));}
	return;
}
void buildt (int p,int l,int r) {
	ans[p]=ans[p<<1]=ans[(p<<1)|1]=1e9;
	if (l==r) {return;}
	int mid=(l+r)>>1;
	buildt(p<<1,l,mid),buildt((p<<1)|1,mid+1,r);
	upd(p);
}
void modify (int p,int l,int r,int xl,int xr,int v) {
	if (s[p].find(v)!=s[p].end()) {
		s[p].erase(v);
		upd(p);
		if (xl<=l&&r<=xr) {return;}
		if (l!=r) {
			s[p<<1].insert(v),s[(p<<1)|1].insert(v);
			upd(p<<1),upd((p<<1)|1);
		}
	}
	if (xl<=l&&r<=xr) {return;}
	int mid=(l+r)>>1;
	if (xl<=mid) {modify(p<<1,l,mid,xl,xr,v);}
	if (xr>mid) {modify((p<<1)|1,mid+1,r,xl,xr,v);}
	upd(p);
	return;
}
int query (int p,int l,int r,int xl,int xr) {
	if (xl<=l&&r<=xr) {return ans[p];}
	int res=0,mid=(l+r)>>1;
	if (xl<=mid) {res=query(p<<1,l,mid,xl,xr);}
	if (xr>mid) {res=max(res,query((p<<1)|1,mid+1,r,xl,xr));}
	if (s[p].size()) {res=min(res,*(s[p].begin()));}
	return res;
}
void add (int x,int y,int z) {
	set < pair<int,int> >::iterator it=p[x].lower_bound(make_pair(y,0));
	if (it!=p[x].begin()) {
		--it;
		if ((*it).second>=y) {
			p[x].insert(make_pair((*it).first,y-1));
			p[x].insert(make_pair(y,(*it).second));
			p[x].erase(it);
		}
	}
	it=p[x].lower_bound(make_pair(z+1,0));
	if (it!=p[x].begin()) {
		--it;
		if ((*it).second>=z+1) {
			p[x].insert(make_pair((*it).first,z));
			p[x].insert(make_pair(z+1,(*it).second));
			p[x].erase(it);
		}
	}
	int tmp=y;
	while (1) {
		it=p[x].lower_bound(make_pair(y,0));
		if (it==p[x].end()||(*it).first>z) {break;}
		if (tmp<=(*it).first-1) {modify(1,0,MAXN-10,tmp,(*it).first-1,x);}
		tmp=(*it).second+1;
		p[x].erase(it);
	}
	if (tmp<=z) {modify(1,0,MAXN-10,tmp,z,x);}
	p[x].insert(make_pair(y,z));
	return;
}
int main () {
	scanf("%d",&q);
	for (int i=0;i<=q;i++) {s[1].insert(i);}
	buildt(1,0,MAXN-10);
	int ttt=0;
	for (int i=1;i<=q;i++) {
		scanf("%d",&op);
		if (op==1) {
			scanf("%lld%lld%lld",&x,&y,&z);
			x^=sum,y^=sum,z^=sum;
			add(x,y,z);
		} else {
			scanf("%lld%lld",&x,&y);
			x^=sum,y^=sum;
			int ans=query(1,0,MAXN-10,x,y);
			printf("%d\n",ans);
			sum+=ans; 
		}
	}
	return 0;
}

---

L. Extreme Wealth

难度：$\bigstar\bigstar\bigstar\bigstar$

题目大意：

给定 $R,B$，在一个赌球游戏中有 $R$ 个红球和 $B$ 个蓝球。

你有初始为 $1$ 的资金，总共有 $R+B$ 回合，每一回合中会等概率随机选择当前剩下的某个球（此后的回合就拿走了这个球），你可以下注 $x$ 赌它为红球或蓝球，如果赌对则获得 $x$ 的利润，否则付出 $x$ 的代价（当然 $x$ 要不超过你的资金总数）。请问结束游戏时，最坏情况下最多可以保证拥有多少资金。

答案以浮点数形式输出，特别地，如果答案超过 $10^9$，只需要输出 Extreme Wealth。

$0\leq R,B\leq 10^{13}$

题目解法：

设 $f(r,b)$ 表示目前还剩 $r$ 个红球和 $b$ 个蓝球时你的资金最坏情况下最多可以保证翻多少倍，不妨设 $r\ge b$，那么肯定赌红球，如果你的下注是本金的 $p$ 倍（$0\leq p\leq 1$），那么有：

$$f(r,b)\leftarrow \min(f(r-1,b)\times (1+p),f(r,b-1)\times (1-p))$$

要让右边取最大值，显然有：

$$f(r-1,b)\times (1+p)=f(r,b-1)\times (1-p) \\ p=\dfrac{f(r,b-1)-f(r-1,b)}{f(r-1,b)+f(r,b-1)}$$

带入原式，然后两边取倒数，就有：

$$f(r,b)=\dfrac{2f(r-1,b)f(r,b-1)}{f(r-1,b)+f(r,b-1)} \\ \dfrac{1}{f(r,b)}=\dfrac{1}{2}\Big(\dfrac{1}{f(r-1,b)}+\dfrac{1}{f(r,b-1)}\Big)$$

将这个式子与格路计数联系起来，容易得到：

$$f(r,b)=\dfrac{2^{r+b}}{\binom {r+b} r}$$

看似这已经做完了，不过实际上前面只是很简单的一部分，真正的问题这时才刚刚开始——如何计算 $\dfrac{2^{R+B}}{\binom {R+B} R}$？

这题当然不是想让你直接精确计算，不妨用一些估计的方法，考虑用斯特林公式带入：

$$n!\approx \sqrt{2\pi n}\Big(\dfrac{n}{e}\Big)^n \\ f(R,B)\approx \sqrt {2\pi}\dfrac{\sqrt {R}(2R)^{R}\times \sqrt {B}(2B)^B}{\sqrt {R+B}(R+B)^{R+B}}$$

有一个比较特殊的情况容易计算，当 $R=B$ 时：

$$f(R,R)\approx\sqrt {\pi R}$$

官方题解给出了更精确的估计，这里不仔细分析了，直接给出结论：

$$f(R,R)=\sqrt {\pi R}(1+\dfrac{1}{8R}+O(R^{-2}))$$

有了 $f(R,R)$ 后我们可以往两边计算，考虑从 $f(R,B)$ 到 $f(R,B+1)$ 的递推式：

$$f(R,B+1)=f(R,B)\times \dfrac{2(B+1)}{R+B+1}=f(R,B)\times \dfrac{B+B+2}{R+B+1}$$

这里可以进行一些基本的估计，如果 $B,R$ 不太小，且 $B=R+c\sqrt R$，其中 $c$ 为适当大小的常数，那么：

$$\dfrac{B+B+2}{R+B+1}=\dfrac{2R+2c\sqrt R+2}{2R+c\sqrt R+1}=1+\dfrac{c\sqrt R+1}{2R+c\sqrt R+1}\approx1+\dfrac{c}{2\sqrt R}$$

将这个贡献累乘：

$$\prod\limits_{B=R+c\sqrt R}^{R+(c+1)\sqrt R}\dfrac{B+B+2}{R+B+1}\approx (1+\dfrac{c}{2\sqrt R})^{\sqrt R}=\exp(\sqrt R\ln(1+\dfrac{c}{2\sqrt R}))\approx \exp(\dfrac{c}{2})$$

尽管这中间的估计有些模糊和不严谨（但其实将上述式子都取 $R\to \infty$ 时的极限，上下两次估计都取等号），总之我们大致知道了：当 $B$ 比 $R$ 稍大时，它每增加 $\sqrt R$，$f(R,B)$ 就会成倍增加。

这告诉我们 $B$ 大致只需要增长 $\sqrt R\times \log 10^9$ 就可以使得 $f(R,B)>10^9$，此时直接输出 Extreme Wealth 即可，否则直接根据 $f(R,R)$ 直接递推出答案。

时间复杂度为 $O(\sqrt R\log C)$，其中 $C=10^9$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const double pi=acos(-1.0);
ll r,b;
double ans;
int main () {
	scanf("%lld%lld",&r,&b);
	if (r>b) {swap(r,b);}
	if (r<=100) {
		if (b>=10000000) {printf("Extreme Wealth\n");return 0;}
		ans=1.0;
		int rst=r+b;
		for (int i=1;i<=r;i++) {
			ans*=(double)i;
			ans/=(r+b-i+1);
			while (ans<1&&rst) {rst--,ans*=2.0;}
		}
		while (rst) {
			rst--,ans*=2.0;
			if (ans>1e9) {printf("Extreme Wealth\n");return 0;}
		}
		if (ans>1e9) {printf("Extreme Wealth\n");return 0;}
		printf("%.9f\n",ans);
	} else {
		ans=sqrt(pi*(double)r)*(1.0+0.125/(double)r);
		for (ll i=r;i<b;i++) {
			ans*=(double)(i+i+2)/(double)(i+r+1);
			if (ans>1e9) {printf("Extreme Wealth\n");return 0;}
		}
		printf("%.9f\n",ans);
	}
	return 0;
}

---

M. Discrete Logarithm is a Joke

难度：$\bigstar$

题目大意：

已知素数 $M=10^{18}+31$ 和它的原根 $g=42$，定义离散对数 $\log(x)$ 为使得 $g^q\equiv x\bmod M$ 的最小正整数 $q$，则 $\log(x)$ 是 $[1,M-1]$ 到 $[1,M-1]$ 的双射。

现在有数列 $\{a_n\}$，其中 $a_1=960002411612632915, a_{i+1}=\log(a_i)$.

给定 $n$，求 $a_n$。

$1\leq n\leq 10^{6}$

等等，忘了说了，$a_{1,000,000}=300$（这是一个样例）！

题目解法：

由于 $a_{i+1}=\log(a_i)$，所以 $a_i=g^{a_{i+1}}$，由于已知 $a_{1,000,000}$，所以可以倒推所有 $a_i (i\in [1,10^6])$。

时间复杂度为 $O(n\log M)$。

作为本场比赛的签到题，还是比较好玩的。

代码

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const ll P=1000000000000000000ll+31,G=42;
ll n,tmp;
ll qmul (ll a,ll b,ll m) {
	long double t=((long double)a*(long double)b/(long double)m);
	ull s=(ull)(t+0.5);
	ull res=(ull)a*(ull)b-s*(ull)m;
	if (res<m) {return res;}
	return res+m;
}
ll qpow (ll a,ll b,ll m) {
	ll res=1;
	while (b) {
		if (b&1) {res=qmul(res,a,m);}
		a=qmul(a,a,m),b>>=1;
	}
	return res;
}
int main () {
	scanf("%lld",&n);
	n=1000000-n;
	tmp=300;
	for (int i=1;i<=n;i++) {tmp=qpow(G,tmp,P);}
	printf("%lld\n",tmp);
	return 0;
}