2017第八届蓝桥杯国赛c/c++ B组
首先提下，题目可以在蓝桥杯官网中下载，提供一个传送门。
一：标题：36进制
对于16进制，我们使用字母A-F来表示10及以上的数字。
如法炮制，一直用到字母Z，就可以表示36进制。
36进制中，A表示10，Z表示35，AA表示370
你能算出 MANY 表示的数字用10进制表示是多少吗?
请提交一个整数，不要填写任何多余的内容（比如，说明文字）
最简单做法：
int("many", 36) // 1040254比较简答，答案是 1040254 别算错了就行了。
#include <iostream>
using namespace std;
int main()
{
int a = 'm' - 'a' + 10;
int b = 'a' - 'a' + 10;
int c = 'n' - 'a' + 10;
int d = 'y' - 'a' + 10;
int base = 36, basen = 1;
d *= basen; basen *= base;
c *= basen; basen *= base;
b *= basen; basen *= base;
a *= basen; basen *= base;
cout << (a+b+c+d) << endl;
return 0;
}
二：标题：磁砖样式
小明家的一面装饰墙原来是 3*10 的小方格。
现在手头有一批刚好能盖住2个小方格的长方形瓷砖。
瓷砖只有两种颜色：黄色和橙色。
小明想知道，对于这么简陋的原料，可以贴出多少种不同的花样来。
小明有个小小的强迫症：忍受不了任何2*2的小格子是同一种颜色。
（瓷砖不能切割，不能重叠，也不能只铺一部分。另外，只考虑组合图案，请忽略瓷砖的拼缝）
显然，对于 2*3 个小格子来说，口算都可以知道：一共10种贴法，如【p1.png所示】
注意：你需要提交的是一个整数，不要填写任何多余的内容（比如：说明性文字）
应该标准做法是状压dp，但是我不会写，就只能用dfs搜一下小数据了。
我的做法是：
1、每次从左到右从上到下找到第一个没有没涂色的位置。
2、判断这个位置的右边是不是空白，如果是尝试给这两个位置上一种颜色（1或2），判断是否会产生冲突，如果没有冲突则继续深搜，否则就放弃。
3、判断这个位置的下边是不是空白，做的事情同2。
我用1和2来表示两种颜色，判断是否有冲突就是把涂色了的点周围会形成的4个（左上，左下，右上，右下）2*2矩阵是不是相同数字，如果是则表明这种方法是不可行的。
我搜出来的答案是：105760 应该是对的（说给自己听的，读者请忽略）。
（代码中用到了goto，我表示很抱歉 ：）
#include <iostream>
using namespace std;
#define MAXW 3
#define MAXH 10
#define MAXC ((MAXW*MAXH)/2)
int a[MAXW][MAXH];
bool valid( int x, int y ) {
return x>=0&&x<MAXW&&y>=0&&y<MAXH;
}
bool ts( int x, int y ) {
if ( a[x][y-1]==a[x][y] && a[x-1][y-1]==a[x-1][y] && a[x-1][y-1]==a[x][y] ) return true;
return false;
}
bool xt( int x, int y ) {
if ( valid(x-1, y-1) && ts(x, y) ) {
return true;
}
if ( valid(x-1, y+1) && ts(x, y+1) ) {
return true;
}
if ( valid(x+1, y-1) && ts(x+1, y) ) {
return true;
}
if ( valid(x+1, y+1) && ts(x+1, y+1) ) {
return true;
}
return false;
}
int ans = 0;
void dfs(int cnt) {
// 如果放够15个 说明是一种答案
if ( cnt == MAXC ) {
ans ++;
} else {
// 找到第一个空白位置 开始尝试横着放 1 2 或者竖着放 1 2
// 递归之前 先判断是否同色
int i = 0, j = 0;
for ( i = 0 ; i < MAXW ; ++ i ) {
for ( j = 0 ; j < MAXH ; ++ j ) {
if ( a[i][j] == 0 ) goto next;
}
}
next:
if ( valid(i, j+1) && !a[i][j+1] ) {
a[i][j] = a[i][j+1] = 1;
if ( !xt(i,j) && !xt(i,j+1) ) dfs(cnt+1);
a[i][j] = a[i][j+1] = 0;
}
if ( valid(i+1, j) && !a[i+1][j] ) {
a[i][j] = a[i+1][j] = 1;
if ( !xt(i,j) && !xt(i+1,j) ) dfs(cnt+1);
a[i][j] = a[i+1][j] = 0;
}
if ( valid(i, j+1) && !a[i][j+1] ) {
a[i][j] = a[i][j+1] = 2;
if ( !xt(i,j) && !xt(i,j+1) ) dfs(cnt+1);
a[i][j] = a[i][j+1] = 0;
}
if ( valid(i+1, j) && !a[i+1][j] ) {
a[i][j] = a[i+1][j] = 2;
if ( !xt(i,j) && !xt(i+1,j) ) dfs(cnt+1);
a[i][j] = a[i+1][j] = 0;
}
}
}
int main()
{
dfs( 0 );
cout << ans << endl; // 105760
return 0;
}
三：标题：希尔伯特曲线
希尔伯特曲线是以下一系列分形曲线 Hn 的极限。我们可以把 Hn 看作一条覆盖 2^n × 2^n 方格矩阵的曲线，曲线上一共有 2^n × 2^n 个顶点(包括左下角起点和右下角终点)，恰好覆盖每个方格一次。
[p1.png]
Hn(n > 1)可以通过如下方法构造：
1. 将 Hn-1 顺时针旋转90度放在左下角
2. 将 Hn-1 逆时针旋转90度放在右下角
3. 将2个 Hn-1 分别放在左上角和右上角
4. 用3条单位线段把4部分连接起来
对于 Hn 上每一个顶点 p ，我们定义 p 的坐标是它覆盖的小方格在矩阵中的坐标(左下角是(1, 1)，右上角是(2^n, 2^n)，从左到右是X轴正方向，从下到上是Y轴正方向)，
定义 p 的序号是它在曲线上从起点开始数第几个顶点(从1开始计数)。
以下程序对于给定的n(n <= 30)和p点坐标(x, y)，输出p点的序号。请仔细阅读分析源码，填写划线部分缺失的内容。
#include <stdio.h>
long long f(int n, int x, int y) {
if (n == 0) return 1;
int m = 1 << (n - 1);
if (x <= m && y <= m) {
return f(n - 1, y, x);
}
if (x > m && y <= m) {
return 3LL * m * m + f(n - 1, ________________ , m * 2 - x + 1); // 填空
}
if (x <= m && y > m) {
return 1LL * m * m + f(n - 1, x, y - m);
}
if (x > m && y > m) {
return 2LL * m * m + f(n - 1, x - m, y - m);
}
}
int main() {
int n, x, y;
scanf("%d %d %d", &n, &x, &y);
printf("%lld", f(n, x, y));
return 0;
}
注意：只填写划线处缺少的内容，不要填写已有的代码或符号，也不要填写任何解释说明文字等。
答案是：m-y+1。
仔细分析过后，需要能猜出，那个m其实确定了x，y所在的象限。
考虑到：
if (x <= m && y <= m) {
return f(n - 1, y, x);
}需要能猜到这估计是第一分区（一下叙述中，均把左下区域描述为第一分区，左上为第二分区，右上为第三分区，右下为第四分区，不再赘述）的情况，因为main函数中是直接以x y递归的，这里形式没有变，说明和最开始情况是相同的，
这样就可以猜到要填的空是第四分区的情况了，然后填空位置前面有个 3*m*m，这个是什么呢？
其实也很容易想到，这应该是前三个分区的点的数目和，再加上要找的点在第四分区的第几个就是答案了。
那么第四分区递归时对应的是哪个值呢？
仔细看看题目，
Hn(n > 1)可以通过如下方法构造：
1. 将 Hn-1 顺时针旋转90度放在左下角
2. 将 Hn-1 逆时针旋转90度放在右下角
3. 将2个 Hn-1 分别放在左上角和右上角
4. 用3条单位线段把4部分连接起来
再看看图形，就可以得出，1这一条指的就是第二分区顺时针旋转后放在第一分区。
2.这一条指的就是第三分区逆时针旋转后放在第四分区。
3.就是左上和右上的第三分区和第四分区了。
4.只是起连接作用。
理解这些之后，就可以得出第一分区和第四分区不是镜像对称，而是旋转180度。
然后象限盒子的大小是m。
因为是递推，其实就是把后一个图形递推到前一个图形，所以我们要做的事情就是对例图中，图三的四个分区递推到图二上面。
首先看图三的第一个分区，其实就是逆时针旋转90度就到图二了，这两个图形是关于y=x对称的，所以递归的参数就是（y，x）
再看图三的第二个分区，就是向下挪了m个单位，所以递归参数是（x，y-m）
再看图三的第三个分区，就是向左下挪了m个单位，所以递归参数是（x-m，y-m）
再看图三的第四个分区，也就是我们要求递推公式的分区了。
首先旋转到对应图形形状也是顺时针旋转90度，为了使图像关于y=-x对称，我们需要先把图像忘左平移2m个单位，
也就是到（x-2m-1，y）处（注：减一是因为从1计数而不是0）。对称之后是（-y，2m-x+1），但这个位置也不是最终位置，而是和y轴对称的位置，所以需要再往右平移m个单位，也就是（m-y+1，2m-x+1）这个位置（注：加一是因为从1计数而不是从0）。所以就得到了最终答案（m-y+1，2m-x+1）;
简单画了个图描述这个过程，没有绘制对称翻转，因为两个会重叠，不会做gif图，不然看着跟清楚些。
基本过程是最右边那个图平移到最左边，然后对称翻转下，然后在平移到第一分区。
不太容易想明白的是对称翻转的操作和那个加1的操作。大家可以带入两个点体验下。
当然写这么多大多是为了以后我看着方便，数学好，几何思维好的同学很容易想明白这个过程。
四：标题：发现环
小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。
为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？
输入
-----
第一行包含一个整数N。
以下N行每行两个整数a和b，表示a和b之间有一条数据链接相连。
对于30%的数据，1 <= N <= 1000
对于100%的数据, 1 <= N <= 100000， 1 <= a, b <= N
输入保证合法。
输出
----
按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。
样例输入：
5
1 2
3 1
2 4
2 5
5 3
样例输出：
1 2 3 5
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
题目的解法应该是拓扑排序，将度为1的点依次删除，最后剩下的就是环上的点了。
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n, x, y, lim;
int a[100010];
vector<int> vec[100010];
queue<int> que;
void findin() {
int cnt = que.front();
que.pop();
a[cnt] = 0;
for ( int i=0, len=vec[cnt].size() ; i < len ; ++ i ) {
if ( a[vec[cnt][i]] ) a[vec[cnt][i]] -= 1;
if ( a[vec[cnt][i]] == 1 ) que.push(vec[cnt][i]);
}
}
int main()
{
scanf( "%d", &n );
for ( int i = 0 ; i < n ; ++ i ) {
scanf( "%d%d", &x, &y );
vec[x].push_back(y);
vec[y].push_back(x);
a[y] ++; a[x] ++;
}
for ( int i = 1 ; i <= n ; ++ i ) {
if ( a[i] == 1 ) que.push(i);
}
// 保存无向图 所以不存在入度为0的点
// 这里找所有度为1 的点 然后对这些点找拓扑排序
// 最后剩下的度不为0的点 都是在环上的点
while ( !que.empty() ) {
findin();
}
lim = n;
while ( a[lim] == 0 ) lim--;
for ( int i = 1 ; i < lim ; ++ i ) {
if ( a[i] ) {
printf( "%d ", i );
}
}
printf( "%d\n", lim );
// putchar('_');
return 0;
}
五：标题：对局匹配
题目链接提交：http://lx.lanqiao.cn/problem.page?gpid=T454
小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。
小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是K的两名用户匹配在一起。如果两人分差小于或大于K，系统都不会将他们匹配。
现在小明知道这个网站总共有N名用户，以及他们的积分分别是A1, A2, ... AN。
小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于K)？
输入
----
第一行包含两个个整数N和K。
第二行包含N个整数A1, A2, ... AN。
对于30%的数据，1 <= N <= 10
对于100%的数据，1 <= N <= 100000, 0 <= Ai <= 100000, 0 <= K <= 100000
输出
----
一个整数，代表答案。
样例输入：
10 0
1 4 2 8 5 7 1 4 2 8
样例输出：
6
再比如，
样例输入：
10 1
2 1 1 1 1 4 4 3 4 4
样例输出：
8
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
这个题不知道标准做法是什么，这里提供两种做法，不保证对，只是提供个思路。
第一种做法：贪心。
设a[i]表示积分为i的人数，对每个 i 每次把积分为 i+k的消除掉。
if ( a[i+k] >= a[i] ) a[i+k]-=a[i];
else a[i+k] = 0;因为 i 和 i+k 是冲突的。而 i+k 和 i+2k 是冲突的，所以优先消除中间的 i+k。
注意，并没有证明这个贪心是正确的，所以这样的做法很可能是错误的，
如果大家有办法证明这个贪心是正确的或者错误的，请留言分享一下。
经蓝桥杯官网oj测试，贪心可以通过全部数据
#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 100010
int a[MAXN];
int main()
{
int n, k, x;
scanf( "%d%d", &n, &k );
for ( int i = 0 ; i < n ; ++ i ) {
scanf( "%d", &x );
a[x] ++;
}
int ans = 0;
if ( k == 0 ) {
for ( int i = 0 ; i < MAXN ; ++ i ) {
if ( a[i] ) ans ++;
}
printf( "%d\n", ans );
return 0;
}
for ( int i = 0 ; i < MAXN-k ; ++ i ) {
if ( a[i] < a[i+k] ) {
a[i+k] -= a[i];
} else {
a[i+k] = 0;
}
}
for ( int i = 0 ; i < MAXN-k ; ++ i ) {
ans += a[i];
}
printf( "%d\n", ans );
return 0;
} 第二种做法是动态规划，相对靠谱很多。
经蓝桥杯官网oj测试，可以通过。
把输入的数据模k之后，就可以得到k组数据，同一个组的膜k的余数都相等，
然后每个组中维护的数是 Ai/k，Ai为用户积分。
这样可以设 a[i][j] 为输入数据 Ai%k的结果为 i， Ai/k的结果为j，而a[i][j]为这样的数字有多少个。
很显然 a[i][j]和a[i][j-1]，a[i][j+1]是冲突的，因为他们之间只差了一个k。
那么动态规划方程就有了。
A[MAXN]; // A[i]: 用户积分
vec[MAXN]; // vec[i]: 用户积分模k值为i 的积分集合
n; // max(vec[i]/k) 每组中 /k 的最大值 为dp循环的上限
dp[MAXN][MAXN]; // dp[i][j]: A%k结果为i，A/k结果小于等于j时 最大的选取人数
// A为A[MAXN]中的值 显然最终答案为 sum(dp[i][max(vec[i]/k)])
a[MAXN]; // a[i]: vec[i]的每个值的个数
for ( i in range(0,n) ) {
dp[i][j] = max(dp[i][j-1], dp[i][j-2]+a[j]);
}下面给出完整代码：
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAXN 100010
struct ST{
int num, sum;
ST( int n, int s ) {
num = n;
sum = s;
}
};
int a[MAXN], b[MAXN];
vector<ST> vec[MAXN];
int dp[MAXN];
int main()
{
int n, k, t, ans = 0, mx = 0;
scanf( "%d%d", &n, &k );
for ( int i = 0 ; i < n ; ++ i ) {
scanf( "%d", &t );
b[t] ++;// b[i] 积分为i的个数
mx = max(mx, t);// 最大积分。
}
if ( k == 0 ) {// 如果k值为0 则看有多少种积分即可
for ( int i = 0 ; i <= mx ; ++ i ) {
if ( b[i] ) ans ++;
}
printf( "%d\n", ans );
return 0;
}
for ( int i = 0 ; i <= mx ; ++ i ) {
// 对积分进行模k分类
vec[i%k].push_back(ST(i,b[i]));
}
for ( int i = 0 ; i < k ; ++ i ) {
memset( a, 0, sizeof(a) );
memset( dp, 0, sizeof(dp) );
n = 0;
for ( int j=0, len=vec[i].size() ; j<len; ++ j ) {
ST& cnt = vec[i][j];
// 将模k结果相同的数字再分类 a[i]: 数字/k结果为i的个数
a[cnt.num/k] = cnt.sum;
}
// 保存一个最大值为上限
n = vec[i][vec[i].size()-1].num/k+1;
dp[0] = a[0];
dp[1] = max(a[0], a[1]);
for ( int j = 0 ; j <= n ; ++ j ) {
dp[j] = max( dp[j-1], dp[j-2]+a[j] );
}
ans += dp[n];
}
printf( "%d\n", ans );
return 0;
} 六：标题：观光铁路
跳蚤国正在大力发展旅游业，每个城市都被打造成了旅游景点。
许多跳蚤想去其他城市旅游，但是由于跳得比较慢，它们的愿望难以实现。这时，小C听说有一种叫做火车的交通工具，在铁路上跑得很快，便抓住了商机，创立了一家铁路公司，向跳蚤国王请示在每两个城市之间都修建铁路。
然而，由于小C不会扳道岔，火车到一个城市以后只能保证不原路返回，而会随机等概率地驶向与这个城市有铁路连接的另外一个城市。
跳蚤国王向广大居民征求意见，结果跳蚤们不太满意，因为这样修建铁路以后有可能只游览了3个城市（含出发的城市）以后就回来了，它们希望能多游览几个城市。于是跳蚤国王要求小C提供一个方案，使得每只跳蚤坐上火车后能多游览几个城市才回来。
小C提供了一种方案给跳蚤国王。跳蚤国王想知道这个方案中每个城市的居民旅游的期望时间（设火车经过每段铁路的时间都为1），请你来帮跳蚤国王。
【输入格式】
输入的第一行包含两个正整数n、m，其中n表示城市的数量，m表示方案中的铁路条数。
接下来m行，每行包含两个正整数u、v，表示方案中城市u和城市v之间有一条铁路。
保证方案中无重边无自环，每两个城市之间都能经过铁路直接或间接到达，且火车由任意一条铁路到任意一个城市以后一定有路可走。
【输出格式】
输出n行，第i行包含一个实数ti，表示方案中城市i的居民旅游的期望时间。你应当输出足够多的小数位数，以保证输出的值和真实值之间的绝对或相对误差不超过1e-9。
【样例输入】
4 5
1 2
2 3
3 4
4 1
1 3
【样例输出】
3.333333333333
5.000000000000
3.333333333333
5.000000000000
【样例输入】
10 15
1 2
1 9
1 5
2 3
2 7
3 4
3 10
4 5
4 8
5 6
6 7
6 10
7 8
8 9
9 10
【样例输出】
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
【数据规模与约定】
对于10%的测试点，n <= 10；
对于20%的测试点，n <= 12；
对于50%的测试点，n <= 16；
对于70%的测试点，n <= 19；
对于100%的测试点，4 <= k <= n <= 21，1 <= u, v <= n。数据有梯度。
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 2000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。