AGC045部分题解

101 阅读 0 评论 67 点赞

我是靠谱客的博主甜美月光，这篇文章主要介绍AGC045部分题解，现在分享给大家，希望可以做个参考。

比赛传送门

太菜了，赛时只能搞个一题……

T1

假如每个 $S_i=1$ 处的 $A_i$ 都可以被后面的 $S_j=0$ 的 $A_j$ 们异或得到，那么最后就一定可以变成 $0$ ，否则不能，因为如果满足这样的条件的话，无论 $1$ 选手是否异或 $A_i$ ， $0$ 选手都能够有办法抵消 $A_i$ 的贡献。

实现的话用线性基判断一下就好了，这题可以做到 $O (n)$ ，但是 $n$ 不知为什么这么小所以就随便写了个 $O(n^2)$ 的。

代码如下：

复制代码

#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
 
namespace my
{
	//-----------------------------------------------------------------------------
	inline char cn()
	{
		static char buf[1000010],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
	}
	#define cn getchar
	template<class TY>void read(TY &x)
	{
		x=0;int f1=1;char ch=cn();
		while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}
		while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
	}
	char OP[1000030],Zhan[30];int op=0,Top;
	void fcheck(int type=0){if(type||op>=1000000)fwrite(OP,1,op,stdout),op=0;}
	template<class TY>inline void write(TY x)
	{
		if(x==0){OP[op++]='0';fcheck();return;}
		Top=0;while(x)Zhan[++Top]=x%10+'0',x/=10;
		while(Top)OP[op++]=Zhan[Top--];fcheck();
	}
	#define K_G OP[op++]=' '
	//----------------------------快读快输 ----------------------------------------
	
	//--------------------------------------------------------------------------------------------
	#define ll long long
	#define uint unsigned int
	#define ull unsigned long long
	#define INV(x) ksm(x,mod-2)
	const int maxn=100010,inf=1000000007;
	int mod=998244353;
	void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
	int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
	int fac[maxn],inv_fac[maxn],inv[maxn];
	void work_math()//阶乘
	{
		inv[1]=1;for(int i=2;i<=maxn-10;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		fac[0]=inv_fac[0]=1;for(int i=1;i<=maxn-10;i++)fac[i]=1ll*fac[i-1]*i%mod;
		inv_fac[maxn-10]=INV(fac[maxn-10]);
		for(int i=maxn-11;i>=1;i--)inv_fac[i]=1ll*inv_fac[i+1]*(i+1)%mod;
	}
	struct disc{int x,y;};
	bool compp(disc x,disc y){return x.x<y.x;}
	void discretization(int *darr,int dn)//离散化 
	{
		static disc b[maxn];
		for(int i=1;i<=dn;i++)
		b[i].x=darr[i],b[i].y=i;
		sort(b+1,b+dn+1,compp);
		static int tot=0;b[0].x=-9666;
		for(int i=1;i<=dn;i++)
		if(b[i].x!=b[i-1].x)darr[b[i].y]=++tot;
		else darr[b[i].y]=tot;
	}
	template<class TY>TY gcd(TY x,TY y){return !y?x:gcd(y,x%y);}
	//----------------------------------------------板子---------------------------------------------
	
	//----------------------------------------------------------------------------------------------- 
	int T,n;char s[maxn];ll a[maxn],d[64];
	bool add(ll x)
	{
		for(int i=60;i>=0;i--)
		if(x&(1ll<<i))
		{
			if(d[i])x^=d[i];
			else {d[i]=x;return true;}
		}
		return false;
	}
	
	void main()
	{
		scanf("%d",&T);while(T--)
		{
			scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);scanf("%s",s+1);
			bool ans=true;
			for(int i=1;i<=n;i++)if(s[i]=='1')
			{
				memset(d,0,sizeof(d));
				for(int j=i+1;j<=n;j++)if(s[j]=='0')add(a[j]);
				if(add(a[i]))ans=false;
			}
			if(ans)printf("0n");else printf("1n");
		}
//		fcheck(1);return;
	}
}
 
int main(){my::main();return 0;}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
 
namespace my
{
	//-----------------------------------------------------------------------------
	inline char cn()
	{
		static char buf[1000010],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
	}
	#define cn getchar
	template<class TY>void read(TY &x)
	{
		x=0;int f1=1;char ch=cn();
		while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}
		while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
	}
	char OP[1000030],Zhan[30];int op=0,Top;
	void fcheck(int type=0){if(type||op>=1000000)fwrite(OP,1,op,stdout),op=0;}
	template<class TY>inline void write(TY x)
	{
		if(x==0){OP[op++]='0';fcheck();return;}
		Top=0;while(x)Zhan[++Top]=x%10+'0',x/=10;
		while(Top)OP[op++]=Zhan[Top--];fcheck();
	}
	#define K_G OP[op++]=' '
	//----------------------------快读快输 ----------------------------------------
	
	//--------------------------------------------------------------------------------------------
	#define ll long long
	#define uint unsigned int
	#define ull unsigned long long
	#define INV(x) ksm(x,mod-2)
	const int maxn=100010,inf=1000000007;
	int mod=998244353;
	void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
	int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
	int fac[maxn],inv_fac[maxn],inv[maxn];
	void work_math()//阶乘
	{
		inv[1]=1;for(int i=2;i<=maxn-10;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		fac[0]=inv_fac[0]=1;for(int i=1;i<=maxn-10;i++)fac[i]=1ll*fac[i-1]*i%mod;
		inv_fac[maxn-10]=INV(fac[maxn-10]);
		for(int i=maxn-11;i>=1;i--)inv_fac[i]=1ll*inv_fac[i+1]*(i+1)%mod;
	}
	struct disc{int x,y;};
	bool compp(disc x,disc y){return x.x<y.x;}
	void discretization(int *darr,int dn)//离散化 
	{
		static disc b[maxn];
		for(int i=1;i<=dn;i++)
		b[i].x=darr[i],b[i].y=i;
		sort(b+1,b+dn+1,compp);
		static int tot=0;b[0].x=-9666;
		for(int i=1;i<=dn;i++)
		if(b[i].x!=b[i-1].x)darr[b[i].y]=++tot;
		else darr[b[i].y]=tot;
	}
	template<class TY>TY gcd(TY x,TY y){return !y?x:gcd(y,x%y);}
	//----------------------------------------------板子---------------------------------------------
	
	//----------------------------------------------------------------------------------------------- 
	int T,n;char s[maxn];ll a[maxn],d[64];
	bool add(ll x)
	{
		for(int i=60;i>=0;i--)
		if(x&(1ll<<i))
		{
			if(d[i])x^=d[i];
			else {d[i]=x;return true;}
		}
		return false;
	}
	
	void main()
	{
		scanf("%d",&T);while(T--)
		{
			scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);scanf("%s",s+1);
			bool ans=true;
			for(int i=1;i<=n;i++)if(s[i]=='1')
			{
				memset(d,0,sizeof(d));
				for(int j=i+1;j<=n;j++)if(s[j]=='0')add(a[j]);
				if(add(a[i]))ans=false;
			}
			if(ans)printf("0n");else printf("1n");
		}
//		fcheck(1);return;
	}
}
 
int main(){my::main();return 0;}

T2

转化一下题意，就是要使序列的最大前缀和与最小前缀和的差值最小。

不妨先将所有?定为-1，然后设 $Z$ 为此时的最大前缀和，显然，此时的 $Z$ 是我们能得到的最小的最大前缀和，然后设此时的最大的最小前缀和为 $f (Z)$ ，考虑怎么在不改变 $Z$ 的前提下求出 $f (Z)$ 。

这个东西可以考虑贪心，从左到右考虑?，原来在这里填的是-1，考虑能否变成1，即判断一下变成1之后是否有前缀和会超过 $Z$ ，假如没有，就贪心地使它变成1，显然这样不会变劣。

照这样看来，我们还需要求出所有 $M (M > Z)$ 的 $f (M)$ ，然后用 $M - f (M)$ 的最小值来作为答案。

但是实际上，可以发现这样一个性质： $M - f (M) \leq (M + 2) - f (M + 2)$ ，因为当 $M$ 加了 $2$ 后，考虑求 $f (M + 2)$ 的过程，最多也就是多一个-1变成1而已，不可能让 $(M + 2)$ 与 $f (M + 2)$ 的差值比 $M$ 与 $f (M)$ 更小。

所以，我们其实只需要求出 $Z$ 和 $Z + 1$ 的 $f$ 就够了，因为从 $Z + 2$ 开始他们的答案肯定不会比 $Z$ 和 $Z + 1$ 的答案更优。

代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 1000010

int n,sum[maxn],msum[maxn];
char s[maxn];

int main()
{
	scanf("%s",s+1);n=strlen(s+1);
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(s[i]=='1'?1:-1);
	msum[n]=sum[n];for(int i=n-1;i>=1;i--)msum[i]=max(msum[i+1],sum[i]);
	int mx=max(msum[1],0),mn,now,ans=n+1;
	for(int j=1;j<=2;j++)
	{
		now=mn=0;
		for(int i=1;i<=n;i++)
		{
			//判断这一位从-1变成1后，后面最大的前缀是否会超过mx
			if(s[i]=='?'){if(msum[i]-sum[i-1]+now+2<=mx)now++; else now--;}
			else if(s[i]=='1')now++; else now--;
			mn=min(mn,now);
		}
		ans=min(ans,mx-mn);mx++;
	}
	printf("%d",ans);
}

T3

这题难在转化题意，不能去考虑如何操作，要考虑如何判断一个序列是否能通过操作得到。

显然我们能得到全部都是 $1$ 的序列，所以 $A$ 和 $B$ 的值交换一下也无所谓的，不妨设 $A \leq B$ 。

观察后可以发现，假如序列中存在长度大于等于 $B$ 的 $1$ 连续串，那么这个序列就一定可以操作出来，因为在这个 $1$ 连续串之外的位置，是可以随意操作每一位为 $0$ 或 $1$ 的，比如说在这个连续串左边的一个位置 $i$ ，你可以通过将 $[i, i + B - 1]$ 变为 $1$ ，然后再将 $i$ 后面的 $1$ 变成 $0$ 即可。

进一步地，可以得到，假如将所有长度大于 $A$ 的连续 $0$ 段都变成 $1$ ，然后存在长度不小于 $B$ 的连续 $1$ 段，那么这个序列就是可以操作出来的。

然后考虑求出不能操作出来的序列数，然后用 $2^n$ 减去得到答案。这个序列肯定是由 $0$ 段和 $1$ 段交替组成的，其中 $0$ 段长度不超过 $A$ ， $1$ 段长度不超过 $B$ ，但是 $1$ 段中可以包含长度不小于 $A$ 的 $0$ 段。

考虑 $d p$ ，设 $g [i] [0 / 1]$ 表示长度为 $i$ 的连续 $1$ 段（可以包含长度不小于 $A$ 的 $0$ 段）并且以 $0 / 1$ 结尾的方案数（但是开头一定是 $1$ ）， $f [i] [0 / 1]$ 表示长度为 $i$ 的以 $0 / 1$ 结尾的不合法方案数，然后就可以 $d p$ 了。

要特别注意的是，一个连续 $1$ 段如果在序列的中间，那么它肯定头尾都是 $1$ ，但是如果在序列的最左边或最右边，那么是可以以 $0$ 开头或以 $0$ 结尾的。

代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define mod 1000000007
#define maxn 5010
 
int n,a,b;
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
int g[maxn][2],f[maxn][2];
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
 
int main()
{
	scanf("%d %d %d",&n,&a,&b);
	if(a>b)swap(a,b); g[1][1]=1;
	for(int i=2;i<b;i++)
	{
		g[i][1]=(g[i-1][0]+g[i-1][1])%mod;
		for(int j=a;j<i;j++)add(g[i][0],g[i-j][1]);
	}
	f[0][0]=f[0][1]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<min(a,i+1);j++)add(f[i][0],f[i-j][1]);
		for(int j=1;j<min(b,i+1);j++)
		{
			if(i==n)add(f[i][0],1ll*f[i-j][0]*g[j][0]%mod);
			if(i==j)add(f[i][1],(g[j][0]+g[j][1])%mod);
			else add(f[i][1],1ll*f[i-j][0]*g[j][1]%mod);
		}
	}
	printf("%d",(ksm(2,n)-(f[n][0]+f[n][1])%mod+mod)%mod);
}