Educational Codeforces Round 115 (Rated for Div. 2)

Catalog

A. Computer Game

B. Groups

C. Delete Two Elements

D. Training Session

---

A. Computer Game

Problem - A - Codeforceshttps://codeforces.com/contest/1598/problem/A The question : There is one 2 That's ok n Column map , We need to (1,1) Go to the (2,n). Can only walk to meet |x1−x2|≤1 && |y1−y2|≤1(1 For the original position ,2 For the new location ).

Ideas , As long as there is not a column 1 You can walk to .

#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 s1,s2;
    int n;
    cin>>n;
    cin>>s1>>s2;
    for(int i=0;i<n;i++)
    {
        if(s1[i]==s2[i]&&s1[i]=='1')
        {
            cout<<"NO\n";
            return ;
        }
    }
    cout<<"YES\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

B. Groups

Problem - B - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1598/problem/B The question : Yes n A student , Divide into two equal groups (n%2==0), Ensure that the two groups can have classes in different two days . Given a matrix ,1 It means they can have class today . Ask if you can tell .

Ideas : The train of thought is hard to say , Look directly at the 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;
const int N =5e5+10,mod=998244353;
int a[1024][6];
void solve()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=5;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=5;i++)
    {
        for(int j=i+1;j<=5;j++)
        {
            int cnt1=0,cnt2=0,f=0;
            for(int k=1;k<=n;k++)
            {   
                if((a[k][i]|a[k][j])==0)
                {
                    f=1;
                    break;
                }
                if(a[k][i]==1)
                    cnt1++;
                if(a[k][j]==1)
                    cnt2++;
            }
            if(f==1)
                continue;
            if(cnt1>=n/2&&cnt2>=n/2)
            {
                printf("YES\n");
                return ;
            }
        }
    }
    printf("NO\n");
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

C. Delete Two Elements

Problem - C - Codeforceshttps://codeforces.com/contest/1598/problem/C The question : You from n Delete two numbers from the array of numbers , Keep the average constant , How many deletion methods are there .

We only need to traverse while using map Record the number of times this number appears , Use the average obtained before *2 Subtract the number currently traversed , If map This result exists in existence , It means that you can delete , Just combine it directly with what appeared before .

#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;
map<double,int>ma;
double a[200005];
void solve()
{
    ma.clear();
    int n,ans=0;
    double sum=0;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf",&a[i]),sum+=a[i];
    double avg=(double)sum/n;
    for(int i=1;i<=n;i++)
    {
        double temp=avg*2-a[i];
        if(ma.count(temp))
            ans+=(ma[temp]);
        ma[a[i]]++;
    }
    printf("%lld\n",ans);
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

D. Training Session

Problem - D - Codeforceshttps://codeforces.com/contest/1598/problem/D

The question : Here you are. n A mission , All contain one a Value and a b value . Choose three tasks , These three tasks should meet one of the two conditions :1.a Be different from each other .2.b Be different from each other . Ask how many options there are .

Ideas : If you ask directly according to the conditions , It's too hard , Stuck me for a long time , You might as well use the idea of tolerance and exclusion , Calculate all the three methods , Then subtract the illegal choice . The illegal choice must be as follows

a b

a y

x b    (x,y It can be any value )

So we can do the following for each task a,b Then go to choose one that contains a Task and one containing b The task of . You can drive two map For recording , Calculate directly in traversal :

#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;
map<int,int>ma,ma1;
int a[200005];
int b[200005];
void solve()
{
    ma.clear();
    ma1.clear();
    int n,ans;
    scanf("%lld",&n);
    ans=n*(n-1)*(n-2)/2/3;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&a[i],&b[i]);
        ma[a[i]]++;
        ma1[b[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        ans-=(ma[a[i]]-1)*(ma1[b[i]]-1);
    }
    printf("%lld\n",ans);
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

Fight hard !