20190531考试

                                     1 Classroom Watch

【问题描述】

 给出一个正整数 n,现在问存在多少个 x,使得  x在十进制下的每一1位之和加上 x 等于 n。

【输入】

  共 1 行,一个正整数n 。

【输出】

第一行输出一个整数 m,表示有 m 个符合条件的 (若没有符合条件的 ,请只输出一个 0)。
下面m行,每行一个 x ,x按从小到大输出。

【输入输出样例1】

num.in

num.out

21

1
15

 这题我一开始想的是从1到n-1枚举一遍,后来发现这样可能会爆炸,然后在随机输入的过程中,我发现n和结果的差不超过100(因为9*9=81),然后就改成枚举n-111到n-1了。n是不用枚举的,因为n+各个位数之和肯定大于自己。当然数字拆分也是这题的重点。

代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,s=0,a[10000010];
int main()
{
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	scanf("%d",&n);
	for (long long i=max(1,n-100);i<n;i++)
	{
		long long x=i,sum=0;
		while (x!=0)
		{
			sum+=x%10;
			x=x/10;
		}
		if (sum+i==n)
		{
			s++;
			a[s]=i;
		}
	}
	printf("%d\n",s);
	for (int i=1;i<=s;i++)
	printf("%d\n",a[i]);
	return 0;
}

                                     2. 组合技能(combo.cpp)

题目描述

       。。。。出新技能书了!!

       如果***想购买“旋风斩”,则他需要花费A元;如果***想买“半月弯刀”,则需要B元;如果***两个一起买,则需要C元。

       蓝月的设计师非常有头脑,每样商品的利润都是相同的。即假设旋风斩半月弯刀的成本为a,b元,则A-a=B-b=C-a-b。

       给出A,B,C求出利润,数据保证为正数。

格式

       输入第一行一个数T,表示T次询问。

       接下来T行,每行三个数A,B,C

       输出T行,每行一个数,表示利润。

Sample Input 0

3
275 214 420
6 9 11
199 199 255

Sample Output 0

69
4
143

 这题A+B-C即为答案,不过我先求了a和b。

代码如下:

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
	freopen("combo.in","r",stdin);
	freopen("combo.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		int A,B,C,a=0,b=0;
		int c;//利润 
	    scanf("%d%d%d",&A,&B,&C);
	    b=C-A;
	    a=C-B;
	    c=C-a-b;
	    printf("%d\n",c);
	}
	return 0;
}

                                  3.表面积(surface.cpp)

题目描述

       ***在搭积木,积木图可以抽象为一个n*m的网格图,其中第(i,j)的位置有A[i][j]个积木。求表面积。

格式

       输入第一行两个数n,m,接下来n行每行m个数,表示A[i][j]。

       输出一个数,表示表面积。

Sample Input 0

1 1
1

Sample Output 0

6

Sample Input 1

3 3
1 3 4
2 2 3
1 2 4

Sample Output 1

 60

我的做法是先将上下左右前后的表面积加起来为sum(不包括中间突出来的),如果哪一列比他的前后左右那一列高,那sum就加上他们的差,当然这列如果矮的话那就不加(不然会多算)。

代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[110][110]={},sum=0;
int main()
{
	freopen("surface.in","r",stdin);
	freopen("surface.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		scanf("%d",&a[i][j]);
	}
	sum+=2*n*m;
	for (int j=1;j<=m;j++)
	sum=sum+a[1][j]+a[n][j];
	for (int i=1;i<=n;i++)
	sum=sum+a[i][1]+a[i][m];
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			if (a[i+1][j]!=0&&a[i+1][j]<a[i][j])
			sum+=a[i][j]-a[i+1][j];
			if (a[i-1][j]!=0&&a[i-1][j]<a[i][j])
			sum+=a[i][j]-a[i-1][j];
			if (a[i][j+1]!=0&&a[i][j+1]<a[i][j])
			sum+=a[i][j]-a[i][j+1];
			if (a[i][j-1]!=0&&a[i][j-1]<a[i][j])
			sum+=a[i][j]-a[i][j-1];
		}
	}
	printf("%d",sum);
	return 0;
}

                           4.红皇后的旅行(redqueen.cpp)

题目描述

       给定一个n*n的棋盘,行和列标号为0,1,2,….,n-1。在棋盘的(i_start,j_start)位置上有一位红皇后,每次红皇后可以往六个方向走,如图所示:

       现在红皇后想去(i_end,j_end)点,求最短距离,并且输出一条路径。显然最短路径有无穷条,请按照以下顺序来搜索:UL, UR, R, LR, LL, L 如果无解,输出Impossible。

格式

       输入第一行一个数n,第二行四个数,i_start,j_start,i_end,j_end。

       输出第一行一个数,最小步数,第二行输出方案。

Sample Input 0

7

6 6 0 1

Sample Output 0

4

UL UL UL L

Sample Input 1

6

5 1 0 5

Sample Output 1

Impossible

Sample Input 2

7

0 3 4 3

Sample Output 2

2

LR LL

 

       这题我们从终点倒着搜回去,即BFS时先把终点加入队列,然后进行拓展拓展只需要枚举6个方向搞一下即可。在记录Dis[x](从x点到终点的最短距离)的同时,再开一个数组pre[x]pre[x]存的是6个方向的其中一个,表示在dis[x]最小的情况下,接下来走哪个方向,字典序最小。输出时递归即可。(这种代码稍微长点的题目还得多练练,因为考试里不能第一时间打出来)。

代码如下:

 

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
int dx[6]={-2,-2,0,2,2,0},dy[6]={-1,1,2,1,-1,-2};
int a,b,c,d,n,pr1[201][201],pr2[201][201],z[201][201],sum[201][201];
void shuchu(int x,int y)
{
    if (!x) return;
    shuchu(pr1[x][y],pr2[x][y]);
    if (z[x][y]==0) printf("UL ");
    else if (z[x][y]==1) printf("UR ");
    else if (z[x][y]==2) printf("R ");
    else if (z[x][y]==3) printf("LR ");
    else if (z[x][y]==4) printf("LL ");
    else if (z[x][y]==5) printf("L ");
    return;
}
int main()
{
	freopen("redqueen.in","r",stdin);
	freopen("redqueen.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	a++;b++;c++;d++;
	queue< pair < int , int> > q;
	memset(sum,20,sizeof(sum));
	sum[a][b]=0;
	pr1[a][b]=pr2[a][b]=0;
	z[a][b]=z[c][d]=6;
	q.push(mp(a,b));
	while(!q.empty())
	{
		int x=q.front().first,y=q.front().second;
		q.pop();
		for (int i=0;i<6;i++)
		{
			int xx=x+dx[i],yy=y+dy[i];
			if (xx<0||xx>n||yy<0||yy>n) continue;
			if (sum[x][y]+1>=sum[xx][yy]) continue;
			sum[xx][yy]=sum[x][y]+1;
			pr1[xx][yy]=x;
			pr2[xx][yy]=y;
			z[xx][yy]=i;
			if(xx==c&&yy==d) break;
			q.push(mp(xx,yy)); 
		}
	}
	if (sum[c][d]==336860180) 
		{
			printf("Impossible");
			return 0;
		}
		else printf("%d\n",sum[c][d]),shuchu(c,d);
	return 0;
}

                                  5.构造序列(construct.cpp)

题目描述

       有一个长度为n的序列A,其中A[1]=1,A[n]=x,A[2…n-1]可以是1至k间任意一个正整数。求有多少个不同的序列,使得相邻两个数不同。

       答案对10^9+7取模。

格式

       输入共一行,包含三个数,n,k,x。

       输出一个数,表示答案。

Sample Input 1

4 3 2

Sample Output 1

3

这题我一看就觉得他是一道特别坑的排列组合,然后一直想着推公式,结果推着推着一个小时就过了。。。

代码如下:(附带解释)

#include<bits/stdc++.h>
using namespace std;
long long dp[110010];//dp[i]为前i个数第j个数为j但不为x的所有方案
long long f[110010];//f[i]为第i个数为x的方案数,f[n]即为目标 
long long n,k,x;
int main()
{
	freopen("construct.in","r",stdin);
	freopen("construct.out","w",stdout);
	scanf("%lld%lld%lld",&n,&k,&x);
	dp[2]=k-1;
	for (int i=3;i<=n;i++)
	dp[i]=dp[i-1]*(k-1)%1000000007;
	if (x==1) f[2]=0; 
	else f[2]=1;//如果x==1,也就是说等于第一个数,那么第二个数就不能为x,所以f[2]=0,反之则为1. 
	for (int i=3;i<=n;i++)
	{
		f[i]=(dp[i-1]-f[i-1]+1000000007)%1000000007;
		//因为第i个数为x,所以第i-1个数不能是x,所以要减去第i-1个数为x时的方案数。
		//(当然这里一定要再加上10^9+1,不然会炸) 
	}
	printf("%lld",f[n]);
	return 0;
}

 

原文链接:加载失败,请重新获取