A. 结果填空：年龄问题
某君的年龄是个两位数，如果把他年龄的两位数字交换位置后与原数字相加和为 x，与原数字相减差的绝对值为 y。已知 x 比 y 大 32。请你计算 y 的值是多少
思路：枚举
结果：45
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
for(int i=10;i<=99;++i) {
int g=i%10;
int s=i/10;
int j=g*10+s;
if(abs(i+j)-abs(i-j)==32) {
printf("%d
",abs(i-j));
break;
}
}
return 0;
}B. 结果填空：方程的解
给出方程组：
11x+13y+17z=2471
13x+17y+11z=2739
已知 x，y，z 均为正整数，请你计算 x，y，z相加和最小为多少
思路：枚举结果：181
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int main() {
int minres=3000;
for(int i=1;i<=2471/11;++i)
for(int j=1;j<=2471/13;++j)
for(int k=1;k<=2471/17;++k)
if(((i*11+j*13+k*17)==2471)&&(13*i+17*j+11*k)==2739)
minres=min(minres,i+j+k);
printf("%d
",minres);
return 0;
}C. 结果填空：九宫格
将数字 1…9 填入一个3×3 的九宫格中，使得格子中每一横行和的值全部相等，每一竖列和的值全部相等。请你计算有多少种填数字的方案。
思路：全排列
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<string>
using namespace std;
int main() {
int ans[9],sum=0;
for(int i=0;i<9;++i) ans[i]=i+1;
do {
int temp1=ans[0]+ans[1]+ans[2];
int temp2=ans[0]+ans[3]+ans[6];
if(((ans[3]+ans[4]+ans[5])==temp1)
&&((ans[6]+ans[7]+ans[8])==temp1)
&&((ans[1]+ans[4]+ans[7])==temp2)
&&((ans[2]+ans[5]+ans[8])==temp2))
sum++;
}while(next_permutation(ans,ans+9));
printf("%d
",sum);
return 0;
}
D. 代码填空：阶梯三角形
我们给出三角形的高度，通过函数在控制台上打印出一个三角形。右侧代码连续打印了几个大小不同三角形，最后形成了一个阶梯状的连续三角形。
请仔细阅读代码，填写缺失代码，完成图形的打印。
代码：
#include<stdio.h>
void print(int n) {
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j <= n + i - 1; ++j) {
if (j+i==n-1) {
printf("*");
} else if (j == n + i - 1) {
printf("*");
} else {
printf(" ");
}
}
printf("
");
}
for (int i = 0; i < n * 2 - 1; ++i) {
printf("*");
}
printf("
");
}
int main() {
for (int i = 1; i <= 16; i *= 2) {
print(i);
}
return 0;
}
E. 代码填空：组合数字
右侧代码是将 6 个整数按照任意顺序组合到一起，计算能组合出的最大数字。
例如：4123，25，66 组合到一起就是 66412325。
请阅读程序补全代码，实现这个功能
#include<stdio.h>
long long max(long long x, long long y) {
return x > y ? x : y;
}
long long test(int a[], int n) {
long long ret = 0;
for (int i = 0; i < n; ++i) {
int tp = a[i];
int j = 1;
while(tp) {
j *= 10;
tp /= 10;
}
ret = ret * j + a[i];
}
return ret;
}
long long f(int a[], int k) {
if (k == 6) {
return test(a, k);
}
long long ret = 0;
for(int i = k; i < 6; ++i) {
int t = a[k];
a[k] = a[i];
a[i] = t;
ret = max(ret,f(a,k+1));
t = a[k];
a[k] = a[i];
a[i] = t;
}
return ret;
}
int main() {
int a[6] = {517, 283, 429, 65, 6566, 32};
printf("%lld
", f(a, 0));
return 0;
}
F. 结果填空：补全等式
下图中，每个方块代表 1…13 中的某一个数字，但不重复。
例如：
1×2+9×7=13×5
10×8+12×3=11×4
只要有任意一个方块代表的数字不同，就算两种不同的方案。
请你计算，一共有多少种不同的方案。
结果：122368 运行时长：300.010s思路：DFS 运行时长比较长
代码：
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
int ans[13];
bool flag[14];
int sum=0;
void cal() {
int temp1=ans[1]*ans[2]+ans[3]*ans[4];
int temp2=ans[5]*ans[6];
int temp3=ans[7]*ans[8]-ans[9]*ans[10];
int temp4=ans[11]*ans[12];
if((temp1==temp2)&&(temp3==temp4)) {
sum++;
printf("%d
",sum);
}
}
void dfs(int pos) {
if(pos==13) {
cal();
return;
}
for(int i=1;i<=13;++i) {
if(flag[i]==true) continue;
flag[i]=true;
ans[pos]=i;
dfs(pos+1);
flag[i]=false;
}
}
int main() {
memset(ans,0,sizeof(ans));
memset(flag,false,sizeof(flag));
dfs(1);
printf("%d
",sum);
return 0;
}
G. 结果填空：礼物盒
小y有一个宽度为 100cm，高度为 20cm，深度为 1cm的柜子，如下图。
小y还有 3636 个礼物盒，他们的深度都为 1cm。
他们对应的宽度和高度如下，单位（cm）。
现在小y想把这些盒子放到柜子上，由于礼物盒里面都装有礼物，礼物盒必须向上放置，并且不能堆放。由于礼物盒深度和柜子深度一样，所以礼物盒和柜子深度方向也必须一致。并且礼物盒的高度还不能大于柜子的高度，否者放不进去。小y希望放到柜子上礼物盒的宽度和正好等于柜子的宽度，也就是希望柜子两边都不存在间隙。如下图符合条件的放置。
满足条件的情况下，小y希望能尽可能多的放置礼物盒，算出最多能放多少个礼物盒。
思路：放满的01背包
结果：18
代码：
/*
11 3
8 12
11 17
16 13
1 14
2 8
6 10
10 18
17 11
10 15
6 14
5 6
2 19
19 10
4 9
7 9
5 14
5 20
15 19
3 17
15 11
7 25
11 20
9 12
17 4
9 19
4 18
10 10
12 19
17 3
19 9
20 16
11 16
10 2
20 15
3 14
*/
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=-0x3f3f3f3f;
int main() {
int t=36,h,w;
vector<int> ans;
while(t--) {
scanf("%d%d",&w,&h);
if(h>20) continue;
ans.push_back(w);
}
int n=ans.size();
ans.push_back(*ans.end());
for(int i=n-1;i>=1;--i) ans[i]=ans[i-1];
int dp[n+1][101];
memset(dp,INF,sizeof(dp));
for(int i=0;i<=n;i++) {
dp[i][0]=0;dp[0][i]=0;
}
for(int i=1;i<=n;++i) {
for(int j=ans[i];j<=100;++j) {
dp[i][j]=max(dp[i-1][j],dp[i-1][j-ans[i]]+1);
}
}
printf("%d
",dp[n][100]);
return 0;
}H. 程序设计：成绩查询系统
数学老师小y想写一个成绩查询系统，包含如下指令：
- insert [name] [score]，向系统中插入一条信息，表示名字为name的学生的数学成绩为score。
- find [name]，表示查找名字为name的学生的数学成绩。
注意有些同学可能会为了刷分多次选课，查询的时候给出最大成绩即可。学生的名字是由小写字母组成。成绩是一个 0 ldots1000…100 的整数。
老师找到你，想你帮他完成这个系统。
输入格式
输入若干行，每行都是insert [name] [score]或者find [name]的形式，或一行end表示输入结束。输入行数不大于 1000，每个学生名字长度不大于 20 个字符。
输出格式
对于每个查询，输出查询的学生的最高成绩，如果系统中不存在该学生，输出 -1。
思路：map
代码：
/*
insert zhangsan 90
insert zhangsan 96
insert lisi 78
insert xiaoming 86
find xiaoming
find zhangsan
find jack
end
*/
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int main() {
string s;
map<string,int> a;
while(cin>>s) {
if(s[0]=='e') break;
else if(s[0]=='i') {
string name;
int score;
cin>>name>>score;
map<string,int>::iterator temp;
temp=a.find(name);
if(temp==a.end()) a.insert(make_pair(name,score));
else a[name]=max(a[name],score);
} else if(s[0]=='f') {
string name;
cin>>name;
map<string,int>::iterator temp;
temp=a.find(name);
if(temp==a.end()) {
cout<<"-1"<<endl;
} else {
cout<<temp->second<<endl;
}
}
}
return 0;
}
I. 程序设计：引爆炸弹
在一个 n×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。
现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。
输入格式
第一行输两个整数 n,m，用空格隔开。
接下来 n 行，每行输入一个长度为 m 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。
数据约定：
对于60% 的数据： 1≤n,m≤100；
对于 100% 的数据： 1≤n,m≤1000；
数据量比较大，不建议用cin输入。
输出格式
输出一个整数，表示最少需要手动引爆的炸弹数。
思路：并查集
代码：
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=1005;
struct edge {
int from,to;
}Edge[maxn*maxn];
int pre[maxn];
bool cmp(const edge &a, const edge &b) {
if(a.from==b.from) return a.to<b.to;
return a.from<b.from;
}
int findfather(int x) {
if(pre[x]!=x) pre[x]=findfather(pre[x]);
return pre[x];
}
void change(int son, int f) {
if(pre[son]!=f) {
change(pre[son],f);
pre[son]=f;
}
}
int main() {
int n,m;
scanf("%d %d
",&n,&m);
char s[m+1];
int index=0;
for(int i=0;i<n;++i) {
gets(s);
for(int j=0;j<m;++j) {
if(s[j]=='1') {
Edge[index].from=i;
Edge[index].to=j+n;
index++;
}
}
}
for(int i=0;i<maxn;++i) pre[i]=i;
sort(Edge,Edge+index,cmp);
for(int i=0;i<index;++i) {
int f1=findfather(Edge[i].from),f2=findfather(Edge[i].to);
if(f1!=f2) {
pre[f1]=f2;
}
}
set<int> ans;
for(int i=0;i<index;++i) {
ans.insert(findfather(Edge[i].from));
ans.insert(findfather(Edge[i].to));
}
int result=ans.size();
printf("%d
",result);
return 0;
}
J. 程序设计：放置守卫
在一张 n 行 m 列的方格地图上放置一些守卫，每个守卫能守护上、左、右三个方向上相邻的方格和自己所在的方格。如下图，红色的方格放置守卫，绿色的方格为该守卫守护的区域。
现在要求在地图上放置若干个守卫，让每个方格至少被一个守卫守护（可以同时被多个守卫守护），但是有些方格上不能放置守卫（这个方格也需要被守护），求出最少需要多少个守卫才能满足条件。
输入格式
第一行输入两个整数 n,m。
接下来输入一个 n×m 的矩阵。矩阵中元素为 0 表示该位置不能放置守卫，为 1 表示该位置能放置守卫。元素之间用空格隔开。
数据约定：所有数据保证一定有一种方案满足条件。
对于 20% 的数据： 1≤n,m≤5；
对于 50% 的数据： 1≤n≤20,1≤m≤10；
对于100% 的数据：1≤n∗m≤1000,1≤m≤15。
输出格式
输出最少需要放置的守卫数量。
思路：轮廓线DP 我还不会啊QAQ