个人技术分享

A Turtle and Piggy Are Playing a Game

题目：

思路：输出2的幂次b使得2^b为最大的不超过x的数

代码：

#include <iostream>
 
using namespace std;
 
const int N = 2e5 + 10;
 
void solve() {
    int l, r;
    cin >> l >> r;
    if(r % 2) r --;
    int ans = 0;
    while(r != 1) {
        ans ++;
        r /= 2;
    }
    cout << ans << endl;
}
 
int main() {
    int t;
    cin >> t;
    while(t -- ) {
        solve();
    }
    return 0;
}

当然也可以直接输出_lg(x)

B. Turtle and an Infinite Sequence

问题：

思路：实际上就是求一个区间内的or值，区间为max(0, n - m), n + m。由于区间范围很大，暴力会t，因此考虑寻找某些规律。

x:100011

y:101001

从x自增到y，发现x，y最左边两位是相等的，因此这两位相等的位只有为1时才会对答案产生贡献，这两位其他位会从小的不断自增到大的，因此这些位肯定会出现1，因此答案就是从左向右拆位直到找到第一个不同的位，这之前只有1对答案有贡献，这之后都对答案有贡献

代码：

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int N = 2e5 + 10;
 
int get(int x) {
    int cnt = 0;
    while(x) {
        cnt ++;
        x >>= 1;
    }
    return cnt;
}
 
int qmi(int a) {
    int res = 1;
    int b = 2;
    while(a) {
        if(a & 1) res *= b;
        b *= b;
        a >>= 1;
    }
    return res;
}
 
void solve() {
   int n, m;
   cin >> n >> m;
  
   int pos = -1;
   int x = m + n;
   int len = get(x);
   vector<int> ans;
   if(m == 0) cout << n << endl;
   else {
       vector<int> a;
       vector<int> b;
       for(int i = len - 1; i >= 0; i -- ) {
           int aa = (x >> i) & 1;
           int bb = (n >> i) & 1;
           a.push_back(aa);
           b.push_back(bb);
       }
       
       bool flag = false;
       for(int i = 0; i <= len - 1; i ++ ) {
           //cout << b[i] << " ";
           if(a[i] != b[i]) flag = true;
           if(!flag) ans.push_back(a[i]);
           else ans.push_back(1);
       }
       len = get(n);
       a.clear();
       b.clear();
       x = n;
       int y = max(0, n - m);
       for(int i = len - 1; i >= 0; i -- ) {
           int aa = (x >> i) & 1;
           int bb = (y >> i) & 1;
           a.push_back(aa);
           b.push_back(bb);
       }
       
       vector<int> ans1;
       flag = false;
       for(int i = 0; i <= len - 1; i ++ ) {
           //cout << b[i] << " ";
           if(a[i] != b[i]) flag = true;
           if(!flag) ans1.push_back(a[i]);
           else ans1.push_back(1);
       }
       reverse(ans.begin(), ans.end());
       reverse(ans1.begin(), ans1.end());
       for(int i = 0; i < ans1.size(); i ++ ) {
           ans[i] |= ans1[i];
       }
       int res = 0;
       for(int i = 0; i < ans.size(); i ++ ) {
           res += ans[i] * qmi(i);
       }
      // for(auto t: a) cout << t << " ";
       cout << res << endl;
   }
}
 
int main() {
    int t;
    cin >> t;
    while(t -- ) {
        solve();
    }
    return 0;
}

赛后优化代码：

#include <iostream>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    int l = max(0, n - m), r = n + m;
    int ans = 0;
    bool flag = false;
    for(int i = 30; i >= 0; i -- ) {
        int x = (l >> i) & 1;
        int y = (r >> i) & 1;
        if(x != y) flag = true;
        if(!flag) {
            ans += (1 << i) * x;
        } else ans += (1 << i) * 1;
    }
    cout << ans << endl;
}
 
int main() {
    int t;
    cin >> t;
    while(t -- ) {
        solve();
    }
    return 0;
}

C: Turtle and an Incomplete Sequence

题目：

思路：先特判，特判掉都是-1的以及只有一个非-1数。特判之后记录所有非-1数的位置对于第一个位置和最后一个位置让他们分别向左右扫，不断除2，如果变成0就赋值-1.对于任意两位置pos[i] pos[i + 1]让他们两个向中间靠拢，哪个大就/2如果变成0就置2 最后当strat + 1 = end时判断下相邻元素是否合法。对于这种解法的正确性可以考虑一颗二叉树(父节点u 左子节点2u 右子节点2u + 1)，有两个节点，两个节点不断除2最终一定会到他们的lca上.

代码：

#include <iostream>
#include <vector>

using namespace std;

const int N = 2e5 + 10;

int a[N];
int n;

void solve() {
    cin >> n;
    vector<int> pos;
    vector<int> b(n + 5);
    for(int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        if(a[i] != -1) {
            pos.push_back(i);
            b[i] = a[i];
        } 
    }

    if(!pos.size()) {
        b[1] = 1;
        for(int i = 2; i <= n; i ++ ) {
            b[i] = b[i - 1] / 2;
            if(b[i] == 0) b[i] = 2;
        }
        for(int i = 1; i <= n; i ++ ) cout << b[i] << " ";
        cout << endl;
        return;
    }

    if(pos.size() == 1) {
        for(int i = pos[0]; i >= 1; i -- ) {
            b[i - 1] = b[i] / 2;
            if(b[i - 1] == 0) b[i - 1] = 2;
        }
        for(int i = pos[0]; i <= n; i ++ ) {
            b[i + 1] = b[i] / 2;
            if(b[i + 1] == 0) b[i + 1] = 2;
        }
        for(int i = 1; i <= n; i ++ ) cout << b[i] << " ";
        cout << endl;
        return; 
    }

    for(int i = 0; i < pos.size() - 1; i ++ ) {
        int start = pos[i];
        int end = pos[i + 1];
        if(i == 0) for(int j = start - 1; j >= 1; j -- ) {
            b[j] = b[j + 1] / 2;
            if(b[j] == 0) b[j] = 2;
        }
        if(i + 1 == pos.size() - 1) for(int j = end + 1; j <= n; j ++ ) {
            b[j] = b[j - 1] / 2;
            if(b[j] == 0) b[j] = 2;
        }
    
        while(start + 1 < end) {
            if(b[start] >= b[end]) {
                start ++;
                b[start] = b[start - 1] / 2;
                if(b[start] == 0) b[start] = 2;
            } else {
                end --;
                b[end] = b[end + 1] / 2;
                if(b[end] == 0) b[end] = 2;
            }
        }
        if(b[start] != b[end] / 2 && b[end] != b[start] / 2) {
            cout << "-1" << endl;
            return;
        }
    }
    for(int i = 1; i <= n; i ++ ) cout << b[i] << " ";
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    while(t -- ) {
        solve();
    }
    return 0;
}

D Turtle and Multiplication

题目：

思路：优先考虑素数，于是问题转化为了在当前数量的素数中是否可以找到一条欧拉通路。点数可以用二分查找，当查找到奇数点时，由于完全连通图各点是度数为偶数，因此一定存在欧拉通路，对于偶数点，所有点度数为奇数，由于每删去一条边可以使得最多两个点度数变成偶数，因此至少要删去x / 2 - 1条边可以使得图中存在欧拉通路。因此建图后跑一遍欧拉路即可

代码：原先链式向前星的建图会mle，这里是vector的建图，也是ac了

#include <bits/stdc++.h>

using namespace std;

const int N = 50000;

int prime[N];
bool st[N];
int cnt, n;

void is_prime(int x) {
    for(int i = 2; i <= x; i ++ ) {
        if(!st[i]) prime[cnt ++] = i;
        for(int j = 0; prime[j] <= x / i; j ++ ) {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

bool check(int mid) {
    if(mid & 1) {
        return mid + mid * (mid - 1) / 2 >= n - 1;
    } else {
        return mid + mid * (mid - 1) / 2 - mid / 2 + 1 >= n - 1;
    }
}

void solve() {
    cin >> n;
    int l = 1, r = 2000;
    while(l < r) {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    //cout << l;
    int tot = 0;
    vector<vector<pair<int, int>>> g(n + 1);

    if(l & 1) {
        for(int i = 0; i < l; i ++ ) {
            for(int j = i; j < l; j ++ ) {
                g[prime[i]].push_back({prime[j], ++ tot});
                g[prime[j]].push_back({prime[i], tot});
            }
        }
    } else {
        int judge = 0;
        for(int i = 0; i < l; i ++ ) {
            for(int j = i; j < l; j ++ ) {
                if(j == i + 1) {
                    judge ++;
                    if((judge & 1) == 0) continue;
                }
                g[prime[i]].push_back({prime[j], ++ tot});
                g[prime[j]].push_back({prime[i], tot});
            }
        }
    }

    vector<bool> used(1200000);
    vector<int> seq;
    function<void(int)> dfs = [&](int u) {
        while(g[u].size()) {
            auto t = g[u].back();
            g[u].pop_back();
            if(used[t.second]) continue;
            used[t.second] = true;
            dfs(t.first);
        }
        seq.push_back(u);
    };
    dfs(2);
    
    for(int i = 0; i < n; i ++ ) {
        cout << seq[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    is_prime(20000);
    int t;
    cin >> t;
    while(t -- ) {
        solve();
    }
    return 0;
}

E：