526互联

AtCoder Grand Contest 045

发布时间 2023-09-27 18:55:08作者: Zhou_JK

A - Xor Battle

可以发现，从后往前扫，遇到一个 \(1\) 找后面是否有若干个 \(0\) 的位置的 \(a_i\) 与当前位置的异或和相等，用线性基维护一下就好了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=205;
int T;
int n;
long long a[N];
char s[N];
struct Basis
{
	static const int M=60;
	long long d[N];
	void clear()
	{
		memset(d,0,sizeof(d));
		return;
	}
	void insert(long long t)
	{
		for(int i=M;i>=0;i--)
			if(t&(1LL<<i))
			{
				if(d[i]) t^=d[i];
				else
				{
					for(int j=0;j<i;j++)
						if(t&(1LL<<j)) t^=d[j];
					for(int j=i+1;j<=M;j++)
						if(d[j]&(1LL<<i)) d[j]^=t;
					d[i]=t;
					break;
				}
			}
		return;
	}
	bool find(long long t)
	{
		for(int i=M;i>=0;i--)
			if(t&(1LL<<i))
			{
				if(d[i]) t^=d[i];
				else return false;
			}
		return true;
	}
}lb;
void solve()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	scanf("%s",s+1);
	lb.clear();
	for(int i=n;i>=1;i--)
		if(s[i]=='1')
		{
			if(!lb.find(a[i]))
			{
				printf("1\n");
				return;
			}
		}
		else if(s[i]=='0') lb.insert(a[i]);
	printf("0\n");
	return;
}
int main()
{
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}

B - 01 Unbalanced

不妨先将所有的 ? 填成 1，最后再调整。

把 1 看成 \(+1\)，0 看成 \(-1\)，做一个前缀和 \(s\)，问题就变成了求 \(s\) 的最大值减最小值的值最小。

考虑枚举 \(s\) 的最小值 \(\min\)，问题就变成了要使得 \(\max\) 最小。考虑从前往后决定每个位置是否将 ? 改成 0，对 \(s\) 产生的影响即为后缀 \(-2\)，可以证明这是最优的。

令 \(m=\min\\{s_i\\}\)，可以发现，当 \(\min=m-2\) 时，不可能比 \(\min=m\) 时优，故我们只需要求 \(\min=m,m-1\) 的情况就好了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000005;
const int INF=1061109567;
int n;
char s[N];
int a[N];
int sum[N];
int suf[N];
int calc(int Min)
{
	static int b[N];
	int add=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='?'&&suf[i]-add-2>=Min) add+=2;
		b[i]=sum[i]-add;
	}
	int Max=max(*max_element(b+1,b+n+1),0);
	return Max-Min;
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
		if(s[i]=='1'||s[i]=='?') a[i]=1;
		else if(s[i]=='0') a[i]=-1;
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+a[i];
	suf[n+1]=INF;
	for(int i=n;i>=1;i--)
		suf[i]=min(suf[i+1],sum[i]);
	int m=min(*min_element(sum+1,sum+n+1),0);
	printf("%d",min(calc(m),calc(m-1)));
	return 0;
}

C - Range Set

不妨令 \(A\leq B\)，这两种情况是等价的，因为我们可以开始将整个序列染成 \(1\)。

考虑一个最后的字符串是否能被达到，可以将所有的长度 \(\ge A\) 的 \(0\) 段染成 \(1\)，如果串内是否有长度 \(\ge B\) 的 \(1\) 段的话肯定是合法的，因为我们可以每次拓展一个 \(0\)，否则是不合法的。

合法的方案很难算，不妨计算不合法的方案。

令 \(f_{i,0/1}\) 表示长度为 \(i\)，以 \(0/1\) 结尾，段内没有长度 \(< A\) 的 \(0\) 的方案数，枚举上一个段的位置转移。

令 \(dp_{i,0/1}\) 表示长度为 \(i\)，以 \(0/1\) 结尾，段内没有长度 \(< A\) 的 \(0\) 和长度 \(< B\) 的 \(1\) 的方案数，枚举上一个段的位置转移。

注意最后的长度 \(< B\) 的段可以 \(0\) 结尾。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=5005;
const int MOD=1000000007;
int n,a,b;
long long f[N][2];
long long g[N];
long long dp[N][2];
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	if(a>b) swap(a,b);
	if(b==1)
	{
		printf("%lld",ksm(2,n));
		return 0;
	}
	f[0][0]=f[0][1]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<i;j++)
			f[i][1]=(f[i][1]+f[j][0])%MOD;
		for(int j=0;j+a<=i;j++)
			f[i][0]=(f[i][0]+f[j][1])%MOD;
	}
	g[0]=1;
	for(int i=1;i<=n;i++)
		g[i]=(f[i][0]+f[i][1])%MOD;
	long long ans=0;
	for(int i=1;i<n;i++)
	{
		if(i<a) dp[i][0]=(dp[i][0]+1)%MOD;
		for(int j=max(i-a+1,1);j<i;j++)
			dp[i][0]=(dp[i][0]+dp[j][1])%MOD;
		if(i<b) dp[i][1]=(dp[i][1]+g[i-1])%MOD;
		for(int j=max(i-b+1,1);j<i;j++)
			dp[i][1]=(dp[i][1]+dp[j][0]*(i-j==1?1:g[i-j-2])%MOD)%MOD;
		if(i+b-1>=n) ans=(ans+dp[i][0]*g[n-i-1]%MOD)%MOD;
		if(i+a-1>=n) ans=(ans+dp[i][1])%MOD;
	}
	printf("%lld",(ksm(2,n)-ans+MOD)%MOD);
	return 0;
}

D - Lamps and Buttons

可以发现，不合法的情况为环中一个点都没有被点亮，或者有个自环他去点了。

考虑枚举第一个 \(p_i=i\) 且 \(i\leq A\) 的位置，如果不存在则 \(i=A+1\)。可以发现对于所有 \(A< j\le n\)，\(j\) 所在的环至少存在一个小于 \(i\) 的点。

对于 \(i\)，我们需要满足 \(j< i\) 的所有位置 \(p_j\neq j\)，这个可以容斥解决。可以将点分成几类：

  • \(p_i = i\) 的点，可以将这些点去掉。
  • \(1\leq i< t\) 的点，记为 \(a\) 个。
  • \(A< i\le n\) 的点。记为 \(b\) 个。每个点所在环中都要至少存在一个小于 \(i\) 的点。
  • \(t< i\le A\) 的点。记为 \(c\) 个。

每次考虑依次插入每种点，计算方案数，最后乘一个容斥系数就好了。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=10000005,M=5005;
const int MOD=1000000007;
int n,m;
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
long long fac[N],inv[N];
void init(int n=10000000)
{
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%MOD;
	inv[n]=ksm(fac[n],MOD-2);
	for(int i=n;i>=1;i--)
		inv[i-1]=inv[i]*i%MOD;
	return;
}
long long C(int n,int m)
{
	if(m>n) return 0;
	else return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main()
{
	scanf("%d%d",&n,&m);
	init();
	long long ans=0;
	for(int i=1;i<=m+1;i++)
		for(int j=0;j<i;j++)
		{
			int a=i-1-j,b=n-m,c=max(m-i,0);
			long long res=C(i-1,j);
			res=(res*fac[a])%MOD;
			res=(res*fac[a+b-1]%MOD*inv[a-1]%MOD)%MOD;
			res=(res*fac[a+b+c]%MOD*inv[a+b]%MOD)%MOD;
			if(j&1) ans=(ans-res+MOD)%MOD;
			else ans=(ans+res)%MOD;
		}
	printf("%lld",ans);
	return 0;
}

E - Fragile Balls

考虑 \(C_i=1\) 的情况，将原图上连一条 \(A_i\to B_i\) 的边，可以分成几类：

  1. 只包含一个自环；
  2. 只包含一个长度大于等于 \(2\) 的简单环；
  3. 联通块的边数大于点数。

当存在第 2 种联通块的话，答案就是 \(-1\)；否则答案就是 \(P\)，\(P\) 表示图中的 \(A_i\neq B_i\) 的数量。

考虑 \(C_i\ge 1\) 的情况，我们可以调整使得有解。将一个当前联通块外面的点放进来，然后再处理。可以发现，令 \(cnt\) 表示第二种联通块的数量，我们至少需要额外多 \(cnt\) 步。

考虑从外面移入一个球 \(x\)，分几种情况讨论当前点多出的步数：

  1. \(x\) 在第 1 种联通块内，对联通块数贡献为 \(-(C_x-2)\)，需要多花费两步。
  2. \(x\) 在第 2 种联通块内，对联通块数贡献为 \(-(C_x-1)\)，不需要多花费步数。
  3. \(x\) 在第 3 种联通块内，且 \(A_x=B_x\)，对联通块数贡献为 \(-(C_x-1)\)，需要多花费一步。
  4. \(x\) 在第 3 种联通块内，且 \(A_x\neq B_x\)，对联通块数贡献为 \(-(C_x-1)\)，不需要多花费步数。

对于 1 和 2，我们需要一个 3 或者 4 先移动进去，然后再操作。显然不需要多花费步数的都可以取。

接下来就只有 1 和 3 了，考虑枚举 1 的个数，然后 two-pointer 维护就好了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1000005;
const long long INF=4557430888798830399;
int n,m;
int a[N],b[N],c[N];
int fa[N];
int getf(int v)
{
	if(v==fa[v]) return v;
	fa[v]=getf(fa[v]);
	return fa[v];
}
void merge(int u,int v)
{
	int f1=getf(u),f2=getf(v);
	if(f1!=f2) fa[f2]=f1;
	return;
}
int in[N],siz[N];
bool circle[N];
vector<int>pos[4];
long long s2[N],s0[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	long long ans=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
		if(a[i]!=b[i]) ans++;
		merge(a[i],b[i]);
		in[a[i]]++;
	}
	memset(circle,true,sizeof(circle));
	for(int i=1;i<=n;i++)
	{
		siz[getf(i)]++;
		if(in[i]>1) circle[getf(i)]=false;
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(getf(i)==i)
		{
			if(circle[i]&&siz[i]>1) cnt++;
		}
	if(cnt==0)
	{
		printf("%lld",ans);
		return 0;
	}
	ans+=cnt;
	for(int i=1;i<=m;i++)
		if(c[i]>=2)
		{
			int u=getf(a[i]);
			if(circle[u])
			{
				if(siz[u]==1) pos[0].push_back(c[i]-2);
				else if(siz[u]>1) pos[1].push_back(c[i]-1);
			}
			else
			{
				if(a[i]==b[i]) pos[2].push_back(c[i]-1);
				else pos[3].push_back(c[i]-1);
			}
		}
	for(int p=0;p<=3;p++)
		sort(pos[p].begin(),pos[p].end(),greater<int>());
	long long sum=0;
	for(int p=0;p<=3;p++)
		for(int c:pos[p])
			sum+=c;
	if(sum<cnt)
	{
		printf("-1");
		return 0;
	}
	if(pos[2].empty()&&pos[3].empty())
	{
		printf("-1");
		return 0;
	}
	if(pos[3].empty()) ans++,cnt-=pos[2].front(),pos[2].erase(pos[2].begin());
	else cnt-=pos[3].front(),pos[3].erase(pos[3].begin());
	for(int c:pos[3])
		cnt-=c;
	for(int c:pos[1])
		cnt-=c;
	pos[3].clear();
	pos[1].clear();
	if(cnt<=0)
	{
		printf("%lld",ans);
		return 0;
	}
	for(int i=1;i<=pos[0].size();i++)
		s0[i]=s0[i-1]+pos[0][i-1];
	for(int i=1;i<=pos[2].size();i++)
		s2[i]=s2[i-1]+pos[2][i-1];
	long long res=INF;
	for(int i=pos[0].size(),j=0;i>=0;i--)
	{
		while(j<=pos[2].size()&&s0[i]+s2[j]<cnt) j++;
		if(j<=pos[2].size()) res=min(res,2LL*i+j);
	}
	printf("%lld",ans+res);
	return 0;
}

F - Division into Multiples

首先可以将 \(A,B,C\) 转化为两两互质的形式。

考虑每组 \(x,y\) 需要满足的条件，即为 \(Ax+By\equiv 0 \pmod C\)，令 \(D\equiv \frac{A}{B} \pmod C\) 方程的通解为：

\[\begin{cases}x\equiv k\pmod C \\ y\equiv -k\cdot D\pmod C\end{cases} \]

考虑计算出可能成为答案的那些解 \((x,y)\)。

考虑一个高为 \(D\)，宽为 \(C\) 的网格，初始位于 \((0,0)\)，每次向右上前进一格。当 \(x=C\) 的时候令 \(x=0\)，当 \(y=D\) 的时候令 \(y=0\)。当 \(y=0\) 时记录这时的 \(x\)，\((\frac{now}{D},C−x)\) 即为一个可能的解，\(now\) 为前进的步数。

不妨令 \(C\ge D\)，\(C< D\) 的时候同理。先将 \((C,0)\) 加入可能的解中，我们接下来就不需要考虑 \(x< H\) 的情况，那么就可以将宽缩小为 \(W-H\)，大概跟欧几里得差不多吧。

观察上面的算法，将 \((x,y)\) 若按 \(x\) 排序，则是若干个等差数列的形式，我们只需要将端点记录下来，且满足 \(x_i-x_{i-1}\le x_{i+1}-x_i,y_i-y_{i-1}\ge y_{i+1}-y_i\)。

因为每次矩形的高一定会越来越小，故一定满足 \(y_i-y_{i-1}\ge y_{i+1}-y_i\)；相反的，也满足 \(x_i-x_{i-1}\le x_{i+1}-x_i\)。

将所有的 \((x_i,y_i)\) 的图像绘制出来，可以发现这是一个下凸包。

可以发现，肯定选两种相邻或相同的 \((x,y)\) 组成是最优的。因为如果选了 \(i,j\) 这两个二元组（\(i,j\) 表示选的二元组的下标）满足 \(j-i\ge 2\)，显然将 \(i,j\) 贴近更优秀。所以我们肯定是选一条线段和下一个条线段的第一个点中的若干个。

那么就可以二分答案，对于每天线段判断是否可以选 \(mid\) 个点，令当前线段的左上角为 \((x_i,y_i)\)，下一条线段的左上角为 \((x_j,y_j)\)，需要满足的条件为：

\[\begin{cases}\sum\limits_{k=1}^{mid}x_i+z_k\cdot \Delta x\le X \\ \sum\limits_{k=1}^{mid}y_j+(cnt-z_k-1)\cdot \Delta y\le Y\end{cases} \]

将两式转化一下：

\[\begin{cases}\sum\limits_{k=1}^{mid} z_k \le \lfloor \frac{X-x_i\cdot mid}{\Delta x} \rfloor \\ \sum\limits_{k=1}^{mid}(cnt-z_k-1)\le \lfloor \frac{Y-y_j\cdot mid}{\Delta y}\rfloor \end{cases} \]

将相加，可得：

\[\sum\limits_{k=1}^{mid} z_k + \sum\limits_{k=1}^{mid}(cnt-z_k-1)=mid\cdot (cnt-1)\leq \lfloor \frac{X-x_i\cdot mid}{\Delta x} \rfloor + \lfloor \frac{Y-y_j\cdot mid}{\Delta y}\rfloor \]

代码：

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int T;
int ex_gcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	int d=ex_gcd(b,a%b,x,y);
	int tmp=x;
	x=y,y=tmp-a/b*y;
	return d;
}
int getinv(int A,int MOD)
{
	int x,y;
	int d=ex_gcd(A,MOD,x,y);
	if(d!=1) return -1;
	return (x+MOD)%MOD;
}
int a,x,b,y,c;
int d;
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
vector<pair<int,int> >pos;
vector<int>cnt;
void getpos()
{
	pos.clear(),cnt.clear();
	int W=c,H=d;
	int now=0;
	while(true)
	{
		int r=W/H;
		pos.push_back(make_pair(1LL*now*getinv(d,c)%c,now%c==0?c:(c-now+c)%c)),cnt.push_back(r); 
		now+=r*H;
		W%=H;
		if(W==0) break;
		H%=W;
		if(H==0) H=W;
	}
	pos.push_back(make_pair(c,0));
	return;
}
void solve()
{
	scanf("%d%d%d%d%d",&a,&x,&b,&y,&c);
	int G;
	G=gcd(a,b),a/=G,b/=G,c/=gcd(G,c);
	G=gcd(a,c),a/=G,c/=G,y/=G;
	G=gcd(b,c),b/=G,c/=G,x/=G;
	a%=c,b%=c;
	if(c==1)
	{
		printf("%d\n",x+y);
		return;
	}
	d=1LL*a*getinv(b,c)%c;
	getpos();
	int ans=0;
	for(size_t i=0;i<cnt.size();i++)
	{
		int xl=pos[i].first,yl=pos[i].second,xr=pos[i+1].first,yr=pos[i+1].second;
		int dx=(xr-xl)/cnt[i],dy=(yl-yr)/cnt[i];
		int l=0,r=x+y,res=0;
		while(l<=r)
		{
			int mid=((long long)l+r)/2;
			auto check=[=](int mid)
			{
				long long p=(x-1LL*xl*mid)/dx,q=(y-1LL*yr*mid)/dy;
				return (x-1LL*xl*mid)>=0&&(y-1LL*yr*mid)>=0&&p+q>=1LL*cnt[i]*mid;
			};
			if(check(mid)) res=mid,l=mid+1;
			else r=mid-1;
		}
		ans=max(ans,res);
	}
	printf("%d\n",ans);
	return;
}
int main()
{
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}