D. This Is the Last Time#
题目重述#
初始有 $k$ 枚硬币，最多可访问 $n$ 个赌场。
第 $i$ 家赌场给出区间 $[l_i,r_i]$ 与最终硬币数 $real_i$。
仅当当前硬币数 $x$ 满足 $l_i\le x\le r_i$ 才能进入，并立刻令 $x\gets real_i$。
每家赌场最多进入一次，顺序自选，求可获得的最大硬币数。
具体流程#
按 $l_i$ 升序排序 所有赌场。
维护指针 i 扫描到满足 $l_i≤t$ 的所有赌场，并把它们按 $r_i$ 升序插入 set。
BFS 队列存储当前可达的钱数；map 记录是否访问过。
当取出钱数 $t$ 时，对 set 二分找到所有满足 $r_i\ge t$ 的赌场,进行以下更新：
1.更新答案 $ans=max(ans, real_i)$
2.把新的钱数 $real_i$ 入队
3.将该赌场从 set 删除
所有赌场最多被插入、删除各一次，$queue_{size} \le n+1$。
复杂度 $O(n\log n)$
ac code#
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
| //F0rsyth1a
#include<iostream>
#include<algorithm>
#include<random>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#ifdef PBDS
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/priority_queue.hpp>
#endif
#define lowbit(x) (x&-x)
#define fi first
#define se second
using namespace std;
using LL = int;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
#define IOS
#define CF
// #define FRE
// #define PBDS
const int N = 1e5 + 10;
int n, k;
struct node{
int l, r, w;
bool operator <(const node &o) const
{
return l < o.l;
}
};
void solve()
{
cin >> n >> k;
vector<node> v(n);
for(int i = 0, l, r, w; i < n; i ++)
cin >> l >> r >> w, v[i] = {l, r, w};
sort(v.begin(), v.end());
queue<LL> q;
set<PLL> st;
map<int, int> vis;
LL i = 0, ans = k;
q.push(k);
while(q.size()){
LL t = q.front(); q.pop();
if(vis[t]) continue;
vis[t] = 1;
while(i < v.size() && v[i].l <= t)
st.insert({v[i].r, v[i].w}), i ++;
auto it = st.lower_bound({t, -1});
while(it != st.end()){
LL cur = it -> se;
ans = max(ans, cur);
q.push(cur);
it = st.erase(it);
}
}
cout << ans << '\n';
}
int main()
{
#ifdef IOS
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#endif
#ifdef FRE
freopen(".in", "r", stdin); freopen(".out", "w", stdout);
#endif
int Case = 1;
#ifdef CF
cin >> Case;
#endif
while(Case --) solve();
return 0;
}
|
E. G-C-D, Unlucky!#
题目重述#
给定长度同为 $n$ 的数组 $p$、$s$。若存在数组 $a$（整数），满足对所有 $1 \le i \le n$：
$$
p_i = \gcd(a_1,\dots,a_i), \qquad
s_i = \gcd(a_i,\dots,a_n),
$$
则输出 Yes，否则输出 No。
数据范围（多组测试）：$\sum n \le 10^5$，元素 $\le 10^9$。
基本性质#
前缀单调整除链
因为
$$
p_i = \gcd(p_{i-1}, a_i),
$$
必有 $p_i \mid p_{i-1}$。若对某 $i>1$ 不成立，则无解。
后缀单调整除链
因为
$$
s_i = \gcd(a_i, s_{i+1}),
$$
必有 $s_i \mid s_{i+1}$（读作从左到右非增、或从右到左非减）。若某处不整除，则无解。
边界一致性（首、尾）
- $a_1 = p_1$，因此应有
$$
s_1 = \gcd(a_1, s_2) = \gcd(p_1, s_2).
$$
- $a_n = s_n$，因此应有
$$
p_n = \gcd(p_{n-1}, a_n) = \gcd(p_{n-1}, s_n).
$$
（顺便注意：整体 $\gcd(a_1,\dots,a_n) = p_n = s_1$，但上述两条已经隐含该一致性；显式再判一次亦可。）
中间位置的可构造性判定#
考虑任意中间下标 $i$，$1 < i < n$（数学 1-based；代码中对应 1 <= i < n-1 的 0-based 索引）。
记
$$
P = p_i,\quad S = s_i,\quad g = \gcd(P,S),\quad
A = \frac{S}{g},\quad B = \frac{P}{g}.
$$
由于前缀、后缀链整除，可写
$$
p_{i-1} = P \cdot t, \qquad s_{i+1} = S \cdot u,
$$
其中 $t, u$ 为正整数。
我们要找某 $a_i$，使
$$
\gcd(p_{i-1}, a_i) = P, \qquad \gcd(a_i, s_{i+1}) = S.
$$
任一可行 $a_i$ 必至少含有 $P$ 与 $S$ 的所有质因子，因此我们设想
$$
a_i = g \cdot A \cdot B \cdot x \quad(\text{额外因子 } x \ge 1).
$$
代入第一式：
$$
\gcd(p_{i-1}, a_i)
= \gcd(Pt, gABx)
= gB \cdot \gcd(t, Ax).
$$
要令其恰好等于 $P = gB$，需 $\gcd(t, A) = 1$（额外因子 $x$ 可取与 $t$ 互质，故关键在 $t$ 与 $A$ 本身互质）。
同理第二式：
$$
\gcd(a_i, s_{i+1})
= \gcd(gABx, Su)
= gA \cdot \gcd(Bx, u)
$$
要等于 $S = gA$，需 $\gcd(B, u) = 1$。
因此判定条件：
$$
\gcd!\Big(\frac{S}{g}, \frac{p_{i-1}}{P}\Big) = 1
\quad\text{且}\quad
\gcd!\Big(\frac{P}{g}, \frac{s_{i+1}}{S}\Big) = 1.
$$
若所有中间位置均满足，说明可为每个位置选出满足两端 GCD 约束的 $a_i$（直接取 $x=1$ 即可）。
判定算法#
设数组 0-based 索引，输入 p[0..n-1], s[0..n-1]。
- 特判 $n=1$：返回
p[0]==s[0]。 - 检查前缀链：
p[i-1] % p[i] == 0 对所有 i=1..n-1。 - 检查后缀链：
s[i+1] % s[i] == 0 对所有 i=0..n-2。 - 边界：
gcd(p[0], s[1]) == s[0]gcd(p[n-2], s[n-1]) == p[n-1]
- 中间互质性循环（
i=1..n-2）：1
2
3
4
| P = p[i], S = s[i], g = gcd(P,S)
A = S/g, B = P/g
t = p[i-1]/P, u = s[i+1]/S
require gcd(A, t) == 1 and gcd(B, u) == 1
|
ac code#
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
| //F0rsyth1a
#include<iostream>
#include<algorithm>
#include<random>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#ifdef PBDS
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/priority_queue.hpp>
#endif
#define lowbit(x) (x&-x)
#define fi first
#define se second
using namespace std;
using LL = int;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
#define IOS
#define CF
// #define FRE
// #define PBDS
void solve()
{
int n; cin>>n;
vector<LL> p(n), s(n);
for(auto &x : p) cin >> x;
for(auto &x : s) cin >> x;
if(n == 1){
cout << (p[0] == s[0] ? "Yes" : "No") << "\n";
return;
}
bool ok = 1;
for(int i = 1; i < n && ok; i ++)
if(p[i - 1] % p[i]) ok = 0;
for(int i = n - 2; i >= 0 && ok; i --)
if(s[i + 1] % s[i]) ok = 0;
if(ok && __gcd(p[0], s[1]) != s[0]) ok = 0;
if(ok && __gcd(p[n - 2], s[n - 1]) != p[n - 1]) ok = 0;
for(int i = 1; i < n - 1 && ok; i ++){
LL P = p[i], S = s[i], g = __gcd(P, S);
LL A = S / g,
B = P / g,
t = p[i - 1] / P,
u = s[i + 1] / S;
if(__gcd(A, t) != 1 || __gcd(B, u) != 1){
ok = 0;
break;
}
}
cout << (ok ? "Yes" : "No") << "\n";
}
int main()
{
#ifdef IOS
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#endif
#ifdef FRE
freopen(".in", "r", stdin); freopen(".out", "w", stdout);
#endif
int Case = 1;
#ifdef CF
cin >> Case;
#endif
while(Case --) solve();
return 0;
}
|