4.4 模拟赛小记

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

 T1 格雷码 P5657 洛谷传送门

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

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

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

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

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

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

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

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

 T4 生成字符串

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

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

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int len;
ll n;
string s;
ll bpow(ll a, int b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans *= a;
        a *= a; 
        b >>= 1;
    }
    return ans; 
}
ll find(int zu, ll k)
{
    if(zu == 0) return k;
    ll ans;
    if(k == bpow(2, zu) * len / 2 + 1) ans = bpow(2, zu - 1) * len;
    else if(k <= bpow(2, zu - 1) * len) ans = k;
    else ans = k - bpow(2, zu) * len / 2 - 1;
    return find(zu - 1, ans);
}
int main()
{
    cin >> s >> n;
    len = s.size();
    int k = 0;
    ll q = len;
    while(!(q >= n && q / 2 < n)) {k ++; q *= 2;}
    cout << s[find(k, n) - 1];
    return 0;
}

 T5 不再相邻

可以 O(n) 推式子 or O(n ^ 2) dp，咱都不会，会了再说。

今天的一些脑残小问题，可以看着玩玩：

1.scanf 忘记写取地址符了。

2.一开始忘记开 ull。

3.T4 一开始想起来开 long long 了，但没完全开，好像函数里忘开了。感觉不如 int long long。

4.我之前真的不知道 pow 函数有精度问题，今天才知道。emmmmm，记得写快速幂罢，否则会变得不幸。

 审视今天，美好的一天。又是没有脑子的一天。