Educational Codeforces Round 95

        Educational Codeforces Round 95。因为$A$题出了锅导致unrated了。

A. Buying Torches

        答案就是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 5;
typedef long long ll;

int main()
{
int t;
scanf("%d", &t);
while (t--) {
ll x, y, k;
scanf("%lld%lld%lld", &x, &y, &k);
ll s = k * y + k - 1;
if (s % (x - 1) == 0)
s = s / (x - 1);
else
s = s / (x - 1) + 1;
printf("%lld\n", s + k);
}
return 0;
}

B. Negative Prefixes

        把能排序的降序排列即可,这样可以保证它的所有前缀和都是尽可能大的。
        假设此时最大的,前缀和小于$0$的位置是$i$,由于这已经是前缀和最大的情况了,其它情况只会让这个位置前移,导致$i$变小,答案不会更优。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
int op[N], n, l[N];
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i);
for (int i = 1; i <= n; i++) scanf("%d", l + i);
vector<int> vec;
for (int i = 1; i <= n; i++) {
if (!l[i]) vec.push_back(op[i]);
}
sort(vec.begin(), vec.end(), greater<int>());
int at = 0;
for (int i = 1; i <= n; i++) {
if (!l[i]) op[i] = vec[at++];
}
for (int i = 1; i <= n; i++) printf("%d ", op[i]);
printf("\n");
}
return 0;
}

C. Mortal Kombat Tower

        一个傻$DP$,这都不会做就可以退役了

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
#include <bits/stdc++.h>
using namespace std;
const int N = 300000 + 5;
typedef long long ll;
int n, op[N], dp[N][2];
int DP(int x, int y) //y=0 friend;y=1 me
{
if (x > n) return 0;
if (~dp[x][y]) return dp[x][y];
if (y == 1) return dp[x][y] = min(DP(x + 1, 0), DP(x + 2, 0));
dp[x][y] = DP(x + 1, 1) + op[x] - op[x - 1];
if (x + 1 <= n) dp[x][y] = min(dp[x][y], DP(x + 2, 1) + op[x + 1] - op[x - 1]);
return dp[x][y];
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i), dp[i][0] = dp[i][1] = -1;
for (int i = 1; i <= n; i++) op[i] += op[i - 1];
printf("%d\n", DP(1, 0));
}
return 0;
}

D. Trash Problem

        对所有数升序排序后,设最大值为$n$,最小值为$m$,显然答案就是$n-m-\max(a_{i+1}-a_i)$。
        随便拿一个数据结构维护一下最大值,最小值和最大差即可。当然你也可以手写一个平衡树,比如我

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
#include <bits/stdc++.h>
const int N = 300000 + 5, inf = 0x3f3f3f3f;
using namespace std;

struct Node
{
int ch[2], v, key, max, min, ans;
} nd[N];

int root, cnt;

inline void update(int x)
{
nd[x].max = max(max(nd[nd[x].ch[0]].max, nd[nd[x].ch[1]].max), nd[x].v);
nd[x].min = min(min(nd[nd[x].ch[0]].min, nd[nd[x].ch[1]].min), nd[x].v);
nd[x].ans = min(nd[nd[x].ch[0]].ans, nd[nd[x].ch[1]].ans);
if (nd[x].ch[1]) nd[x].ans = min(nd[x].ans, nd[x].v - nd[nd[x].ch[1]].min);
if (nd[x].ch[0]) nd[x].ans = min(nd[x].ans, nd[nd[x].ch[0]].max - nd[x].v);
}

inline int newNode(int x)
{
nd[++cnt].v = x, nd[cnt].ch[0] = nd[cnt].ch[1] = 0;
nd[cnt].max = nd[cnt].min = x, nd[cnt].ans = inf, nd[cnt].key = rand();
return cnt;
}
void split(int rt, int& a, int& b, int v)
{
if (rt == 0) {
a = b = 0;
return;
}
if (nd[rt].v <= v)
a = rt, split(nd[rt].ch[1], nd[a].ch[1], b, v);
else
b = rt, split(nd[rt].ch[0], a, nd[b].ch[0], v);
update(rt);
}
void merge(int& rt, int a, int b)
{
if (a == 0 || b == 0) {
rt = a + b;
return;
}
if (nd[a].key > nd[b].key) {
rt = a, merge(nd[a].ch[1], nd[a].ch[1], b);
} else {
rt = b, merge(nd[b].ch[0], a, nd[b].ch[0]);
}
update(rt);
}
void insert(int x)
{
int a, b;
split(root, a, b, x);
merge(a, a, newNode(x));
merge(root, a, b);
}
void del(int x)
{
int a, b, c;
split(root, a, c, x);
split(a, a, b, x - 1);
merge(root, a, c);
}
int n, q;
inline int getAns()
{
if (n <= 2) return 0;
// cout << nd[root].max << " " << nd[root].min << endl;
return nd[root].max - nd[root].min + nd[root].ans;
}

int main()
{
srand(time(0)), nd[0].min = inf;
scanf("%d%d", &n, &q);
for (int i = 1, x; i <= n; i++) scanf("%d", &x), insert(x);
printf("%d\n", getAns());
while (q--) {
int t, x;
scanf("%d%d", &t, &x);
if (t == 0)
del(x), --n;
else
insert(x), ++n;
printf("%d\n", getAns());
}
return 0;
}

E. Expected Damage

        高中数学题。
        将所有数分为两类,一类小于$b$,一类不小于$b$,显然一个数产生贡献等价于它前面有不少于$a$个第二类的数。
        假设两类数分别有$n$和$m$个,先考虑对于一个第一类数,它能产生贡献的情况有多少种。
        先把第二类数做一个全排列,有$m!$种情况,然后把这个第一类数插进去,有$m-a+1$种情况,然后组合一下它们的位置,有$C_{n+m}^{m+1}$种情况,剩下的随便排,有$(n-1)!$种情况。总数就是:

        再除以总数$(n+m)!$,即:

        这就是它产生贡献的概率。对于第二类数产生贡献的概率,由于它本身会使$m$减少一,所以只需要把$m=m-1$代进去即可:

        注意判不成立的情况,然后二分配合前缀和,复杂度$O(mlogn)$。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5, mod = 998244353;
typedef long long ll;
int n, m, d[N], sumd[N];
inline int qpow(int x, int y)
{
int ans = 1, sta = x;
while (y) {
if (y & 1) ans = 1ll * ans * sta % mod;
sta = 1ll * sta * sta % mod, y >>= 1;
}
return ans;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", d + i);
sort(d + 1, d + n + 1);
for (int i = 1; i <= n; i++) sumd[i] = (sumd[i - 1] + d[i]) % mod;
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
int l = 0, r = n, mid;
while (l < r) {
if (r == l + 1) break;
mid = (l + r) >> 1;
if (d[mid] >= b)
r = mid;
else
l = mid;
}
int x;
if (d[r] >= b)
x = n - r + 1;
else
x = 0, r = n + 1;
// cout << x << " " << r << endl;
int ans = 0;
if (x >= a) ans = 1ll * sumd[r - 1] * (x - a + 1) % mod * qpow(x + 1, mod - 2) % mod;
if (x >= a + 1) {
int ss = sumd[n] - sumd[r - 1];
ans = (ans + 1ll * ss * (x - a) % mod * qpow(x, mod - 2) % mod) % mod;
}
printf("%d\n", (ans + mod) % mod);
}
return 0;
}

F. Equal Product

        将等式化为以下形式:

        我们枚举$x_1$,并且枚举它的每一个因子$b$,这一步的时间复杂度是$O(nlogn)$。此时我们可以得到对应的$y_1$取值范围。由于$l\leq x_1y_1\leq r$,所以$y_1$有一个取值范围,我们把它和$[1,m]$取个交。
        注意到$a|y_1$,并且$a>b$,这意味着$y_1$应含有至少一个大于$b$的因子$a$。另一方面,可以计算出$x_2=\frac{ax_1}{b},y_2=\frac{y_1b}{a}$,如果$y_1$存在,那么$y_2$必然也是存在且合法的。但是由于$x_2\leq n$,我们需要使$x_2$尽可能小,即$a$尽可能小。于是现在问题转化为在给定区间$[L,R]$中,找一个数$x$,它存在一个因子$a>b$,并且$a$最小。
        对于这种二维问题,我们当然可以使用主席树去做,但是主席树的空间复杂度(对于这个题)高达$O(nlog^2n)$,直接$MLE$。
        注意到$y_1$的区间左右端点随$x_1$的增大时不增的,于是可以不用主席树,而是使用一维的权值线段树来搞,这样空间复杂度降到$O(nlogn)$。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5;
typedef long long ll;
int n, m, cnt, root[N], nd[N << 2];
ll l, r;
vector<int> vec[N];
void modify(int x, int v, int l = 1, int r = m, int k = 1)
{
if (l == r) {
nd[k] += v;
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
modify(x, v, l, mid, k << 1);
} else {
modify(x, v, mid + 1, r, k << 1 | 1);
}
nd[k] = nd[k << 1] + nd[k << 1 | 1];
}
int query(int x, int l = 1, int r = m, int k = 1)
{
if (nd[k] == 0) return -1;
if (l == r) return l > x ? l : -1;
int mid = (l + r) >> 1;
if (x >= mid) return query(x, mid + 1, r, k << 1 | 1);
int tmp = query(x, l, mid, k << 1);
if (tmp != -1) return tmp;
return query(x, mid + 1, r, k << 1 | 1);
}
inline void update(int L, int R)
{
static int lat = m + 1, rat = m + 1;
while (lat - 1 >= L) {
for (int i = 0; i < vec[lat - 1].size(); i++) modify(vec[lat - 1][i], 1);
--lat;
}
while (rat - 1 > R) {
for (int i = 0; i < vec[rat - 1].size(); i++) modify(vec[rat - 1][i], -1);
--rat;
}
}
int main()
{
scanf("%d%d%lld%lld", &n, &m, &l, &r);
for (int i = 1; i <= n || i <= m; i++) {
for (int j = i; j <= n || j <= m; j += i) vec[j].push_back(i);
}
for (int i = 1; i <= n; i++) {
int flag = 1;
for (int j = 0; j < vec[i].size(); j++) {
ll L = l % i == 0 ? l / i : l / i + 1, R = min(r / i, 1ll * m), at;
if (L > m || L > R || R <= vec[i][j]) continue;
update(L, R), at = query(vec[i][j]);
if (at == -1) continue;
ll x2 = 1ll * i * at / vec[i][j];
int y1 = (L % at == 0 ? L / at : L / at + 1) * at;
int y2 = 1ll * vec[i][j] * y1 / at;
if (x2 <= n) {
printf("%d %d %d %d\n", i, y1, (int)x2, y2), flag = 0;
break;
}
}
if (flag) printf("-1\n");
}
return 0;
}

G. Three Occurrences

        从小到大枚举右端点,看有多少个左端点是合法的。
        维护一个数组$num[x]$,记录$x$到现在出现的次数模$3$的值,如果一个区间$[l,r]$合法,则$l-1$和$r$处的$num$数组应该相同。
        我们使用数组哈希的方法配合$map$就可以快速查询有多少个$l$满足这个条件,进而计入答案。
        但是这只是一个必要条件,不是充分条件。注意这种方法找出的可能使某些数出现$6$次或更多,需要删去一些答案。这一步只需要标记出现$3$次以上的数的左侧位置,将它们的哈希值删去即可。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 5;
typedef unsigned long long ull;
ull val[N], hs[N];
int n, num[N];
vector<int> vec[N];
map<ull, int> mmp;
int main()
{
srand(time(0));
scanf("%d", &n);
for (int i = 1; i <= n; i++) val[i] = (1ll * rand() << 32) + (1ll * rand() << 16) + rand();
ull ans = 0;
int lt = -1, at = -1;
++mmp[0];
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x);
hs[i] = hs[i - 1] - num[x] * val[x];
vec[x].push_back(i);
if (vec[x].size() > 3) lt = max(lt, vec[x][0]), vec[x].erase(vec[x].begin());
while (at + 1 < lt) --mmp[hs[at + 1]], ++at;
num[x] = (num[x] + 1) % 3;
hs[i] += num[x] * val[x];
ans += mmp[hs[i]];
++mmp[hs[i]];
}
printf("%lld", ans);
return 0;
}

0%