第一题
标题： 购物单 小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。 这不，XX大促销又来了！老板夫人开出了长长的购物单，都是有打折优惠的。 小明也有个怪癖，不到万不得已，从不刷卡，直接现金搞定。 现在小明很心烦，请你帮他计算一下，需要从取款机上取多少现金，才能搞定这次购物。 取款机只能提供100元面额的纸币。小明想尽可能少取些现金，够用就行了。 你的任务是计算出，小明最少需要取多少现金。 以下是让人头疼的购物单，为了保护隐私，物品名称被隐藏了。 -------------------- **** 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，不要填写任何多余的内容。
题解：
要学会用处理没有用的数据，比如那个 **** 直接可以用记事本给替换成空格，还有后面那些xx折，可以直接用替换功能，替换了，不要傻傻的用手改。
#include <iostream> #include <fstream> #include <cstdio> #include <cstdlib> #include <cmath> using namespace std; int main() { ifstream in("test01.txt"); double value, discount; int ans = 0; double tmp = 0; while (in >> value >> discount) { tmp += value * discount; if (ans < tmp) { while (ans < tmp) { ans += 100; } } } cout << ans << endl; return 0; }
第二题
标题：等差素数列 2,3,5,7,11,13,....是素数序列。 类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。 上边的数列公差为30，长度为6。 2004年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。 这是数论领域一项惊人的成果！ 有这一理论为基础，请你借助手中的计算机，满怀信心地搜索： 长度为10的等差素数列，其公差最小值是多少？ 注意：需要提交的是一个整数，不要填写任何多余的内容和说明文字。
题解：
先用埃氏筛法，把1~N (N先设置一个10000吧，不够再加)以内的素数都筛选出来，然后再枚举 1~10000(公差，不够再加)，寻找连续10个的素数。
#include <iostream> using namespace std; const int maxn = 10000000; int prime[maxn]; bool is_prime[maxn + 10]; //is_prime[i]为true表示i是素数 bool is_Prime(int n) { int i = 0; for (i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return n != 1; } //返回n以内的素数 int sieve(int n) { int p = 0; //初始化 for (int i = 0; i <= n; i++) { is_prime[i] = true; } is_prime[0] = is_prime[1] = false; for (int i = 0; i <= n; i++) { if (is_prime[i]) { prime[p++] = i; //将素数添加到prime中 //1.首先2是素数, 然后划去所有2的倍数 //2.表中剩余的最小数字是3, 他不能被更小的数整除,所以是素数 //再将表中所有3的倍数都划去 //3.以此类推, 如果表中剩余的最小数字是m时,m就是素数。然后将表中所有m的倍数都划去 for (int j = 2 * i; j <= n; j += i) { is_prime[j] = false; } } } return p; } void solve() { int N = 10000; int cnt = sieve(N); //公差 for (int d = 10; d < N; d++) { //枚举N以内所有素数 for (int i = 0; i < cnt; i++) { int tmp = prime[i], flag = true; //是否连续10个都为素数 for (int j = 0; j < 9; j++) { if (tmp + d > N || !is_Prime(tmp + d)) { flag = false; break; } else { tmp += d; //下一个素数 } } if (flag) { cout << d << " " << prime[i] << endl; return; } } } } int main() { solve(); return 0; }
第三题
标题：承压计算 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 请你推算出：读数最大的电子秤的示数为多少？
题解：
看起来好像很难！！但是要细心看题目呀！其实就是 把 a[i - 1][j] 的数平均分给 a[i][j - 1] 和 a[i][j]，然后一直循环到30行这样，然后循环看一下最大位置和最小数的位置，为啥要看位置呢，注意题目是说，计量单位小，所以显示大，所以还得换一下单位： a[29][max] * (2086458231 / a[29][min] )，直接输出double会有科学计数，所以用printf("%1f", xxx) 输出double型数据。
#include <iostream> #include <fstream> #include <cstring> #include <cstdlib> #include <cstdio> using namespace std; const int maxn = 30 + 10; double num[maxn][maxn]; void solve() { ifstream in("test03.txt"); for (int i = 0; i < 29; i++) { for (int j = 0; j <= i; j++) { in >> num[i][j]; } } //最大和最小的位置 int Max = 0, Min = 0; for (int i = 1; i <= 29; i++) { for (int j = 0; j < i; j++) { num[i][j] += num[i - 1][j] / 2.0; num[i][j + 1] += num[i - 1][j] / 2.0; } } for (int i = 0; i < 30; i++) { if (num[29][i] > num[29][Max]) Max = i; if (num[29][i] < num[29][Min]) Min = i; } cout << num[29][Min] << endl; printf("%1f ", num[29][Max] * (2086458231) / num[29][Min]); } int main() { solve(); return 0; }
第四题
标题：方格分割
6x6的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
如图：p1.png, p2.png, p3.png 就是可行的分割法。
试计算：
包括这3种分法在内，一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。
请提交该整数，不要填写任何多余的内容或说明文字。
题解：
可以转换为，这是一个 6 x 6的矩阵，将[3, 3]位置看成起点，分相反的两条路径开始搜索（标志），当搜索到 边界时就是停止遍历 (r == 0 || c == 0 || r == 6 || c == 6) ，即是一种方案。这显然是经典的回溯问题，但是要注意这要对两条相反的路径进行标志。最后方案数/4, 因为旋转对称属于一种方案（4个方向嘛）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int maxn = 6 + 2;
bool used[maxn][maxn];
int ans;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
void dfs(int r, int c)
{
if (r == 0 || c == 0 || r == 6 || c == 6) {
ans++;
return;
}
for (int i = 0; i < 4; i++)
{
int rx = r + dir[i][0], ry = c + dir[i][1];
if (!used[rx][ry])
{
used[rx][ry] = true;
used[6 - rx][6 - ry] = true;
dfs(rx, ry);
used[rx][ry] = false;
used[6 - rx][6 - ry] = false;
}
}
}
void solve()
{
memset(used, 0, sizeof(used));
used[3][3] = true;
dfs(3, 3);
cout << ans / 4 << endl;
}
int main()
{
solve();
return 0;
}
第七题
标题：日期问题 小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。 比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。 给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？ 输入 ---- 一个日期，格式是"AA/BB/CC"。 (0 <= A, B, C <= 9) 输出 ---- 输出若干个不相同的日期，每个日期一行，格式是"yyyy-MM-dd"。多个日期按从早到晚排列。 样例输入 ---- 02/03/04 样例输出 ---- 2002-03-04 2004-02-03 2004-03-02 资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms
题解：
1. 设置一个日期类（感觉日期问题这样写不错），编写判断日期格式函数，自定义排序
2. 输入可以用 scanf("%d/%d/%d") 直接输入整型数
3. insert(年, 月, 日) , insert(日，月，年), insert(日，年，月）, 可以插入到set中，自动进行删选重复和进行排序
#include <iostream>
#include <cstring>
#include <iterator>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <vector>
#include <iterator>
using namespace std;
int mon_day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
struct Date {
int year,
month,
day;
Date(int y = 0, int m = 0, int d = 0) : year(y), month(m), day(d) {
}
bool isLeap(int year)
{
return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
bool vaild()
{
if (year < 1960 || year > 2059) return false;
if (isLeap(year))
{
if (month <= 0 || month > 12) return false;
if (month == 2) return day <= mon_day[month] + 1;
return day >= 1 && day <= mon_day[month];
}
else
{
if (month <= 0 || month > 12) return false;
return day >= 1 && day <= mon_day[month];
}
}
bool operator < (const Date b) const
{
if (year == b.year)
{
if (month == b.month)
{
return day < b.day;
}
return month < b.month;
}
return year < b.year;
}
void printDate() const
{
printf("%d-%02d-%02d
", year, month, day);
}
};
set<Date> ss;
void Insert(int y, int m, int d)
{
Date dd(y, m, d);
if (dd.vaild())
{
ss.insert(dd);
}
}
void solve()
{
int y, m, d;
scanf("%d/%d/%d", &y, &m, &d);
//年月日
Insert(1900 + y, m, d);
Insert(2000 + y, m, d);
//月日年
Insert(1900 + d, y, m);
Insert(2000 + d, y, m);
//日月年
Insert(1900 + d, m, y);
Insert(2000 + d, m, y);
set<Date>::iterator it = ss.begin();
for ( ; it != ss.end(); ++it)
{
it->printDate();
}
}
int main()
{
solve();
return 0;
}
第八题
标题：包子凑数
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有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
题解：
拓展欧几里德：
1. 求整数 x和y 使得 ax + by = 1.
2. 可以发现, 如果gcd(a, b) ≠ 1，则显然无解.
3. 反之, 如果gcd(a, b) = 1, 则可以通过拓展原来的 辗转相除法 来求解.
4. 事实上,一定存在整数对(x, y)使得ax+by = gcd(a,b) = 1
如果所有 蒸笼里的包子数的最大公约数，不为1，则说明有无数种数目凑不出来。如果最大公约数为1，则说明有限个数目凑不出来。
然后打表...看注释
#include <iostream>
using namespace std;
int N;
const int maxn = 150 + 20;
const int max_N = 100*100 + 20;
int Bao[maxn];
bool dp[max_N];
int gcd(int a, int b)
{
if (b == 0) return a;
return gcd(b, a % b);
}
void solve()
{
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> Bao[i];
}
int g = Bao[0];
//求所有数的最大公约数
for (int i = 1; i < N; i++)
{
g = gcd(g, Bao[i]);
}
//如果不为1，则有无穷个
if (g != 1) {
printf("INF
");
}
else
{
dp[0] = true;
for (int i = 0; i < N; i++)
{
//max_N: 最多那么多包子 100*100
//将加上该笼的所有可能的都枚举下来！(每种蒸笼都是无限笼)
for (int j = 0; j + Bao[i] < max_N; j++)
{
if (dp[j]) {
dp[j + Bao[i]] = true;
}
}
}
//凑不出的方案数
int ans = 0;
for (int i = max_N - 1; i >= 0; i--)
{
if (dp[i] == false) ans++;
}
printf("%d
", ans);
}
}
int main()
{
solve();
return 0;
}
第九题
标题： 分巧克力 儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。 为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足： 1. 形状是正方形，边长是整数 2. 大小相同 例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。 当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？ 输入 第一行包含两个整数N和K。(1 <= N, K <= 100000) 以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000) 输入保证每位小朋友至少能获得一块1x1的巧克力。 输出 输出切出的正方形巧克力最大可能的边长。 样例输入： 2 10 6 5 5 6 样例输出： 2 资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms
题解：
1. 经典的利用二分求解最大最小值问题，主要就是判断条件C的编写。模板题。
2. 还有就是二分搜索法的结束判定，推荐用直接循环100次，100次循环可以达到10^-30的精度范围，足够了。不推荐用while (lh < rh) 感觉容易死循环
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 100;
int N, K;
struct Food {
int Hi,
Wi;
Food(int h = 0, int w = 0) : Hi(h), Wi(w) {}
} fds[maxn];
//可以切出来 K 个 边长为x 的正方形
bool C(int x)
{
int ans = 0;
for (int i = 0; i < N; i++)
{
ans += (fds[i].Hi / x) * (fds[i].Wi / x);
if (ans >= K) return true;
}
return ans >= K;
}
void solve()
{
cin >> N >> K;
int INF = 0;
for (int i = 0; i < N; i++)
{
scanf("%d%d", &fds[i].Hi, &fds[i].Wi);
INF = max(INF, max(fds[i].Hi, fds[i].Wi));
}
int lh = 0, rh = INF + 1;
int mid = 0;
for (int i = 0; i < 100; i++)
{
mid = (lh + rh) / 2;
if (C(mid)) {
lh = mid;
}
else {
rh = mid;
}
}
cout << lh << endl;
}
int main()
{
solve();
return 0;
}