新鲜出炉的今晚烽火通信在线编程题目及详细题解。

http://exercise.acmcoder.com/online/online_judge_list?konwledgeId=170

学打字

题意

输入只有大写字母、小写字母的字符串，要求输出最少的按键次数。最少按键次数由两

部分构成：

1.输入字符串内的字母（无论大小写，每个字母均只需按一次）；

2.当遇到大小写切换时需要使用Caps Lock键

（初始默认为小写，需要切换时按一次）。

根据字符串统计出最少按键次数即可。

参考代码：

#include <bits/stdc++.h>
#define maxn 100009
using namespace std;
char s[maxn];
int sgn(char c){
	if('a'<=c&&c<='z')
		return 0;
	else
		return 1;
}
int main(){
	scanf("%s",s+1);
	s[0]='a';
	int n=strlen(s+1);
	int ans=n;
	for(int i=1;i<=n;i++){
		if(sgn(s[i-1])!=sgn(s[i]))
			ans++;
	}
	printf("%d\n",ans);
	//system("pause");
	return 0;
}

小明的棋盘

题意

假设有n×m的棋盘，棋盘里面有黑子或者白子，小明可以将矩形块内的黑白子颠倒，那么输入棋盘大小和能够使用超能力次数，要求得出是否可以完成使得整个棋盘变为纯色的要求。

假设黑子和白子之间有着分隔符（竖向和横向2个方向），如下图所示，O代表白子，X代表黑子，这个3×3的棋盘内共有12个分割符。

而每一次使用超能力，就相当于将一个矩形内的分割符覆盖一次，相当于分隔符方向上的棋子变成同色，显然易得覆盖两次相当于又变为异色。故使得棋盘变为纯色，只需要将所有分隔符覆盖奇数次。

如果实现将所有分隔符覆盖奇数次使用矩形次数大于可使用超能力次数，则无法实现将棋盘变为纯色，不应购买；如果小于可使用超能力次数，则可以实现将棋盘变为纯色，应该购买。

参考代码：

#include<cstdio>

using namespace std;
int main()
{
    int n,m,c;
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,c;
        scanf("%d%d%d",&n,&m,&c);
        (n/2+m/2)<=c?puts("Yes"):puts("No");
    }
    return 0;
}

又是士兵队列

题意

n个士兵在操场上排成一列，这些士兵的身高分别为a₁; a₂; : : : ; a_n。列队完毕后，将军在最前面看这一队士兵，将军能看到队列中第i个位置的士兵，当且仅当第1;2; : : : ; i-1个位置上的士兵身高严格小于第i个士兵。问有多少种站队方式可以使得将军恰好看到m个士兵。

参考代码：

#include <bits/stdc++.h>
#define maxn 1009
using namespace std;
const int MOD=1e9+7;
int n,m,cnt[maxn];
long long dp[maxn][maxn];
long long fact[maxn],rfact[maxn];
long long mgml(long long a,int b){
	long long res=1;
	while(b){
		if(b&1)
			res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}
map<int,int>mp;
int main(){
	fact[0]=1;
	for(int i=1;i<maxn;i++)
		fact[i]=fact[i-1]*i%MOD;
	for(int i=0;i<maxn;i++)
		rfact[i]=mgml(fact[i],MOD-2);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		mp[x]++;
	}
	int tot=0;
	for(map<int,int>::iterator it=mp.begin();it!=mp.end();++it){
		tot++;
		cnt[tot]=it->second;
	}
	reverse(cnt+1,cnt+tot+1);
	dp[1][1]=fact[cnt[1]];
	int sum=cnt[1];
	for(int i=2;i<=tot;i++){
		for(int j=1;j<=i;j++){
			dp[i][j]=dp[i-1][j]*fact[sum-1+cnt[i]]%MOD*rfact[sum-1]%MOD+dp[i-1][j-1]*cnt[i]%MOD*fact[sum+cnt[i]-1]%MOD*rfact[sum]%MOD;
			dp[i][j]%=MOD;
		}
		sum+=cnt[i];
	}
	cout<<dp[tot][m]<<endl;
	//system("pause");
	return 0;
}

更详细题解点击这里：

http://exercise.acmcoder.com/online/online_judge_list?konwledgeId=170