蓝桥杯2016年B组C++国赛题解
admin
|
|
441
|
杂项

1937 字
|
21 分钟

一步之遥

题目描述：

从昏迷中醒来，小明发现自己被关在 X 星球的废矿车里。 矿车停在平直的废弃的轨道上。 他的面前是两个按钮，分别写着 “F” 和 “B” 。

小明突然记起来，这两个按钮可以控制矿车在轨道上前进和后退。 按 F，会前进 97 米。按B 会后退127 米。 透过昏暗的灯光，小明看到自己前方 1 米远正好有个监控探头。 他必须设法使得矿车正好停在摄像头的下方，才有机会争取同伴的援助。 或许，通过多次操作 F 和 B 可以办到。

矿车上的动力已经不太足，黄色的警示灯在默默闪烁… 每次进行 F 或 B 操作都会消耗一定的能量。 小明飞快地计算，至少要多少次操作，才能把矿车准确地停在前方 1 米远的地方。

请问为了达成目标，最少需要操作的次数是多少。

思路：

其实就是问 97x – 127y = 1的解x + y为多少

利用扩展欧几里得来求解即可

不会扩展欧几里得的来看这里–>传送门

AC代码

#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 1000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int a, b, x, y, gcd;

void exgcd(int a, int b, int &gcd, int &x, int &y){
    if(b == 0){
        gcd = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, gcd, y, x);
    y -= x * (a / b);
}

int main(){
    a = 97;b = -127;
    exgcd(a, b, gcd, x, y);
    cout<<x + y<<endl;
    return 0;
}

凑平方数

题目描述：

把 0 ~ 9 这 10 个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。

比如：

0, 36, 5948721

再比如：

1098524736
1, 25, 6390784
0, 4, 289, 15376
...

注意，0 可以作为独立的数字，但不能作为多位数字的开始。 分组时，必须用完所有的数字，不能重复，不能遗漏。

如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？

思路：

这是一道思维题

对于每个成功分组中的每个数，他们没有重复的数字，且这个组内也没有重复的数字。而对每个数进行一位位判断是否出现的话就太浪费时间辽，所以我们可以对每个数x构造一个值为k的二进制数，也就是一个01串，这个串中任意一个1的位置i，代表x中有数字 i，

例如：23479

其01串为： 0101001110

然后预处理1-1e10内所有的平方数，判断每个平方数是否自身存在重复数字，判断方法也很简单：

利用位运算……

对于一个数x，我们取一个k初始化为0

对于x的每一位数字a，我们取出来，看看(1 >> x) & k是否为0，如果为0，就说明目前还没出现数字a，就可以更新k的值：k |= (1>>x)，并让x /= 10，然后一直这么算下去，如果确实没有重复的数字，就扔进vector里面

然后再打个dfs，参数是pos和k，pos 指目前枚举到数组中的哪个位置了，k也是一个01串，指的是到目前为止选用了哪些数字。

出现符合要求的答案是在k = (1 >> 10) – 1

#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 1000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

vector<int>v;
int ans;

void check(ll x){
    int k = 0;
    if(x == 0) k = 1;
    while (x) {
        int a = x % 10;
        if(k & (1 << a))return;
        k |= (1 << a);
        x /= 10;
    }
    v.push_back(k);
}

void dfs(int pos, int k){
    if(k == (1 << 10) - 1){
        ++ans;
        return;
    }
    for(int i = pos; i < v.size(); ++i){
        if(v[i] & k)continue;
        dfs(i + 1, k | v[i]);
    }
}

int main(){
    for(ll i = 0; i <= 100000; ++i){
        check(i * i);
    }
    dfs(0, 0);
    cout<<ans<<endl;
    return 0;
}

棋子换位

题目描述：

有 n 个棋子 A，n个棋子 B，在棋盘上排成一行。 它们中间隔着一个空位，用“.”表示，比如：

AAA.BBB

现在需要所有的 A 棋子和 B 棋子交换位置。 移动棋子的规则是：

  1. A 棋子只能往右边移动，B 棋子只能往左边移动。
  2. 每个棋子可以移动到相邻的空位。
  3. 每个棋子可以跳过相异的一个棋子落入空位（A 跳过 B 或者 B 跳过 A ）。

AAA.BBB 可以走法： 移动 A ==> AA.ABBB 移动 B ==> AAAB.BB

跳走的例子： AA.ABBB ==> AABA.BB

思路：

跳棋，两种走法

因为只有一个空位置，所以，我们应该尽量是能隔着跳就隔着跳，无法隔着跳才考虑跳到相邻的空位，因为如果上来就是直接跳相邻的位置，就会导致空位 '.' 移动到最左边，而无法继续走下去

其次，对于相邻的跳法，有一种跳法是死路，也就是 A.BA或者是BA.B,这种情况如果跳了，这两边的棋子就会有一边无法继续走了，这种情况是得跳过的

所以代码如下：

#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 1000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

string s;
int n;

bool judge(int x){//判断出界否
    if(x < 0 || x >= n)return false;
    return true;
}

void change(int from, int to){//交换棋子
    s[to] = s[from];
    s[from] = '.';
}

void work(){
    while (1) {
        bool a = 0;//判断有没有进行跳棋
        int d = 0;//表示当前棋子的走的方向
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == '.')continue;
            if(s[i] == 'A')d = 1;
            if(s[i] == 'B')d = -1;
            if(judge(i + d + d) && judge(i + d) && s[i + d] != '.' && s[i + d] != s[i] && s[i + d + d] == '.'){
                change(i, i + d + d);//先是隔着跳
                a = 1;
                cout<<s<<endl;
            }
        }
        if(a)continue;//跳过了以后就重新再找
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == '.')continue;
            if(s[i] == 'A')d = 1;
            if(s[i] == 'B')d = -1;
            if(judge(i + d) && s[i + d] == '.'){
                if(judge(i - d) && judge(i + d + d) && s[i - d] == s[i + d + d])continue;//死棋不跳
                change(i, i + d);//相邻跳
                a = 1;
                cout<<s<<endl;
            }
        }
        if(!a)break;//不进行跳棋，就跳出
    }
}

int main(){
    s = "AAAA.BBBB";
    n = 9;
    work();
    return 0;
}

机器人塔

题目描述：

X 星球的机器人表演拉拉队有两种服装，A 和 B。

他们这次表演的是搭机器人塔。

类似：

A

B B

A B A

A A B B

B B B A B

A B A B B A

队内的组塔规则是：

A 只能站在 AA 或 BB 的肩上。

B 只能站在 AB 或 BA 的肩上。

你的任务是帮助拉拉队计算一下，在给定 A 与 B 的人数时，可以组成多少种花样的塔。

思路：

第一反应就是从上往下dfs，但是发现数据挺大滴，可能跑不出来

正解其实是从下往上去判断。

为什么呢？

因为你从上往下去判断的时候，下一行的每一个都是不确定的，而从下往上去判断的时候，整个塔就是确定下来的，只需要去判断这个塔是否符合题意即可

再者，这题A在AA和BB上面， B在AB，BA上面，如果把A看成0，把B看成1，那就是同为0，异为1，这不就是异或嘛！！！

所以就可以用位运算去优化

操作：

我们要通过塔的第i行去推出第i-1行，就用第i行的01串代表的二进制数x，去异或 x>>1，同时再去掉第一位即可

#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 1000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int a, b, num, ans;

int getnum(int x){
    int cnt = 0;
    while (x) {
        if(x & 1)++cnt;
        x >>= 1;
    }
    return cnt;
}

bool check(int x){
    int numa = 0, numb = 0;
    for(int i = num; i >= 1; --i){
        numb += getnum(x);
        numa += i - getnum(x);
        x ^= (x >> 1);
        x &= (1 << (i - 1)) - 1;
    }
    return numa == a && numb == b;
}


int main(){
    cin>>a>>b;
    num = sqrt((a + b) * 2);
    for(int i = 0; i <= (1 << num); ++i){
        if(check(i))++ans;
    }
    cout<<ans<<endl;
    return 0;
}

还有两个题，一个是计算几何，一个是超级大图论，不太想写(╥﹏╥)，国赛的题好难啊orz

 

博客内容均系原创，未经允许严禁转载！
蓝桥杯
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
第十二届蓝桥杯省赛第一场C++A组 「左孩子右兄弟」

							
							

							
蓝桥杯2017年B组C++国赛

							
							

							
第十二届蓝桥杯省赛第一场C++「异或数列」

							
							

							
第十二届蓝桥杯省赛第一场C++「砝码称重」

							
							

							
蓝桥杯2018年C++组国赛