Atcoder ABC365 A-D 题解（天津青年宫青少年计算思维算法周赛活动(三十一) 题解）

时间：2024-10-25 19:39:31

题目翻译信息学基地由提供，不得转载！！！

A：闰年
题目描述you

给你一个介于 1583 和 2023 之间的整数 Y 。

求公历 Y 年的天数。

在给定的范围内， Y 年的天数如下：

  • 如果 Y 不是 4 的倍数，则为 365 天；

  • 如果 Y 是 4 的倍数，但不是 100 的倍数，则为 366 天；

  • 如果 Y 是 100 的倍数，但不是 400 的倍数，则为 365 天；

  • 如果 Y 是 400 的倍数，则为 366 天。

注：
  • Y 是介于 1583 和 2023 (含)之间的整数。
输入

Y

输出

以整数形式打印 Y 年中的天数。

样例输入1
2023
样例输出1
365
样例输入2
1992
样例输出2
366
样例输入3
1800
样例输出3
365
提示/说明

样例一：

2023 不是 4 的倍数，所以有 365 天。

样例二：

1992 是 4 的倍数，但不是 100 的倍数，所以有 366 天。

样例三：

1800 是 100 的倍数，但不是 400 的倍数，所以有 365 天。

打卡题

思路：特判

#include<iostream>
using namespace std;
int main(){
    int y;
    cin>>y;
    if(y%4!=0) cout<<365;
    else if(y%4==0&&y%100!=0) cout<<366;
    else if(y%100==0&&y%400!=0) cout<<365;
    else if(y%400==0) cout<<366;
    return 0;
}
 B：第二大的数
样例输入1
4
8 2 5 1
样例输出1
3
样例输入2
8
1 2 3 4 5 10 9 11
样例输出2
6
提示/说明

样例一：

A 中的第二大元素是 A3，所以打印 3 。

简单题  

思路：两个数组a,b，a排序，b存储

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int x,int y){
    return x>y;
}
int main(){
    int n;
    cin>>n;
    int a[n+10],b[n+10];
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(a[2]==b[i]){
            cout<<i;
            return 0;
        }
    }
    return 0;
}
C：运输费用
样例输入1
4 8
1 3 2 4
样例输出1
2
样例输入2
3 20
5 3 2
样例输出2
infinite
样例输入3
10 23
2 5 6 5 2 1 7 9 7 2
样例输出3
2
提示/说明

样例一：

如果将补贴限额设为 2 元，则所有 N 人的交通补贴总额为 

min(2,1)+min(2,3)+min(2,2)+min(2,4)=7 元，未超出 8 元的预算。

如果补贴限额设定为 3 元，则所有 N 人的交通补贴总额为 

min(3,1)+min(3,3)+min(3,2)+min(3,4)=9 元，超出了 8 元的预算。

因此，补贴限额的最大可能值为 2 元。

样例二：

补贴限额可以无限大。

简单题

思路：二分法，左端点0，右端点2e14（最大值）

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define N 10000001
int a[N],n,m,s;
bool check(int p){
    int cost=0;
    for(int i=1;i<=n;++i) cost+=min(p,a[i]);
    return cost<=m;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++) s+=a[i];
    if(s<=m) cout<<"infinite"<<'\n';
    else{
        int l=0,r=2e14,mxsubsidy=0;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                mxsubsidy=mid;
                l=mid+1;
            } 
            else r=mid-1;
        }
        cout<<mxsubsidy<<'\n';
    }
    return 0;
}
 D：剪刀石头布
题目描述

小竹和小何玩了 N 次剪刀石头布。注：在这个游戏中，石头赢剪刀，剪刀赢纸，纸赢石头。

小何的动作由长度为 N 的字符串 S 表示，字符串由 "R"、"P "和 "S "组成。S 中的第 i 个字符表示小何在第 i 次对局时的动作：R "表示 "石头"，"P "表示 "纸"，"S "表示 "剪刀"。

小竹的动作满足以下条件：

  • 小竹从未输给过小何。
  • 对于 i=1,2,…,N−1 ，小竹在第 i 次对局中的动作与他在 (i+1) 对局中的动作不同。

确定小竹可能赢得的最大对局数。

可以保证存在一个满足这些条件的小竹下棋顺序。

样例输入1
6
PRSSRS
样例输出1
5
样例输入2
10
SSSSSSSSSS
样例输出2
5
样例输入3
24
SPRPSRRRRRPPRPRPSSRSPRSS
样例输出3
18
提示/说明

样例一：

在六局剪刀石头布游戏中，小何分别出了布、石头、剪刀、剪刀、石头和剪刀。

小竹可以出剪刀、布、石头、剪刀、布和石头，赢得第一、第二、第三、第五和第六局。

对于小竹来说，没有满足条件并赢得所有六盘棋的下棋顺序，因此打印 5 。

一般题

思路：字符串动规。以下是动规过程：

当前字符是'R'（石头） ， 石头能赢剪刀和布，取最大值  ，石头被剪刀打败，但可能通过之前的布获胜来延续序列  ，石头被布打败，设置为极小值  。当前字符是'P'（剪刀），剪刀被石头打败，设置为极小值，剪刀能赢石头和布，取最大值 ，剪刀被布打败，但可能通过之前的石头获胜来延续序列  。当前字符是'S'（布），布能赢剪刀和布（通过之前的石头），取最大值并+1 ，布被剪刀打败，设置为极小值 ， 布能赢石头，取最大值  。

#include<bits/stdc++.h> // 包含几乎所有标准库的头文件  
#define int long long // 将int类型重新定义为long long，以处理更大的数值范围  
#define MAX 1000000000 // 定义一个非常大的数，用于表示不可能达到的状态  
#define N 1000001 // 定义数组的最大长度  
using namespace std;  
  
int a[N], n, m; // a数组未使用，n用于存储字符串长度，m未使用  
int box[N]; // box数组未使用  
int f[N][3]; // f数组用于存储动态规划的状态，f[i][j]表示到第i个字符时，以j手势结尾的最长获胜序列长度  
// j=0表示石头，j=1表示剪刀，j=2表示布  
  
signed main(){ // 使用signed long long的main函数  
    cin >> n; // 读取字符串长度  
    string s; // 定义字符串s  
    cin >> s; // 读取字符串  
    s = ' ' + s; // 在字符串前添加一个空格，方便后续处理  
  
    // 初始化第一个字符的状态  
    if(s[1] == 'R'){ // 如果第一个字符是'R'（石头）  
        f[1][0] = 0; // 石头自己打败不了自己，长度为0  
        f[1][1] = 1; // 石头打败剪刀，长度为1  
        f[1][2] = -MAX; // 石头被布打败，设置为一个极小值  
    }  
    else if(s[1] == 'P'){ // 如果第一个字符是'P'（剪刀）  
        f[1][0] = -MAX; // 剪刀被石头打败，设置为一个极小值  
        f[1][1] = 0; // 剪刀自己打败不了自己，长度为0  
        f[1][2] = 1; // 剪刀打败布，长度为1  
    }  
    else{ // 如果第一个字符是'S'（布）  
        f[1][0] = 1; // 布打败石头，长度为1  
        f[1][1] = -MAX; // 布被剪刀打败，设置为一个极小值  
        f[1][2] = 0; // 布自己打败不了自己，长度为0  
    }  
  
    // 动态规划过程  
    for(int i = 2; i <= n; ++i){  
        if(s[i] == 'R'){ // 当前字符是'R'（石头）  
            f[i][0] = max(f[i-1][1], f[i-1][2]); // 石头能赢剪刀和布，取最大值  
            f[i][1] = max(f[i-1][0], f[i-1][2]) + 1; // 石头被剪刀打败，但可能通过之前的布获胜来延续序列  
            f[i][2] = -MAX; // 石头被布打败，设置为极小值  
        }  
        else if(s[i] == 'P'){ // 当前字符是'P'（剪刀）  
            f[i][0] = -MAX; // 剪刀被石头打败，设置为极小值  
            f[i][1] = max(f[i-1][0], f[i-1][2]); // 剪刀能赢石头和布，取最大值  
            f[i][2] = max(f[i-1][0], f[i-1][1]) + 1; // 剪刀被布打败，但可能通过之前的石头获胜来延续序列  
        }  
        else if(s[i] == 'S'){ // 当前字符是'S'（布）  
            f[i][0] = max(f[i-1][1], f[i-1][2]) + 1; // 布能赢剪刀和布（通过之前的石头），取最大值并+1  
            f[i][1] = -MAX; // 布被剪刀打败，设置为极小值  
            f[i][2] = max(f[i-1][0], f[i-1][1]); // 布能赢石头，取最大值  
        }  
    }  
  
    // 输出最长获胜序列的长度  
    cout << max(f[n][0], max(f[n][1], f[n][2])) << '\n';  
    return 0;  
}

信息学基地三十一周周赛

相关文章