程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Codeforces 300

Codeforces 300

編輯：關於C++

A題就是水題，直接按要求分類就行了。

#include
#include
#include
using namespace std;

int main()
{
    int n,cnt1,cnt2,cnt3,a[110];
    int b1[110],b2[110],b3[110];
    while(scanf("%d",&n)!=EOF)
    {
        cnt1=cnt2=cnt3=0;
        for(int i=0;i0)
            {
                b2[cnt2++]=x;
            }
         }
            printf("1 %d\n",b1[0]);
            if(cnt2==0)
            {
                b2[cnt2++]=b3[--cnt3];
                b2[cnt2++]=b3[--cnt3];
            }
            printf("%d ",cnt2);
            for(int i=0;i<cnt2;i++) printf("%d="" ",b2[i]);="" printf("\n%d="" 0="" ",cnt3+1);="" for(int="" i="0;i

B題的話我們先把必須在一個隊的人標記成同一個數，然後對那些沒有組隊要求的人，我們也隨意給他們分成幾組（標記）;然後我們檢查一下，如果有哪個隊的人數大於三或則是小於3就是不可能的情況，輸出-1；其它情況按標記輸出組隊情況。代碼寫的有點亂

代碼如下：

#include
#include
#include
using namespace std;

int M[50][50],vis[50];
int m,n;

int dfs(int x,int cnt)
{
    vis[x]=cnt;
    for(int i=1;i<=n;i++)
        if(M[x][i])
        {
            M[x][i]=M[i][x]=0;
            dfs(i,cnt);
        }
}

int main()
{

    while(scanf("%d%d",&n,&m)!=EOF)
    {
         memset(vis,0,sizeof(vis));
         memset(M,0,sizeof(M));
         for(int i=1;i<=m;i++)
         {
             int a,b;
             scanf("%d%d",&a,&b);
             if(a==b)
                continue;
             M[a][b]=1; M[b][a]=1;
         }
         int flag=0,cnt=0;
         for(int i=1;i<=n;i++)
         {
             int j;
             for(j=1;j<=n;j++)
             {
                 if(M[i][j])
                    break;
             }
             if(j<=n)
               dfs(i,++cnt);
         }
         for(int i=1;i<=n/3;i++)
         {
             int d=0;
             for(int j=1;j<=n;j++)
                if(vis[j]==i)
                    d++;
             if(d>3)
             {
                flag=1;
                break;
             }
             while(d<3)
             {
                 for(int k=1;k<=n;k++)
                    if(vis[k]==0)
                    {
                       vis[k]=i;
                       break;
                    }
                d++;
             }
         }
         for(int i=1;i<=n/3;i++)
         {
             int d=0;
             for(int j=1;j<=n;j++)
             {
                 if(vis[j]==i)
                        d++;
             }
             if(d<3)
             {
                 flag=12;
                 break;
             }
         }
         if(flag)
         {
             printf("-1\n");
             continue;
         }
         for(int i=1;i<=n/3;i++)
         {
            for(int j=1;j<=n;j++)
            {
                if(vis[j]==i)
                    printf("%d ",j);
            }
            printf("\n");
         }
    }
 return 0;
}

C題的話我們應該枚舉(構造)結果，然後檢查是否符合要求。然後的話就是一個排列組合的問題了。注意一個公式：(a/b)%mod==a*pow(b,mod-2),mod是素數。這個公式可以用來快速算組合數。

代碼如下：

#include
#include
#include
using namespace std;

#define mod 1000000007
#define ll long long

ll f[1000009];

ll pow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans%mod;
}

int a,b,n;

bool check(ll x)
{
    while(x)
    {
        int i=x%10;
        if(i!=a&&i!=b)
            return false;
        x/=10;
    }
    return true;
}

int main()
{

    f[0]=1;
    for(int i=1;i<=1000001;i++)
        f[i]=f[i-1]*i%mod;
    while(scanf("%d%d%d",&a,&b,&n)!=EOF)
    {
        ll ans=0;
        for(int i=0;i<=n;i++)
        {
            ll sum=(ll)i*a+(ll)(n-i)*b;
            if(check(sum))
            {
                ll d=f[i]*f[n-i]%mod;
                ans=(ans+f[n]*pow(d,mod-2)%mod)%mod;
            }
        }
        printf("%lld\n",ans);
    }
  return 0;
}