Educational Codeforces Round 119 (Rated for Div. 2)

Dashboard - Educational Codeforces Round 119 (Rated for Div. 2) - Codeforceshttps://codeforces.com/contest/1620

A. Equal or Not Equal

Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1620/problem/A

统计E的数量,为1即输出"NO".

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    string s;
    cin>>s; 
    int cnt=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='N')
            cnt++;
    }
    if(cnt==1)
        cout<<"NO\n";
    else
        cout<<"YES\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while( t--)
        solve();
    return 0;
}

B. Triangles on a Rectangle

Problem - B - Codeforceshttps://codeforces.com/contest/1620/problem/B直接枚举,取最大值即可:

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
int arr[200005]; 
void solve()
{
    int ans=0;
    int w,h,k,cheng;
    cin>>w>>h;
    for(int i=0;i<4;i++)
    {
        if(i<2)
            cheng=h;
        else  
            cheng=w;
        cin>>k;
        for(int j=1;j<=k;j++)
            cin>>arr[j];
        sort(arr+1,arr+1+k);
        ans=max(ans,abs(arr[1]-arr[k])*cheng);
    }
    cout<<ans<<"\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

C. BA-String

Problem - C - Codeforceshttps://codeforces.com/contest/1620/problem/C题意:给你三个数字n,k,x,给你一个只含a,*的字符串 将其中的*替换成[ 0 , k ] 个b，问你所有情况中字典序第x 小的是什么。

思路,我们可以把a当做一个分割符号,因为无论怎么变,a始终存在.这个字符串就可以看成很多个可以确定上限个数的只含字符b的子串和分割他们的只含a的子串.通过枚举,会发现,当分割的a子串(下面叫他分割串)右边的可变换长度的只含有b的子串(下面叫他变换串)子串中b的个数填满了,还要按照字典序向下遍历的时候,就需要在这个分割串的前一位加上一个b,才可以在后面的分割串继续从一个b开始增加.这就很类似于我们的进制,只不过这个题每一位的进制不一定是一样长.那么我们就可以计算好每个变换串的可变换长度,当做此位进制转换的个数,直接将字典序从0开始进行进制转换即可,在输出相应字符串.

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
void solve()
{
    string s;
    int n,k,x;
    cin>>n>>k>>x;
    cin>>s;
    reverse(s.begin(),s.end());
    int cnt=0;
    string res="";
    x--;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='a')
        {
            int num=x%(cnt*k+1);
            x/=(cnt*k+1);
            for(int i=0;i<num;i++)
                res+='b';
            res+='a';
            cnt=0;
        }
        else
            cnt++; 
    }
    int num=x%(cnt*k+1);
    for(int i=0;i<num;i++)
        res+='b';
    reverse(res.begin(),res.end());
    cout<<res<<"\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

E. Replace the Numbers

Problem - E - Codeforceshttps://codeforces.com/contest/1620/problem/E题意:给你n次操作,每次输入一个数字,当这个数字是1时,在一个原本是空数组的末尾插入一个输入的数字x,当这个数字是2的时候,输入x和y,把所有现在在数组里面的x都变成y.

这个题一开始模拟,很自然而然的t在23个样例.然后看题解,学到了一个并查集做法.

我们直接把存放这相同数字的值的数组的位置(用位置记录),放在一个集合里面,如果要修改就只需要进行并查集的合并的操作了,吧两个并查集合并,然后由根节点指向一个值,这个值就是目前的这个位置放得数的值.详细注释在下面代码里.

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int fa[500005],num[500005],vis[500005];
//fa记录的是父亲节点,好让很多个节点组成一个集合(当然这里面存的都是他们的序号)
//vis记录的是某个序号的值,也就是对应序号应该存在数组里面的值
//num记录的是某个存在数组里面的值的序号(这个存进去的序号时不一定的,只要是在一个集合里面的数都可以)
int find(int x)
{
    if(x!=fa[x])
        fa[x]=find(fa[x]);
    return fa[x];
}
//路径压缩并查集
void solve()
{
    int q,op,x,y,tot=0;
    scanf("%d",&q);
    for(int i=1;i<=500000;i++)
        fa[i]=i;
    while(q--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            tot++;
            scanf("%d",&x);
            fa[tot]=tot;//记录父亲节点为自己
            vis[tot]=x;//给父亲节点赋值
            if(num[x])
                fa[tot]=num[x];
            //如果储存在数组中的值x已经包含有节点(初始化都是0,如果是0就说明数组里面没有这个数x)
            else
                num[x]=tot;
            //确定该数字在数组里存在,并且取集合里面一个数字来存储,由这个数我们可以直接find到它的父节点,也就可以直接确定vis里面的值
        }
        else
        {
            scanf("%d%d",&x,&y);
            if(num[x]&&x!=y)
            {   
//如果存在值为x的数字在数组中,并且x,y需要变化
                if(num[y])
                {
                    fa[num[x]]=num[y];
                    num[x]=0;
                }
//如果存在有y的值在数组中,直接进行集合合并,当然,合并之后,值为x的集合就消失了,置为0
                else
                {
                    num[y]=num[x];
                    vis[num[x]]=y;
                    num[x]=0;
                }
//如果不存在y的值在数组中,直接把整个x的集合变换为y的结合,在把x集合消除
            }
        }
    }
    for(int i=1;i<=tot;i++)
        printf("%d ",vis[find(i)]);
//输出父节点对应的vis值即可
    return ;
}
signed main()
{
    solve();
    return 0;
}

斗奋力努