怎么说呢，对比以前考过的毒瘤题，今天的题还算是有一点良心的。
1.Classroom Watch
【问题描述】
给出一个正整数n，现在问存在多少个x，使得x在十进制下的每一位之和加上x等于n。
【输入格式】
共 1 行，一个正整数n 。
【输出格式】
第一行输出一个整数m，表示有m个符合条件的（若没有符合条件的，请只输出一个 0）。
下面m行，每行一个x,x按从小到大输出。
【输入】
21
【输出】
1
15
【数据范围】
对于100%的数据 \(1≤n≤10^9\)。
看上去很简单，其实。。。正如看上去的一样简单
开始想要从 1~n 暴力枚举，但是绝对会超时，所以我们来易证一波：
因为数据 \(n≤10^9\) 所以各个数位上的和最高为81；所以只用从 n-81 到 n 枚举就好了，不过我从 n-100 开始枚举。
ps.这题告诉了我有时候要相信题面，不能过于复杂化题面，要细心考虑复杂度的问题，可以通过数学证明法来排除大量冗杂的过程。
代码如下
#include<bits/stdc++.h>
using namespace std;
int n,ans=0,a[1001],y,g;
int main(){
scanf("%d",&n);
for(int i=max(1,n-100);i<=n;i++){
g=y=i;
while(y){
g=g+y%10;
y=y/10;
}
if(g==n) a[++ans]=i;
}
if(ans==0) printf("0");
else{
printf("%d\n",ans);
for(int i=1;i<=ans;i++)
printf("%d\n",a[i]);
}
return 0;
}
2.组合技能
【题目描述】
蓝月商城出新技能书了！！
如果古天乐想购买“旋风斩”，则他需要花费 A 元；如果古天乐想买“半月弯刀”，则需要 B 元；如果古天乐两个一起买，则需要 C 元。
蓝月的设计师非常有头脑，每样商品的利润都是相同的。即假设旋风斩和半月弯刀的成本为 a,b 元，则 A-a=B-b=C-a-b。
给出 A，B，C 求出利润，数据保证为正数。
【输入格式】
输入第一行一个数 T，表示 T 次询问。
接下来 T 行，每行三个数 A,B,C
【输出格式】
输出 T 行，每行一个数，表示利润。
【数据范围】
\(T≤100\)
\(A,B,C≤2000\)
【输入】
3
275 214 420
6 9 11
199 199 255
【输出】
69
4
143
感谢贪玩蓝月设计师。
老刘说要给我们出 A+B，然后。。。真的出了A+B！！
证明：因为 A-a=C-a-b，所以 b=C-A；所以利润就是 B-b 即 B-(C-A) 即 B-C+A。
代码如下
#include<bits/stdc++.h>
using namespace std;
int T,A,B,C;
int main(){
scanf("%d",&T);
for(int i=1;i<=T;i++){
scanf("%d%d%d",&A,&B,&C);
printf("%d\n",B-C+A);
}
return 0;
}
3.表面积
【题目描述】
古天乐在搭积木，积木图可以抽象为一个 n*m 的网格图，其中第 (i,j) 的位置有 A[i][j] 个积木。求表面积。
【输入格式】
输入第一行两个数 n,m，接下来 n 行每行 m 个数，表示 A[i][j]。
【输出格式】
输出一个数，表示表面积。
【数据范围】
\(1≤n,m≤100\)
\(1≤a[i][j]≤100\)
【输入样例1】
1 1
1
【输出样例1】
6
如图所示
【输入样例2】
3 3
1 3 4
2 2 3
1 2 4
【输出样例2】
60
如图所示
先吐槽一波，为什么又是古天乐。。。
其实我们可以先将图中所有的正方体的表面积加上，再减去重合的部分即可。
求相邻两块积木之间的接触面积，如果当前的积木低于周围的积木，说明它们重合的面是较低的积木的高度*2：
if(a[i][j]<a[i][j+1]) ans=ans-a[i][j]*2;
if(a[i][j]<a[i+1][j]) ans=ans-a[i][j]*2;
if(a[i][j]<a[i][j-1]) ans=ans-a[i][j]*2;
if(a[i][j]<a[i-1][j]) ans=ans-a[i][j]*2;
如果遇到相等的情况，则需要特殊考虑积木是否重复搜索，即上一次从1搜到2，这次就不能再从2搜到1。
因为它是按照行和列的顺序来搜的，所以向左和向上的比较都是非法的：
if(a[i][j]==a[i][j+1]&&v[s2]!=s){
v[s]=s2; ans=ans-a[i][j]*2;
}
if(a[i][j]==a[i+1][j]&&v[s4]!=s){
v[s]=s4; ans=ans-a[i][j]*2;
}
ps.本来有简单的做法的，考试时没想到，只好用这种特别复杂的方法，还用map记录我的搜索是否重复。
代码如下
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,num,a[1001][1001];
map<string,string>v;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
num+=a[i][j];
}
ans=6*num;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
string s="",s2="",s4="";
s=s+char(i+48)+char(j+48);
s2=s2+char(i+48)+char((j+1)+48);
s4=s4+char((i+1)+48)+char((j)+48);
if(a[i][j]!=0) ans=ans-(a[i][j]-1)*2;
if(a[i][j]<a[i][j+1]) ans=ans-a[i][j]*2;
if(a[i][j]<a[i+1][j]) ans=ans-a[i][j]*2;
if(a[i][j]<a[i][j-1]) ans=ans-a[i][j]*2;
if(a[i][j]<a[i-1][j]) ans=ans-a[i][j]*2;
if(a[i][j]==a[i][j+1]&&v[s2]!=s){
v[s]=s2; ans=ans-a[i][j]*2;
}
if(a[i][j]==a[i+1][j]&&v[s4]!=s){
v[s]=s4; ans=ans-a[i][j]*2;
}
}
printf("%d\n",ans);
return 0;
}
4.红皇后的旅行
【题目描述】
给定一个 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。
【输出格式】
输出第一行一个数，最小步数，第二行输出方案。
【数据范围】
\(5≤n≤100\)
\(0≤i_start,j_start,i_end,j_end<n\)
【输入样例1】
7
6 6 0 1
【输出样例1】
4
UL UL UL L
如图所示
【输入样例2】
6
5 1 0 5
【输出样例2】
Impossible
【输入样例3】
7
0 3 4 3
【输出样例3】
2
LR LL
如图所示
有点像改编版的青铜莲花池。
简单的bfs加上dfs求方案数。
因为要求最短路，而bfs第一次搜到的绝对是最短的路线，并且在搜索的过程中记录下进队列，坐标进行转移的情况，方便输出方案。
void bfs(){
memset(ljx,-1,sizeof(ljx));
memset(ljy,-1,sizeof(ljy));
int head=1,tail=0;
q[++tail].x=sx; q[tail].y=sy;
v[sx][sy]=1; ans=0;
while(tail>=head){
ans++; t=tail;
for(int i=head;i<=t;i++)
for(int j=1;j<=6;j++){
int x=q[i].x+dx[j],y=q[i].y+dy[j];
if(x<0||x>=n||y<0||y>=n) continue;
if(!v[x][y]){
q[++tail].x=x; q[tail].y=y; v[x][y]=1;
ljx[x][y]=q[i].x; ljy[x][y]=q[i].y;
num[x][y]=j;//记录转移的状态
}
if(x==ex&&y==ey){
printf("%d\n",ans);
sc(ex,ey); return;
}
}
head=t+1;
}
printf("Impossible\n");
}
然后当搜到终点时，进行dfs来搜索移动的方案，并输出：
void sc(int x,int y){
if(ljx[x][y]<0)return;
sc(ljx[x][y],ljy[x][y]);
if(num[x][y]==1) printf("UL ");
if(num[x][y]==2) printf("UR ");
if(num[x][y]==3) printf("R ");
if(num[x][y]==4) printf("LR ");
if(num[x][y]==5) printf("LL ");
if(num[x][y]==6) printf("L ");
}
完整代码如下
#include<bits/stdc++.h>
using namespace std;
struct que{
int x,y;
}q[10001];
int n,sx,sy,ex,ey,ans,t;
int num[201][201],ljx[201][201],ljy[201][201],v[201][201];
int dx[7]={0,-2,-2,0,2,2,0},dy[7]={0,-1,1,2,1,-1,-2};
void sc(int x,int y){
if(ljx[x][y]<0)return;
sc(ljx[x][y],ljy[x][y]);
if(num[x][y]==1) printf("UL ");
if(num[x][y]==2) printf("UR ");
if(num[x][y]==3) printf("R ");
if(num[x][y]==4) printf("LR ");
if(num[x][y]==5) printf("LL ");
if(num[x][y]==6) printf("L ");
}
void bfs(){
memset(ljx,-1,sizeof(ljx));
memset(ljy,-1,sizeof(ljy));
int head=1,tail=0;
q[++tail].x=sx; q[tail].y=sy;
v[sx][sy]=1; ans=0;
while(tail>=head){
ans++; t=tail;
for(int i=head;i<=t;i++)
for(int j=1;j<=6;j++){
int x=q[i].x+dx[j],y=q[i].y+dy[j];
if(x<0||x>=n||y<0||y>=n) continue;
if(!v[x][y]){
q[++tail].x=x; q[tail].y=y; v[x][y]=1;
ljx[x][y]=q[i].x; ljy[x][y]=q[i].y;
num[x][y]=j;
}
if(x==ex&&y==ey){
printf("%d\n",ans);
sc(ex,ey); return;
}
}
head=t+1;
}
printf("Impossible\n");
}
int main(){
scanf("%d",&n);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
bfs();
return 0;
}
ps.这题就一个输出方案比较毒瘤，但是，你还得按题目规定的顺序搜索，这也就提醒了我读题的重要。
ps.ps.我要认真学习bfs了。