程序设计思维与实践 Week14 作业 (3/4/数据班)

程序设计思维与实践 Week14 作业 (3/4/数据班)

Q老师与石头剪刀布（必做）

问题分析

遍历字符串，尽可能的多赢，记录赢的总次数。
若总次数大于n/2(上取整) 次，则根据标记判断每一局的结果，若有标记，输出赢的情况，否则判断剩余的出招情况，任选未使用的一种出拳即可。
若小于n/2(上取整)次，则直接输出NO。

#include <iostream>
#include <string.h>
using namespace std;
const int size=100+10;
int n;
int a,b,c;
char str[size];
bool res[size];
int ans;
void solve()
{
	ans=0;
	for(int i=0;i<n;i++)
	{
		if(str[i]=='R')
		{
			if(b>0)
			{
				b--;res[i]=true;ans++;
			}
			else
				res[i]=false;
		}
		else if(str[i]=='P')
		{
			if(c>0)
			{
				c--;res[i]=true;ans++;
			}
			else
				res[i]=false;
		}
		else
		{
			if(a>0)
			{
				a--;res[i]=true;ans++;
			}
			else
				res[i]=false;
		}
	}
	if(ans>=n/2.0)
	{
		printf("YES
");
		for(int i=0;i<n;i++)
		{
			if(res[i])
			{
				if(str[i]=='R')printf("P");
				else if(str[i]=='P')printf("S");
				else printf("R"); 
			}
			else
			{
				if(a>0)
				{
					printf("R");a--;
				}
				else if(b>0)
				{
					printf("P");b--;
				}
				else 
				{
					printf("S");c--;
				}
			}
		}
		printf("
");
	}
	else
		printf("NO
"); 
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		scanf("%d%d%d",&a,&b,&c);
		scanf("%s",str);
		solve();
	}
	return 0;
}

Q老师与十字叉（必做）

问题分析

遍历网格图。对黑格，以该位置为十字叉所需分钟数为该位置所在行列的空白格数相加，空白格则还需减一，求小分钟数。

#include <iostream>
#include <string.h>
using namespace std;
const int size=4e5+10;
const int inf=1e9;
char map[size];
int col[size];
int row[size];
int ans;
int n,m;
void solve()
{
   for(int i=0;i<n;i++)
   {
   	row[i]=0;
   	for(int j=i*m;j<(i+1)*m;j++)
   	{
   		if(map[j]=='.')row[i]++;
   	}
   }
   for(int i=0;i<m;i++)
   {
   	col[i]=0;
   	for(int j=i;j<n*m;j+=m)
   	{
   		if(map[j]=='.')col[i]++;
   	}
   }
   ans=inf;
   for(int i=0;i<n;i++)
   {
   	for(int j=0;j<m;j++)
   	{
   		int temp=row[i]+col[j];
   		if(map[i*m+j]=='.')temp--;
   		ans=min(ans,temp);
   	}
   }
   printf("%d
",ans);
}
int main() {
   int T;
   scanf("%d",&T);
   while(T--)
   {
   	scanf("%d%d",&n,&m);
   	for(int i=0;i<n;i++)
   	{
   		scanf("%s",map+i*m);
   	}
   	solve();
   }
   return 0;
}

Q老师的考验（必做）

问题分析

使用矩阵快速幂。

#include <iostream>
#include <string.h>
using namespace std;
int k,m;
const int N=10;
struct Matrix{
   int x[N][N];
   Matrix operator*(const Matrix&b)
   {
   	Matrix ret;
   	for(int i=0;i<N;i++)
   	{
   		for(int j=0;j<N;j++)
   		{
   			for(int k=0;k<N;k++)
   			{
   				ret.x[i][j]+=(x[i][k]*b.x[k][j])%m;
   				ret.x[i][j]%=m;
   			}
   		}
   	}
   	return ret;
   }
   Matrix()
   {
   	memset(x,0,sizeof(x));
   }
   Matrix(Matrix&b)
   {
   	memcpy(x,b.x,sizeof(x));
   }
};
Matrix quick_pow(Matrix a,int x)
{
   Matrix ret;
   for(int i=0;i<N;i++)
   	ret.x[i][i]=1;
   while(x)
   {
   	if(x&1)ret=ret*a;
   	a=a*a;
   	x>>=1;
   }
   return ret;
}
int main(int argc, char** argv) {
   while(scanf("%d%d",&k,&m)!=EOF)
   {
   	if(k<=9)
   	{
   		printf("%d
",k%m);
   		continue;
   	}
   	Matrix temp;
   	for(int i=0;i<N;i++)
   		scanf("%d",&temp.x[0][i]);
   	for(int i=1;i<N;i++)
   		temp.x[i][i-1]=1;
   	temp=quick_pow(temp,k-9);
   	
   	int ans=0;
   	for(int i=0;i<10;i++)
   	{
   		ans+=(temp.x[0][i]*(9-i))%m;
   		ans%=m;
   	}
   	printf("%d
",ans);
   }
   return 0;
}