25上海省赛

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin ， Cool-breeze

D. 与或博弈

博弈规则如下：

  • gsh 和 AI 轮流操作，gsh 先手。
  • 他们操作两个非负整数 \(a\) 和 \(b\)，gsh 的目标是将其变为目标非负整数 \(x\) 和 \(y\)，而 AI 需要阻止 gsh 达成目标。
  • gsh 在自己的回合可以执行以下两种操作之一：
    1. \(a := a \mathbin{\&} v\)（按位与某个非负整数 \(v\)）。
    2. \(b := b \mathbin{|} v\)（按位或某个非负整数 \(v\)）。
  • AI 在自己的回合可以执行以下两种操作之一：
    1. \(a := a \mathbin{|} v\)（按位或某个非负整数 \(v\)）。
    2. \(b := b \mathbin{\&} v\)（按位与某个非负整数 \(v\)）。
  • 允许选择的 \(v\) 满足 \(0 \leq v \lt 2^{60}\)。
  • 双方都足够聪明，并且都会采取最优策略以赢得游戏。
  • 若在 \(10^{100}\) 回合内，存在某一时刻 \(a = x\) 且 \(b = y\)，则 gsh 获胜；否则，AI 获胜。

请你判断 gsh 是否必胜，若必胜，输出 Yes，否则输出 No。

博弈论 如果 \(a=x,b=y\)，gsh 获胜。如果 \(a,b\) 其中一个等于 \(x,y\)，则另一个需要可以一步变成 \(x,y\) 才能获胜。否则 AI 可以一直阻止，无法获胜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 0, inf = 1e17;

void solve() {
    ll a, b, x, y;
    cin >> a >> b >> x >> y;
    if (a == x && b == y) {
        cout << "Yes" << endl;
    } else if (a == x && (b | y) == y) {
        cout << "Yes" << endl;
    } else if (b == y && (a & x) == x) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

G. 矩阵

给定一个正整数 \(n\)，你需要构造一个 \(n\times n\) 的矩阵。矩阵中，所有的数字与它上下左右相邻的四个数字都互质，并且矩阵中的数都不超过 \(n^2 + 40n\)。

构造题 最大公约数 注意到：大小上相邻的两个数必定互质，\(kp+c,(k+1)p+c\) 互质，其中 \(p\) 是质数，\(c<p\)。所以构造方法为：设第一个大于 \(n\) 的质数为 \(p\)，则 \(a_{i,j}=i+p(j-1)\)。经过打表验证数字不会超过 \(n^2+40n\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 3000;

ll isNotP[N];
vector<ll> primes;

void init() {
	isNotP[1] = 1;
	for (ll i = 2; i <= 2600; i++) {
		if (!isNotP[i]) {
			primes.push_back(i);
		}
		for (auto j : primes) {
			if (i * j > 2600) {
				break;
			}
			isNotP[i * j] = 1;
			if (i & j == 0) {
				break;
			}
		}
	}
}
void __() {
	ll n;
	cin >> n;
	ll p = 0;
	for (auto i : primes) {
		if (n < i) {
			p = i;
			break;
		}
	}
	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= n; j++) {
			cout << i + p * (j - 1) << " ";
		}
		cout << endl;
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T = 1;
	// cin >> T;
	init();
	while (T--) __();
	return 0;
}
/*
6,262,505 - 2504*(2503-2477+1)
6,234,609
*/

M. 魔法使考核

初始时数组元素为 \(0\)，要在若干次操作后使得第 \(i\in[1,n]\) 个元素最终等于 \(a_i\)。

  • 将任意一个元素增加 \(1\)，消耗 \(x\) 点体力。
  • 选择任意区间 \([l,r]\)，将第 \(l\) 个到第 \(r\) 个共 \(r-l+1\) 个元素的值翻倍，消耗 \(y\) 点体力。

算出最少用多少体力可以完成。

思维题 二进制 可以想到操作 2 最优是每次都选择区间 \([1,n]\)。因为可以设想把数字二进制分解，其中 \(1\) 的地方一定是进行了操作 1。把二进制串“右对齐”，操作 2 的次数就至多为“最长的二进制串的长度”次。之后，例如对于数字 2 来讲，如果进行两次操作 1 体力小于先操作 1 再操作 2，可以用操作 1 代替操作 2，减少操作 2 次数。

最后思路是：从高到低枚举二进制位，\(n\) 个元素一起考虑，维护变量 sum 模拟操作过程。如果某个数字当前位为 \(1\)，说明必定进行操作 1，sum 加一。之后考虑操作 2（翻倍操作）：如果 \(\text{sum}\times x<y\)，说明可以用 sum 次操作 1 代替一次操作 2。之后 sum 翻倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 0, inf = 1e17;

ll getBit(ll x, ll p) { return ((x >> (p - 1)) & 1); }

void solve() {
    ll n, x, y, sum = 0, ans = 0;
    cin >> n >> x >> y;
    ll a[n + 10];
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (ll i = 32; i >= 1; i--) {
        for (ll j = 1; j <= n; j++) {
            ans += getBit(a[j], i) * x;
            sum += getBit(a[j], i);
        }
        if (sum > 0 && i != 1) {
            if (sum > y) {
                ans += y;
            } else if (sum * x > y) {
                ans += y;
            } else {
                ans += sum * x;
            }
            sum *= 2;
        }
    }
    cout << (ll) ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    while (T--) {
        solve();
    }
    return 0;
}