Preface

前两天刚买了个U盘，然后今天又水了一个（乐

做完签到感觉F很一眼，结果一个特判重复出现两次的地方写挂了，苦苦白调一个小时（甚至被迫在ACM比赛里写对拍）

然后赶紧把本质很简单的E写了，最后一个小时堪堪写了I就结束了

感觉题目出得还是挺有意思的，说成Div3的难度还是有点低了

主要打CF补题的时候就一直靠cup-pyy大佬的题解过活，今天总体体验还是很棒的说

（以上直接复制粘贴自我在知乎该问题的回答，以下题目按我比赛时做的顺序写）

云影密码

刚开赛不知道哪题最简单，先找个A题签到下，直接模拟即可

这里小小吐槽一嘴牛客的编译器开了register就会报错，刚开始狠狠地CE了好几发

#include<cstdio>
#include<iostream>
#include<cstring>
#define RI int
#define CI const int&
using namespace std;
const int N=1000005;
int t,n; char s[N],ans[N],cnt;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; int x=0,cnt=0; for (scanf("%s",s+1),n=strlen(s+1),i=1;i<=n;++i)
		if (s[i]=='0') ans[++cnt]=x-1+'a',x=0; else x=x+s[i]-'0';
		if (x) ans[++cnt]=x-1+'a'; for (i=1;i<=cnt;++i) putchar(ans[i]); putchar('\n');
	}
	return 0;
}

引流

看一眼榜，纯签到题

#include<cstdio>
#include<iostream>
#include<string>
#define RI int
#define CI const int&
using namespace std;
const int N=1000005;
int t,n; string s;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	cin>>s; cout<<"guan zhu "<<s<<" miao, guan zhu "<<s<<" xie xie miao!";
	return 0;
}

上分

由于数据范围很小，可以直接枚举全排列然后验证

然后因为没注意到时间可以超过比赛总时长WA了一发，苦路西

好像这个问题和TSP有点相似啊，那如果\(n\le 20\)应该是有状压DP的做法的，具体懒得写了

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI int
#define CI const int&
using namespace std;
const int N=10;
int t,n,m,a[N],b[N],c[N],id[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; int ans=0; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
		scanf("%d%d%d",&a[i],&b[i],&c[i]),id[i]=i;
		do
		{
			int t=0,ret=0; for (i=1;i<=n;++i)
			if (t+=b[id[i]],t<=m) ret+=max(a[id[i]]/10*3,a[id[i]]-a[id[i]]*4/1000*t-50*c[id[i]]);
			ans=max(ans,ret);
		}while (next_permutation(id+1,id+n+1));
		printf("%d\n",ans);
	}
	return 0;
}

三门问题

显然换是最优的策略，然后我们发现我们刚开始时没选到轿车的概率是\(\frac{n-1}{n}\)，然后去掉一个错误项之后就是在\(\frac{1}{n-2}\)个门中挑一个

最后答案就是\(\frac{n-1}{n\times (n-2)}\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI int
#define CI const int&
using namespace std;
int t,n;
inline int gcd(CI n,CI m)
{
	return m?gcd(m,n%m):n;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d",&n); int x=n-1,y=n*(n-2),d=gcd(x,y);
		printf("%d %d\n",x/d,y/d);
	}
	return 0;
}

小菲爱数数

很套路的题目啊，首先不难想到先分解质因数，然后分别考虑每一个质因子的贡献

考虑把含有这个质因数的位置置为\(1\)，直接含有\(1\)的区间总数不好算，我们容斥去算不含有\(1\)的区间总数就很trivial了

然后实现的时候由于又多组数据所以在枚举质因数和清空的时候都要技巧性地记录一下，具体就看代码了

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#define RI int
#define CI const int&
using namespace std;
const int N=1000005;
int t,n,x,pri[N],cnt,stk[N],top; bool vis[N]; vector <int> v[N];
inline void init(CI n)
{
	for (RI i=2,j;i<=n;++i)
	{
		if (!vis[i]) pri[++cnt]=i;
		for (j=1;j<=cnt&&i*pri[j]<=n;++j)
		if (vis[i*pri[j]]=1,i%pri[j]==0) break;
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init(1000000);t;--t)
	{
		RI i,j; for (top=0,scanf("%d",&n),i=1;i<=n;++i)
		{
			for (scanf("%d",&x),j=1;j<=cnt&&1LL*pri[j]*pri[j]<=x;++j)
			if (x%pri[j]==0)
			{
				v[pri[j]].push_back(i); stk[++top]=pri[j];
				while (x%pri[j]==0) x/=pri[j];
			}
			if (x>1) v[x].push_back(i),stk[++top]=x;
		}
		sort(stk+1,stk+top+1); top=unique(stk+1,stk+top+1)-stk-1;
		long long ans=0; for (i=1;i<=top;++i)
		{
			long long ret=1LL*n*(n+1)/2LL; int pre=0;
			for (int x:v[stk[i]]) ret-=1LL*(x-pre-1)*(x-pre)/2LL,pre=x;
			ret-=1LL*(n-pre)*(n-pre+1)/2LL; ans+=ret;
		}
		for (printf("%lld\n",ans),i=1;i<=top;++i) v[stk[i]].clear();
	}
	return 0;
}

最小异或对

签到题部分结束了，然后当时榜上趋势是做EF，然后我E看了眼一时间没想到，然后F又是如此的套路就开写了

结果因为一个把重复的数特判的部分写了个极其傻逼的错误，WA了好几发不说还浪费了大量时间调试和写对拍

回归正题首先我们考虑原问题的弱化版本，给定一个集合\(S\)，求其中任意两个元素的异或值的最小值怎么做

凭借着我OI时期的一点点印象，我们可以把所有数扔进0/1Trie中，然后最后的答案一定是在0/1Trie上位置相邻的两个数之间产生

因此有了这个思路之后对于动态插入和删除操作也不难了，只要维护每个数在0/1Trie上的前驱与后继即可

然后这里我的写法就很愚蠢了，我是用一个链表维护当前所有数按0/1Trie上的顺序排列后的次序，然后在0/1Trie上维护每个点的子树中最右侧的儿子节点

然后插入的时候利用类似于线段树上二分的思想，对于当前插入的某个数，若它在插入的某一位上为\(1\)，就可以在这个节点的左儿子的子树里找一个最右侧的数，这样就在插入的时候找出每个数的前驱了

于是这样就做完了，链表部分直接开个map维护一下就完事，总复杂度为\(O(n\log |x|)\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<cstring>
#define RI int
#define CI const int&
using namespace std;
const int N=200005,P=30,INF=1<<30;
int n,x,ch[N*P][2],rst[N*P],tot=1,t,L,R; char s[10];
map <int,int> pre,nxt,cnt; multiset <int> hp;
inline void pushup(CI now)
{
	rst[now]=~rst[ch[now][1]]?rst[ch[now][1]]:rst[ch[now][0]];
}
inline void insert(CI x,CI now=1,CI y=P-1)
{
	if (!~y) return (void)(rst[now]=x); int d=(x>>y)&1; if (!ch[now][d]) ch[now][d]=++tot;
	if (d&&~rst[ch[now][0]]) L=rst[ch[now][0]]; insert(x,ch[now][d],y-1); pushup(now);
}
inline void remove(CI x,CI now=1,CI y=P-1)
{
	if (!~y) return (void)(rst[now]=-1); remove(x,ch[now][(x>>y)&1],y-1); pushup(now);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&n),memset(rst,-1,sizeof(rst)),nxt[-1]=INF,pre[INF]=-1;n;--n)
	{
		scanf("%s",s+1); switch (s[1])
		{
			case 'A':
				if (scanf("%d",&x),++cnt[x]==2) ++t;
				if (cnt[x]==1)
				{
					L=-1; insert(x); R=nxt.count(L)?nxt[L]:INF;
					if (~L&&R!=INF) hp.erase(hp.find(L^R)),hp.insert(L^x),hp.insert(R^x);
					else if (~L) hp.insert(L^x); else if (R!=INF) hp.insert(R^x);
					nxt[L]=x; pre[x]=L; nxt[x]=R; pre[R]=x;
				}
				break;
			case 'D':
				if (scanf("%d",&x),--cnt[x]==1) --t;
				if (cnt[x]==0)
				{
					L=pre[x]; R=nxt[x]; remove(x);
					if (~L&&R!=INF) hp.erase(hp.find(L^x)),hp.erase(hp.find(R^x)),hp.insert(L^R);
					else if (~L) hp.erase(hp.find(L^x)); else if (R!=INF) hp.erase(hp.find(R^x));
					nxt[L]=R; pre[R]=L;
				}
				break;
			case 'Q':
				if (t) puts("0"); else printf("%d\n",*hp.begin());
				break;
		}
	}
	return 0;
}

然后今天写博客的时候突然发现其实有简单很多的做法，完全不需要再开一个链表维护的说

我们可以直接在0/1Trie上维护每个点最左侧和最右侧的数，然后在每次插入和删除的时候直接在0/1Trie上合并子节点的时候维护即可

具体代码略了，估计这样实现的话20min就可以轻松写完了，而且出错点少了很多

UPD：我好像纯纯小丑了，对于序列的结论是直接排序之后找相邻的数即可，所以只要单纯地维护前驱后继即可

不过只用0/1Trie的写法也是可以的，我TM比赛的把两种写法混在一起写，属实逆天

Construction Complete!

刚开始竟然没一眼秒掉，还是在ztc的提醒下才发现是个傻逼题（不过话说这题为什么过的人这么少啊）

考虑如果我们枚举左上的端点的话，那么区域里没有障碍的限制是很容易满足的，直接二位前缀和预处理一下即可

现在的主要问题就是这个到某个已有建筑的距离小于等于\(d\)怎么搞，其实就是一个多源最短路的思想

我们从每个已有建筑开始跑一个多源最短路（由于边权都是\(1\)所以其实就是BFS），然后得出每个格子到距离它最近的已有建筑的距离\(dis_{i,j}\)

然后若\(dis_{i,j}\le d\)我们就给这个格子的权值置为\(1\)，然后再用一个二位前缀和维护下，每次查询看这个子矩阵里有没有一个为\(1\)的元素即可

总复杂度\(O(n\times m)\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
#define RI int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=1000005,INF=1e9,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int t,n,m,r,c,d; char s[N]; queue <pi> q;
vector <char> a[N]; vector <int> dis[N],sp[N],sum[N];
inline void BFS(void)
{
	while (!q.empty())
	{
		int x=q.front().first,y=q.front().second; q.pop();
		for (RI i=0;i<4;++i)
		{
			int nx=x+dx[i],ny=y+dy[i];
			if (nx<1||nx>n||ny<1||ny>m) continue;
			if (dis[nx][ny]>dis[x][y]+1)
			dis[nx][ny]=dis[x][y]+1,q.push(pi(nx,ny));
		}
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d%d%d%d",&n,&m,&r,&c,&d),i=1;i<=n;++i)
		for (scanf("%s",s+1),a[i].resize(m+1),j=1;j<=m;++j) a[i][j]=s[j];
		for (i=1;i<=n;++i) for (dis[i].resize(m+1),j=1;j<=m;++j)
		if (a[i][j]=='x') q.push(pi(i,j)),dis[i][j]=0; else dis[i][j]=INF;
		for (BFS(),i=0;i<=n;++i) sp[i].resize(m+1),sum[i].resize(m+1);
		for (i=1;i<=n;++i) for (j=1;j<=m;++j)
		sp[i][j]=dis[i][j]<=d,sum[i][j]=a[i][j]=='.';
		for (i=1;i<=n;++i) for (j=1;j<=m;++j)
		sp[i][j]+=sp[i][j-1],sum[i][j]+=sum[i][j-1];
		for (j=1;j<=m;++j) for (i=1;i<=n;++i)
		sp[i][j]+=sp[i-1][j],sum[i][j]+=sum[i-1][j];
		int ans=0; for (i=1;i+r-1<=n;++i) for (j=1;j+c-1<=m;++j)
		{
			int S=sp[i+r-1][j+c-1]-sp[i+r-1][j-1]-sp[i-1][j+c-1]+sp[i-1][j-1];
			int W=sum[i+r-1][j+c-1]-sum[i+r-1][j-1]-sum[i-1][j+c-1]+sum[i-1][j-1];
			if (S>0&&W==r*c) ++ans;
		}
		printf("%d\n",ans);
	}
	return 0;
}

最大公约数求和

这题纯被ztc带飞，直接不解释欧拉筛肝薄纱

首先比赛时认为\(i^k\)那部分可以直接快速幂硬上（事实也确实是可以硬上），所以就只考虑\(\gcd(i,k)\)那部分

然后由于\(G(x)=\gcd(x,k)\)显然是个不完全积性函数，那么我们可以用欧拉筛来做

首先若\(x\)为质数，只要看\(x|k\)是否成立即可，即可得到所有质数的\(G(x)\)

然后考虑在欧拉筛的过程中，对于数\(x\)，设其最小质因子为\(p\)

若\(\frac{k}{g(\frac{x}{p})} \equiv 0 (\bmod \ p)\)，即\((G(\frac{x}{p})\times p)|k\)，则有\(G(x)=p\times G(\frac{x}{p})\)，否则有\(G(x)=G(\frac{x}{p})\)

因此这部分的复杂度就是\(O(n)\)的，最后跑的时候由于一个快速幂的常数比较小，可以大力Rush过去

不过在写题解的时候又有发现，显然\(P(x)=x^k\)是个完全积性函数，我们只要对质数的情况暴力快速幂一下，然后其它的都可以推出来

这样总复杂度就变成\(O(\pi(n)\times \log k+n)\)的了，代入\(\pi(n)=\frac{n}{\ln n}\)得到总复杂度大约就是\(O(\frac{\log k}{\ln n}\times n+n)\)的，就可以从2800ms压到1000ms了

#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI int
#define CI const int&
using namespace std;
const int N=20000005,mod=1e9+7;
int n,pri[N],cnt,P[N],G[N],ans=1; bool vis[N]; long long k;
inline int quick_pow(int x,int p,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	P[1]=1; G[1]=1; int kk=k%(mod-1);
	for (RI i=2,j;i<=n;++i)
	{
		if (!vis[i]) if (pri[++cnt]=i,P[i]=quick_pow(i,kk),k%i) G[i]=1; else G[i]=i;
		for (j=1;j<=cnt&&i*pri[j]<=n;++j)
		{
			if (k%(G[i]*pri[j])) G[i*pri[j]]=G[i]; else G[i*pri[j]]=G[i]*pri[j];
			if (vis[i*pri[j]]=1,P[i*pri[j]]=1LL*P[i]*P[pri[j]]%mod,i%pri[j]==0) break;
		}
		(ans+=1LL*P[i]*G[i]%mod)%=mod;
	}
}
signed main()
{
	return scanf("%lld%lld",&n,&k),init(n),printf("%lld",ans),0;
}

魔术卡片

思博题，比赛的时候最后心态不是很平稳没仔细把题看了，其实感觉还是很有意思的一个构造题（构造题精通的被动没触发）

我们考虑给\(1\sim n\)的数字都对应一个八位的二进制数表示其在每张卡片上是否出现过

考虑对于数字\(x\)，设它没有在第\(c_1,c_2,c_3\cdots\)张卡片上出现过，则说明除了\(x\)以外的所有数字\(y\)都在\(c_1,c_2,c_3\cdots\)这些卡片上出现过

换句话说在所有\(x\)为\(0\)的位置上\(y\)至少有一个\(1\)存在，但是这样正着思考还是不够清晰我们转换下思路若\(y\)不合法则说明\(y\)所有出现\(1\)的位置\(x\)也出现\(1\)了，即说明\(y\)是\(x\)的一个子集

因此我们再做一个推广就有结论：没有一个数对应的二进制数是其它数对应的二进制数的子集

然后构造方法就很多了，参照题解里的简单方法，我们注意到\(C_8^4=70>60\)，因此可以选取所有二进制表示下\(1\)的个数为\(4\)的八位二进制数来构造，这些数之间显然不会出现某个数是另一个数的子集的情况

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#define RI int
#define CI const int&
using namespace std;
int t,n; vector <int> v[8];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=0;i<8;++i) v[i].clear();
		int cnt=0; for (i=0;i<(1<<8);++i)
		{
			int cur=0; for (j=0;j<8;++j) if (i&(1<<j)) ++cur;
			if (cur!=4) continue;
			for (++cnt,j=0;j<8;++j) if (i&(1<<j)) v[j].push_back(cnt);
			if (cnt==n) break;
		}
		for (puts("8"),i=0;i<8;++i)
		{
			for (printf("%d ",v[i].size()),j=0;j<v[i].size();++j)
			printf("%d ",v[i][j]); putchar('\n');
		}
	}
	return 0;
}

推队

状态设计有手就行，但转移比较复杂的DP，比赛时我肯定是没信心写完调出来的

很容易想到设\(f_{i,c_1,c_2,c_3}\)表示击败对手的前\(i\)个精灵之后，攻击等级为\(c_1\)，防御等级为\(c_2\)，速度等级为\(c_3\)时剩余的最大hp

考虑转移，由于\(k\)的范围很小很小，不难想到暴力枚举在与当前对手的精灵战斗后每个技能的等级，问题就是关于强化和攻击的顺序如何安排

一个比较naive的想法如果对于回合制游戏稍微有所了解的都知道肯定是先放强化（并且强化防御的一定先放），然后再进行攻击时最优的

但是转念一想这道题的数值不一定是随等级升高而升高的，这样先提升完再打好像就不是最优了

遂感觉GG去看题解，好家伙结果发现是我想多了，这里直接引一下官方题解里的说法：

虽然提升等级可能会导致属性值降低，但是我们可以发现在最优策略中，击败第\(i\)只精灵后每项属性一定不会低于对战第\(i\)只精灵之前的属性

因为强化某项属性值但是使得这项属性降低对我们当前的对战是没有好处的

我们完全可以选择该回合强化到更高的属性值或者这回合不强化全部留到与对手下一只精灵对战时强化，而这两种策略中一定至少有一种不劣于使某项属性值降低的策略

因此按照之前的想法做就可以了，显然在点完强化后我们可以\(O(1)\)模拟战斗过程，因此总复杂度就是\(O(n\times k^7)\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define RI int
#define CI const int&
using namespace std;
const int N=10005;
int t,n,k,A[4],D[4],S[4],H,h,a,d,s,f[N][4][4][4];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d%d",&n,&k,&H),i=0;i<=n;++i) memset(f[i],-1,sizeof(f[i]));
		for (i=0;i<=k;++i) scanf("%d",&A[i]);
		for (i=0;i<=k;++i) scanf("%d",&D[i]);
		for (i=0;i<=k;++i) scanf("%d",&S[i]);
		for (f[0][0][0][0]=H,i=0;i<n;++i)
		{
			scanf("%d%d%d%d",&h,&a,&d,&s);
			RI c1,c2,c3; for (c1=0;c1<=k;++c1)
			for (c2=0;c2<=k;++c2) for (c3=0;c3<=k;++c3)
			if (f[i][c1][c2][c3]>0)
			{
				RI t1,t2,t3; for (t1=c1;t1<=k;++t1)
				for (t2=c2;t2<=k;++t2) for (t3=c3;t3<=k;++t3)
				{
					int hp=f[i][c1][c2][c3]; for (j=1;j<=t2-c2;++j)
					{
						hp-=max(0,a-D[c2+j-1+(S[c3]>=s)]);
						if (hp<=0) break;
					}
					if (hp<=0) continue;
					int D1=max(0,a-D[t2]),D2=max(0,A[t1]-d);
					if (!D2) continue; if (1LL*(t1-c1+t3-c3)*D1>=hp) continue;
					if (!D1) { f[i+1][t1][t2][t3]=max(f[i+1][t1][t2][t3],hp); continue; }
					hp-=(t1-c1+t3-c3)*D1; int tim=(h+D2-1)/D2-(S[t3]>=s);
					if (1LL*tim*D1>=hp) continue; hp-=tim*D1;
					f[i+1][t1][t2][t3]=max(f[i+1][t1][t2][t3],hp);
				}
			}
		}
		int ans=-1; for (RI c1=0,c2,c3;c1<=k;++c1)
		for (c2=0;c2<=k;++c2) for (c3=0;c3<=k;++c3)
		ans=max(ans,f[n][c1][c2][c3]); printf("%d\n",ans);
	}
	return 0;
}