2018第九届蓝桥杯B组决赛题解

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const double esp = 1e-12;
const int ff = 0x3f3f3f3f;
map<int,int>::iterator it;
ll ans=0;
int sta[52];
void dfs(int x) {
	if(x == 31) {
		ans++;
		return ;
	}
	dfs(x+1);
	if(sta[x-1] == 0) {
		sta[x] = 1;
		dfs(x+1);
		sta[x] = 0;
	}
	return ;
}
int main() {
	dfs(1);
	cout<<ans<<endl;
	return 0;
}

#include<stdio.h>
#include<stdlib.h>
int main()
{
	long long a[30] = { 0 };
	int i;
	a[0] = 2;
	a[1] = 3;
	for (i = 2; i < 30; i++)
	{
		a[i] = a[i - 1] + a[i - 2];
	}
	printf("%I64d\n", a[29]);
	system("pause");
	return 0;
}

• 从编码全0开始生成。
• 当产生第奇数个数时，只把当前数字最末位改变（0变1，1变0）
• 当产生第偶数个数时，先找到最右边的一个1，把它左边的数字改变。
• 用这个规则产生的4位格雷码序列如下：
  0000
  0001
  0011   
  0010
  0110   
  0111
  0101   
  0100
  1100   
  1101
  1111   
  1110
  1010   
  1011
  1001   
  1000以下是实现代码，仔细分析其中逻辑，并填写划线部分缺少的代码。

  #include <stdio.h>
  void show(int a,int n) {
  	int i;
  	int msk = 1;
  	for(i=0; i<n-1; i++) msk = msk << 1;
  	for(i=0; i<n; i++) {
  		printf((a & msk)? "1" : "0");
  		msk = msk >> 1;
  	}
  	printf("\n");
  }
  void f(int n) {
  	int i;
  	int num = 1;
  	for(i=0; i<n; i++) num = num<<1;
  	int a = 0;
  	for(i=0; i<num; i++) {
  		show(a,n);
  		if(i%2==0) {
  			a = a ^ 1;
  		} else {
  			a = _________________________ ; //填空
  		}
  	}
  }
  int main() {
  	f(4);
  	return 0;
  }
  

• 首先我们知道用 (a&(-a)) 可以找到右边第一个1以及后面的0组成的数
• 那么我们将其左移一位再按位异或a即可
• 即 a^(a&(-a)<<1)

• 求在任一情况下最快到达k的最小值中的最大值
• 可以bfs、完全背包
• 但是实际上，我们可以将k当作0，仍然和题意相符
• 我们将从n-1开始的每k个数字当作一组
  • 可以得到两个结论
    • 对于同一组中的数字，除去离n的距离余k等于0的数字以外，总是最小的需要次数多 
    • 对于同余k的数字，在离0越近时需要次数越多，即最区间左端最大
  • 而最后一组可能并没有k个数字，所以有可能小于倒数第二组，即最后一组的区间最左端可能小于倒数第二组的区间最左端（倒数第二组的区间最左端又大于前面的所有）
  • 所以我们选 (n-1)/k+(n-1)%k 与 (n-1)/k-1+(k-1)中的较大者为答案，加粗的减一的意义是倒数第二个区间可以比最后一个区间少跳跃一个离最右端距离余k等于0的屏障

• #include<bits/stdc++.h>
  using namespace std;
  int main()
  {
  	int n,k;
  	cin>>n>>k;
  	cout<<max((n-1)/k+(n-1)%k, (n-1)/k-1+k-1);
  	return 0;
  }