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

Statistics E The number of , by 1 The output "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 Direct enumeration , Take the maximum value :

#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 The question : Here are three numbers n,k,x, I'll give you one that only contains a,* String Will be one of the * Replace with [ 0 , k ] individual b, Ask you the order of the dictionary in all cases x What is the small .

Ideas , We can a As a division symbol , Because no matter how it changes ,a Always there . This string can be regarded as many characters that can determine the upper limit b The substring of and dividing them only contain a The string of . By enumeration , Will find , When divided a Substring ( Let's call him to split the string ) The variable length on the right only contains b The string of ( Let's call him to change the string ) In substring b The number of is filled , When traversing down according to the dictionary order , You need to add a before this split string b, Only then can we continue from one b Began to increase . This is very similar to our radix , But the base of each digit of this question is not necessarily the same length . Then we can calculate the transformable length of each transformation string , As the number of this bitwise conversion , Order the dictionary directly from 0 Just start the hexadecimal conversion , Output the corresponding string .

#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 The question : Here you are. n operations , Enter one number at a time , When this number is 1 when , Insert an input number at the end of an originally empty array x, When this number is 2 When , Input x and y, Put all that is now in the array x All become y.

This problem is simulated at the beginning , Naturally t stay 23 A sample . Then look at the solution , Learned a method of merging and searching sets .

We directly put the position of the array storing the values of the same number ( Record with position ), Put it in a collection , If you want to modify it, you only need to perform the operation of merging and querying sets , Let's merge two parallel search sets , Then the root node points to a value , This value is the value of the current position . Detailed comments are in the following code .

#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 It records the parent node , So that many nodes can form a set ( Of course, their serial numbers are stored here )
//vis What is recorded is the value of a sequence number , That is, the corresponding sequence number should exist in the value in the array 
//num The record is the sequence number of a value stored in the array ( The serial number of this deposit is not necessarily , As long as the number is in a set )
int find(int x)
{
    if(x!=fa[x])
        fa[x]=find(fa[x]);
    return fa[x];
}
// Path compression and set lookup 
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;// Record the parent node for yourself 
            vis[tot]=x;// Assign a value to the parent node 
            if(num[x])
                fa[tot]=num[x];
            // If the value stored in the array x Already contains nodes ( Initialization is 0, If it is 0 It means that there is no such number in the array x)
            else
                num[x]=tot;
            // Make sure that the number exists in the array , And take a number in the set to store , From this number, we can directly find To its parent node , It can be directly determined vis The value of the inside 
        }
        else
        {
            scanf("%d%d",&x,&y);
            if(num[x]&&x!=y)
            {   
// If present, the value is x The number of is in the array , also x,y It needs to change 
                if(num[y])
                {
                    fa[num[x]]=num[y];
                    num[x]=0;
                }
// If there is y The value of is in the array , Directly merge sets , Of course , After the merger , The value is x The collection of disappeared , Set as 0
                else
                {
                    num[y]=num[x];
                    vis[num[x]]=y;
                    num[x]=0;
                }
// If it doesn't exist y The value of is in the array , Directly put the whole x The set of is transformed into y The combination of , In the x Set elimination 
            }
        }
    }
    for(int i=1;i<=tot;i++)
        printf("%d ",vis[find(i)]);
// Output the corresponding vis value 
    return ;
}
signed main()
{
    solve();
    return 0;
}

Fight hard