1． Classroom Watch
【问题描述】
给出一个正整数 n，现在问存在多少个 x，使得 x在十进制下的每一1位之和加上 x 等于 n。
【输入】
共 1 行，一个正整数n 。
【输出】
第一行输出一个整数 m，表示有 m 个符合条件的 （若没有符合条件的 ，请只输出一个 0）。
下面m行，每行一个 x ，x按从小到大输出。
【输入输出样例1】
|
num.in |
num.out |
|
21 |
|
这题我一开始想的是从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;
}