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條邊可以使得圖中存在歐拉通路。因此建圖后跑一遍歐拉路即可

代碼：不知道什么原因1 1000000這個樣例過不去，有時間再說吧

#include <iostream>
#include <cstring>
#include <vector>using namespace std;const int N = 1e6 + 1000;vector<int> seq;
int n, cnt;
int prime[N];
int val[N * 2], ne[N * 2], h[N], idx;
bool st[N], used[N * 2];void add(int a, int b) {val[idx] = b;ne[idx] = h[a];h[a] = idx ++;
}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 x) {if(x & 1) {int cnt = x + (x * (x - 1)) / 2;return cnt >= n - 1;} else {int cnt = x + (x * (x - 1)) / 2 - x / 2 + 1;return cnt >= n - 1;}
}void dfs(int u) {while(h[u] != -1) {int i = h[u];if(used[i]) {h[u] = ne[i];continue;}used[i] = 1;used[i ^ 1] = 1;h[u] = ne[i];dfs(val[i]);seq.push_back(val[i]);}
}/*void dfs(int u) {for(int i = h[u]; i != -1; i = ne[i]) {if(used[i]) {h[u] = ne[i];continue;}used[i] = 1;used[i ^ 1] = 1;h[u] = ne[i];dfs(val[i]);seq.push_back(val[i]);}
}*/void init() {for(int i = 1; i <= 2 * n + 5000; i ++ ) used[i] = 0; memset(h, -1, sizeof h);idx = 0;seq.clear();
}void solve() {init();cin >> n;int l = 1, r = 2000;//二分點數while(l < r) {int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}if(l & 1) {for(int i = 0; i < l; i ++ ) {for(int j = i; j < l; j ++ ) {add(prime[i], prime[j]);add(prime[j], prime[i]);}}} else {int judge = 0;int cnt = l / 2 - 1;for(int i = 0; i < l; i ++ ) {for(int j = i; j < l; j ++ ) {if(j == i + 1) {judge ++;if(!(judge & 1)) {continue;}}add(prime[i], prime[j]);add(prime[j], prime[i]);}}}dfs(2);int len = seq.size();for(int i = 0; i < min(len, n); i ++ ) cout << seq[i] << " ";if(len < n) cout << 2;cout << endl;
}int main() {is_prime(200000);int t;cin >> t;while(t -- ) {solve();}return 0;
}

E：