admin 管理员组

文章数量: 893893

填图格子+放球

Description
给你n个方格,m种颜色,要求相邻格和首尾格的颜色不同,请问有多少种不同的填涂方法。

Input
每行一个正整数n,n≤40。如果n为0,表示输入结束,不需要处理。

Output
每行输出一个结果,为一个整数。

Sample Input
1
2
3
0

Sample Output
2
3
5

解题思路:
n=1时:m
n=2时:m*(m-1)
n=3时:m*(m-1)*(m-2)

当n>3时,需分两种情况考虑:

①第n-1格与第1格颜色不同,则f[n-1]是排列好的,第n格有(m-2)种涂法,f(n)=f(n-1)*(m-2)

②第n-1格与第1格颜色相同,则f[n-2]是排列好的,第n格有(m-1)种涂法,f(n)=f(n-2)*(m-1)

所以得递推式f(n)=f(n-1)*f(m-2)+f(n-2)*f(m-1)

注意:在使用while语句时,如果题目没有说明结束条件,则应该使用!=EOF,否则会造成Output Limit Exceed。

#include<stdio.h>
#define mod 1000003
int f[1002];int main()
{int n,m,i;while(scanf("%d %d",&n,&m)!=EOF){f[1]=m;    f[2]=m*(m-1)%mod; f[3]=m*(m-1)*(m-2)%mod;if(n>3){for(i=4;i<=n;i++){f[i]=(f[i-1]*(m-2)%mod+f[i-2]*(m-1)%mod)%mod;}}printf("%d\n",f[n]);}return 0;
}

————————————————
版权声明:本文为CSDN博主「Kiwi1025」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:


Description
你有r颗红球,g颗绿球,b颗蓝球,它们排成一个直线。你想它们按红绿蓝顺序分成三个颜色区域,你每次可以任意交换两个球的位置,请问至少需要交换多少次?

Input
每行输入一个字符串表示开始时球的序列,使用RGB分别表示红绿蓝三色球,字符串长度不超过10000。

Output
每行输出一个样例的结果。

Sample Input
RRGGBB
RGBRGB

Sample Output
0
2

解题思路:
统计R,G,B的出现次数,在0…R-1统计G,B的出现次数,记为R1,R2,在R…R+G-1统计R,B的出现次数,记为G1,G2,在R+G…length-1统计R,G的出现次数,记为B1,B2。

那么首先肯定是两个两个区间互相交换,R1,G1交换,R2,B1交 换和G2,B2交换。有可能交换不完,成为0…R-1还有’G’,R…R+G-1还有’B’,R+G…length-1还有’R’的情况,那对于每个未交换字符的需要交换2次。

#include<bits/stdc++.h>
using namespace std;

int main()
{
char s[10001];
while(~(scanf("%s",s)))
{
int length=strlen(s);
int R=0,G=0,B=0;

	for(int i=0; i<length; i++){if(s[i] == 'R') R++;else if(s[i] == 'G') G++;else B++;}//0~R-1 G,Bint R1=0,R2=0;for(int i=0; i<R; i++){if(s[i] == 'G') R1++;else if(s[i] == 'B') R2++;}//R~R+G-1 R,Bint G1=0,G2=0;for(int i=R; i<R+G; i++){if(s[i] == 'R') G1++;else if(s[i] == 'B') G2++;}//R+G~length-1 R,Gint B1=0,B2=0;for(int i=R+G; i<length; i++){if(s[i] == 'R') B1++;else if(s[i] == 'G') B2++;}int sum=0,temp=0;if(R1 && G1){temp=min(R1,G1);sum += temp;R1  -= temp;G1  -= temp;}if(R2 && B1){temp=min(R2,B1);sum += temp;R2  -= temp;B1  -= temp;}if(G2 && B2){temp=min(G2,B2);sum += temp;G2	-= temp;B2	-= temp;}sum += (R1+R2+G1+G2+B1+B2)/3*2;cout<<sum<<endl;
}

}
————————————————
版权声明:本文为CSDN博主「Kiwi1025」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:

本文标签: 填图格子放球