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

2024-05-31 22:03
c语言, 开发语言
46人已看

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++;
			else
				break;
		}
		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;
}