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