ACGO挑战赛#8 T1~T4题解
2024-08-12 01:01:09
发布于：广东
ACGO挑战赛#8 T1~T4题解
前言
是的这篇挑战赛题解只有T1到T4的，因为本蒟蒻只做了这4题...
该篇题解方便个人总结和整理思路，如果能帮到你那么我将肥肠荣幸！
欢迎指正或者提供hack数据！违规紫衫QwQ AK大神 Orz
T1 交集
数轴上两个部分，起点和终点分别为，输出两部分重合的长度，注意如果两部分相邻不算长度 样例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名玩家参加比赛，比赛结果存储在的二维表当中 题目描述
如果玩家战胜了玩家，则为W；
如果玩家输给了玩家，则为L；
如果玩家和玩家打成平局，则为D
要去判断该二维表是否存在矛盾
简单思考一下
如果为W，那么相应的应该为L，因为玩家赢了玩家，玩家输给了玩家；
同理如果为L，相应的应该为W；
如果为D，相应的应该为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的话时间已经到的复杂度，这简直惊为天人！！！
但当时没思路，觉得计数器这个东西带有后效性不符合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;
}
在随后分析了一下，每次对计数器的更改只增加了当时的金额，不对后面的金额发生影响，因此没有后效性
同时又可以分阶段求解前次投掷可获得的最大金额，符合动态规划的特性
对于任一次硬币的操作只有正面朝上和反面朝上两种情况，要求在次操作中可获得的最大金额，这不就是01背包吗！
定义状态表，为第次投掷且计数器为时可获得的最大金额
可得状态转移方程
注：为计数器为时可获的奖金，为第次硬币正面朝上所获的金额
其中为正面时的情况，为反面朝上的情况
但是特别注意：为时，等于次投掷时所能获得的最大值(为了保证的定义)
这样就能优化到了
代码如下：
#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;
}
有帮助，赞一个