agc 048部分题解

骗阅读量

B

题意:给定两个整数序列A,B,找出一种括号方案，对于每一对匹配的括号i,j，贡献为$max(A_i+A_j,B_i+B_j)$，找出最大贡献和
$1⩽n⩽10^5$
做法:钦定哪些位置是A，哪些为B
那么存在方案的等价条件是:B在原序列占有的奇偶位置数量一样
然后借此贪心即可
P,Q 如果P，那么Q Q是P的必要条件 P是Q的充分条件
proof:首先这肯定是个必要条件
接下来我们证明这是个充分条件
如果我们给出B括号的一种匹配方案，对于每一对匹配的i,j(i<j)，如果我们满足$2|j-i-1$，那么就对了

#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从最右边取，取不了就是输的。$T⩽100,n⩽100,A_i⩽10^9$
如果先手赢的话，那么对于$A^{\prime }1>=A_1$的石子序列$A^{\prime }1A_2{A}_3...A_n$，仍然是先手先赢，策略可以照搬
我们再观察下整个博弈的过程，发现可以设计出这么一个dp
$F_{0}i,j,k$表示仅考虑i到j的石子堆，先手从左边开始取,且最左边只剩下k个(而不是$A_i$个),$k⩽A_i$，先手能否赢
$F_{1}i,j,k$表示仅考虑i到j的石子堆，先手从右边开始取，且最右边只剩下k个(而不是$A_j$个),$k⩽A_j$,先手能否赢
所以我们得到个区间dp
根据刚才的观察
$fj{z}_{i,j,0}=num$先手左边,最左边石子数<=num即会失败，否则会成功
$fj{z}_{i,j,1}$差不多
dp过程略

#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\ast x_i$，那么有$z_i<=A_1-T$或$z_i>A_1$,证明参考上面的贪心
然后通过这个，我们可以构造出$A_2$到$A_n$的x，然后对于$z_i^{\prime }>A_1-T$的，$x_i=x_i^{\prime }+1$
然后就随便dp了，我写的是$O(nKlo{g}_{2}K+n^{3}K)$的做法

#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;
}

最后

以上就是勤恳冥王星为你收集整理的agc 048部分题解的全部内容，希望文章能够帮你解决agc 048部分题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。