蓝桥杯 2013 C++ A 题解 只记录部分题，2013所有题的网盘链接 T4 标题: 颠倒的价牌 T8 买不到的数 T9 标题：剪格子 T10 标题：大臣的旅费
链接：https://pan.baidu.com/s/1C4pZkgw5XTeMEvn6okas5g
提取码：qe26
T4 标题: 颠倒的价牌
小李的店里专卖其它店中下架的样品电视机，可称为：样品电视专卖店。
其标价都是4位数字（即千元不等）。
小李为了标价清晰、方便，使用了预制的类似数码管的标价签，只要用颜色笔涂数字就可以了（参见p1.jpg）。
这种价牌有个特点，对一些数字，倒过来看也是合理的数字。如：1 2 5 6 8 9 0 都可以。这样一来，如果牌子挂倒了，有可能完全变成了另一个价格，
比如：1958 倒着挂就是：8561，差了几千元啊!!
当然，多数情况不能倒读，比如，1110 就不能倒过来，因为0不能作为开始数字。
有一天，悲剧终于发生了。某个店员不小心把店里的某两个价格牌给挂倒了。并且这两个价格牌的电视机都卖出去了!
庆幸的是价格出入不大，其中一个价牌赔了2百多，另一个价牌却赚了8百多，综合起来，反而多赚了558元。
请根据这些信息计算：赔钱的那个价牌正确的价格应该是多少？
答案是一个4位的整数，请通过浏览器直接提交该数字。
注意：不要提交解答过程，或其它辅助说明类的内容。
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
void i2s(int num, string &str) {
stringstream ss;
ss << num;
ss >> str;
}
void s2i(string &str, int &num) {
stringstream ss;
ss << str;
ss >> num;
}
char to(char x) {
if (x == '6')return '9';
else if (x == '9')return '6';
else return x;
}
string reverse(const string &str) {
string ans;
for (int i = 3; i >= 0; --i) {
ans.insert(ans.end(), to(str[i]));
}
return ans;
}
struct price {
int a, b, c;//原始价格，错误价格，差
};
vector<price> v1;//存储-200多的
vector<price> v2;//存储+800多的
int main(int argc, const char *argv[]) {
// cout<<reverse("1958")<<endl;
// 枚举所有四位数中可以颠倒的
//将其颠倒过来，与原来的数值做差，将-200多和+800的记录下来，分别记录在两个集合中
//遍历两个集合将-+两两求和，结果为558的即为正确答案
for (int i = 1000; i < 10000; ++i) {
string str;
i2s(i, str);
if (str.find('3') != string::npos || str.find('4') != string::npos || str.find('7') != string::npos ||
str.rfind('0') == 3)
continue;
string r = reverse(str);
int r_int;
s2i(r, r_int);//r_int就是翻转后的价格，i是原始价格
int plus = r_int - i;
if (plus > -300 && plus < -200) {
price p = {i, r_int, plus};
v1.push_back(p);
} else if (plus > 800 && plus < 900) {
price p = {i, r_int, plus};
v2.push_back(p);
}
// 此时，v1存储了-200多的，v2存储了+800多的
for (int i = 0; i < v1.size(); ++i) {
for (int j = 0; j < v2.size(); ++j) {
if (v1[i].c + v2[j].c == 558) {
printf("%d %d %d %d %d %d
", v1[i].a, v1[i].b, v1[i].c, v2[j].a, v2[j].b, v2[j].c);
}
}
}
}
return 0;
}
T8 买不到的数
标题：买不到的数目
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入：
两个正整数，表示每种包装中糖的颗数(都不多于1000)
要求输出：
一个正整数，表示最大不能买到的糖数
不需要考虑无解的情况
例如：
用户输入：
4 7
程序应该输出：
17
再例如：
用户输入：
3 5
程序应该输出：
7
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 3000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
//ax+by=C,不定方程的解 a=4,b=7,C=17 这种情况下，xy实际上有解，7*2+（7-4）==3*7 -1*4
//a,b互质，一定有解且解的数目无穷 *******************************************************
//C是gcd(a,b)的倍数，方程一定有解，而且有无穷多解
//条件：一定有解=》a,b互质
//条件2：xy都是大于等于0的整数，在这个限定条件下有的C是无解的，那么C的上界是多少呢？至多是a*b
#include <iostream>
#include <set>
using namespace std;
int main(int argc, const char *argv[]) {
int a, b;
scanf("%d %d", &a, &b);
set<int> ss;
// 枚举a*x+b*y的值，上边界是a*b
for (int x = 0; a * x <= a * b; ++x) {
for (int y = 0; a * x + b * y <= a * b; ++y) {
ss.insert(ss.end(), a * x + b * y);
}
}
for (int i = a * b; i >= 0; --i) {
if (ss.find(i) == ss.end())//i不在set中，那么i就是答案
{
printf("%d
", i);
break;
}
}
return 0;
}
T9 标题：剪格子
如图p1.jpg所示，3 x 3 的格子中填写了一些整数。
我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是60。
本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0
程序输入输出格式要求：
程序先读入两个整数 m n 用空格分割 (m,n<10)
表示表格的宽度和高度
接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000
程序输出：在所有解中，包含左上角的分割区可能包含的最小的格子数目。
例如：
用户输入：
3 3
10 1 52
20 30 1
1 2 3
则程序输出：
3
再例如：
用户输入：
4 3
1 1 1 1
1 30 80 2
1 1 1 100
则程序输出：
10
(参见p2.jpg)
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 5000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
#include<stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#define mk(i,j) make_pair(i,j)
using namespace std;
int m, n;
int total;
int g[10][10];
int ans;
/*抽象了一种剪辑方法*/
class Cut {
public:
set<pair<int, int> > grids;//包含若干格子
int sum;//所有格子的数值的求和
};
/**
* 将st中的元素拷贝到新set中
* @param st
* @return
*/
set<pair<int, int> > copySet(set<pair<int, int> > &st) {
set<pair<int, int> >::iterator iter = st.begin();
set<pair<int, int> > ans;
while (iter != st.end()) {
// 重新mkpair，加入新set中
ans.insert(*iter);
iter++;
}
return ans;
}
void add(int sum, int i, int j, set<pair<int, int> > &grids, Cut *&cut_new) {
const pair<int, int> &pair_n = make_pair(i , j);
// 深度拷贝set
set<pair<int, int> > grids_copy=copySet(grids);
grids_copy.insert(pair_n);
cut_new->grids=grids_copy;
cut_new->sum=sum+g[i][j];
}
vector<Cut *> vs[100];//分别存储格子数为1~100的各种剪法
int main(int argc, const char *argv[]) {
scanf("%d %d", &m, &n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &g[i][j]);
total += g[i][j];
}
}
// 第一个格子就是一半
if (g[0][0] == total / 2) {
printf("%d
", 1);
return 0;
}
/*左上角格子,只有一种剪法，加入v[1]*/
Cut *c = new Cut();
const pair<int, int> p = make_pair(0, 0);
c->grids.insert(p);
c->sum = g[0][0];
vs[1].push_back(c);//只包含一个格子且包含00的只有一种剪法
for (int i = 2; i <= m * n; ++i) {
// i是格子数，用vs[i-1]里面的来生成
//迭代vs[i-1]里面的所有剪法
for (int j = 0; j < vs[i - 1].size(); ++j) {
// pCut代表一种剪辑方法
Cut *pCut = vs[i - 1][j];
// 这种剪辑方法里面记录了所有格子，这些格子每个都扩展一个，即形成个数+1的剪法
set<pair<int, int> > &grids = pCut->grids;
int sum = pCut->sum;
set<pair<int, int> >::iterator iter = grids.begin();
// 迭代所有的格子，尝试添加它的邻居
while (iter != grids.end()) {
const pair<int, int> &p = *iter;//代表一个格子的坐标
int x=p.first;
int y=p.second;
if(x+1<n&&grids.find(mk(x+1,y))==grids.end()){//下方，能走通且下方格子不在当前集合中
Cut *cut_new=new Cut();//生成一个新的剪法
add(sum, x+1, y, grids, cut_new);//将原有的格子全部拷入，再增加当前试探的新的格子
if(cut_new->sum==total/2){
printf("%d
", i);
return 0;
}else if(cut_new->sum<total/2)
vs[i].push_back(cut_new);
}
if(x-1>=0&&grids.find(mk(x-1,y))==grids.end()){//上方
Cut *cut_new=new Cut();
add(sum, x-1, y, grids, cut_new);
if(cut_new->sum==total/2){
printf("%d
", i);
return 0;
}else if(cut_new->sum<total/2)
vs[i].push_back(cut_new);
}
if(y+1<m&&grids.find(mk(x,y+1))==grids.end()){//右方
Cut *cut_new=new Cut();
add(sum, x, y+1, grids, cut_new);
if(cut_new->sum==total/2){
printf("%d
", i);
return 0;
} else if(cut_new->sum<total/2)
vs[i].push_back(cut_new);
}
if(y-1>=0&&grids.find(mk(x,y-1))==grids.end()){//左方
Cut *cut_new=new Cut();
add(sum, x, y-1, grids, cut_new);
if(cut_new->sum==total/2){
printf("%d
", i);
return 0;
}else if(cut_new->sum<total/2)
vs[i].push_back(cut_new);
}
iter++;
}
}
}
printf("%d
", 0);
return 0;
}
T10 标题：大臣的旅费
很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者
通过其他大城市间接到达。
同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。
他有一个钱袋，用于存放往来城市间的路费。
聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，
在走第x千米到第x+1千米这一千米中（x是整数），
他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。
J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入格式：
输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数
城市从1开始依次编号，1号城市为首都。
接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）
每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。
输出格式:
输出一个整数，表示大臣J最多花费的路费是多少。
样例输入:
5
1 2 2
1 3 1
2 4 5
2 5 4
样例输出:
135
样例说明:
大臣J从城市4到城市5要花费135的路费。
根据资源限制尽可能考虑支持更大的数据规模。
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 5000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
//本题求树的直径
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
class Point {
public:
int num, cost;//点的编号，和到这个点的距离
};
int ans;
void f(vector<Point> m[], int vis[], int i, int j, int dis) {
//查看是否直接邻居
vector<Point> nei_i = m[i];//i的邻居的集合
for (int k = 0; k < nei_i.size(); k++) {
if (nei_i[k].num == j)//i的直接邻居中有j
{
ans = max(ans, dis + nei_i[k].cost);
return;
}
}
vis[i] = 0;
// 不是直接邻居，就从现有的直接邻居去连接
for (int k = 0; k < nei_i.size(); k++) {
int num = nei_i[k].num;
if (vis[num] == -1)
f(m, vis, num, j, dis + nei_i[k].cost);
}
vis[i] = -1;
}
int pnt=-1;
void dfs(vector<Point> m[], int vis[], int start,int dis) {
vector<Point> nei_i = m[start];//i的邻居的集合
vis[start]=0;
bool isLeaf=true;
for (int k = 0; k < nei_i.size(); k++) {
int num = nei_i[k].num;//邻居点的标号
if (vis[num] == -1){
isLeaf= false;
dfs(m, vis, num,dis + nei_i[k].cost);
}
}
vis[start]=-1;
if(isLeaf){
if(dis>ans){
ans=dis;
pnt=start;
}
}
}
int dis2money(int dis) {
return 11 * dis + dis * (dis - 1) / 2;
}
int main(int argc, const char *argv[]) {
scanf("%d", &n);
vector<Point> m[n + 1];
int vis[n + 1];
memset(vis, -1, sizeof(vis));//初始化为-1
for (int i = 0; i < n - 1; ++i) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
Point p1 = {b, c};
Point p2 = {a, c};
m[a].push_back(p1);
m[b].push_back(p2);
}
/*1.暴力，求任意两点间距离，并维护最长距离*/
/*for (int i = 1; i <= n - 1; ++i) {
for (int j = i + 1; j <= n; ++j) {
// int ans_t = ans;
f(m, vis, i, j, 0);
// if (ans > ans_t) {
// cout << i << " " << j << " " << ans << endl;
// }
}
}*/
dfs(m,vis,1,0);
ans=0;
dfs(m,vis,pnt,0);
// printf("%d
", pnt);
printf("%d
", dis2money(ans));
// printf("%d
", ans);
return 0;
}