一、试题A：购物单
二、试题B：等差素数列
三、试题C：承压计算
四、试题D：方格分割
五、试题E：取数位
六、试题F：最大公共子串
七、试题G：日期问题
八、试题H：包子凑数
九、试题I：分巧克力
十、试题J：k倍区间
一、试题A：购物单
----------------- **** 180.90 88折 **** 10.25 65折 **** 56.14 9折 **** 104.65 9折 **** 100.30 88折 **** 297.15 半价 **** 26.75 65折 **** 130.62 半价 **** 240.28 58折 **** 270.62 8折 **** 115.87 88折 **** 247.34 95折 **** 73.21 9折 **** 101.00 半价 **** 79.54 半价 **** 278.44 7折 **** 199.26 半价 **** 12.97 9折 **** 166.30 78折 **** 125.50 58折 **** 84.98 9折 **** 113.35 68折 **** 166.57 半价 **** 42.56 9折 **** 81.90 95折 **** 131.78 8折 **** 255.89 78折 **** 109.17 9折 **** 146.69 68折 **** 139.33 65折 **** 141.16 78折 **** 154.74 8折 **** 59.42 8折 **** 85.44 68折 **** 293.70 88折 **** 261.79 65折 **** 11.30 88折 **** 268.27 58折 **** 128.29 88折 **** 251.03 8折 **** 208.39 75折 **** 128.88 75折 **** 62.06 9折 **** 225.87 75折 **** 12.89 75折 **** 34.28 75折 **** 62.16 58折 **** 129.12 半价 **** 218.37 半价 **** 289.69 8折 --------------------
需要说明的是，88折指的是按标价的88%计算，而8折是按80%计算，余者类推。
特别地，半价是按50%计算。
请提交小明要从取款机上提取的金额，单位是元。
答案是一个整数，类似4300的样子，结尾必然是00，不要填写任何多余的内容。
特别提醒：不许携带计算器入场，也不能打开手机。
解题思路：
- 先用记事本把****去掉，9折换成90之类的
- 用Excel或者程序来计算
代码如下：
#include<iostream>
using namespace std;
double a,b,c;
int main() {
for(int i = 1; i <= 50; i ++ ){
cin >> a >> b;
c += a * b / 100;
}
cout<<c;
return 0;
}二、试题B：等差素数列
解题思路：
模拟题
- 首先把素数列表求出来
- 枚举素数、公差
- 满足长度为10，取最小的公差
代码如下:
#include<iostream>
using namespace std;
#define inf 0x3f3f3f3f
const int N = 1e5 + 10;
bool is_prime[N];
int prime[N];
int cnt;
bool st[N];
int ans = inf,dist;
void get_primes(){
for(int i = 2; i <= N; i ++ ){
if(!st[i]){
is_prime[i] = true;
prime[cnt ++ ] = i;
for(int j = i + i; j <= N; j += i ){
st[j] = true;
}
}
}
}
int main() {
get_primes();
for(int i = 0; i < cnt; i ++ ){
int d;
for(d = 1; d <= 10005; d ++ ){
bool flag = false;
int len = 1;int sum = prime[i];
while(!flag){
if(is_prime[sum + d]){
len ++;sum += d;
if(len == 10) flag = true;
}else{
break;
}
}
if(flag) break;
}
ans = min(ans,d);
}
cout<<ans;
return 0;
}三、试题C：承压计算
X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。
每块金属原料的外形、尺寸完全一致，但重量不同。
金属材料被严格地堆放成金字塔形。
7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 其中的数字代表金属块的重量（计量单位较大）。
最下一层的X代表30台极高精度的电子秤。
假设每块原料的重量都十分精确地平均落在下方的两个金属块上，
最后，所有的金属块的重量都严格精确地平分落在最底层的电子秤上。
电子秤的计量单位很小，所以显示的数字很大。
工作人员发现，其中读数最小的电子秤的示数为：2086458231
请你推算出：读数最大的电子秤的示数为多少？
注意：需要提交的是一个整数，不要填写任何多余的内容。
题目解读：
- 所有的金属块的重量都严格精确地平分落在最底层的电子秤上
- 读数最小的电子秤的示数为：2086458231
坑点：我们算出来的是金属块的重量，而不是电子秤的示数，所以需要转换一下
代码如下:
#include<iostream>
using namespace std;
#define inf 0x3f3f3f3f
const int N = 40;
double a[N][N];
int main() {
for(int i = 1; i <= 29; i ++ ){
for(int j = 1; j <= i; j ++) {
cin >> a[i][j];
}
}
for(int i = 2; i <= 30; i ++ ){
for(int j = 1; j <= i; j ++ ){
a[i][j] += a[i-1][j-1]/2 + a[i-1][j]/2;
}
}
double minn = inf,maxx = -inf;
for(int i = 1; i <= 30; i ++){
minn = min(a[30][i],minn);
maxx = max(a[30][i],maxx);
}
printf("%lf\n",2086458231/minn*maxx);
return 0;
}四、试题D：方格分割
图一：
图二：
图三：
解题思路：
DFS
- 本题要求分割成两块完全相同
- 从中心开始对称分割
- 下面两种分法算一种，它自身旋转也算一种，所以答案要除以4
代码如下:
#include<iostream>
using namespace std;
#define inf 0x3f3f3f3f
const int N = 10;
int ans;
bool st[N][N];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
void dfs(int x,int y){
if(x == 0 || y == 0 || x == 6 || y == 6){
ans ++;
return ;
}
for(int i = 0; i < 4; i ++ ){
int a,b,c,d;
a = x + dx[i];
b = y + dy[i];
c = 6 - a; d = 6 - b;
if(a < 0 || a > 6 || b < 0 || b > 6 || c < 0 || c > 6 || d < 0 || d > 6) continue;
if(st[a][b]) continue;
st[a][b] = st[c][d] = true;
dfs(a,b);
st[a][b] = st[c][d] = false;
}
}
int main() {
st[3][3] = true;
dfs(3,3);
cout<<ans/4;
return 0;
}五、试题E：取数位
标题：取数位
求1个整数的第k位数字有很多种方法。
以下的方法就是一种。
// 求x用10进制表示时的数位长度
int len(int x){
if(x<10) return 1;
return len(x/10)+1;
}
// 取x的第k位数字
int f(int x, int k){
if(len(x)-k==0) return x%10;
return _____________________; //填空
}
int main()
{
int x = 23574;
printf("%d\n", f(x,3));
return 0;
}
对于题目中的测试数据，应该打印5。
请仔细分析源码，并补充划线部分所缺少的代码。
注意：只提交缺失的代码，不要填写任何已有内容或说明性的文字。水题：f(x/10,k)
六、试题F：最大公共子串（待补）
标题：最大公共子串
最大公共子串长度问题就是：
求两个串的所有子串中能够匹配上的最大长度是多少。
比如："abcdkkk" 和 "baabcdadabc"，
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。
请分析该解法的思路，并补全划线部分缺失的代码。
#include <stdio.h>
#include <string.h>
#define N 256
int f(const char* s1, const char* s2)
{
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;
memset(a,0,sizeof(int)*N*N);
int max = 0;
for(i=1; i<=len1; i++){
for(j=1; j<=len2; j++){
if(s1[i-1]==s2[j-1]) {
a[i][j] = __________________________; //填空
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
}
int main()
{
printf("%d\n", f("abcdkkk", "baabcdadabc"));
return 0;
}
注意：只提交缺少的代码，不要提交已有的代码和符号。也不要提交说明性文字。
七、试题G：日期问题（待补）
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。</xxx>
提交程序时，注意选择所期望的语言类型和编译器类型。
八、试题H：包子凑数
标题：包子凑数
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)
输出
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。
例如，
输入：
2 4 5
程序应该输出：
6
再例如，
输入：
2 4 6
程序应该输出：
INF
解题思路：
扩展欧几里得算法
- 若两数互质则两数不能组合的最大值为a * b - a - b。 根据题意 Ai<=100,所以开数组的大小要 > 100*99-100-99
- 如果满足所有数的最大公约数不为1则有无穷个，否则都是有限个
- 用一个数组标记所有能取到的情况
#include<iostream>
using namespace std;
const int N = 1e4 + 10;
#define inf 0x3f3f3f3f
int n,x,g;
bool st[N + 110];
int ans;
int gcd(int a,int b){
if(b == 0){
return a;
}
return gcd(b,a%b);
}
int main() {
cin >> n;
st[0] = true;
for(int i = 0; i < n; i ++ ){
cin >> x;
if(!i) g = x;
else g = gcd(g,x);
for(int j = 0; j< N; j ++){
if(st[j]) st[j + x] = true;
}
}
if(g != 1){
cout<<"INF\n";
}else{
for(int i = 0; i < N; i ++ ){
if(!st[i]) ans++;
}
cout<<ans;
}
return 0;
}九、试题I：分巧克力
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。</xxx>
提交程序时，注意选择所期望的语言类型和编译器类型。
解题思路：
- 每块巧克力有两条边（两个属性），用结构体存储N个巧克力
- 分解巧克力：长分解为ｎ个、宽分解为ｍ个，一共有ｎ＊ｍ个
方法一：暴力求解
- 因为题中说了:输入保证每位小朋友至少能获得一块1x1的巧克力。
- 枚举最大的边N到最小的边1,可以分就结束
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n,k;
int ans;
struct Node{
int x,y;
}node[N];
int main() {
scanf("%d %d",&n,&k);
for(int i = 0; i < n; i ++ ){
scanf("%d %d",&node[i].x,&node[i].y);
}
for(ans = N; ans >= 1; ans --){
int cnt = 0;
for(int i = 0; i < n; i ++ ){
cnt += (node[i].x/ans) * (node[i].y/ans);
}
if(cnt >= k){
cout<<ans;
break;
}
}
return 0;
}方法二:二分法
- 这是一道很明显的二分题
- 范围在(1,1e5)之间取最大的边
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n,k;
int ans;
struct Node{
int x,y;
}node[N];
bool check(int m){
int cnt = 0;
for(int i = 0; i < n; i ++ ){
cnt += (node[i].x / m) * (node[i].y / m);
}
if(cnt >= k) return true;
return false;
}
int main() {
scanf("%d %d",&n,&k);
for(int i = 0; i < n; i ++ ){
scanf("%d %d",&node[i].x,&node[i].y);
}
int l = 1, r = 1e5;
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;//偏右半边
else r = mid - 1;
}
cout << l;
return 0;
}
京公网安备 11010502036488号