Preface

在课程的夹缝中补题，苦路西

不过这场的A~D极水，吃完晚饭一个小时不到就全写了，不过E转化想到了没设计好状态没写出来可惜可惜

A. Lame King

SB题，显然要么往目标方向走要么停住，没有回头这一说

稍微手玩一下推一下式子即可，具体看代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
int t,a,b;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d",&a,&b); a=abs(a); b=abs(b); if (a<b) swap(a,b);
		printf("%d\n",2*b+max(2*(a-b)-1,0));
	}
	return 0;
}

B. Vaccination

稍微手玩一下就会发现我们利用以下的贪心策略是最优的：

若对于当前操作到的第\(i\)个人，上一支疫苗不能给他用或者之前已经没有疫苗剩余了，则在\(t_i+w\)这个时刻我们打开一包新的疫苗

否则就让他蹭前一支疫苗即可，不难发现这样操作肯定是最优的

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
int t,n,k,d,w,x,ans,lst,num;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d%d%d",&n,&k,&d,&w),ans=0,lst=-1,i=1;i<=n;++i)
		if (scanf("%d",&x),!~lst||x>lst+d||num==k) ++ans,lst=x+w,num=1; else ++num;
		printf("%d\n",ans);
	}
	return 0;
}

C. Pull Your Luck

刚开始有点不知道如何下手，直到看到\(\sum n\le 2\times 10^5\)就知道写\(O(n)\)的算法即可

考虑问题本质就是让我们求一个\(t\in[1,p]\)，使得\(\frac{t(t+1)}{2}+x\equiv0\pmod n\)，考虑到如果\(p\)的范围是和\(n\)同阶的话就很trivial了，因此我们往这个方向考虑

不难发现我们每次增加一个数的增量在对\(n\)取模后有一个长度为\(n\)的循环节，因此我们可以利用类似于BSGS的思想，预处理出每个循环节内的前缀有数是可以凑出来的

然后枚举前面整块的个数即可，不过如果直接这么做可能会出现\(p\)很大而\(n\)很小的情况导致整块的个数非常多而超时

但我们仔细一想如果这些整块的增量和出现和之前重复的情况（即出现环了）那么显然是无解的，由于余数的数目是\(O(n)\)的，根据抽屉原理这部分复杂度还是\(O(n)\)

因此这题就做完了，不过对于最后的散块还是要暴力枚举一下，具体实现看代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,x,p,m,pfx; bool vis[N],bkt[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d%d",&n,&x,&p),i=0;i<n;++i) bkt[i]=vis[i]=0;
		for (m=p/n,pfx=0,i=1;i<=min(n,p);++i) vis[(pfx+=i)%=n]=1;
		if (p<=n) { puts(vis[(n-x)%n]?"Yes":"No"); continue; }
		bool flag=0; for (i=0;i<m;++i)
		{
			int t=1LL*pfx*i%n; if (bkt[t]) break; bkt[t]=1;
			if (vis[(2*n-x-t)%n]) { flag=1; break; }
		}
		for (pfx=1LL*pfx*(m-1)%n,i=(m-1)*n+1;i<=p;++i)
		if ((pfx+=i)%=n,(pfx+x)%n==0) { flag=1; break; }
		puts(flag?"Yes":"No");
	}
	return 0;
}

D. Accommodation

这nm是一个2000分的D题？感觉比B题还一眼

首先每行是独立的，只要分别考虑并累加即可，然后前面拿到题目的时候上来先rush了一个DP

设\(f_{i,j}\)表示前\(i\)个房间中有\(j\)个双人房的最大/最小值，然后转移就是枚举以\(i\)结尾的是单人房还是双人房即可

然后后面仔细一想发现是个很naive的贪心，首先如果每个灯亮的房间我们都先把它算上贡献，那么当出现一个双人房占用了两个有灯的房间时，我们就要把贡献减去\(1\)

因此做法就很简单了，对于最小的情况我们贪心地把两个相邻的\((1,1)\)匹配，而最大的情况就贪心地把\((0,0),(0,1),(1,0)\)匹配即可

直接扫一遍就行了

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
int n,m,mi,mx,cur,sum; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),mi=mx=0,i=1;i<=n;++i)
	{
		for (scanf("%s",s+1),sum=0,j=1;j<=m;++j) sum+=s[j]=='1';
		for (cur=0,j=1;j<m&&cur<m/4;++j)	
		if (s[j]=='1'&&s[j+1]=='1') ++cur,++j;
		for (mi+=sum-cur,cur=0,j=1;j<m&&cur<m/4;++j)
		if (s[j]!=s[j+1]||(s[j]=='0')) ++cur,++j;
		mx+=sum-(m/4-cur);
	}
	printf("%d %d\n",mi,mx);
	return 0;
}

E. Routing

挺劲的一道题的，没想到成环的状压DP可以这么写，算是get到一种新姿势了

首先把题意的核心找出来，其实就是要在原图中找一个环，满足所有的点要么在环上要么和环上的点直接有边相连

然后刚开始我还以为是个图论问题，傻傻想了半天感觉这不是NP的吗，后来一看数据范围原来是状压

不过思来想去都没想到怎么吧成环这个条件扔进状态里，遂只能去看dalao的题解

其实处理起来很简单，就是破环为链的思想，我们考虑枚举一个起点\(st\)，然后设\(f_{i,j}\)表示从\(st\to i\)的路径上，直接经过的点的集合为\(j\)（状压）的路径是否存在

同时设\(s_{i,j}\)表示若\(f_{i,j}\)存在，其每个点自身与其邻居构成的点集（状压），并且由于要输出答案，还要记一下每个状态是从哪个点转移来的

然后我们就可以大力DP了，不过直接做的话由于要枚举起点\(O(n)\)，然后状态数是\(O(n\times 2^n)\)的，转移也要\(O(n)\)的复杂度，总体\(O(n^3\times 2^n)\)会被卡

我们仔细思考上面的方法，一个长度为\(k\)的环会在枚举\(k\)个起点的时候都能找到，但实际上我们只要找到其中一个即可

因此我们可以用一个经典trick，在枚举起点\(st\)之后，我们假定之后环上的所有点的编号必须小于等于\(st\)，这样就可以保证每个环只会在我们枚举到环上编号最大的点时才被枚举到了

因此总复杂度就变成了\(\sum_{i=1}^n i^2\times 2^i\le \sum_{i=1}^n n^2\times 2^i=n^2\times(2^{n+1}-2)\)，是\(O(n^2\times 2^n)\)级别的，就可以卡过了

#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=20;
int n,m,x,y,f[N][1<<N],ans[N],cyc[N],g[N],s[N][1<<N],pre[N][1<<N],cnt;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k,t,st; for (scanf("%d%d",&n,&m),i=0;i<n;++i) g[i]=1<<i;
	for (i=1;i<=m;++i) scanf("%d%d",&x,&y),--x,--y,g[x]|=(1<<y),g[y]|=(1<<x);
	for (st=n-1;~st;--st)
	{
		memset(f,0,sizeof(f)); memset(s,0,sizeof(s)); memset(pre,-1,sizeof(pre));
		for (f[st][1<<st]=1,s[st][1<<st]=g[st],i=0;i<(1<<st+1);++i)
		for (j=0;j<=st;++j) if (f[j][i])
		{
			if (s[j][i]==(1<<n)-1&&(g[j]&(1<<st)))
			{
				for (k=0;k<n;++k) if (!(i&(1<<k)))
				{
					for (t=0;t<n;++t) if ((i&(1<<t))&&(g[t]&(1<<k)))
					{
						ans[k]=t; break;
					}
				}
				int s=i,p=j; while (~p)
				cyc[cnt++]=p,s^=(1<<p),p=pre[p][s|(1<<p)];
				for (k=0;k<cnt;++k) ans[cyc[k]]=cyc[(k+1)%cnt];
				if (cnt==1) ans[cyc[0]]=(cyc[0]+1)%n;
				for (puts("Yes"),k=0;k<n;++k) printf("%d ",ans[k]+1);
				return 0;
			}
			for (k=0;k<=st;++k) if (!(i&(1<<k))&&(g[j]&(1<<k))&&!f[k][i|(1<<k)])
			f[k][i|(1<<k)]=1,pre[k][i|(1<<k)]=j,s[k][i|(1<<k)]=s[j][i]|g[k];
		}
	}
	return puts("No"),0;
}

F. Approximate Diameter

鬼神境界的一道题，很吃图论基本功，看了眼题目觉得很有趣，但却一点写不来，只能看看Tutorial的说

不妨设\(G\)为原图，\(G_i\)为加入第\(i\)条边后的图，同时\(C_G(u)\)为图上\(u\)到与它最远的点的距离

同时记\(d(G)\)为图的直径，\(r(G)\)为图的半径（即\(\min_\limits{1\le i\le n}C_G(i)\)），由定义我们可以知道\(r(G)\le C_G(u)\le d(G)\)

首先我们要明确一点，图的直径不能像树那样用两遍BFS求出，具体证明可以看下面

因此我们要用一个结论（如果知道这个结论的话对于这个求解的答案区间就能一眼看出意义所在了），就是\(d(G)\le 2\times r(G)\)

证明的话我们考虑直径的两个端点分别为\(u,v\)，半径的两个端点分别是\(a,b\)（这些点可能会有相同的但不影响）

则我们有\(d(G)=d(u,v)\le d(u,a)+d(v,a)\le d(a,b)+d(a,b)=2\times r(G)\)

如果我们像求树的直径那样，从\(1\)号点开始BFS，得到的最远的点为\(w\)，这个点不一定是\(u,v\)中的一个，因此是有问题的

不过如果像这样拿来放缩就没问题了，因此我们结合询问条件有：\(\frac{d(G)}{2}\le r(G)\le C_G(u)\le d(G)\le 2\times r(G)\le 2\times C_G(u)\le 2\times d(G)\)

因此我们随便取一个点\(u\)，容易发现\([C_G(u),2\times C_G(u)]\)之间的点均符合题意

那么此时我们可以\(O(n)\)处理一次询问了，但仅仅是这样还不够，我们还要考虑优化

一个很显然的性质就是随着边的加入\(C_{G_i}(u)\)是单调不升的，即对于\(i<j\)，总有\(C_{G_i}(u)\le C_{G_j}(u)\)

考虑我们可行的回答区间为\([C_{G_i}(u),2\times C_{G_i}(u)]\)和\([C_{G_j}(u),2\times C_{G_j}(u)]\)，不难发现如果两个区间有交那么这个区间交显然可以满足所有\([i,j]\)之间的询问

因此我们考虑对于当前的询问\(i\)，二分找到最大的且满足\(C_{G_j}(u)\le 2\times C_{G_i}(u)\)的\(j\)即可

由于对于边权全为\(1\)的图跑单源最短路的复杂度是\(O(n)\)的，因此总复杂度为\(O(n\log n\log q)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<queue>
#include<cstring>
#define RI register int
#define CI const int&
#define pb push_back
using namespace std;
const int N=100005,INF=1e9;
typedef pair <int,int> pi;
int n,m,q,x,y,dis[N],ans[N]; vector <pi> v[N]; queue <int> Q;
inline int BFS(CI lim)
{
	RI i; for (i=1;i<=n;++i) dis[i]=INF;
	Q.push(1); dis[1]=0; while (!Q.empty())
	{
		int now=Q.front(); Q.pop();
		for (auto [to,t]:v[now])
		if (t<=lim&&dis[to]>dis[now]+1)
		dis[to]=dis[now]+1,Q.push(to);
	}
	int mx=0; for (i=1;i<=n;++i) mx=max(mx,dis[i]); return mx;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d%d",&n,&m,&q),i=1;i<=m;++i)
	scanf("%d%d",&x,&y),v[x].pb(pi(y,0)),v[y].pb(pi(x,0));
	for (i=1;i<=q;++i)
	scanf("%d%d",&x,&y),v[x].pb(pi(y,i)),v[y].pb(pi(x,i));
	for (i=0;i<=q;)
	{
		int tmp=BFS(i),l=i,r=q,mid,ret;
		while (l<=r) if (tmp<=2*BFS(mid=l+r>>1)) ret=mid,l=mid+1; else r=mid-1;
		while (i<=r) ans[i++]=tmp;
	}
	for (i=0;i<=q;++i) printf("%d ",ans[i]);
	return 0;
}