ACGO挑战赛#8 T1~T4题解

Lee Wen

2024-08-12 01:01:09

发布于：广东

20阅读

0回复

0点赞

ACGO挑战赛#8 T1~T4题解

前言

是的这篇挑战赛题解只有T1到T4的，因为本蒟蒻只做了这4题...

该篇题解方便个人总结和整理思路，如果能帮到你那么我将肥肠荣幸！

欢迎指正或者提供hack数据！违规紫衫QwQ AK大神 Orz

T1 交集

数轴上两个部分，起点和终点分别为 $L_1,R_1,L_2,R_2$ ，输出两部分重合的长度，注意如果两部分相邻不算长度 $Like$ 样例3

很容易写出模拟代码毕竟数据不大

#include<bits/stdc++.h>
using namespace std;
int l1,r1,l2,r2,sum;
int a[105]; 
int main() {
	cin>>l1>>r1>>l2>>r2;
	for(int i=l1;i<=r1;i++){
		a[i]++;
	}
	for(int i=l2;i<=r2;i++){
		if(a[i]>=1&&i!=r1&&i!=r2){
			sum++;
		}
	}
	cout<<sum;
	return 0;
}

T2 比赛结果

N名玩家参加比赛，比赛结果存储在 $N\times N$ 的二维表当中题目描述

如果玩家 $i$ 战胜了玩家 $j$ ，则 $A_{i,j}$ 为W；

如果玩家 $i$ 输给了玩家 $j$ ，则 $A_{i,j}$ 为L；

如果玩家 $i$ 和玩家 $j$ 打成平局，则 $A_{i,j}$ 为D

要去判断该二维表是否存在矛盾

简单思考一下

如果 $A_{i,j}$ 为W，那么相应的 $A_{j,i}$ 应该为L，因为玩家 $i$ 赢了玩家 $j$ ，玩家 $j$ 输给了玩家 $i$ ；

同理如果 $A_{i,j}$ 为L，相应的 $A_{j,i}$ 应该为W；

如果 $A_{i,j}$ 为D，相应的 $A_{j,i}$ 应该为D

这样就很简单写出判断了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;//n个人 
char G[1005][1005];//存储对局情况 
bool flag=1;//标记是否有矛盾 
int main() {
	cin>>n;
	for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>G[i][j];}}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(G[i][j]=='-') continue;
			if(G[i][j]=='W'){
				if(G[j][i]!='L'){
					flag=0;
				}
			}
			else if(G[i][j]=='L'){
				if(G[j][i]!='W'){
					flag=0;
				}
			}
			else if(G[i][j]=='D'){
				if(G[j][i]!='D'){
					flag=0;
				}
			}
		}
	}
	if(flag){cout<<"correct";}
	else{cout<<"incorrect";}
	return 0;
}

T3 新建文件夹（1）

简化题目，就是输出字符串的出现次数，建立map从string映射到int型的关系即可，也是hash思想的简单应用

数据不大，模拟解决

#include<bits/stdc++.h>
using namespace std;
int n;
map<string,int> mp;//定义一个从string型映射到int型数量的mp 
int main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		string a;
		cin>>a;
		if(mp[a]==0){
			cout<<a<<endl;
		}else{
			cout<<a<<"("<<mp[a]<<")"<<endl;
		}
		mp[a]+=1;
	}
	return 0;
}

T4 投硬币

一开始见这题想用DFS解决，但是见了数据范围知道肯定不行，毕竟DFS的话时间已经到 $O(2^n)$ 的复杂度，这简直惊为天人！！！

但当时没思路，觉得计数器这个东西带有后效性不符合DP，所以还是先写了个记忆化DFS泪拿42pts。。。

记忆化，非AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll X[5005],Y[5005];
ll f[5005][5005];
ll maxa(ll a,ll b){
	if(a>b){return a;}
	else{return b;}
}
void read(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){cin>>X[i];}
	for(int i=1;i<=m;i++){
		ll c,y;
		cin>>c>>y;
		Y[c]=y;
	}
}
ll dfs(int deep,ll now_sum,ll count)
{
	cout<<deep<<' '<<now_sum<<' '<<count<<endl;
	if(f[deep][count]){
		return f[deep][count];
	}
	if(deep>=n){
		return now_sum;
	}
	ll next_forUP=dfs(deep+1,now_sum+X[deep+1]+Y[count+1],count+1);
	ll next_forDOWN=dfs(deep+1,now_sum,0);
	return f[deep+1][count+1]=maxa(maxa(next_forUP,next_forDOWN),f[deep+1][count+1]);
}
int main() {
	read();
	cout<<dfs(0,0,0);
	return 0;
}

在随后分析了一下，每次对计数器的更改只增加了当时的金额，不对后面的金额发生影响，因此没有后效性

同时又可以分阶段求解前 $i$ 次投掷可获得的最大金额，符合动态规划的特性

对于任一次硬币的操作只有正面朝上和反面朝上两种情况，要求在 $N$ 次操作中可获得的最大金额，这不就是01背包吗！

定义 $DP$ 状态表， $DP[i][count]$ 为第 $i$ 次投掷且计数器为 $count$ 时可获得的最大金额

可得状态转移方程 $DP[i][count]=max(DP[i-1][count-1]+Y[count]+X[i],DP[i-1][count])$

注： $Y[count]$ 为计数器为 $count$ 时可获的奖金， $X[i]$ 为第 $i$ 次硬币正面朝上所获的金额

其中 $DP[i-1][count-1]+Y[count]+X[i]$ 为正面时的情况， $DP[i-1][count]$ 为反面朝上的情况

但是特别注意： $count$ 为 $0$ 时，等于 $i-1$ 次投掷时所能获得的最大值(为了保证 $DP$ 的定义)

这样就能优化到 $O(n^3)$ 了

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;//投N次硬币,M个额外奖金
ll money_sum=0;//存储最大获得的钱数 
ll X[5005],Y[5005];//X[i]为第i次投掷所获的钱,Y[i]为当计数器为i时可得Y[i]奖金 
ll DP[5005][5005];//当投第i次硬币,计数器为c时所获最大奖金 
void read(){//读取 
	cin>>n>>m;
	for(int i=1;i<=n;i++){cin>>X[i];}
	for(int i=1;i<=m;i++){
		ll c,y;
		cin>>c>>y;
		Y[c]=y;
	}
}
ll maxn(ll a,ll b){//取最大值函数 
	if(a>b){return a;}
	else{return b;}
}
int main(){
	read();
	for(int i=1;i<=n;i++){
		for(int c=0;c<=i;c++){
			if(c==0){//当计数器为0时 
				ll before_max=0;
				for(int j=1;j<=i-1;j++){before_max=maxn(before_max,DP[i-1][j]);}
				DP[i][c]=before_max;//DP[i][c]为前一轮投掷中获得最大的金额 
			}else{
				DP[i][c]=maxn(DP[i-1][c-1]+Y[c]+X[i],DP[i-1][c]);//投正面和反面哪一个最优 
			}
		}
	} 
	for(int i=0;i<=n;i++){
		money_sum=maxn(money_sum,DP[n][i]);//在最后一次中找到最优的结果 
	}
	cout<<money_sum<<endl;
	return 0;
}