8.24test

· · 个人记录

T1

直接前缀和先求出区间和，然后一直和上一个比较如果a[i]+b[i]不变就更新右边边界和最大值，否则新开区间就行

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+7;
int a[maxn],b[maxn],sum[maxn];
signed main() {
    int t;
    cin>>t;
    while(t--) {
        memset(sum,0,sizeof(sum));
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
        }
        for(int i=1;i<=n;i++) {
            cin>>b[i];
        }
        int maxx=0;
        int l=1,r;
        for(int i=2;i<=n;i++) {
            if(a[i]+b[i]==a[i-1]+b[i-1]) {
                r=i;
                maxx=max(maxx,(sum[r]-sum[l-1])*(r-l+1));
            } else {
                l=i;
            }
        }
        cout<<maxx<<'\n';
    }
    return 0;
}

T2

使用dp会只考虑当前最优所以不能用，因为取模会干扰dp结果，正解思路是转换题意变成求sum[r]-sum[l-1]的最大值，而答案范围只有0-99，所以只需要用桶记录区间答案枚举最小sum[l-1]求出最大值

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int sum[maxn],a[maxn];
map<int,int>vis;
int maxx=-1e9;
signed main() {
    int n;
    cin>>n; 
    vis[0]=1;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        sum[i]%=100;
        for(int j=0;j<=99;j++) {
            if(vis[j]==0) {
                continue;
            } else {
                maxx=max(maxx,((sum[i]-j)%100+100)%100);
            }
        }
        vis[sum[i]]++;
    }
    cout<<maxx;
    return 0;
}

T3

模拟，尤其注意在小写的时候要特判合成之后能不能和另一个大写消除

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--) {
        string s;
        cin>>s;
        stack<char>Q;
        for(int i=0;i<s.size();i++) {
            if(Q.size()==0) {
                Q.push(s[i]);
            } else {
                if(Q.top()==s[i]) {
                    if(s[i]>='A'&&s[i]<='Z') {
                        Q.pop();
                    } else if(s[i]>='a'&&s[i]<='z') {
                        Q.pop();
                        s[i]=s[i]-'a'+'A';
                        if(!Q.empty()&&Q.top()==s[i]) {
                            Q.pop();
                        } else {
                            Q.push(s[i]);
                        }
                    }
                } else {
                    Q.push(s[i]);
                }
            }
        }
        stack<char>Q2;
        while(!Q.empty()) {
            Q2.push(Q.top());
            Q.pop();
        }
        while(!Q2.empty()) {
            cout<<Q2.top();
            Q2.pop();
        }
        cout<<'\n';
    }
    return 0;
}

T4

n==0或者b[i]都是1的时候如果q>1那就死翘翘了，不然输出100
a[i]都是1的时候求出魔法最大伤害然后如果最大伤害>q就可以击败
正解不出意料是背包，首先可以注意到我们是先手攻击，所以我们可以多攻击敌方一次，双方血量都是100，敌方伤害固定，那么敌方攻击次数和我方的攻击次数是固定的为100/q向上取整，如果单独计算普通攻击很麻烦，所以可以将普通攻击也视为魔法攻击当作魔力值0，伤害1的魔法，然后将使用魔力当作背包储存空间，将伤害看作最大价值
状态：dp[i][j]i次攻击使用j魔力值可以打出的最高伤害
初始值：0
状态转移方程：dp[i][tmp]=max(dp[i][tmp],dp[i-1][j]+h[k]);
答案：只要dp[i][j]>=100就输出i 其中注意，必须要攻击完才能恢复，所以在计算能不能攻击时，j要大于a[i]，但是在结算的时候要加上t

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e3+7;
int dp[maxn][maxn];
int m[maxn],h[maxn];
int n,t,q;
signed main() {
    int T;
    cin>>T;
    while(T--) {
        memset(dp,0,sizeof(dp));
        cin>>n>>t>>q;
        m[0]=0,h[0]=1;
        for(int i=1;i<=n;i++) {
            cin>>m[i]>>h[i];
        }
        int limi=ceil(100.0/q);
        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*1ll);
                    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==1) {
            cout<<ans<<'\n';
        } else {
            cout<<"Loser!"<<'\n';
        }
    }
    return 0;
}