codeforces round 949 div2

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：