第十五次训练：Educational Codeforces Round 72 (Rated for Div. 2) ＆＆ Codeforces Round #582 (Div. 3)

1.Educational Codeforces Round 72 (Rated for Div. 2) D

题意：给定ｎ个顶点和ｍ条边，问如何对边涂色，使得不会出现某个环上的边都是同一个颜色。输出需要涂的颜色和每条边涂色情况。
　　做题时看到我能够想到只会涂一种或者两种颜色，不过没想到具体怎么做。当时我还在犹豫这些边考虑不考虑方向问题，不过看到测例里边的数字有由大到小的，应该就是考虑方向了。所以所谓的环就和之前做过的某个题一样了，拓扑排序找环，而既然形成环，一定有一条边是由大数到小数的，其它都是由小到大的。因此，没形成环就涂一个颜色，形成环了就仅把由大数到小数的边涂另一种颜色即可。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<utility>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=5*1e3;
const int mx=(1<<20)+99;
ll n,m,ans,aans1,aans2,flag,num,cnt,b[maxn+10],col[maxn+10][maxn+10];
struct lll{
    ll l,r;
}a[maxn+10];
void st(int x,int y)
{
    if(b[x]==2)
    {
        col[y][x]=2;
        return ;
    }
    b[x]=2;
    for(int i=1;i<=n;i++)
    {
        if(col[x][i]!=0)
        {
            if(b[i]==0)
            st(i,x);
            else if(b[i]==2)
            { cnt=2; col[x][i]=2; }
        }
    }
    b[x]=1;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    //int t;
    //cin>>t;
    //for(int o=1;o<=t;++o)
    //{
        cin>>n>>m;
        ans=0; cnt=1;
        memset(b,0,sizeof(b));
        for(int i=1;i<=m;i++)
        {
            cin>>a[i].l>>a[i].r;
            col[a[i].l][a[i].r]=1;
        }
        for(int i=1;i<=n;i++)
        {

            if(b[i]==0)
            st(i,0);
        }
        cout<<cnt<<endl;
        for(int i=1;i<=m;i++)
        cout<<col[a[i].l][a[i].r]<<" ";
        cout<<endl;
    //}
    return 0;
}

2.Educational Codeforces Round 72 (Rated for Div. 2) A

题意：玩游戏中有些英雄有各自的力量值和智力值，另外还有些额外的点数，可以选择加到这两个属性中。问有几种不同的加法能够让英雄力量值大于智力值（不能等于）。
　　开始想着应该从大到小一个一个试就可以，所以超时了。然后就分情况一点一点的讨论做的，结束后搜了一下发现全是二分的，而且这个题是A题，我花的时间真不少。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<utility>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=2*1e5;
const int mx=(1<<20)+99;
ll n,m,k,ans,aans,num,cnt,a[11],flag[11];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;++o)
    {
        cin>>n>>m>>k;
        if(n<=m)
        {
            aans=min(k,m+1-n);
            k-=aans;
            n+=aans;
        }
        if(k==0&&n>m)
        {
            cout<<1<<endl;
            continue;
        }
        if(k==0&&n<=m)
        {
            cout<<0<<endl;
            continue;
        }
        if(n>(m+k))
        {
            cout<<k+1<<endl;
            continue;
        }
        ll x=(k+m-n+2)/2;
        ll y=k-x;
        if(n+x==m+y)
        { x++; y--; }
        cout<<y+1<<endl;
    }
    return 0;
}

3.Educational Codeforces Round 72 (Rated for Div. 2) B

题意：有个怪物很多个头，你有些英雄，每回合不同英雄可以砍掉怪物不同数目的头，不过每回合如果怪物没死也会生长对应不同英雄不同数目的头，问打死怪物最少需要几回合（打不死输出-1）。
　　开始自以为的只能选一种英雄用，一错了就意识到了。所以打怪的步骤就是记录单回合能够打掉净头数最多的和能够打掉头数最多的，用打掉净头数最多的消耗后用打掉最多的绝杀。不过真正做题时要先减去打掉最多的数目来求需要消耗最多的回合数，最后加上绝杀的回合。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<utility>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=2*1e5;
const int mx=(1<<20)+99;
ll n,m,k,ans,aans,maxx,num,cnt,d[200],h[200],flag[11];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;++o)
    {
        cin>>n>>m;
        aans=-1; maxx=-1e18; ans=0;
        for(int i=1;i<=n;i++)
        {
            cin>>d[i]>>h[i];
            maxx=max(maxx,d[i]);
            aans=max(d[i]-h[i],aans);
        }

        //cout<<maxx<<"     "<<aans<<endl;

        if(maxx>=m)
        { cout<<"1"<<endl; continue; }
        if(aans<=0) { cout<<"-1"<<endl; continue; }
        ans+=(m-maxx)/aans;
        if((m-maxx)%aans!=0)
        ans++;
        ans++;
        cout<<ans<<endl;
    }
    return 0;
}

4.Educational Codeforces Round 72 (Rated for Div. 2) C

题意：给定一个０１串，其子串（允许前导零）下标之差等于其二进制数的值，就说是个好串。问给定的字符串中有多少个好串。
　　想到主要看０１串中的‘１’，可以先找到字符串中的１，然后直接一个一个判断加上（前面或后面）一些０是否符合条件。不过做题时代码一直没能写出来。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<utility>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=2*1e5;
const int mx=(1<<20)+99;
ll n,m,ans,aans1,aans2,flag,num,d,cnt,num0[maxn+10];
char s[maxn+10];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;++o)
    {
        cin>>s+1;
        n=strlen(s+1);
        ans=0; num0[0]=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='0')
            num0[i]=num0[i-1]+1;
            else
            num0[i]=num0[i-1];
        }
        for(int len=1;len<=18;len++)
        {
            for(int i=1;i<=n-len+1;i++)
            {
                if(s[i]=='1')
                {
                    num=0; d=1;
                    for(int j=i+len-1;j>=i;j--)
                    {
                        if(s[j]=='1') num+=d;
                        d*=2;
                    }
                    if(num>=len&&(i-1)>=(num-len)&&num0[i-1]-num0[i-1-(num-len)]>=(num-len))
                    ans++;
                }

            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

5.Codeforces Round #582 (Div. 3) A

题意：n个数，其中每个数加减二没花费，加减1花费1，问使所有数相等最少花费多少。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<utility>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=2*1e5;
const int mx=(1<<20)+99;
ll n,num,flag,ans,aans,num1,num2,a[maxn+10];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    //int t;
    //cin>>t;
    //for(int o=1;o<=t;++o)
    //{
        cin>>n;
        num1=num2=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]%2) num1++;
            else num2++;
        }
        cout<<(num1<num2?num1:num2)<<endl;
    //}
    return 0;
}

6.Codeforces Round #582 (Div. 3) C

题意：给定两数n和m。求不大于n的可以整除m的数的个位数字之和。
　　解这个题的关键就是要知道任何数的倍数的个位数总会循环，可以证明的，不过没必要，知道就好。所以，就看有多少个循环和最后有没有半循环就好。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<utility>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=2*1e5;
const int mx=(1<<20)+99;
ll n,m,ans,aans,num,cnt,a[11],flag[11];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;++o)
    {
        cin>>n>>m;
        memset(flag,0,sizeof(a));
        num=0;
        for(int i=1;;i++)
        {
            if(!flag[(i*m)%10])
            { a[++num]=(i*m)%10; flag[(i*m)%10]=1; }
            else break;
        }
        ans=aans=0;
        for(int i=1;i<=num;i++)
        aans+=a[i];
        //cout<<num<<" "<<aans<<endl;
        cnt=n/m;
        ans+=(cnt/num)*aans;
        if(cnt%num)
        {
            for(int i=1;i<=cnt%num;i++)
            ans+=a[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

7.Codeforces Round #582 (Div. 3) B

题意：给定一个数组表示手机不同天的价格，如果某天之后存在价格比这一天价格多的情况就说这天是个坏天，问有多少个坏天。
　　从后往前，记录当前最小的价格，看下一个元素比当前最小价格小就是坏天。开始时忽略了等于的情况，所以错了几次。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<utility>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=2*1e5;
const int mx=(1<<20)+99;
ll n,num,flag,ans,aans,a[maxn+10];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int o=1;o<=t;++o)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        ans=0; aans=a[n];
        for(int i=n-1;i>0;i--)
        {
            if(a[i]<aans) aans=a[i];
            else if(a[i]>aans) ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

8.Codeforces Round #582 (Div. 3) D1

题意：给定一个数组，可以对其中元素除二，问最少除几次可以得到ｍ个相等的数。
　　看到这个题的时候没有思路。看别人的题解才恍然大悟，没必要一步到位，全部除下，之后看能够得到Ｋ个相同数步数，更新最小值即可。

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<utility>
#include<ostream>
#include<istream>
typedef long long ll;
using namespace std;
#define mod 1e9+7
#define PI acos(-1.0)
const ll maxn=2*1e5;
const int mx=(1<<20)+99;
ll n,m,ans,aans,flag,num,cnt,a[maxn+10],b[maxn+10],c[maxn+10];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    //int t;
    //cin>>t;
    //for(int o=1;o<=t;++o)
   //{
        cin>>n>>m;
        ans=1e16;
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        cin>>a[i];
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++)
        {
            aans=-1;
            for(;a[i];)
            {
                b[a[i]]++;
                aans++;
                c[a[i]]+=aans;
                if(b[a[i]]==m)
                ans=min(ans,c[a[i]]);
                a[i]/=2;
            }
        }
        cout<<ans<<endl;
    //}
    return 0;
}

总结：前面做较简单的题还稳定做题，到最后时间时，因为也不知道题目难度，剩下的三个题两个都有一定的想法，没想好做哪个题，两个都试了试，结果一个也没做出来。简单题也会有时候犯糊涂，读题还要仔细。而且，代码中的变量不应该太省劲，最好一定程度体现变量的含义。有时一时混淆变量的作用出了错，大部分不好查错。当然，在这方面出毛病也够丢人的了。。。