4.4 模拟赛小记-526互联

从之前惨痛的经历中吸取教训，我决定一天写一篇博客来记录我的学习，毕竟多写题解多交流才能学好 oi。

根据题目给出的要求找规律，有两种做法，一是口胡找规律，二是用递归分治的思想，一半一半切下去。

我这里是口胡的，如果你写出来 k 号的二进制，会发现格雷码就是将自己这一位和左边那一位进行异或，然后就结束了。

注意数据大小要用 unsigned long long。

 1 #include<bits/stdc++.h>
 2 #define ull unsigned long long
 3 using namespace std;
 4 ull k;
 5 int n, len = 0;
 6 int a[110], ans[110];
 7 int main()
 8 {
 9 scanf("%d%llu", &n, &k);
10 while(k) {a[++ len] = k % 2; k /= 2;}
11 for(int i = n; i >= 1; i -- ) a[i + 1] == a[i] ? (cout << 0) : (cout << 1);
12 return 0;
13 }

T2 新汉诺塔 P1242 新汉诺塔传送门

提供一个思路是递归，从大到小移动盘子，那么移这个盘子时就需要把放在它上面的比他小的移开，移到第三个柱子上。这样只需要标记每次移的盘子和移动目标。

但是洛谷上被 hack 了，事实上这个做法无法证明正确性，但是这个做法大概不刻意卡的话能骗点分。被 hack 了就不放代码了www。

T3 一眼不可做，有空再看罢。

T4 生成字符串

先根据长度确定这是第几次的变化，然后递归分治向前，找到这个位置时从最初的哪一个变化而来的。

对于每个串，前一半即从上一次复制而来，紧接着的一个来自上一次的末尾，剩下的位置一一对应着上一次的前一半。说起来有点绕，写写就很清楚了。

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 int len;
 5 ll n;
 6 string s;
 7 ll bpow(ll a, int b)
 8 {
 9 ll ans = 1;
10 while(b)
11 {
12 if(b & 1) ans *= a;
13 a *= a;
14 b >>= 1;
15 }
16 return ans;
17 }
18 ll find(int zu, ll k)
19 {
20 if(zu == 0) return k;
21 ll ans;
22 if(k == bpow(2, zu) * len / 2 + 1) ans = bpow(2, zu - 1) * len;
23 else if(k <= bpow(2, zu - 1) * len) ans = k;
24 else ans = k - bpow(2, zu) * len / 2 - 1;
25 return find(zu - 1, ans);
26 }
27 int main()
28 {
29 cin >> s >> n;
30 len = s.size();
31 int k = 0;
32 ll q = len;
33 while(!(q >= n && q / 2 < n)) {k ++; q *= 2;}
34 cout << s[find(k, n) - 1];
35 return 0;
36 }