Codeforces Round 806 (Div. 4) 5

A. YES or YES?

考察大小写转化

直接谁用toupper函数即可

void solve()
{
    string s; cin>>s;
    for(int i=0;s[i];i++)
    s[i]=toupper(s[i]);
    if(s=="YES") cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
        return ;
}

B. ICPC Balloons

考察暴力

直接map存起来即可

map<char,int> mp;
int t,n,m;

void solve()
{
    cin>>n;
    mp.clear();
    string s; cin>>s;
    LL ans=0;
    for(int i=0;i<n;i++){
        mp[s[i]]++;
    }
    for(auto &[k,v]:mp) ans+=v+1;
    cout<<ans<<endl;
        return ;
}

C. Cypher

考察暴力模拟

数据范围很小直接暴力模拟即可

int a[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        cin>>m;
        int ans=0;
        while(m--){
            char x; cin>>x;
            if(x=='D') ans++;
            else ans--;
        }
        a[i]=(a[i]+ans+10)%10;
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
        return ;
}

D. Double Strings

数据范围暴力

我没可以发现数据范围特别小每一个串我没直接暴力枚举每一个位置就好看是否存在

string s[N];
void solve()
{
    cin>>n;
    mp.clear();
    for(int i=1;i<=n;i++){
        cin>>s[i];
        mp[s[i]]++;
    }
    for(int i=1;i<=n;i++){
        string x=s[i];
        int l=x.size();
        int f=0;
        for(int j=1;j<l;j++){
            if(mp[x.substr(0,j)]&&mp[x.substr(j)]){
                f=1; break;
            }
        }
        cout<<f;
    }
    cout<<endl;
        return ;
}

E. Mirror Grid

经典旋转

把四个点都每一个位置的四个方向都跑一遍接着来看出现的次数是哪一个多判断答案即可

char g[M][M];
bool st[M][M];
int check(int x,int y)
{
    int ans=0;
    if(g[x][y]!=g[n-y+1][x]) ans++;
    if(g[x][y]!=g[y][n-x+1]) ans++;
    if(g[x][y]!=g[n-x+1][n-y+1]) ans++;
    if(ans>=2) ans=4-ans;
    st[x][y]=true;
    st[n-y+1][x]=true;
    st[y][n-x+1]=true;
    st[n-x+1][n-y+1]=true;
    return ans;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>g[i][j];
            st[i][j]=false;
        }
    }
    int ans=0;
   for(int i=1;i<=n;i++){
   for(int j=1;j<=n;j++){
        if(!st[i][j]){
            ans+=check(i,j);
        }
    }
   }
    cout<<ans<<endl;
        return ;
}

F. Yet Another Problem About Pairs Satisfying an Inequality

简单式子和前缀和

题目：求 ai< i < aj < j 的对数

我没明显发现具有前面的直接延续到后面的继承性我没只需要对前面的判断是否是满足接着就直接前缀和维护一遍就好了

int t,n,m;
LL a[N],b[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=0;
    for(int i=1;i<=n;i++){
        if(a[i]<i){
            b[i]++;
        }
    }
    LL ans=0;
    for(int i=1;i<=n;i++) b[i]+=b[i-1];
    for(int i=1;i<=n;i++){
        if(a[i]<i){
            ans+=b[a[i]-1];
        }
    }
    cout<<ans<<endl;
        return ;
}

G. Good Key, Bad Key

性质分析和动态规划

题目意思：n个箱子里面的钱是ai一把钥匙是k元我没可以直接暴力开那么从这个位置到后后面的所有箱子的钱都将会除以2

加黑色不考虑任何东西我们可以直接二维dp但是明显要优化,我们可以发现这个除以2的性质最多除以32个就都是0了所以
我们最多用32把坏钥匙所以状态就变少了常常需要思考除法乘法的性质最少是2的时候32和64都是敏感数字

LL a[N],g[50];
LL f[N][50];
void get()
{
    g[0]=1;
    for(int i=1;i<=32;i++) g[i]=g[i-1]*2;
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=32;j++) 
        f[i][j]=-1e18;
    }
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=min(i,32);j++){
            f[i][j]=max(f[i][j],f[i-1][j]+a[i]/g[j]-m);
            if(j) f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]/g[j]);
            if(j>=31) f[i][j]=max(f[i][j],f[i-1][j]);
        }
    }

    LL ans=0;
    for(int i=0;i<=32;i++) ans=max(ans,f[n][i]);
    cout<<ans<<endl;
        return ;
}