D
题目大意：给定长度为 $n$ 的排列 $p$ ，判断是否存在一棵 $n$ 点标号树，使得任意边 $(u,v)$ 在 $u 数据范围：$1 \leq t \leq 10^4, 2 \leq n \leq 2 \cdot 10^5, 1 \leq p_i \leq n, \sum n \leq 2 \cdot 10^5$ 思路： 题目大意：构造一个长度为 $n$ 的排列 $p$ ，使得连续三项两两互质的位置数量不超过 $6$ 。只需要输出任意合法排列。 数据范围：$1 \leq t \leq 10^4, 3 \leq n \leq 2 \cdot 10^5, \sum n \leq 2 \cdot 10^5$ 思路： 题目大意：给定长度为 $n$ 的排列 $p$ ，判断是否存在一棵 $n$ 点标号树，使得任意边 $(u,v)$ 在 $u 数据范围：$1 \leq t \leq 10^4, 2 \leq n \leq 2 \cdot 10^5, 1 \leq p_i \leq n, \sum n \leq 2 \cdot 10^5$ 思路： 题目大意：给定两个长度为 $n$ 的数组 $a,b$ ，其中 $a_i \leq b_i$ 。每次操作可以把某个 $a_i$ 加一，或者把整个数组 $a$ 全部乘二。设最少需要 $x$ 次操作把 $a$ 变成 $b$ ，求 $x$ 以及恰好 $x$ 次操作的不同序列数。 数据范围：$1 \leq t \leq 10^4, 2 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq b_i \leq 10^6, \sum n \leq 2 \cdot 10^5, \operatorname{mod}=10^6+3$ 思路： 题目大意：定义 $v(b,x)$ 为满足 $b^k \mid x$ 的最大 $k$ 。给定 $n,m$ ，在所有长度为 $n$ 且严格递增、元素位于 $[1,m]$ 的数组 $a$ 中，最大化 $\sum_{i=2}^{n}v(i,a_i)$ 。 数据范围：$1 \leq t \leq 10^4, 2 \leq n \leq m \leq 2 \cdot 10^5, \sum m \leq 2 \cdot 10^5$ 思路： 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
template <typename T = long long>
class Tree {
vector<T> tree;
public:
// 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
Tree(int n, T val = 0) : tree(n + 1) {
for (int i = 1; i <= n; i++) {
tree[i] += val;
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
Tree(const vector<T>& data) {
int n = data.size();
tree.resize(n + 1);
for (int i = 1; i <= n; i++) {
tree[i] += data[i - 1]; // data是 0-based
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 单点修改：将 0-based 下标 i 处的元素增加 val
void add(int i, T val = 1) {
for (++i; i < tree.size(); i += i & (-i)) {
tree[i] += val;
}
}
// 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
T pre(int i) const {
T res = 0;
for (++i; i > 0; i &= i - 1) {
res += tree[i];
}
return res;
}
// 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
T query(int l, int r) const {
if (r < l) {
return 0;
}
return pre(r) - pre(l - 1); // 当 l=0 时, pre(-1) 会合理地返回 0
}
// 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
int lower_bound(T val) const {
int w = bit_width(tree.size() - 1);
int res = 0;
T s = 0;
for (int i = w - 1; i >= 0; i--) {
int nxt = res + (1 << i);
if (nxt < tree.size() && tree[nxt] + s < val) {
res += (1 << i);
s += tree[nxt];
}
}
return res; // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
}
};
void solve() {
ll n;
cin >> n;
vl a(n);
vl pos(n);
rep(i, 0, n - 1) {
cin >> a[i];
a[i]--;
}
vl pre(n);
pre[0] = a[0];
rep(i, 1, n - 1) pre[i] = min(pre[i - 1], a[i]);
vl suf(n);
suf[n - 1] = a[n - 1];
frep(i, n - 2, 0) suf[i] = max(suf[i + 1], a[i]);
rep(i, 0, n - 2) {
if (pre[i] > suf[i + 1]) {
cout << "No" << endl;
return;
}
}
cout << "Yes" << endl;
return;
}
E
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
void solve() {
ll n;
cin >> n;
vl even;
vl odd;
vl tem;
rep(i, 1, n) {
if (i % 2 == 0)
even.push_back(i);
else if (i % 3 == 0)
odd.push_back(i);
else
tem.push_back(i);
}
while (!tem.empty() && sz(even) >= 2) {
cout << tem.back() << ' ';
tem.pop_back();
cout << even.back() << ' ';
even.pop_back();
cout << even.back() << ' ';
even.pop_back();
}
while (!tem.empty() && sz(odd) >= 2) {
cout << tem.back() << ' ';
tem.pop_back();
cout << odd.back() << ' ';
odd.pop_back();
cout << odd.back() << ' ';
odd.pop_back();
}
while (!even.empty()) {
cout << even.back() << ' ';
even.pop_back();
}
while (!odd.empty()) {
cout << odd.back() << ' ';
odd.pop_back();
}
while (!tem.empty()) {
cout << tem.back() << ' ';
tem.pop_back();
}
cout << endl;
return;
}
F
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
void solve() {
ll n;
cin >> n;
vl a(n);
vl pos(n);
rep(i, 0, n - 1) { cin >> a[i]; }
vl pre(n);
pre[0] = a[0];
rep(i, 1, n - 1) pre[i] = min(pre[i - 1], a[i]);
vl suf(n);
vl idx(n);
suf[n - 1] = a[n - 1];
idx[n - 1] = n - 1;
frep(i, n - 2, 0) {
suf[i] = suf[i + 1];
idx[i] = idx[i + 1];
if (a[i] > suf[i + 1]) {
suf[i] = a[i];
idx[i] = i;
}
}
vector<pll> res;
rep(i, 0, n - 2) {
if (pre[i] > suf[i + 1]) {
cout << "No" << endl;
return;
}
}
cout << "Yes" << endl;
int l = 0;
while (l < n) {
rep(i, l, idx[l] - 1) { res.emplace_back(a[i], a[idx[l]]); }
if (l > 0) res.emplace_back(a[idx[l]], pre[l - 1]);
l = idx[l] + 1;
}
for (auto& p : res) cout << p.first << ' ' << p.second << endl;
return;
}
G
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
const ll MOD = 1e6 + 3;
constexpr int MX = 1e6 + 3;
ll F[MX]; // 预处理阶乘
ll INV_F[MX]; // 预处理逆元
ll qpow(ll x, int n) {
ll res = 1;
for (; n; n >>= 1) {
if (n % 2) res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
auto init = [] {
F[0] = 1;
for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD; // 预处理阶乘
INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
} // 预处理逆元
return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
void solve() {
ll n;
cin >> n;
vl a(n), b(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) cin >> b[i];
ll tem = LLONG_MAX;
rep(i, 0, n - 1) { tem = min(tem, 1LL * (int)log2(b[i] / a[i])); }
ll ans = tem;
rep(i, 0, n - 1) {
ans += b[i] / (1LL << tem) - a[i];
ans += popcount((unsigned)(b[i] % (1LL << tem)));
}
cout << ans << ' ';
vl cnt(tem + 1);
rep(i, 0, n - 1) {
ll tem2 = b[i] / (1LL << tem) - a[i];
cnt[0] += tem2;
rep(j, 1, tem) { cnt[j] += ((b[i] % (1LL << tem)) >> (j - 1) & 1); }
}
ll res = 1;
if (cnt[0] >= MOD) {
cout << 0 << endl;
return;
}
res = F[cnt[0]];
rep(i, 1, tem) { res = (res * F[cnt[i]] % MOD); }
rep(i, 0, n - 1) { res = res * INV_F[b[i] / (1LL << tem) - a[i]] % MOD; }
cout << res << endl;
return;
}
H
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
struct Info {
ll sum;
Info(ll x = 0) : sum(x) {}
};
Info operator+(const Info& a, const Info& b) {
Info c;
c.sum = max(a.sum, b.sum);
return c;
}
template <typename T>
class SegmentTree {
int n;
vector<T> tree;
T merge_val(T a, T b) const { return a + b; } // 合并子树
void maintain(int node) { // 维护整棵树
tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
}
void build(const vector<T>& a, int node, int l, int r) {
if (l == r) {
tree[node] = a[l];
return;
}
int m = (l + r) / 2;
build(a, node * 2, l, m);
build(a, node * 2 + 1, m + 1, r);
maintain(node);
} // 建树
void update(int node, int l, int r, int i, T val) {
if (l == r) {
tree[node] = val;
return;
}
int m = (l + r) / 2;
if (i <= m)
update(node * 2, l, m, i, val);
else
update(node * 2 + 1, m + 1, r, i, val);
maintain(node);
} // 更新i处的值为val
T query(int node, int l, int r, int ql, int qr) const {
if (ql <= l && r <= qr) return tree[node];
int m = (l + r) / 2;
if (qr <= m) return query(node * 2, l, m, ql, qr);
if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
T l_res = query(node * 2, l, m, ql, qr);
T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
return merge_val(l_res, r_res);
} // 查询[ql,qr]的值
int find_first(int node, int l, int r, int ql, int qr, T val) const {
if (r < ql || l > qr) return -1;
if (tree[node].val < val) return -1;
if (l == r) return l;
int m = (l + r) >> 1;
int res = find_first(node << 1, l, m, ql, qr, val);
if (res != -1) return res;
return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
}
// 若固定左端点，需要记录前缀分段最大值，并加被待求区间完全覆盖的剪枝
int find_last(int node, int l, int r, int ql, int qr, T val) const {
if (r < ql || l > qr) return -1;
if (tree[node].val < val) return -1;
if (l == r) return l;
int m = (l + r) >> 1;
int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
if (res != -1) return res;
return find_last(node << 1, l, m, ql, qr, val);
}
public:
SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}
// 传入一个数组维护
SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }
void update(int i, T val) { update(1, 0, n - 1, i, val); } // 更新i的值为val
T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); } // 查询[ql,qr]的值
T get(int i) const { return query(1, 0, n - 1, i, i); } // 取出i处的值
// 查询[ql,qr]中第一个满足条件的下标
int find_first(int ql, int qr, T val) const { return find_first(1, 0, n - 1, ql, qr, val); }
// 查询[ql,qr]中最后一个满足条件的下标
int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); }
};
void solve() {
ll n, m;
cin >> n >> m;
vector<Info> init(m - n + 1, Info(0));
SegmentTree<Info> seg(init);
rep(i, 2, n) {
for (ll j = (i + m - n) / i * i; j >= i; j -= i) {
ll tem = seg.query(0, j - i).sum;
ll tem2 = j;
ll tem3 = 0;
while (tem2 % i == 0) {
tem3++;
tem2 /= i;
}
if (tem3 + tem > seg.get(j - i).sum) seg.update(j - i, Info(tem + tem3));
}
}
cout << seg.query(0, m - n).sum << endl;
return;
}