Codeforces Round 949 (Div. 2) （A~C）

1981A - Turtle and Piggy Are Playing a Game

贪心，每次取x = 2，求最大分数

// Problem: B. Turtle and an Infinite Sequence
// Contest: Codeforces - Codeforces Round 949 (Div. 2)
// URL: https://codeforces.com/contest/1981/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{cin >> n >> m;int l = max(0LL , n - m);int r = n + m;int ans = 0;vector<int>tmp1 , tmp2;long long cnt = 0; //统计从高位数起，a,b有多少位不一样while(l != r){cnt++;l >>= 1;r >>= 1;}while(cnt--) r = (r<<1)^1;cout << r << endl;
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

1981B - Turtle and an Infinite Sequence

思路：对于数字 $i$ 而言， $m$ 轮之后的结果是 $[i - m , i + m]$ 所有数的或。因此只需要求区间或就行了。

// Problem: B. Turtle and an Infinite Sequence
// Contest: Codeforces - Codeforces Round 949 (Div. 2)
// URL: https://codeforces.com/contest/1981/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{cin >> n >> m;int l = max(0LL , n - m);int r = n + m;int ans = 0;vector<int>tmp1 , tmp2;long long cnt = 0; //统计从高位数起，a,b有多少位不一样while(l != r){cnt++;l >>= 1;r >>= 1;}while(cnt--) r = (r<<1)^1;cout << r << endl;
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

1981C - Turtle and an Incomplete Sequence

思路：考虑将操作统一，即满足 $b_{i} = b_{i - 1} /2$ 或者 $b[i] = b[i - 1] * 2$ 或者 $b[i] = b[i - 1] * 2+1$ 。因此放二进制上考虑就是将前一个数右移一位或者在末尾填上0或者1。

接下来考虑从 $x$ 变成 $y$ 至少需要多少个操作，首先求出 $x,y$ 的二进制最长公共前缀,然后将 $x$ 通过右移操作变成其最长公共前缀，然后再通过填1或者填0来变成 $y$ 。最后之间剩余的数通过反复*2/2操作即可。

// Problem: C. Turtle and an Incomplete Sequence
// Contest: Codeforces - Codeforces Round 949 (Div. 2)
// URL: https://codeforces.com/contest/1981/problem/C
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int n;cin >> n;int bit[n + 5][32];for(int i = 1 ; i <= n ; i ++)cin >> a[i];vector<int>pos;int st = 0 , en = 0;for(int i = 1 ; i <= n ; i ++){if(a[i] != -1){if(!st) st = i;pos.pb(i);for(int j = 0 ; j < 32 ; j ++){bit[i][j] = ((a[i] >> j) & 1);}en = i;}}int f = 0;for(int i = st - 1 ; i >= 1 ; i --){if(f == 0){a[i] = a[i + 1] * 2;}else{a[i] = a[i + 1] / 2;}f ^= 1;}f = 0;for(int i = en + 1 ; i <= n ; i ++){if(i == 1){a[i] = 2;continue;}if(f == 0){a[i] = a[i - 1] * 2;}else{a[i] = a[i - 1] / 2;}f ^= 1;}	int len = pos.size();for(int i = 0 ; i < len - 1; i ++){int l = a[pos[i]] , r = a[pos[i + 1]];int tmp = l;int len1 = 0 , len2 = 0;while(tmp){tmp /= 2;len1++;}tmp = r;while(tmp){tmp/=2;len2++;}int tot = 0;for(int j = 0 ; j < min(len1 , len2) ; j ++){if(bit[pos[i]][len1 - j - 1] == bit[pos[i + 1]][len2 - j - 1])tot++;elsebreak;}int need = len1 + len2 - 2 * tot;//cout << l << " " << r << " " << need << endl;if(pos[i + 1] - pos[i]  < need || (pos[i + 1] - pos[i] - need) % 2 != 0){cout << -1 << endl;return;}int need1 = len1 - tot;int need2 = len2 - tot;int po = pos[i] + 1;for(int j = 0 ; j < need1 ; j ++){a[po] = a[po - 1] / 2;po++;}for(int j = 0 ; j < need2 ; j ++){if(bit[pos[i + 1]][len2 - tot - j - 1] == 0){a[po] = a[po - 1] * 2;}else{a[po] = a[po - 1] * 2 + 1;}po++;}int f = 1;for(po ; po < pos[i + 1] ; po++){if(f == 1){a[po] = a[po - 1] * 2;}else{a[po] = a[po - 1] / 2;}f ^= 1;}}for(int i = 1 ; i <= n ; i ++){cout << a[i] << " ";}cout << endl;
}            int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}