Educational Codeforces Round 135 (Rated for Div. 2)(A-D)

Dashboard - Educational Codeforces Round 135 (Rated for Div. 2) - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1728

目录

A. Colored Balls: Revisited(思维)

B. Best Permutation(思维)

C. Digital Logarithm(优先队列,贪心)

D. Letter Picking(区间dp)

---

A. Colored Balls: Revisited(思维)

题意:给你n种颜色的球,告诉你每种球的数量,你每次可以拿走2个颜色不同的球,问你最后剩下的球的编号(输出任意)是多少.(ps:球总个数一定是奇数个)

思路:我们取数量最多的那一组的一个球,那么剩下的球一定是偶数个,且可以两两消除.输出数量最大的球的种类的序号即可.

#include
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
int a[30];
void solve()
{
    int n,maxx=-1,ans=1;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]>=maxx)
        {
            maxx=a[i];
            ans=i;
        }
    }
    cout<
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

B. Best Permutation(思维)

题意:给你一个全排列(1-n),并且给你一个x,然后从前往后遍历,当当前遍历的全排列的值pi>x时,x+=pi,反之x置为0.依次遍历完.问最后x最大的情况下全排列的排列方式是怎样的.

思路:仔细推算之后,不难的得出最大值时n-1+n(因为让当前位置前面得到的x最大,贪心一下就是x=n-1的时候,如果n-1前面还有其他的x,必会置为0,所以最大值必为n-1+n)

所以我们可以尝试先让第i位为i,然后模拟题目给的操作,遍历到n-2,观察此时x的值为多少,如果此时x==0,那么最后两位一定可以加上来,反之,我们交换1和n-2的值在遍历输出即可.当前情况你的n-3位置x一定不是0且>n-1,那么满足这个情况的话只存在于n-3,n-2这两个位置的x都是>0的,(因为只有这样才会让n-1为0来不合法,n-2+n-3>n-1)所以交换之后,n-3是肯定<1的,n-2的位置变成了1,所以在n-2的位置上x必定为0.

#include
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
int a[110];
void solve()
{
    int n,x=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        a[i]=i;
    for(int i=1;i<=n-2;i++)
    {
        if(x
            x+=i;
        else
            x=0;
    }
    if(x)
        swap(a[1],a[n-2]);
    for(int i=1;i<=n;i++)
        cout<" ";
    cout<
    
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

C. Digital Logarithm(优先队列,贪心)

题意:给你两个集合a,b.(集合元素相同)我们想要让两个元素完全相同.我们可以做以下的操作,选任意一个集合里面的元素x变成他的十位数的个数,例如7变成1,1000变成4,19922变成5.问你多少次操作后让a,b内的元素完全相等.

思路:我们从每次从两个集合中取出最大值,贪心的思想,最大的肯定只能和最大的匹配,这样是最优的,因为和小的去匹配还要改变自己,和大的匹配可能直接匹配成功.匹配成功就直接删去这两个元素,不成功就对更大的那根元素进行上述的操作,在放回源集合,重复上述操作即可.用两个优先队列维护.

#include
#define int long long
using namespace std;
const int N =2e5+10,mod=998244353;
priority_queue<int,vector<int>,less<int>>a,b;
void solve()
{
    int ans=0,ax,bx,n,x;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        a.push(x);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        b.push(x);
    }
    while(a.size())
    {
        ax=a.top();
        bx=b.top();
        a.pop(),b.pop();
        if(ax==bx)
        {
            continue;
        }
        else if(ax>bx)
        {
            ans++;
            int t=0;
            while(ax)
            {
                t++;
                ax/=10;
            }
            a.push(t);
            b.push(bx);
        }
        else
        {
            ans++;
            int t=0;
            while(bx)
            {
                t++;
                bx/=10;
            }
            a.push(ax);
            b.push(t);
        }
    }
    cout<
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

D. Letter Picking(区间dp)

题意:Alice和Bob这队老搭档又在玩博弈,当然两者足够聪明.Alice女士优先,他们轮流的从一个长度为偶数的字符串取字母,每次可以选择从头取或者从尾部取.去了之后就放在他们两个的字符串的头部(一开始都是空),取完之后,两者的字符串字典序更小的胜利.

思路:当看到是对一个区间的两头分别取的时候,就想到了区间dp,f[l][r]定义为记录了在区间[l,r]谁是胜者.为了方便状态转移,定义-2为Alice胜利,-1为Bob胜利,0为平局.

那么对于区间[l,r]我们进行分类讨论.我们首先对整个f数组初始化为0,都是平局.在进行分情况讨论:

1.假设Alice取s[l],Bob取s[r].

如果两者没有取的区间f[l+1,r-1]的状态不是0,那么就说明这种情况的胜负已经确定,因为越在后面取的字母越在两者的最后结果字符串的前方,前方的字母越小,那么字典序越小.如果胜负不确定,也就是f[l+1,r-1]==0,那么s[l],s[r]就决定了这种情况的胜负.下面的情况类似于这种就可以得到胜负

2.假设Alice取s[l],Bob取s[l+1]

3.假设Alice取s[r],Bob取s[l]

4.假设Alice取s[r],Bob取s[r-1]

那么我们怎么求f[l,r]的状态呢,首先对比1,2的状态,因为是Alice优先,那么这里按照两者很聪明的情况去博弈的话,肯定是往Bob胜利和平局的方向走,3和4也是,然后求出这两组情况的结果之后,就轮到了Alice选,她肯定勾选对自己有利可图的情况,又会向着Alice胜利和平局去选.所以我们把Bob胜利定为-1,Alice定为-2,平局为0,就可以用一下的式子求出f[l][r]的结果:

 f[l][r]=min(max(sheng[1],sheng[2]),max(sheng[3],sheng[4]));

完整code:

/*
思路:当看到是对一个区间的两头分别取的时候,就想到了区间dp,
f[l][r]定义为记录了在区间[l,r]谁是胜者.为了方便状态转移,
定义-2为Alice胜利,-1为Bob胜利,0为平局.那么对于区间[l,r]
我们进行分类讨论.我们首先对整个f数组初始化为0,都是平局.
再进行分情况讨论:
1.假设Alice取s[l],Bob取s[r].
如果两者没有取的区间f[l+1,r-1]的状态不是0,那么就说明这种
情况的胜负已经确定,因为越在后面取的字母越在两者的最后结果
字符串的前方,前方的字母越小,那么字典序越小.如果胜负不确定,
也就是f[l+1,r-1]==0,那么s[l],s[r]就决定了这种情况的胜负.
下面的情况类似于这种就可以得到胜负
2.假设Alice取s[l],Bob取s[l+1]
3.假设Alice取s[r],Bob取s[l]
4.假设Alice取s[r],Bob取s[r-1]
那么我们怎么求f[l,r]的状态呢,首先对比1,2的状态,因为是Alice
优先,那么这里按照两者很聪明的情况去博弈的话,肯定是往Bob胜利
和平局的方向走,3和4也是,然后求出这两组情况的结果之后,就轮到
了Alice选,她肯定勾选对自己有利可图的情况,又会向着Alice胜利
和平局去选.所以我们把Bob胜利定为-1,Alice定为-2,平局为0,就
可以用一下的式子求出f[l][r]的结果:
f[l][r]=min(max(sheng[1],sheng[2]),max(sheng[3],sheng[4]));
*/
#include
using namespace std;
const int N =2e3+10,mod=998244353;
int f[N][N];
void solve()
{
    memset(f,0,sizeof f);//0为平手,-1,b,-2为a胜利
    string s;
    cin>>s;
    int n=s.size();
    s="!"+s;
    for(int i=1;i+1<=n;i++)
    {
        if(s[i]!=s[i+1])
            f[i][i+1]=-2;
        else
            f[i][i+1]=0;
    }
//这里的预处理是必须的,如果长度为2是要这里处理
    for(int i=4;i<=n;i+=2)
    {
        for(int l=1;l+i-1<=n;l++)
        {
        //枚举4种情况,当区间为[l,r]
            int r=l+i-1;
            int sheng[5]={0,0,0,0,0};
            if(f[l+1][r-1]!=0)
                sheng[1]=f[l+1][r-1];
            else
            {
                if(s[l]
                    sheng[1]=-2;
                else if(s[l]>s[r])
                    sheng[1]=-1;
            }
 
            if(f[l+2][r]!=0)
                sheng[2]=f[l+2][r];
            else
            {
                if(s[l]1])
                    sheng[2]=-2;
                else if(s[l]>s[l+1])
                    sheng[2]=-1;
            }
            
            if(f[l+1][r-1]!=0)
                sheng[3]=f[l+1][r-1];
            else
            {
                if(s[r]
                    sheng[3]=-2;
                else if(s[r]>s[l])
                    sheng[3]=-1;
            }
 
            if(f[l][r-2]!=0)
                sheng[4]=f[l][r-2];
            else
            {
                if(s[r]-1])
                    sheng[4]=-2;
                else if(s[r]>s[r-1])
                    sheng[4]=-1;
            }
            f[l][r]=min(max(sheng[1],sheng[2]),max(sheng[3],sheng[4]));
        }   
    }
    if(f[1][n]==-2)
        cout<<"Alice"<
    else if(f[1][n]==0)
        cout<<"Draw"<
    else if(f[1][n]==-1)
        cout<<"Bob"<
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}