2021CCPC黑龙江省赛题解ADFHIJKL
2021CCPC黑龙江省赛题解ADFHIJKL
K. Keep Eating
题意
有 n ( 1 ≤ n ≤ 2 e 5 ) n\ \ (1\leq n\leq 2\mathrm{e}5) n (1≤n≤2e5)块蛋糕,重量分别为 a 1 , ⋯ , a n ( 1 ≤ a i ≤ 1 e 6 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 1\mathrm{e}6) a1,⋯,an (1≤ai≤1e6).每次某人只能吃不超过当前蛋糕的重量的一半的重量,且他不吃重量小于 k ( 2 ≤ k ≤ 1 e 6 ) k\ \ (2\leq k\leq 1\mathrm{e}6) k (2≤k≤1e6)的蛋糕.此外,他可合并两块蛋糕,合并的蛋糕的重量等于原来两蛋糕的重量之和.求他最多能吃多少蛋糕.
思路
先将所有蛋糕拼在一起,设总重量为 s u m sum sum.
①若 s u m < k sum<k sum<k,则他不能吃到任何蛋糕.
②若 s u m ≥ k sum\geq k sum≥k,最优策略:先吃 ( s u m − k ) (sum-k) (sum−k)的重量,再吃剩下的 k k k的重量中的 ⌊ k 2 ⌋ \left\lfloor\dfrac{k}{2}\right\rfloor ⌊2k⌋.
不能吃到的重量为 ⌈ k 2 ⌉ \left\lceil\dfrac{k}{2}\right\rceil ⌈2k⌉,故他能吃到的重量为 s u m − ⌈ k 2 ⌉ sum-\left\lceil\dfrac{k}{2}\right\rceil sum−⌈2k⌉.
代码 -> 2021CCPC黑龙江省赛-K(思维)
void solve() {
int n, k; cin >> n >> k;
ll sum = 0;
while (n--) {
int a; cin >> a;
sum += a;
}
cout << (sum >= k ? sum - (k + 1) / 2 : 0);
}
int main() {
solve();
}
J. JOJO’s Factory
题意
有A型机器和B型机器各 n ( 5 ≤ n ≤ 5 e 5 ) n\ \ (5\leq n\leq 5\mathrm{e}5) n (5≤n≤5e5)台,每台A型机器必须与有且只有一台B型机器一起工作,每台B型机器必须与有且只有一台A型机器一起工作.现有 m ( 0 ≤ m ≤ 2 n − 3 ) m\ \ (0\leq m\leq 2n-3) m (0≤m≤2n−3)个数对 ( i , j ) ( 1 ≤ i , j ≤ n ) (i,j)\ \ (1\leq i,j\leq n) (i,j) (1≤i,j≤n),表示第 i i i个A型机器与第 j j j个B型机器不能一起工作.问最多有多少对机器同时工作.
思路
只考虑A型机器,设 n n n台B型机器都无限制,对此求得答案 a n s l ansl ansl.同理只考虑B型机器,求得答案 a n s r ansr ansr.最终答案 a n s = min { a n s l , a n s r } ans=\min\{ansl,ansr\} ans=min{ansl,ansr}.
只考虑A型机器,设 n n n台B型机器都无限制.一台A型机器能与B型机器工作的充要条件是:该A型机器的出度 < n <n <n.
[证] (必) 若该A型机器的出度 ≥ n \geq n ≥n,显然它无法与任一B型机器工作.
(充) 只需证明A型机器的出度 < n <n <n时能构造出一组解.
考虑最坏的情况, A 1 A_1 A1向 B 1 , ⋯ , B n − 1 B_1,\cdots,B_{n-1} B1,⋯,Bn−1连边,则 A 1 A_1 A1要工作只能与 B n B_n Bn.
再让 A 2 , ⋯ , A n A_2,\cdots,A_n A2,⋯,An向 B n B_n Bn连边将 B n B_n Bn占据,此时 A 1 A_1 A1无法工作,且当前共连了 ( 2 n − 2 ) (2n-2) (2n−2)条边.
而边数 ≤ 2 n − 3 \leq 2n-3 ≤2n−3,故必能构造出一组解.
代码 -> 2021CCPC黑龙江省赛-J(思维)
const int MAXN = 1e6 + 5;
int n, m; // 节点数、边数
int outl[MAXN], outr[MAXN]; // 左右节点的出度
void solve() {
cin >> n >> m;
int ansl = n, ansr = n;
while (m--) {
int i, j; cin >> i >> j;
outl[i]++, outr[j]++;
if (outl[i] >= n) ansl--;
if (outr[j] >= n) ansr--;
}
cout << min(ansl, ansr);
}
int main() {
solve();
}
D. Doin’ Time
题意
有一长度为 n ( 1 ≤ n ≤ 300 ) n\ \ (1\leq n\leq 300) n (1≤n≤300)的序列 a 1 , ⋯ , a n ( 1 ≤ a i ≤ 1 e 6 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 1\mathrm{e}6) a1,⋯,an (1≤ai≤1e6),每次操作可选一个下标 x x x,合并 a x a_x ax和 a x + 1 a_{x+1} ax+1为 a x ⋅ a x + 1 m o d 1000003 a_x\cdot a_{x+1}\ \mathrm{mod}\ 1000003 ax⋅ax+1 mod 1000003,并得到 ( a x − a x + 1 ) 2 (a_x-a_{x+1})^2 (ax−ax+1)2的分数.求最大得分.
思路
d p [ l ] [ r ] dp[l][r] dp[l][r]表示合并区间 [ l , r ] [l,r] [l,r]中的数的最大得分.
对区间 [ l , r ] [l,r] [l,r],枚举分界点 k ( l ≤ k < r ) k\ \ (l\leq k<r) k (l≤k<r),
状态转移方程: d p [ l ] [ r ] = max l ≤ k < r d p [ l ] [ k ] + d p [ k + 1 ] [ r ] + ( ∏ i = k + 1 r a [ i ] − ∏ i = l l a [ i ] ) 2 \displaystyle dp[l][r]=\max_{l\leq k<r} dp[l][k]+dp[k+1][r]+\left(\prod_{i=k+1}^r a[i]-\prod_{i=l}^l a[i]\right)^2 dp[l][r]=l≤k<rmaxdp[l][k]+dp[k+1][r]+(i=k+1∏ra[i]−i=l∏la[i])2.
暴力转移时间复杂度 O ( n 4 ) O(n^4) O(n4),显然可用前缀积优化到 O ( n 3 ) O(n^3) O(n3).
注意预处理前缀积的逆元.
代码 -> 2021CCPC黑龙江省赛-D(区间DP)
const int MAXN = 305;
const int MOD = 1e6 + 3;
int n;
int pre[MAXN]; // 原数组的前缀积
int inv[MAXN]; // inva[i]为pre[i]的逆元
ll dp[MAXN][MAXN]; // dp[l][r]表示合并区间[l,r]中的数的最大得分
void solve() {
cin >> n;
pre[0] = inv[0] = 1;
for (int i = 1; i <= n; i++) {
cin >> pre[i];
pre[i] = (ll)pre[i] * pre[i - 1] % MOD;
inv[i] = qpow(pre[i], MOD - 2, MOD);
}
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for (int k = l; k < r; k++) { // 枚举分界点
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r]
+ ((ll)pre[r] * inv[k] % MOD - (ll)pre[k] * inv[l - 1] % MOD) * ((ll)pre[r] * inv[k] % MOD - (ll)pre[k] * inv[l - 1] % MOD));
}
}
}
cout << dp[1][n];
}
int main() {
solve();
}
F. Function
题意
对正整数 n n n,定义函数 f ( n ) = { 1 , n = { 1 } ⋃ p r i m e s p ⋅ f ( p k − 2 ) , n = p k ( p ∈ p r i m e s , k > 1 ) f ( p 1 e 1 ) ∏ i = 2 r p i e i , n = ∏ i = 1 r p i e i ( p 1 < ⋯ < p r ; p i ∈ p r i m e s , r ≥ 2 ) f(n)=\begin{cases}1,n=\{1\}\bigcup primes \\ p\cdot f(p^{k-2}),n=p^k\ \ (p\in primes,k>1) \\ \displaystyle f(p_1^{e_1})\prod_{i=2}^r p_i^{e_i},n=\prod_{i=1}^r p_i^{e_i}\ \ (p_1<\cdots<p_r;p_i\in primes,r\geq 2)\end{cases} f(n)=⎩ ⎨ ⎧1,n={1}⋃primesp⋅f(pk−2),n=pk (p∈primes,k>1)f(p1e1)i=2∏rpiei,n=i=1∏rpiei (p1<⋯<pr;pi∈primes,r≥2).
给定整数 n ( 1 ≤ n ≤ 1 e 7 ) n\ \ (1\leq n\leq 1\mathrm{e}7) n (1≤n≤1e7),求 ∑ i = 1 n f ( i ) \displaystyle\sum_{i=1}^n f(i) i=1∑nf(i).数据保证答案不超过 2 64 − 1 2^{64}-1 264−1.
思路
显然可用线性筛求 f ( n ) f(n) f(n).
f ( p ) = 1 , f ( p 2 ) = p ⋅ f ( 1 ) = p , f ( p 3 ) = p ⋅ f ( p ) = p , f ( p 4 ) = p ⋅ f ( p 2 ) = p 2 f(p)=1,f(p^2)=p\cdot f(1)=p,f(p^3)=p\cdot f(p)=p,f(p^4)=p\cdot f(p^2)=p^2 f(p)=1,f(p2)=p⋅f(1)=p,f(p3)=p⋅f(p)=p,f(p4)=p⋅f(p2)=p2,故 f ( p k ) = p ⌊ k 2 ⌋ f(p^k)=p^{\left\lfloor\frac{k}{2}\right\rfloor} f(pk)=p⌊2k⌋.
设 n = p s q n=p^s q n=psq,其中 p s p^s ps为 n n n的最小素因子之积, q q q为 n n n的其余素因子之积.则 f ( n ) = p ⌊ s 2 ⌋ q f(n)=p^{\left\lfloor\frac{s}{2}\right\rfloor}q f(n)=p⌊2s⌋q.
代码 -> 2021CCPC黑龙江省赛-F(线性筛)
const int MAXN = 1e7 + 5;
int primes[MAXN], cnt; // 存素数
bool state[MAXN]; // 记录每个数是否被筛掉
ll init(int n) { // 线性筛
ll res = 1; // f(1)=1
for (int i = 2; i <= n; i++) {
if (!state[i]) { // 素数
primes[cnt++] = i;
res++; // f(p)=1
}
for (int j = 0; primes[j] <= n / i; j++) {
state[primes[j] * i] = true;
if (i % primes[j] == 0) { // primes[j]是i的最小素因子
int s = 1; // 最小素因子的次数,次数为1因为q从i开始而不是从primes[j]*i开始
int q = i; // 其他素因子之积
while (q % primes[j] == 0) q /= primes[j], s++;
ll tmp = 1;
for (int i = 0; i < s / 2; i++) tmp *= primes[j];
res += tmp * q;
break;
}
// primes[j]是primes[j]*i的最小素因子,次数为1
res += i; // f(primes[j]^1)*i
}
}
return res;
}
void solve() {
int n; cin >> n;
cout<< init(n);
}
int main() {
solve();
}
H. Hack DSU!
题意
int find(int x) {
while (x != parent[x]) {
if (x < parent[x]) parent[x] = parent[parent[x]];
x = parent[x];
counter++;
}
return x;
}
void merge(int a, int b) {
a = find(a), b = find(b);
parent[a] = b;
}
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i++) parent[i] = i;
for (int i = 1; i <= n; i++) {
int a, b; cin >> a >> b;
merge(a, b);
}
for (int i = 1; i <= n; i++)
if (i == find(i)) ans++;
cout << ans << endl;
}
输入两个整数 n , t ( 10 ≤ n ≤ 1 e 4 , n ≤ t ≤ n 2 log 2 n ) n,t\ \ \left(10\leq n\leq 1\mathrm{e}4,n\leq t\leq \dfrac{n^2}{\log_2 n}\right) n,t (10≤n≤1e4,n≤t≤log2nn2).输出 n n n个数对 ( a , b ) ( 1 ≤ a , b ≤ n ) (a,b)\ \ (1\leq a,b\leq n) (a,b) (1≤a,b≤n),使得上述代码执行结束后find()函数中 c o u n t e r > t counter>t counter>t.
思路
c o u n t e r counter counter表示查询一个节点的根节点时需向上走的步数.为使得 c o u n t e r counter counter尽可能大,应尽可能地保证不路径压缩,即不进入find()中的if,亦即保证每个集合的根节点的编号都$\leq $其儿子节点的编号.
显然可构造一条包含 n n n个节点的链,其中节点 ( i + 1 ) (i+1) (i+1)的父节点为节点 i i i,根节点为节点 1 1 1,这样 f i n d ( n ) find(n) find(n)时需一步一步向上走到节点 1 1 1,时间复杂度 O ( n 2 ) O(n^2) O(n2).而 n > n> n>时, O ( n 2 ) > O ( n 2 log 2 n ) O(n^2)>O\left(\dfrac{n^2}{\log_2 n}\right) O(n2)>O(log2nn2),故满足要求.
构造一条链只需 ( n − 1 ) (n-1) (n−1)对 ( a , b ) (a,b) (a,b),最后一对可取 ( 1 , n ) (1,n) (1,n).
代码 -> 2021CCPC黑龙江省赛-H(并查集路径压缩+思维)
void solve() {
int n, t; cin >> n >> t;
for (int i = n; i; i--)
cout << i << ' ' << (i - 1 ? i - 1 : n) << endl;
}
int main() {
solve();
}
A. And RMQ
题意 ( 3 s 3\ \mathrm{s} 3 s)
维护一个序列 { a n } \{a_n\} {an},支持如下操作:
① A N D l r v AND\ l\ r\ v AND l r v,表示将所有 a i ( l ≤ i ≤ r ) a_i\ \ (l\leq i\leq r) ai (l≤i≤r)变为 a i & v ( 1 ≤ v ≤ 2 30 − 1 ) a_i\ \&\ v\ \ (1\leq v\leq 2^{30}-1) ai & v (1≤v≤230−1).
② U P D x v UPD\ x\ v UPD x v,表示将 a x ( 1 ≤ x ≤ n ) a_x\ \ (1\leq x\leq n) ax (1≤x≤n)变为 v ( 1 ≤ v ≤ 2 30 − 1 ) v\ \ (1\leq v\leq 2^{30}-1) v (1≤v≤230−1).
③ Q U E l r QUE\ l\ r QUE l r,表示询问区间 [ l , r ] ( 1 ≤ l , r ≤ n ) [l,r]\ \ (1\leq l,r\leq n) [l,r] (1≤l,r≤n)中的最大值.
第一行输入两个整数 n , m ( 1 ≤ n , m ≤ 4 e 5 ) n,m\ \ (1\leq n,m\leq 4\mathrm{e}5) n,m (1≤n,m≤4e5),表示序列长度和操作数.第二行输入 n n n个整数 a 1 , ⋯ , a n ( 1 ≤ a i ≤ 2 30 − 1 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 2^{30}-1) a1,⋯,an (1≤ai≤230−1).接下来 m m m行每行输入一个操作,格式如上.
思路
在每个节点处维护一个 31 31 31位的二进制数作为势能函数,记录每个节点所代表的区间的元素值的二进制表示中 0 0 0的位置,其中叶子节点的势能函数等于其对应元素的值,父节点的势能函数等于其两个子节点的势能函数值相或.如左右区间的势能函数分别为 0110001 0110001 0110001和 0011001 0011001 0011001,则它们的父节点的势能函数为 0111001 0111001 0111001.
对区间与操作,若对 v v v的二进制表示中为 0 0 0的位置,当前区间的势能函数值的二进制表示对应数位也为 0 0 0,则该操作对该区间无影响,直接返回;否则递归修改到左右两区间.如对上述父节点所表示的区间与 v = ( 0011011 ) 2 v=(0011011)_2 v=(0011011)2时,先将 v v v按位取反得 v ′ = ( 1100100 ) 2 v'=(1100100)_2 v′=(1100100)2.因 ( 0111001 ) & v ′ ≠ 0 (0111001)\ \&\ v'\neq 0 (0111001) & v′=0,递归到左右区间.对左区间,因 ( 0110001 ) 2 & v ′ ≠ 0 (0110001)_2\ \&\ v'\neq 0 (0110001)2 & v′=0,继续递归;对右区间,因 ( 0011001 ) 2 & v ′ = 0 (0011001)_2\ \&\ v'=0 (0011001)2 & v′=0,直接返回.
代码 -> 2021CCPC黑龙江省赛-A(势能线段树)
const int MAXN = 4e5 + 5;
int n, m; // 序列长度、操作数
int a[MAXN];
struct Node {
int l, r; // 区间左右端点
int maxnum; // 区间最大值
bitset<31> lazy; // 势能函数
}SegT[MAXN << 2];
void push_up(int u) {
SegT[u].maxnum = max(SegT[u << 1].maxnum, SegT[u << 1 | 1].maxnum);
SegT[u].lazy = SegT[u << 1].lazy | SegT[u << 1 | 1].lazy;
}
void build(int u, int l, int r) {
SegT[u].l = l, SegT[u].r = r;
if (l == r) {
SegT[u].maxnum = a[l];
SegT[u].lazy = bitset<31>(a[l]);
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
push_up(u);
}
void modify_and(int u, int l, int r, int x) { // [l,r] &= x
bitset<31> tmpx(x);
bitset<31> rtmpx(tmpx);
rtmpx.flip();
if ((rtmpx & SegT[u].lazy).none()) return; // 本操作不会对该区间产生影响
if (SegT[u].l == SegT[u].r) { // 暴力修改叶子节点
SegT[u].maxnum &= x;
SegT[u].lazy &= tmpx;
return;
}
int mid = SegT[u].l + SegT[u].r >> 1;
if (l <= mid) modify_and(u << 1, l, r, x);
if (r > mid) modify_and(u << 1 | 1, l, r, x);
push_up(u);
}
void modify(int u, int x, int v) { // a[x]=v
if (SegT[u].l == SegT[u].r) { // 叶子节点
SegT[u].maxnum = v;
SegT[u].lazy = bitset<31>(v);
return;
}
int mid = SegT[u].l + SegT[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
push_up(u);
}
int query(int u, int l, int r) { // 询问[l,r]的最大值
if (l <= SegT[u].l && SegT[u].r <= r) return SegT[u].maxnum;
int mid = SegT[u].l + SegT[u].r >> 1;
int res = -INF;
if (l <= mid) res = max(res, query(u << 1, l, r));
if (r > mid) res = max(res, query(u << 1 | 1, l, r));
return res;
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (m--) {
string op; cin >> op;
if (op == "AND") {
int l, r, v; cin >> l >> r >> v;
modify_and(1, l, r, v);
}
else if (op == "UPD") {
int x, v; cin >> x >> v;
modify(1, x, v);
}
else {
int l, r; cin >> l >> r;
cout << query(1, l, r) << endl;
}
}
}
int main() {
solve();
}
L. Labi-Ribi
题意
初始时有编号 1 ∼ n 1\sim n 1∼n的 n n n个关卡,其中第 i i i个关卡的BOSS等级为 h i h_i hi,玩家只有等级不小于BOSS的等级时才能打败BOSS,打败BOSS后其他所有未打败的BOSS等级加 a i a_i ai,玩家等级加 b i b_i bi.求通过所有关卡的最小初始等级.现有 q q q个新增关卡,每个关卡包含三个整数 h i , a i , b i h_i,a_i,b_i hi,ai,bi,意义同上.每新增一个关卡后,求通过所有关卡的最小初始等级.
第一行输入一个整数 n ( 1 ≤ n ≤ 1 e 5 ) n\ \ (1\leq n\leq 1\mathrm{e}5) n (1≤n≤1e5),表示初始关卡数.第二行输入 n n n个整数 h 1 , ⋯ , h n ( − 1 e 9 ≤ h i ≤ 1 e 9 ) h_1,\cdots,h_n\ \ (-1\mathrm{e}9\leq h_i\leq 1\mathrm{e}9) h1,⋯,hn (−1e9≤hi≤1e9).接下来 n n n行每行输入两个整数 a i , b i ( − 1 e 9 ≤ a i , b i ≤ 1 e 9 ) a_i,b_i\ \ (-1\mathrm{e}9\leq a_i,b_i\leq 1\mathrm{e}9) ai,bi (−1e9≤ai,bi≤1e9).接下来一行输入一个整数 q ( 0 ≤ q ≤ 1000 ) q\ \ (0\leq q\leq 1000) q (0≤q≤1000),表示新增关卡数.接下来 q q q行每行输入三个整数 h i , a i , b i ( − 1 e 9 ≤ h i , a i , b i ≤ 1 e 9 ) h_i,a_i,b_i\ \ (-1\mathrm{e}9\leq h_i,a_i,b_i\leq 1\mathrm{e}9) hi,ai,bi (−1e9≤hi,ai,bi≤1e9).
先输出通过所有初始关卡的最小初始等级.对每个新增关卡,输出新增该关卡后通过所有关卡的最小初始等级.
思路
显然只需考虑 c i = b i − a i c_i=b_i-a_i ci=bi−ai,问题转化为:有 n n n个物品,能量分别为 h 1 , ⋯ , h n h_1,\cdots,h_n h1,⋯,hn,只有自身能量 ≥ h i \geq h_i ≥hi时才能拿第 i i i个物品,且拿完后自身能量 + = c i +=c_i +=ci,求拿完所有物品所需的最小初始能量.
显然应先拿 c ≥ 0 c\geq 0 c≥0的物品,并按 h h h升序拿.
对 c < 0 c<0 c<0的物品,可能出现先拿物品 i i i就不能拿物品 j j j,但先拿物品 j j j还可拿物品 i i i的情况.设当前能量为 c u r cur cur,则 c u r + c i < h j , c u r + c j ≥ h i cur+c_i<h_j,cur+c_j\geq h_i cur+ci<hj,cur+cj≥hi,整理得 h i + c i < h j + c j h_i+c_i<h_j+c_j hi+ci<hj+cj,故将 c < 0 c<0 c<0的物品按 h + c h+c h+c值降序排列,对 h + c h+c h+c值相等的物品,显然应先拿 h h h大的.
可将 n n n个初始关卡的最后一个也作为一个询问,若每次询问都对序列排序,总时间复杂度 O ( ( n − 1 ) log ( n − 1 ) + ∑ i = 1 q + 1 ( n − 1 + i ) log ( n − 1 + i ) ) = O ( q n log n ) \displaystyle O\left((n-1)\log(n-1)+\sum_{i=1}^{q+1}(n-1+i)\log(n-1+i)\right)=O(qn\log n) O((n−1)log(n−1)+i=1∑q+1(n−1+i)log(n−1+i))=O(qnlogn),最坏为 1.6 e 9 1.6\mathrm{e}9 1.6e9,会TLE.考虑优化,不将 n n n个初始关卡的最后一个作为询问,注意到每次插入一个新关卡再排序后,大部分关卡的顺序不变,故可直接扫一遍已有序的关卡,将新关卡插入到排序后的位置.总时间复杂度 O ( n log n + ∑ i = 1 q ( n + i − 1 ) ) = O ( n log n + q ( 2 n + q − 1 ) 2 ) ≤ O ( n q ) \displaystyle O\left(n\log n+\sum_{i=1}^q (n+i-1)\right)=O\left(n\log n+\dfrac{q(2n+q-1)}{2}\right)\leq O(nq) O(nlogn+i=1∑q(n+i−1))=O(nlogn+2q(2n+q−1))≤O(nq),最坏 1 e 8 1\mathrm{e}8 1e8,可过.
注意cal()函数中的初始等级和当前等级初始化为 − I N F -INF −INF,因为可能所有BOSS的等级都是负的.注意答案可能爆int.
代码 -> 2021CCPC黑龙江省赛-L(贪心)
const int MAXN = 1e5 + 5;
int n;
struct Stage {
int h, a, b;
ll c;
bool operator<(const Stage& B)const {
if (c >= 0 && B.c >= 0) return h < B.h; // c≥0的物品按h升序排列
else if (c < 0 && B.c < 0) return h + c > B.h + B.c; // c<0的物品按h+c降序排列
else return c > B.c; // c≥0的物品排在前
}
};
vector<Stage> stages;
ll cal() {
ll res = -INFF; // 初始等级
ll cur = -INFF; // 当前等级
for (auto& st : stages) {
res += cur >= st.h ? 0 : st.h - cur;
cur += st.c + (cur >= st.h ? 0 : st.h - cur);
}
return res;
}
void solve() {
cin >> n;
stages.resize(n);
for (int i = 0; i < n; i++) cin >> stages[i].h;
for (int i = 0; i < n; i++) {
int a, b; cin >> a >> b;
stages[i].a = a, stages[i].b = b, stages[i].c = b - a;
}
sort(all(stages));
cout << cal() << endl;
CaseT{
int h,a,b; cin >> h >> a >> b;
Stage st({ h, a, b, b - a });
// 将新的关卡插到排序后的位置
bool ok = false;
for (int i = 0; i < stages.size(); i++) {
if (st < stages[i]) {
stages.insert(stages.begin() + i, st);
ok = true;
break;
}
}
if (!ok) stages.push_back(st);
cout << cal() << endl;
}
}
int main() {
solve();
}
I. ICU4C
题意
Alice和Bob交替地在网格上移动棋子,Alice先手,无法进行操作者输…每一步可选择一个棋子 P P P将其往右移动一格,同时满足下列所有条件的棋子也会同时向右移动一格:①与 P P P在同一赛道;②在 P P P的正右边;③与 P P P相连.两棋子 x , y x,y x,y相连当且仅当 x x x与 y y y间无间隔格子或它们都与棋子 z z z相连.若某次操作的最右边的棋子已接触终点线,则本次操作不合法,不可进行.有 n n n条赛道同时进行该游戏.对每条赛道,给定其上的棋子数 m m m,棋子的初始位置 x x x和终点线的位置 e e e.问谁最后胜利.
有 t ( 1 ≤ t ≤ 20 ) t\ \ (1\leq t\le 20) t (1≤t≤20)组测试数据.每组测试数据第一行输入一个整数 n ( 1 ≤ n ≤ 1000 ) n\ \ (1\leq n\leq 1000) n (1≤n≤1000),表示赛道数.每个赛道用两行输入描述:第一行输入两整数 m , e ( 1 ≤ m ≤ 1000 , 1 ≤ e ≤ 1 e 9 ) m,e\ \ (1\leq m\leq 1000,1\leq e\leq 1\mathrm{e}9) m,e (1≤m≤1000,1≤e≤1e9),分别表示赛道上的棋子数和终点线的位置…第二行输入 m m m个整数 x 1 , ⋯ , x m ( 1 ≤ x i ≤ e ) x_1,\cdots,x_m\ \ (1\leq x_i\leq e) x1,⋯,xm (1≤xi≤e),分别表示该赛道上棋子的初始位置.数据保证对 ∀ i < j \forall i<j ∀i<j,有 x i < x j x_i<x_j xi<xj.数据保证每组测试数据的所有赛道的 m m m之和不超过 1.5 e 6 1.5\mathrm{e}6 1.5e6.
思路
先考虑只有一条赛道的情况.因连在一起的棋子会同时移动,可将每个棋子右边的空格数视为其所在的台阶数,转化为台阶的Nim游戏.考察奇数级台阶上的棋子数的异或和是否为 0 0 0即可.
考虑有多条赛道的情况.取每一条赛道的奇数级台阶上的棋子数的异或和为该赛道的SG函数,考察所有赛道的SG函数的异或和是否为 0 0 0即可.总时间复杂度 O ( t m ) O\left(tm\right) O(tm).
代码 -> 2021CCPC黑龙江省赛-I(Nim游戏)
void solve() {
int ans = 0;
CaseT{
int m,e; cin >> m >> e;
map<int, int> cnt; // 记录每个棋子右边的空格数
for (int j = m - 1; j >= 0; j--) {
int x; cin >> x;
cnt[e - x - j]++;
}
for (auto& [u, v] : cnt)
if (u & 1) ans ^= v;
}
cout << (ans ? "Alice" : "Bob") << endl;
}
int main() {
CaseT // 单测时注释掉该行
solve();
}