agc 048部分题解

106 阅读 0 评论 70 点赞

我是靠谱客的博主勤恳冥王星，这篇文章主要介绍agc 048部分题解，现在分享给大家，希望可以做个参考。

~~骗阅读量~~

B

题意:给定两个整数序列A,B,找出一种括号方案，对于每一对匹配的括号i,j，贡献为 $max(A_i+A_j,B_i+B_j)$ ，找出最大贡献和
$10^5$
做法:钦定哪些位置是A，哪些为B
那么存在方案的等价条件是:B在原序列占有的奇偶位置数量一样
然后借此贪心即可
P,Q 如果P，那么Q Q是P的必要条件 P是Q的充分条件
proof:首先这肯定是个必要条件
接下来我们证明这是个充分条件
如果我们给出B括号的一种匹配方案，对于每一对匹配的i,j(i<j)，如果我们满足 $2 ∣ j - i - 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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
#define Maxn 100010
int A[Maxn],B[Maxn];
int seq1[Maxn],seq2[Maxn];
bool vis[Maxn];

int main(){
	ll Ans=0;
	cin>>n;
	for(int i=1;i<=n;++i)cin>>A[i],Ans+=A[i];
	for(int i=1;i<=n;++i){
		cin>>B[i];
		B[i]-=A[i];
		if(i&1)seq1[i/2+1]=B[i];
		else seq2[i/2]=B[i];
	}
	sort(seq1+1,seq1+n/2+1);sort(seq2+1,seq2+n/2+1);
	for(int i=n/2;i>=1;--i)Ans+=max(0,seq1[i]+seq2[i]);
	printf("%lldn",Ans);
	return 0;
}

D

题意:多组数据,n堆石子，A和B轮流玩游戏，A每次从最左边石子堆中取若干石子，B从最右边取，取不了就是输的。 $100,A_i leqslant 10^9$
如果先手赢的话，那么对于 $A'1>=A_1$ 的石子序列 $A'1A_2A_3...A_n$ ，仍然是先手先赢，策略可以照搬
我们再观察下整个博弈的过程，发现可以设计出这么一个dp
$F_0{i,j,k}$ 表示仅考虑i到j的石子堆，先手从左边开始取,且最左边只剩下k个(而不是 $A_i$ 个), $A_i$ ，先手能否赢
$F_1{i,j,k}$ 表示仅考虑i到j的石子堆，先手从右边开始取，且最右边只剩下k个(而不是 $A_j$ 个), $A_j$ ,先手能否赢
所以我们得到个区间dp
根据刚才的观察
$fjz_{i,j,0}=num$ 先手左边,最左边石子数<=num即会失败，否则会成功
$fjz_{i,j,1}$ 差不多
dp过程略

复制代码

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
#include<bits/stdc++.h>
using namespace std;
int n;
#define Maxn 105
int A[Maxn];
int fjz[Maxn][Maxn][2];

inline void rd(int &x){
	x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
}

int main(){
	int T;
	rd(T);
	while(T--){
	rd(n);
	for(int i=1;i<=n;++i)rd(A[i]);
	for(int i=1;i<=n;++i)fjz[i][i][0]=fjz[i][i][1]=0;
	for(int len=2;len<=n;++len)
		for(int i=1;i<=n-len+1;++i){
			int j=i+len-1;
			//fjz[i][j-1][0] fjz[i+1][j][1]
			if(fjz[i][j-1][0]==A[i])fjz[i][j][1]=0;
			else fjz[i][j][1]=min(fjz[i+1][j][1]+A[i]-fjz[i][j-1][0],A[j]);		
			//fjz[i+1][j][1] fjz[i][j-1][0]
			if(fjz[i+1][j][1]==A[j])fjz[i][j][0]=0;
			else fjz[i][j][0]=min(fjz[i][j-1][0]+A[j]-fjz[i+1][j][1],A[i]);
		}
	if(A[1]>fjz[1][n][0])puts("First");
	else puts("Second");	
}
	return 0;
}

E

题意:不想说了。。。。。。
解法:官方题解不是很详细。~~我这个更加简略~~
通过画图像，当你前i个确定好x(不考虑后面)，满足仅考虑前i个限制，后面一定会有对应的方案，这启示我们贪心。
像题解那样,令 $z_i=A_i+T*x_i$ ，那么有 $z_i<=A_1-T$ 或 $z_i>A_1$ ,证明参考上面的贪心
然后通过这个，我们可以构造出 $A_2$ 到 $A_n$ 的x，然后对于 $z'_i>A_1-T$ 的， $x_i=x'_i+1$
然后就随便dp了，我写的是 $O(nKlog_2K+n^3K)$ 的做法

复制代码

#include<bits/stdc++.h>
using namespace std;
const int Mod=1000000007;
int n,T,K;
#define Maxn 52
int B[Maxn][Maxn];
int A[Maxn][Maxn][Maxn][Maxn];
int Ans[Maxn];

namespace modular{
	int add(int a,int b){return a+b>=Mod?a+b-Mod:a+b;}
	int mul(int a,int b){return 1ll*a*b%Mod;}
	void Add(int &a,int b){a=a+b>=Mod?a+b-Mod:a+b;}
}using namespace modular;

inline void rd(int &x){
	x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
}

int main(){
	rd(n);rd(K);rd(T);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=K;++j)rd(B[i][j]);
		sort(B[i]+1,B[i]+K+1);
	}
	for(int i=1;i<=K;++i)A[n][n][i][0]=1;
	int Kpow=1;
	for(int i=n;i>=2;--i){
		Kpow=mul(Kpow,K);
		for(int j=i;j<=n;++j)
			for(int l=0;l<=n-i;++l){
				int at=0;
				for(int k=1;k<=K;++k){
					int t=A[i][j][k][l];
					while(at<K&&B[i-1][at+1]-T<B[j][k]+l*T)at++;
					Add(A[i-1][j][k][l+1],mul(t,at));
					Add(A[i-1][j][k][l],mul(t,K-at));
				}
			}
		for(int j=1;j<=K;++j)A[i-1][i-1][j][0]=Kpow;		
	}
	for(int i=1;i<=n;++i){
		Ans[i]=0;
		for(int j=1;j<=K;++j)
			for(int l=0;l<n;++l)Add(Ans[i],mul(A[1][i][j][l],l));
		printf("%dn",Ans[i]);
	}
	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
#include<bits/stdc++.h>
using namespace std;
const int Mod=1000000007;
int n,T,K;
#define Maxn 52
int B[Maxn][Maxn];
int A[Maxn][Maxn][Maxn][Maxn];
int Ans[Maxn];

namespace modular{
	int add(int a,int b){return a+b>=Mod?a+b-Mod:a+b;}
	int mul(int a,int b){return 1ll*a*b%Mod;}
	void Add(int &a,int b){a=a+b>=Mod?a+b-Mod:a+b;}
}using namespace modular;

inline void rd(int &x){
	x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
}

int main(){
	rd(n);rd(K);rd(T);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=K;++j)rd(B[i][j]);
		sort(B[i]+1,B[i]+K+1);
	}
	for(int i=1;i<=K;++i)A[n][n][i][0]=1;
	int Kpow=1;
	for(int i=n;i>=2;--i){
		Kpow=mul(Kpow,K);
		for(int j=i;j<=n;++j)
			for(int l=0;l<=n-i;++l){
				int at=0;
				for(int k=1;k<=K;++k){
					int t=A[i][j][k][l];
					while(at<K&&B[i-1][at+1]-T<B[j][k]+l*T)at++;
					Add(A[i-1][j][k][l+1],mul(t,at));
					Add(A[i-1][j][k][l],mul(t,K-at));
				}
			}
		for(int j=1;j<=K;++j)A[i-1][i-1][j][0]=Kpow;		
	}
	for(int i=1;i<=n;++i){
		Ans[i]=0;
		for(int j=1;j<=K;++j)
			for(int l=0;l<n;++l)Add(Ans[i],mul(A[1][i][j][l],l));
		printf("%dn",Ans[i]);
	}
	return 0;
}