第一题 某君的年龄是个两位数，如果把他年龄的两位数字交换位置后与原数字相加和为 x，与原数字相减差的绝对值为 y。已知 x 比 y 大 32。请你计算 y 的值是多少
#include<iostream> #include<math.h> using namespace std; int main() { int a,b; for(int a=0; a<=9; a++) { for(int b=0; b<=9; b++) { if(abs((a*10+b)-(b*10+a))==a*10+b+b*10+a-32) { cout<<abs((a*10+b)-(b*10+a))<<endl; return 0; } } } }答案：45
第二题 给出方程组： 11x+13y+17z=2471 13x+17y+11z=2739 已知 x，y，z 均为正整数，请你计算 x，y，z相加和最小为多少
#include<iostream> #include<math.h> using namespace std; int main() { // 2471/11~224;2471/13~190;2471/17~145 int x,y,z,minimal,minamal=2471; for(int x=0;x<=224;x++){ for(int y=0;y<=190;y++){ for(int z=0;z<=145;z++){ if(11*x+13*y+17*z==2471){ if(13*x+17*y+11*z==2739){ minimal=x+y+z; minamal=min(minimal,minamal); } } } } } cout<<minamal<<endl; }答案：181
第三题 将数字 1…9 填入一个3×3 的九宫格中，使得格子中每一横行和的值全部相等，每一竖列和的值全部相等。请你计算有多少种填数字的方案。
#include<iostream> #include<string.h> using namespace std; const int size=10; int a[size],ans=0; bool used[size]={false}; void dfs(int step){ if(step==7){ if(a[1]+a[2]+a[3]!=a[4]+a[5]+a[6])return; } if(step==10){ if(a[4]+a[5]+a[6]!=a[7]+a[8]+a[9])return; else{ if(a[1]+a[4]+a[7]!=a[2]+a[5]+a[8])return; if(a[2]+a[5]+a[8]!=a[3]+a[6]+a[9])return; else{ for(int i=1;i<=9;i++) cout<<a[i]<<" "; cout<<endl; ans++; } } } for(int i=1;i<=9;i++){ if(used[i]==false){ a[step]=i; used[i]=true; dfs(step+1); used[i]=false; } } } int main() { dfs(1); cout<<ans<<endl; }答案：72
第四题 我们给出三角形的高度，通过函数在控制台上打印出一个三角形。右侧代码连续打印了几个大小不同三角形，最后形成了一个阶梯状的连续三角形。 请仔细阅读代码，填写缺失代码，完成图形的打印。
#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 ( /*在这里填写必要的代码*/) { printf("*"); } else if (j == n + i - 1) { printf("*"); } else { printf(" "); } } printf("\n"); } for (int i = 0; i < n * 2 - 1; ++i) { printf("*"); } printf("\n"); } int main() { for (int i = 1; i <= 16; i *= 2) { print(i); } return 0; }答案：j == n - i - 1
第五题 右侧代码是将 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, /*在这里填写必要的代码*/); 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\n", f(a, 0)); return 0; }答案：f(a,k+1)
第六题 下图中，每个方块代表 1…13 中的某一个数字，但不重复。 例如： 1×2+9×7=13×5 10×8+12×3=11×4 只要有任意一个方块代表的数字不同，就算两种不同的方案。 请你计算，一共有多少种不同的方案。
#include<iostream> #include<string.h> using namespace std; const int size=14; int a[size],ans=0; bool used[size]= {false}; void dfs(int step) { if(step==7) { if(a[1]*a[2]+a[3]*a[4]!=a[5]*a[6])return; } if(step==11) { if(a[7]*a[8]<=a[9]*a[10])return; } if(step==13) { if(a[7]*a[8]-a[9]*a[10]!=a[11]*a[12])return; else { // for(int i=1; i<=9; i++) // cout<<a[i]<<" "; // cout<<endl; ans++; } } for(int i=1; i<=13; i++) { if(used[i]==false) { a[step]=i; used[i]=true; dfs(step+1); used[i]=false; } } } int main() { dfs(1); cout<<ans<<endl; }答案：122368
第七题 小y 有一个宽度为 100cm，高度为 20cm，深度为 1cm 的柜子 小y 还有 3636 个礼物盒，他们的深度都为 1cm。 他们对应的宽度如下，单位（cm）。 现在小y 想把这些盒子放到柜子上，由于礼物盒里面都装有礼物，礼物盒必须向上放置，并且不能堆放。由于礼物盒深度和柜子深度一样，所以礼物盒和柜子深度方向也必须一致。并且礼物盒的高度还不能大于柜子的高度，否者放不进去。小y 希望放到柜子上礼物盒的宽度和正好等于柜子的宽度，也就是希望柜子两边都不存在间隙。如下图符合条件的放置。 满足条件的情况下，小y 希望能尽可能多的放置礼物盒，算出最多能放多少个礼物盒。
解析： 高度超过20厘米的我已经删除，只留下高度不超过20厘米的盒子的宽度： 11,8,11,16,1,2,6,10,17,10,6,5,2,19,4,7,5,5,15,3,15,11,9,17,9,4,10,12,17,19,20,11,10,20,3
#include<iostream> #include <stdio.h> #include<algorithm> #include<string.h> using namespace std; const int size=20; int widths[] = {11,8,11,16,1,2,6,10,17,10,6,5,2,19,4,7, 5,5,15,3,15,11,9,17,9,4,10,12,17,19,20,11,10,20,3}; int a[size]; void dfs(int n,int sum,int step){ if(sum>100)return; if(sum==100){ int ans=0; for(int i=0;i<20;i++){ if(a[i]>0)ans++; } cout<<ans<<endl; exit(0); } for(int i=n;i<35;i++){ a[step]=widths[n]; dfs(i+1,sum+widths[n],step+1); a[step] = 0; } } int main() { sort(widths,widths+35); dfs(0,0,0); return 0; }答案：18
第八题 数学老师小y 想写一个成绩查询系统，包含如下指令： 1.insert [name] [score]，向系统中插入一条信息，表示名字为name的学生的数学成绩为score。 2.find [name]，表示查找名字为name的学生的数学成绩。 注意有些同学可能会为了刷分多次选课，查询的时候给出最大成绩即可。学生的名字是由小写字母组成。成绩是一个 0 \ldots 1000…100 的整数。 老师找到你，想你帮他完成这个系统。 输入格式 输入若干行，每行都是insert [name] [score]或者find [name]的形式，或一行end表示输入结束。输入行数不大于 1000，每个学生名字长度不大于 20 个字符。 输出格式 对于每个查询，输出查询的学生的最高成绩，如果系统中不存在该学生，输出 -1。
解析： 利用map映射
#include<iostream> #include<map> 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 it; it=a.find(name); if(it==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 it; it=a.find(name); if(it==a.end())cout<<"-1"<<endl; else{ cout<<it->second<<endl; } } } return 0; }第九题 在一个 n×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。 现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。 输入格式 第一行输两个整数 n, m，用空格隔开。 接下来 n 行，每行输入一个长度为 m 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。 数据约定： 对于60% 的数据： 1≤n,m≤100； 对于 100% 的数据： 1≤n,m≤1000； 数据量比较大，不建议用cin输入。 输出格式 输出一个整数，表示最少需要手动引爆的炸弹数。
解析： 采用并查集方法
#include<iostream> #include<sstream> using namespace std; int father[50002],a[100][100]; int find(int x) { if(father[x]!=x) father[x]=find(father[x]); return father[x]; } int main() { int n,m; cin>>n>>m; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin>>a[i][j]; father[i*10+j]=i*10+j; } } for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(a[i][j]==1) { for(int k=0; k<n; k++) { if(a[i][k]==1) { int g=i*10+j; int h=i*10+k; g=find(g); h=find(h); father[g]=h; } if(a[k][j]==1) { int v=i*10+j; int c=k*10+j; v=find(v); c=find(c); father[v]=c; } } } } } int ans[10],t=0; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(a[i][j]==1) { ans[t++]=find(i*10+j); //cout<<father[i*10+j]<<" "; } } //cout<<endl; } //cout<<t<<endl; for(int i=0; i<t; i++) cout<<ans[i]<<" "; cout<<endl; for(int i=0; i<t-1; i++) { int num=ans[i]; for(int j=i+1; j<t; j++) { if(num==ans[j]) { ans[j]=-1; } } } int len=0; for(int i=0; i<t; i++) { if(ans[i]!=-1) { len++; } } cout<<len<<endl; return 0; }第十题 在一张 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。 输出格式 输出最少需要放置的守卫数量。 遗憾：不会
