8.24-东塘-401-下午-陈-训练

· · 个人记录

U559540 美味度

对于 50% 的数据范围，满足 1≤n≤10 3 ， 保证 a i ​ =b i ​ ， 并且所有的 a i ​ 都相等。

题目前50pts可以通过特殊性质获得a[i]==b[i]

证明每一个下表为i的a[i],b[i]的和都一样

所以所有都能选取 可以用前缀和处理所有a[1~n]的前缀和再乘上（r-l+1）实际就是（n-1+1）=n

所以五十分代码如下

    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
        }
        int tmp=1;
        for(int i=1;i<=n;i++){
            cin>>b[i];
            if(b[i]!=a[i]){
                tmp=0;
            }
            c[i]=a[i]+b[i];
        }
        if(tmp){
            cout<<n*sum[n]<<"\n";
            continue;
        }

100pts

1. 可以模拟一下将当前的a[i]+b[i]与下一个a[i+1]+b[i+1]记录起始下表i 每次都成立r++

2.当不成立是将上一次的结果与最大值对比运用前缀和 sum[r]-sum[l-1];然后重新进行操作1.

代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int t;
const int maxn=1e6+10;
int a[maxn];
int b[maxn];
int c[maxn];
int ans[maxn];
int sum[maxn]; 
int ansl=1,ansr=1;
signed main(){
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
        }
        int tmp=1;
        for(int i=1;i<=n;i++){
            cin>>b[i];
            if(b[i]!=a[i]){
                tmp=0;
            }
            c[i]=a[i]+b[i];
        }
        if(tmp){
            cout<<n*sum[n]<<"\n";
            continue;
        }
        bool flag=0;
        int maxx=INT_MIN;
        for(int i=1;i<n;i++){
            if(c[i]==c[i+1]&&flag==0){
                flag=1;
                ansl=i;
                ansr=i+1;
            }else if(c[i]==c[i+1]&&flag==1){
                ansr=i+1;
            }else{
                maxx=max(maxx,(ansr-ansl+1)*(sum[ansr]-sum[ansl-1]));
                flag=0;
                ansl=i;
                ansr=i;
            }
        }
        cout<<maxx<<"\n";
    }

    return 0;
}

U512656 数字选择3

这道题知识点是 动态规划和前缀和

这道题mod只有100 可以直接枚举结束点r 运用前缀和和暴力 sum[r]-sum[l-1];

O(k*n)k=100

U419333 大小组合

这道题就是栈的模拟

根据题意即可

但有个细节需要注意就是

当两个相同的小写字母变成一个大写字母时还需要判断是否跟栈顶字母相同（不判会漏情况） 如果相同需要删除（出栈）不相同直接入栈就行

代码如下

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
stack<char>q;
stack<char>a;
int t;
int main(){
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        s='#'+s;
        int len=s.size()-1;
        for(int i=1;i<=len;i++){
            if(q.empty()){
                q.push(s[i]);
            }else if(!q.empty()&&q.top()==s[i]&&s[i]>='A'&&s[i]<='Z'){
                q.pop();
            }else if(!q.empty()&&q.top()==s[i]&&s[i]>='a'&&s[i]<='z'){
                q.pop();
                if(!q.empty()&&q.top()==char(s[i]-32)){
                    q.pop();
                }else {
                    q.push(char(s[i]-32));
                }
            }else if(q.top()!=s[i]){
                q.push(s[i]);
            }
        }

        while(!q.empty()){
            a.push(q.top());
            q.pop();
        }
        while(!a.empty()){
            cout<<a.top();
            a.pop();
        }
        cout<<"\n";
    }
    return 0;
}

芒果王国拼尽全力无法战胜王国 A 。

对于 20% 的数据范围，保证 n=0 。

对于额外 20% 的数据范围，保证 b i ​ =1 。

对于额外 20% 的数据范围，保证 a i ​ =1,b i ​

1 。

对于 100% 的数据范围， 保证 1≤T≤10,0≤n≤100,1≤t≤5,0<q≤100,0≤a i ​ ,b i ​ ≤100 。

U559566 抵御

最后一题正解其实长得像背包 但考试时不会写

所以就看特殊样例拿60分

当n=0时芒果只能用普通攻击

而王国A一直用暴力攻击

所以只能这样一回合一回合打

直接判断哪个伤害高哪个就赢

当魔法攻击最大只有1时就与普通攻击一样没区别

当消耗最大魔法只有1时 并且回复值一定大于等于1

所以不用考虑消耗 直接找魔法攻击的最大值进攻 所以只需要算出芒果王国的次数ceil（100*1.0/maxx）和 A的次数对比看那个优先击败对方就获胜

正解细节

1.魔力值<=100

2.芒果王国只能先魔法攻击再回复对应魔力值

3.王国A暴力攻击固定可以直接算出它的次数

4 .芒果王国率先攻击 攻击值大于A的生命值也是一次攻击次数

代码如下

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+7;
int dp[maxn][maxn];
int m[maxn];
int h[maxn];
int n,t,q;
int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>t>>q;
        memset(dp,0,sizeof(dp));
        m[0]=0;
        h[0]=1;
        for(int i=1;i<=n;i++){
            cin>>m[i]>>h[i];
        }
        int limi=100/q;
        if(100%q>0){
            limi++;
        }
        int ans=-1;
        int flag=0;
        for(int i=1;i<=limi;i++){
            for(int k=0;k<=n;k++){
                for(int j=0;j<=100;j++){
                    int tmp=j-m[k]+t;
                    tmp=min(tmp,100);
                    if(j>=m[k]){
                        dp[i][tmp]=max(dp[i][tmp],dp[i-1][j]+h[k]);

                    }
                    if(dp[i][tmp]>=100){
                        ans=i;
                        flag=1;
                        break;
                    }
                }
                if(flag){
                    break; 
                }
            }
            if(flag)break;

        }
        if(flag){
            cout<<ans<<"\n";
        }
        else{
            cout<<"Loser!"<<"\n";
        }
    }
    return 0;
}