Educational Codeforces Round 115 (Rated for Div. 2)

目录

A. Computer Game

B. Groups

C. Delete Two Elements

D. Training Session

---

A. Computer Game

Problem - A - Codeforceshttps://codeforces.com/contest/1598/problem/A题意:有一个2行n列的地图,我们要从(1,1)走到(2,n).只能走法满足|x1−x2|≤1 && |y1−y2|≤1(1为原来的位置,2为新位置).

思路,只要不会有一列都是1就可以走到.

#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题意:有n个学生,分成相等的两组(n%2==0),保证两组在不同的两天内都可以上课.给定一个矩阵,1表示他们今天可以上课.问可不可以分出来.

思路:思路不太好说,直接看代码:

#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题意:你从n个数的数组里删除两个数,保证平均数不变,有多少种删除方法.

我们只需要一边遍历边用map记录这个数出现的次数,用之前求的平均数*2减去当前遍历到的数,如果map存在中存在这个结果,就说明可以进行删除,直接和前面出现的进行组合即可.

#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

题意:给你n个任务,都包含有一个a值和一个b值.选择三个任务,这三个任务要满足两个条件中的一个:1.a要互不相同.2.b要互不相同.问有多少种选法.

思路:如果直接按照条件去求,太难了,卡了我半天,不妨用容斥的思想,算出所有的选三种的方法,再减去非法的选法即可.非法的选法一定如下所示

a b

a y

x b    (x,y可以为任意值)

所以我们就可以对于每一个任务的a,b再去进行选一个包含a的任务和一个包含b的任务.可以开两个map进行记录,在遍历直接进行计算:

#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;
}

斗奋力努!