目前进度：
| solved contest |
solved contest |
solved contest |
solved contest |
solved later |
solved later |
简要翻译
给定一个数列 \(a\)， 每次操作可以将某个数 \(+1\)，求使中位数变大的最少操作数。
思路解析
排序后考虑中位数及其右侧，让中位数 \(+1\) 必须让与中位数相等的数都 \(+1\)。
代码
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
| #include <algorithm>
#include <cstdio>
#include <vector>
namespace Input{
const int BUFFLEN = 1 << 20;
char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
inline char getc(){
if(p1 == p2)
p1 = buf,
p2 = buf + fread(buf, 1, BUFFLEN, stdin);
return p1 == p2? EOF: *p1++;
}
inline bool isdgt(const char op){return op >= '0' && op <= '9';}
inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
long long read(){
static long long res; static char op, f;
for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
return f? -res: res;
}
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 300010;
int a[N], n;
void solve(){
n = read();
for(int i = 1; i <= n; ++i)
a[i] = read();
sort(a + 1, a + n + 1);
int p = (n - 1) / 2 + 1;
if(n == 1)
printf("1\n");
else{
int ans = 0;
for(int i = p; i <= n; ++i)
if(a[i] == a[p])
ans++;
printf("%d\n", ans);
}
}
signed main(int argc,char **argv){
int T = read();
while(T--) solve();
return 0;
}
|
B. Maximum Sum
简要翻译
给定一个序列 \(a\)，每次可以将一个子段的和（可以为空，此时和为 \(0\)）插入 \(a\) 中，求恰好 \(k\) 次操作后序列和的最大值。
思路解析
设 \(a\) 的最大子段和为 \(x\)，那每一步可以将 \(x\) 插入到最大子段的旁边，新的最大字段和变为 \(2x\)。
这样操作 \(k\) 次，获得的增量为 \(x \times (2^k - 1)\)。\(k\) 不大，所以可以不用快速幂。
代码
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
| #include <algorithm>
#include <cstdio>
#include <vector>
namespace Input{
const int BUFFLEN = 1 << 20;
char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
inline char getc(){
if(p1 == p2)
p1 = buf,
p2 = buf + fread(buf, 1, BUFFLEN, stdin);
return p1 == p2? EOF: *p1++;
}
inline bool isdgt(const char op){return op >= '0' && op <= '9';}
inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
long long read(){
static long long res; static char op, f;
for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
return f? -res: res;
}
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 300010;
const ll mod = 1000000007;
ll a[N], n, k;
void solve(){
n = read(); k = read();
ll sum = 0, ans = 0, asum = 0;
for(int i = 1; i <= n; ++i){
a[i] = read();
sum += a[i];
asum += a[i];
if(sum < 0)
sum = 0;
ans = max(ans, sum);
}
asum %= mod;
asum = (asum + mod) % mod;
ans %= mod;
for(int i = 1; i <= k; ++i){
asum = (asum + ans) % mod;
ans = (ans << 1ll) % mod;
}
printf("%lld\n", asum);
}
signed main(int argc, char **argv){
int T = read();
while(T--) solve();
return 0;
}
|
C. Tree Cutting
简要翻译
给定一棵树，要求切掉 \(k\) 条边，求剩下的连通块最小值的最大值。
思路解析
最小连通块的最大值，听着就很像二分。那么考虑二分答案，转化为能不能凑出 \(k + 1\) 块大小为 \(lim\) 的连通块。
设 \(size_x\) 为 \(x\) 子树内大小为 \(x\) 的连通块个数，\(rest_x\) 表示 \(x\) 所在的连通块的大小。
对于一个待确定的连通块，如果它大小已经到达 \(lim\)，那么再合并其他的散点对于凑出答案不会更优。
所以在 \(rest_x \ge lim\) 时就断开即可。
首先有 \(size_x = \sum_{y} size_y\)，\(rest_x = \sum_{y} rest_x\)。
如果 \(rest_x \ge lim\)，则连通块在 \(x\) 处就可以断开，将 \(size_x + 1\)，并将 \(rest_x\) 清零。
赛时写法略有不同，但效果相同。
时间复杂度 \(\Theta(N \lg N)\)。
代码
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
| #include <algorithm>
#include <cstdio>
#include <vector>
namespace Input{
const int BUFFLEN = 1 << 20;
char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
inline char getc(){
if(p1 == p2)
p1 = buf,
p2 = buf + fread(buf, 1, BUFFLEN, stdin);
return p1 == p2? EOF: *p1++;
}
inline bool isdgt(const char op){return op >= '0' && op <= '9';}
inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
long long read(){
static long long res; static char op, f;
for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
return f? -res: res;
}
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 300010;
vector<int> ver[N];
int res[N], siz[N];
int n, m;
void dfs(int x, int fa, int lim){
siz[x] = 0; res[x] = 1;
for(int y : ver[x]){
if(y == fa) continue;
dfs(y, x, lim);
siz[x] += siz[y];
if(res[y] >= lim){
siz[x]++;
res[y] = 0;
}
res[x] += res[y];
}
}
bool chk(int lim){
dfs(1, 0, lim);
if(res[1] >= lim)
siz[1]++;
return siz[1] > m;
}
void solve(){
n = read(); m = read();
for(int i = 1; i <= n; ++i)
ver[i].clear();
for(int i = 1, x, y; i < n; ++i){
x = read(); y = read();
ver[x].emplace_back(y);
ver[y].emplace_back(x);
}
int l = 0, r = n, mid, ans;
while(l <= r){
mid = (l + r) >> 1;
if(chk(mid))
l = mid + 1, ans = mid;
else
r = mid - 1;
}
printf("%d\n",ans);
}
signed main(int argc, char **argv){
int T = read();
while(T--) solve();
return 0;
}
|
D. Birthday Gift
简要翻译
有一个数列 \(a\)，现在将其分为 \(k\) 个不相交区间，同时 \(k\) 个区间的并为 \([1, n]\)。
需要满足：\((a_{l_1} \oplus a_{l_1 + 1} \oplus \ldots \oplus a_{r_1}) | (a_{l_2} \oplus a_{l_2 + 1} \oplus \ldots \oplus a_{r_2}) | \ldots | (a_{l_k} \oplus a_{l_k + 1} \oplus \ldots \oplus a_{r_k}) \le x\)。
求 \(k\) 的最大值。
思路解析
先分析一下不等式的性质。设 \(S_i = a_1 \oplus a_2 \oplus \ldots \oplus a_i\)。
同时考虑到 \(r_i + 1 = l_{i + 1}, l_1 - 1 = 0, r_k = n\)。
则不等式左侧变为 \(A = (S_{r_1}) | (S_{r_1} \oplus S_{r_2}) | \ldots | (S_{r_{k-1}} \oplus S_{n})\)。
再来看单独的一位上如何限制。
如果 \(A = 0\)，那么 \(S_{r_1} = 0, (S_{r_1} \oplus S_{r_2}) = 0 \Rightarrow S_{r_2} = 0\)。 稍加分析，这一关系可以推至任意 \(S_{r_i}\)。
所以 \(A = 0\) 时一定有 \(S_{r_1} = S_{r_2} = \ldots = S_{n} = 0\)。
考虑其逆否命题，若 \(S_{r_1}, S_{r_2}, \ldots, S_{n}\) 中有至少一个值为 \(1\)，则有 \(A = 1\)。
所以如果 \(x\) 的第 \(k\) 位为 \(0\)，我们只能选则 \(S_p\) 第 \(k\) 位为 \(0\) 的 \(p\) 构成序列 \(r\)。
在推导过程中，可以发现 \(S_n\) 是必选项，所以如果 \(S_n\) 第 \(k\) 位为 \(1\) 时 \(A = 1\)，有 \(A \ge S_n\)。
直接的写法不会，想了一个二分答案，看我们能不能选出 \(lim\) 个右端点构成 \(r\)。
设当前在考虑第 \(k\) 位，当前位为 \(0\) 的 \(S\) 构成的集合为 \(\mathrm{now}\), 高位符合要求的集合为 \(\mathrm{bit}\)。
统计 \(\mathrm{bit}_i\ \&\ \mathrm{now}_i = 1\) 的位置个数 \(t\)。
如果 \(x\) 第 \(k\) 位为 \(1\) 而 \(t \ge lim\)，说明此位选 \(0\) 就可以满足要求，而低位选出的值无论是 \(0\) 是 \(1\) 都不影响 \(A < x\)；
如果 \(t < lim\)，则考虑不应用 \(\mathrm{now}\) 的限制，这一位在低位的计算中会取 \(1\)。
如果 \(x\) 第 \(k\) 位为 \(0\)，因为已经构造的 \(A\) 的高位和 \(x\) 相等，所以此位只能选 \(0\)。将 \(\mathrm{bit}\) 与 \(\mathrm{now}\) 求交集即可。
什么时候无解呢？上面有 \(A \ge S_n\)，所以 \(S_n > x\) 时无解；反之，选取区间 \([1, n]\) 一定成立，答案至少为 \(1\)。
时间复杂度 \(O(N\lg N \lg X)\)。
代码
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
| #include <algorithm>
#include <bitset>
#include <cstdio>
#include <vector>
namespace Input{
const int BUFFLEN = 1 << 20;
char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
inline char getc(){
if(p1 == p2)
p1 = buf,
p2 = buf + fread(buf, 1, BUFFLEN, stdin);
return p1 == p2? EOF: *p1++;
}
inline bool isdgt(const char op){return op >= '0' && op <= '9';}
inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
long long read(){
static long long res; static char op, f;
for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
return f? -res: res;
}
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 100010;
int n,x;
int sum[N];
bitset<N> bit,now;
bool chk(int lim){
for(int i = 1; i <= n; ++i)
bit.set(i, 1);
for(int k = 30, cnt = 0; ~k; cnt = 0, --k){
for(int i = 1; i <= n; ++i)
now.set(i, !((sum[i] >> k) & 1));
for(int i = 1; i <= n; ++i)
cnt += bit[i] & now[i];
if((x >> k) & 1){
if(cnt >= lim && (bit[n] & now[n]))
return true;
}
else{
if(cnt < lim || !(bit[n] & now[n]))
return false;
bit = bit & now;
}
}
return true;
}
void solve(){
n = read(); x = read();
for(int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] ^ read();
if(sum[n] > x){
puts("-1");
return;
}
int l = 0, r = n, mid, ans;
while(l <= r){
mid = (l + r) >> 1;
if(chk(mid))
l = mid + 1, ans = mid;
else
r = mid - 1;
}
printf("%d\n", ans);
}
signed main(int argc, char **argv){
int T = read();
while(T--) solve();
return 0;
}
|
E. Girl Permutation
简要翻译
对于一个排列，给定它的前缀最大值的位置序列、后缀最大值的位置序列，求可能的排列的数量。
前缀最大值的位置序列 \(p\)，指的是序列中的一个值 \(p_i\) 对应 \(v_{p_i}\) 是 \(v_1, v_2, \ldots, v_{p_i}\) 中的最大值。
后缀最大值类似。
思路解析
纯纯数学题。赛场上没想完，亏了。
设前缀最大值的位置序列为 \(a_1, a_2, \ldots, a_{m_1}\)，后缀最大值的位置序列为 \(b_1, b_2, \ldots, b_{m_2}\)。
根据定义不难得出 \(a_1 = 1, b_{m_1} = n\)。同时 \(v_p = n\) 的位置应该既是 \(a_{m_1}\) 又是 \(b_1\)。有一条不满足，则答案为 \(0\)。
显然前缀最大值和后缀最大值相交于 \(v_p = n\) 而不会交叉，所以两边可以分开计算。
同时我们可以把任意 \(m_1 - 1\) 个数放在 \(n\) 的左边，然后让它们按规则排列。这样答案就有一个基数 \(\binom{n - 1}{m_1 - 1}\)。
先算左边。设 \(f_i\) 为序列 \(1 \sim i\) 位置上的方案数。不妨先假设值域为 \([1, m_1]\)。
如果 \(i\) 是某个 \(a_j\)，那么 \(v_i\) 在前 \(i\) 个数排序后必须处于末尾，\(f_i = f_{i-1}\)；
否则 \(v_i\) 在前 \(i\) 个数排序后不能处于末尾，有 \(i - 1\) 个位置可供选择，\(f_i = f_{i-1} \times (i - 1)\)。
对后缀最大值的处理类似，不再赘述。
时间复杂度 \(\Theta(N)\)。
代码
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
| #include<algorithm>
#include<cstdio>
#include<vector>
namespace Input{
const int BUFFLEN = 1 << 20;
char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
inline char getc(){
if(p1 == p2)
p1 = buf,
p2 = buf + fread(buf, 1, BUFFLEN, stdin);
return p1 == p2? EOF: *p1++;
}
inline bool isdgt(const char op){return op >= '0' && op <= '9';}
inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
long long read(){
static long long res;static char op,f;
for(f = 0, op = getc(); !isdgt(op); op = getc())f |= (op == '-');
for(res = 0; isdgt(op); op = getc())res = res * 10 + (op ^ '0');
return f? -res: res;
}
int readstr(char *s){
static int len;static char op;
do op = getc(); while(!ischr(op));
for(len = 0; ischr(op); op = getc())s[len++] = op;
return len;
}
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 200010;
const ll mod = 1000000007;
ll fac[N], inv[N], invfac[N];
int pre[N], suf[N], n, m1, m2;
void init(){
fac[0] = fac[1] = 1;
inv[0] = inv[1] = 1;
invfac[0] = invfac[1] = 1;
for(int i = 2; i < N; ++i){
fac[i] = (fac[i - 1] * i) % mod;
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
invfac[i] = (invfac[i - 1] * inv[i]) % mod;
}
}
ll binom(int n, int m){
return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
void solve(){
n = read();
m1 = read();
m2 = read();
for(int i = 1; i <= m1; ++i)
pre[i] = read();
for(int i = 1; i <= m2; ++i)
suf[i] = read();
if(pre[1] != 1 || pre[m1] != suf[1] || suf[m2] != n){
printf("0\n");
return;
}
ll ans = 1;
for(int i = 1, p = 1; i <= pre[m1]; ++i)
if(i != pre[p])
ans = ans * (i-1ll) % mod;
else
p++;
for(int i = n, p = m2; i >= suf[1]; --i)
if(i != suf[p])
ans = ans * (n - i) % mod;
else
p--;
ans = ans * binom(n - 1, pre[m1] - 1) % mod;
printf("%lld\n", ans);
}
signed main(int argc, char **argv){
init();
int T=read();
while(T--)solve();
return 0;
}
|
F. Title
简要翻译
给定一个序列 \(a\)，每次查询一个区间，询问区间中子序列的数量，要求子序列中前一个数是后一个数的约数。
思路解析
这题 6s 时限，看上去会略超过 \(10^8\) 计算量。
区间用类扫描线的方法转化，在右端点加入集合的时候查询。
设 \(s_i\) 表示从 \(i\) 开始，到目前的右界 \(r\) 中合法子序列的数量。
当右界从 \(r - 1\) 移动到 \(r\) 时，所有新增的子序列必须以 \(r\) 结尾。
那么新增序列去掉 \(r\) 之后的末尾，它的值一定是 \(v_r\) 的约数。
我们可以将标记打在 \(\{p | (v_p | v_r)\}\) 上，这时候 \(p\) 就是新增序列的等效末尾，再用它来向前更新。
更新 \(s_i\) 之后就可以查询了。这里因为复杂度比较高，使用了树状数组来降低常数。
计算所有的 \(r\) 一共更新了多少个值，可以反过来算每个 \(v_i\) 的倍数出现的次数和。
因为 \(v\) 构成排列，这个数应当等于 \((\frac{N}{1} + \frac{N}{2} + \ldots + \frac{N}{N})\)，即 \(N\ln N\)。
所以总复杂度为 \(O(N\ln N \lg^2 N)\)，能卡过也是神奇。
代码
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
namespace Input{
const int BUFFLEN = 1 << 20;
char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
inline char getc(){
if(p1 == p2)
p1 = buf,
p2 = buf + fread(buf, 1, BUFFLEN, stdin);
return p1 == p2? EOF: *p1++;
}
inline bool isdgt(const char op){return op >= '0' && op <= '9';}
inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
long long read(){
static long long res;static char op,f;
for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
return f? -res: res;
}
int readstr(char *s){
static int len;static char op;
do op = getc(); while(!ischr(op));
for(len = 0; ischr(op); op = getc()) s[len++] = op;
return len;
}
}
using namespace std;
using Input::read;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1000010;
template<typename Tp, int LEN>
class BIT{
public:
void resize(int len);
void clear();
void add(int x, Tp v);
Tp ask(int x);
private:
Tp c[LEN];
int c_len;
};
template<typename Tp, int LEN>
void BIT<Tp, LEN>::clear(){
for(int x = 0; x <= c_len; x++) c[x] = 0;
}
template<typename Tp, int LEN>
void BIT<Tp, LEN>::resize(int len){
c_len = len;
clear();
}
template<typename Tp, int LEN>
void BIT<Tp, LEN>::add(int x, Tp v){
for(; x <= c_len; x += x & -x) c[x] += v;
}
template<typename Tp, int LEN>
Tp BIT<Tp, LEN>::ask(int x){
Tp ans(0);
for(; x; x -= x & -x) ans += c[x];
return ans;
}
BIT<ll, N> B;
vector<int> divend[N];
vector<pii> query[N];
priority_queue<int> Q;
int per[N], pos[N], n, m;
ll tag[N], ans[N];
void init(){
for(int x = 1; x < N; x++)
for(int y = x << 1; y < N; y += x)
divend[y].emplace_back(x);
}
void solve(){
n = read();
m = read();
B.resize(n);
for(int i = 1; i <= n; ++i)
query[i].clear();
for(int i = 1; i <= n; ++i)
pos[per[i] = read()] = i;
for(int i = 1, l, r; i <= m; ++i){
l = read();
r = read();
query[r].emplace_back(make_pair(l, i));
}
for(int i = 1; i <= n; ++i){
Q.push(i);
tag[i] = 1;
while(!Q.empty()){
int x = Q.top(); Q.pop();
for(int y : divend[per[x]])
if(pos[y] < x){
if(!tag[pos[y]])
Q.push(pos[y]);
tag[pos[y]] += tag[x];
}
B.add(x, tag[x]);
tag[x] = 0;
}
for(auto [l, id] : query[i])
ans[id] = B.ask(i) - B.ask(l - 1);
}
for(int i = 1; i <= m; ++i)
printf("%lld ", ans[i]);
putchar('\n');
}
signed main(int argc,char **argv){
init();
int T = read();
while(T--) solve();
return 0;
}
|
后记
这把 D 题做完还有 30min，以为自己不能拿下很数学的 E 题，遂开摆。最后发现自己离 1900 只有一步之遥，感觉很后悔。
最近作业压力太大，Lab 和 Proj 堆了一个又一个，感觉清明之前不完成的话会度过一个很不愉快的假期。
转念一想，清明可以和烧烤群的各位面基，还是很期待的。
加把劲吧。