Educational Codeforces Round 135 （构造、优先队列、区间DP）

A. Colored Balls: Revisited

普通签到题 找最大的序号

#include
using namespace std;
pair<int,int> a[103];
bool cmp(pair<int,int>a,pair<int,int>b){
    return a.first>b.first;
}
int main()
{
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=1;i<=n;i++){cin>>a[i].first;a[i].second=i;}
        sort(a+1,a+n+1,cmp);
        cout<1].second<<'\n';
    }
    return 0;
}

B. Best Permutation

比较巧妙的构造题

因为n-2+n-1 >n (n>2)， 所以要找最大的话， 答案直接就是2n-1。

构造数组的话无论前面怎么输出，最后几个数是 n-2 1 n-1 n 就可以了。

#include
using namespace std;
int main()
{
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=n-3;i>1;i--)cout<" ";
        cout<-2<<" "<<1<<" "<-1<<" "<'\n';
    }
    return 0;
}

C. Digital Logarithm

优先队列直接做

#include
using namespace std;
priority_queue<int,vector<int>,less<int> >qa,qb;
int f(int x){
    int ans=0;
    while(x){x/=10;ans++;}
return ans;
}
int main()
{
    int t;cin>>t;
    while(t--){
        int n;cin>>n;int res=0,aaa,bbb;
        for(int i=1;i<=n;i++){cin>>aaa;qa.push(aaa);}
        for(int i=1;i<=n;i++){cin>>bbb;qb.push(bbb);}
        while(!qa.empty()){
            int aa=qa.top(),bb=qb.top();
            if(aa==bb){qa.pop();qb.pop();}
            else if(aa>bb){int x=f(aa);qa.pop();qa.push(x);res++;}
            else {int x=f(bb);qb.pop();qb.push(x);res++;}
        }
        cout<'\n';
    }
    return 0;
}

D. Letter Picking

已知 Bob不可能赢 所以只有 Alice赢 和 平局 两个结果。

设字符串范围是[ i , j ]。

假设Alice拿了s[i]，那么Bob拿s[i+1]或者s[j]，剩下的范围是dp[i+2][j]和dp[i+1][j-1]，若范围显示是Alice赢，则最终结果是Alice赢；若范围显示是平局，那么比较 Alice拿到的 和 Bob拿到的：若Bob随便怎么拿，Alice拿的都比Bob小，则Alice胜利，否则平局。

假设Alice拿了s[j]，那么Bob拿s[i]或者s[j-1]，剩下的范围是dp[i][j-2]和dp[i+1][j-1]，

剩下的都是同理了……

#include
using namespace std;
bool check(char a,char b,bool fl){// 1是Alice
    if(fl)return 1;
    else if(areturn 1;
    else return 0;
}
int main()
{
    int T;cin>>T;
    while(T--){
        bool dp[2005][2005]={0};
        string s;cin>>s;
        s=" "+s;int n=s.size()-1;
        for(int k=2;k<=n;k+=2){
            for(int i=1;i+k-1<=n;i++){
                int j=i+k-1;
                dp[i][j]=0;
                if(check(s[i],s[j],dp[i+1][j-1])&&check(s[i],s[i+1],dp[i+2][j]))dp[i][j]=1;
                if(check(s[j],s[i],dp[i+1][j-1])&&check(s[j],s[j-1],dp[i][j-2]))dp[i][j]=1;
            }
        }
        if(dp[1][n])cout<<"Alice\n";
        else cout<<"Draw\n";
    }
    return 0;
}