No Prime Differences
出处：CF1838C
题目大意：给定 $n \times m$ 的矩阵，要求在其中填入 $1 \sim n \cdot m$ 的整数，使得网格中任意相邻单元格的绝对差不是质数。
数据范围： $4 \leq n,m \leq 1000, 1 \leq sum(n \cdot m) \leq 10^6$
思路：首先考虑 $n$ 和 $m$ 中有一个是合数的情况，显然按顺序填就可以。
然后，若它们都是质数，那么只需考虑每一行跳的是 $2 \cdot m$ 即可。
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
|
bool check(int x) {
if (x == 1) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
void solve() {
int n, m;
cin >> n >> m;
vvi a(n, vi(m));
if (!check(m)) {
rep(i, 0, n - 1) { rep(j, 0, m - 1) a[i][j] = i * m + j + 1; }
} else if (!check(n)) {
rep(j, 0, m - 1) { rep(i, 0, n - 1) a[i][j] = j * n + i + 1; }
} else {
rep(i, 0, n / 2) { rep(j, 0, m - 1) a[i][j] = 2 * m * i + j + 1; }
rep(i, n / 2 + 1, n - 1) { rep(j, 0, m - 1) a[i][j] = m + 2 * m * (i - n / 2 - 1) + j + 1; }
}
rep(i, 0, n - 1) {
rep(j, 0, m - 1) cout << a[i][j] << ' ';
cout << endl;
}
return;
}
|
Vlad and a Pair of Numbers
出处：CF1790E
题目大意：给定 $x=a \bigoplus b,$ 问是否存在 $a,b$ ，使得 $\frac{a+b}{2}=x$ ，此处除法为实数除法，若存在则输出任意解，若不存在则输出-1.
数据范围： $1 \leq x \leq 2^{29}$ 。
思路：考虑异或性质，发现异或为1的位贡献是确定的，0的贡献是不确定的，于是判断对于 $x$ 的每个为1的位，后面都需要跟着至少一个0，答案为 $\frac{3x}{2}$ 和 $\frac{x}{2}$ 。
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
|
void solve() {
ll x;
cin >> x;
vi tem2;
int te = bit_width((unsigned)x) - 1;
ll tem = 0;
frep(i, te, 0) {
if ((x >> i) & 1) {
if (i == 0 || ((x >> (i - 1)) & 1)) {
cout << -1 << endl;
return;
}
}
}
int a = 0, b = 0;
frep(i, te, 0) {
if ((x >> i) & 1)
a += (1 << i);
else {
if (i != te && ((x >> (i + 1)) & 1)) {
a += (1 << i);
b += (1 << i);
}
}
}
cout << a << ' ' << b << endl;
return;
}
|
Array and GCD
出处：CF2104D
题目大意：给定一个大小为 $n$ 的数组 $a$ ，每次需要执行一次以下操作：
- 支付一枚硬币，并将数组中的任意一个元素增加1，但是不能贷款。
- 获得一枚硬币，并将数组中的任意一个元素减少1。
现在定义这样的一个数组是好的：
- 每个元素至少为2。
- 对于任意两个元素，它们都互质，如果元素数量少于2，那么自动满足这个条件。
现在要让这个数组变好，最少需要删除多少个数字？
数据范围： $1 \leq n \leq 4 \cdot 10^5, 2 \leq a_i \leq 10^9$
思路：看到最少其实很容易想到二分，不过这里其实不二分直接O(N)也可以，做麻烦了。
随后观察到对于某个取出的数组进行操作，则元素和应当小于等于原来的元素和。
考虑最少的条件，一个很直觉的东西就是，所有元素是按顺序排下来的最小 $k$ 个质数，然后就等价于原来的元素和大于等于这些质数的和，而根据贪心原来的元素和又可以取到原本数组中最大的 $k$ 个元素，于是做一下前缀和即可。
这里需要用到一些素数的筛法，我这边用了欧拉筛，它是一种 $O(n)$ 的筛法，基于每个合数只被它的最小素因子筛出的原理来做的，因此可以求出最小素因子，不过这里用埃氏筛也可以。
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
|
constexpr int MX = 6e6 + 1;
bool pd[MX];
vi primes;
auto init = [] {
rep(i, 2, MX - 1) {
if (!pd[i]) primes.push_back(i);
for (int& p : primes) {
if (1LL * p * i >= MX) break;
pd[i * p] = true;
if (i % p == 0) break;
}
}
return 0;
}();
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
sort(all2(a));
vl pre(n);
pre[0] = a[0];
rep(i, 1, n - 1) pre[i] = pre[i - 1] + 1LL * a[i];
vl pre2(n);
pre2[0] = primes[0];
rep(i, 1, n - 1) pre2[i] = pre2[i - 1] + 1LL * primes[i];
int l = 1, r = n, mid, ans = 1;
auto check = [&](int mid) -> bool {
if (mid == 1) return true;
return pre[mid - 1] >= pre2[mid - 1];
};
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else
r = mid - 1;
}
cout << n - ans << endl;
return;
}
|
