「第一弹」Codeforces杂题

Codeforces杂题

CF559D

题意

给出一个nn个点的凸包,等概率选则该凸包点集的大于等于三的子集形成一个新凸包,问该凸包内部整点的期望值。
3n105,109xi,yi1093\leq n\leq 10^5,-10^9\leq x_i,y_i\leq 10^9

题解

皮克定理:S=n+s21S=n+\frac{s}{2}-1
枚举每一条边对应的(劣弧)上的正点数+面积算出期望的内部整点numnum,贡献为

num2nk12n1nCn2num\cdot \frac{2^{n-k}-1}{2^n-1-n-C_n^2}

最后通过总面积-期望面积

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
int n;
const int N = 210000;
struct Node {
double x, y;
Node operator - (const Node u) {
return (Node){x-u.x,y-u.y};
}
double operator *(const Node u) {
return x * u.y - y*u.x;
}
}a[N], tmp, l, r;
double bin[N];
int Gcd(int x, int y) {
if(!y) return x;
return Gcd(y, x %y);
}
int gcd(int x, int y) {
return Gcd(abs(x), abs(y));
}
double kk;
ll c1, c2, kkz;
double tot, now, ans;
#define nxt(x) ((x%n+1))
#define pick(u,v) ((u)+1.0-0.5*(v))
#define cal(u) (n>=100? 1 / bin[u + 1] : (bin[n - k - 1] - 1.0) / kk)
int main() {
n = read();
bin[0] = 1;
for(int i = 1; i <= n; ++i) {
a[i].x = read();
a[i].y = read();
bin[i] = bin[i - 1] * 2;
}
kk = bin[n] - 1 - n - (double)n * (n - 1) / 2;
tmp = a[n] - a[1];
c1 += gcd(tmp.x, tmp.y);
r = a[2] - a[1];
c1 += gcd(r.x, r.y);
for(int i = 3; i <= n; ++i) {
l = a[i] - a[1];
tmp = a[i] - a[i - 1];
tot += r * l / 2;
c1 += gcd(tmp.x, tmp.y);
r = l;
}
for(int i = 1; i <= n; ++i) {
r = a[nxt(i)] - a[i];
c2 = gcd(r.x, r.y);
now = 0;
for(int j = nxt(nxt(i)), k = 2; k <= 35 && nxt(j) != i; j = nxt(j), ++k) {
l = a[j] - a[i];
tmp = l - r;
c2 += ((kkz = gcd(l.x, l.y)) + gcd(tmp.x, tmp.y));
now += r * l / 2;
ans += (pick(now, c2) + (nxt(j) == i ? 0 : kkz - 1)) * cal(k);
r = l;
c2 -= kkz;
}
}
printf("%.7lf\n", pick(tot, c1) - ans);
return 0;
}

CF559E

题意

数轴上有n(n100)n(n\le100)个聚光灯,每个聚光灯可以照亮的区间为[pili,pi][p_i-l_i,p_i]或者[pi,pi+li][p_i,p_i+l_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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
const int N = 110;
const int inf = 1 << 30;
int f[N][N][2], ans, n;
// f[i][j][k] 到第i个灯,目前覆盖到区间最右边的是第j个,第j个方向为k
struct T {
int x, y;
}a[N];
bool cmp(T x, T y) {
return x.x + x.y <y.x + y.y;
}
int main() {
n = read();
for(int i = 1; i <= n; ++i) {
a[i].x = read();
a[i].y = read();
}
sort(a + 1, a +1 + n, cmp);
a[0].x = -1e9;
int ans = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= i; ++j) {
for(int k = 0; k < 2; ++k) {
int L, R;
if(k == 0) {
L = a[j].x - a[j].y;
R = a[j].x;
} else {
L = a[j].x;
R = a[j].x + a[j].y;
}
int len = R - L;

for(int l = 0; l < j; ++l) {
for(int m = 0; m < 2; ++m) {
int nl, nr;
if(m == 0) {
nl = a[l].x - a[l].y;
nr = a[l].x;
} else {
nl = a[l].x;
nr = a[l].x + a[l].y;
}
// if(i == 2 && k == 1) {
// printf("(%d,%d,%d)->(%d,%d,%d) (%d,%d)(%d,%d) (%d->) %d\n", i - 1, l, m, i, j, k, nl, nr, L, R,f[i-1][l][m],f[i][j][k]);
// }
if(nr < L)
f[i][j][k] = max(f[i][j][k], f[i - 1][l][m] + len);
else {
if(nr > R) continue;

// assert(nr>R);
// f[i][j][k] = max(f[i][j][k], f[i - 1][l][m] + abs(R - nr));
// f[i][j][k] = max(f[i][j][k], )
}
}
}
f[i][j][k] = max(f[i][j][k], f[i - 1][j][k]);
ans = max(ans, f[i][j][k]);
}
}
}
writeln(ans);
return 0;
}

正解

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
const int N = 110;
const int inf = 1 << 30;
int f[N][N][2], ans, n;
// f[i][j][k] 到第i个灯,目前覆盖到区间最右边的是第j个,第j个方向为k
struct T {
int x, y;
}a[N];
bool cmp(T x, T y) {
return x.x + x.y <y.x + y.y;
}
int main() {
n = read();
for(int i = 1; i <= n; ++i) {
a[i].x = read();
a[i].y = read();
}
sort(a + 1, a +1 + n, cmp);
a[0].x = -1e9;
int ans = 0;
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= i; ++j) {
for(int d = 0; d < 2; ++d) {
ans = max(ans, f[i][j][d]);
int pre = a[j].x + a[j].y * d;
for(int k = i + 1, Mx = -1e9, x, y; k <= n; ++k) {
for(int d2 = 0; d2 < 2; ++d2) {
int nxt = a[k].x + a[k].y * d2;
if(nxt > Mx) Mx = nxt, x = k, y = d2;
f[k][x][y] = max(f[k][x][y], f[i][j][d] + min(a[k].y, nxt - pre) + Mx - nxt);
}
}
}
}
}
writeln(ans);
return 0;
}

CF111D

题意

Petya喜欢计数。他想计算:

KK种颜色绘制尺寸为nmn*m ( nn行,mm列)的矩形棋盘的方法数。

此外,着色应满足以下要求:

对于沿格子的线穿过的任何垂直线,会将棋盘分成两个非空的部分,这两个部分中的(不同颜色)的数量应相同。

帮助PetyaPetya对这些颜色进行计数。

题解

CF679B

题意

有若干积木体积为13,23,k31^3,2^3,\cdots k^3,对于一个总体积XX要求每次贪心地取X\leq X的最大积木拼上去(每个积木有无限个)使得,最后总体积恰好为XX,求给定的1m1\sim m内使选取的积木数量最大的XX,相同数量取XX较大者。m1015m\leq 10^{15}

题解

假设当前剩余vv,那么选取下一个有两种可能.
假设a=max{x}(x3v)a=\max \{x\}(x^3\leq v)

  1. a3a^3,那么剩余va3v-a^3
  2. a3a^3, 那么剩余a31(a1)3a^3-1-(a-1)^3

因为a31(a1)3>(a1)31(a2)3a^3-1-(a-1)^3 > (a-1)^3-1-(a-2)^3
所以不用考虑选(a2)3(a-2)^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
31
32
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
ll m;
vector<ll> a;
#define pa pair<ll,ll>

pa dfs(ll v, ll h, ll x) { // 剩余体积,得到的高度,最大的体积
pa res;
if(v == 0) {
return make_pair(h, x);
}
int pos = upper_bound(a.begin(), a.end(), v) - a.begin() - 1;
res = dfs(v - a[pos], h + 1, x + a[pos]);
--pos;
if(pos >= 0) res = max(res, dfs(a[pos + 1] - a[pos] - 1, h + 1, x + a[pos]));
return res;
}

int main() {
m = read();
for(ll i = 1; i <= 1e5; ++i)
a.push_back(i*i*i);
pa ans = dfs(m, 0, 0);
printf("%lld %lld\n", ans.first, ans.second);
return 0;
}

CF360B

题意

定义

C(a)=max1in1ai+1ai,n>1;c(a)=0,0n1.C(a)=\max_{1\leq i\leq n - 1} |a_{i+1}-a_i|,n>1; c(a)=0,0\leq n\leq 1.

现在给出一个长度为nn的数组aa,可以进行最多KK次修改,每次修改可以把任意一个aa元素替换成任意一个数字,问能得到的C(a)C(a)的最小值

题解

二分答案,fif_i表示从[1,i][1,i]中,aia_i强制不改变,前面都符合条件所需最少修改次数。

fi=minj<i,abs(aiaj)(ij)×x{fj+(ij+1)}f_i=\min_{j<i,abs(a_i-a_j)\leq (i-j)\times x}\{ f_j + (i-j+1)\}

xx是二分的答案

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;


const int N = 2100;
int n, K;
ll f[N], a[N];
ll check(ll x) {
f[1] = 0;
for(int i = 2; i <= n ;++i) {
f[i] = i - 1;
for(int j = 1; j < i; ++j)
if(abs(a[i] - a[j]) <= (i - j) * x)
f[i] = min(f[i], f[j] + (i - j - 1));
}
ll ans = 1e9;
for(int i = 1; i <= n; ++i)
if(f[i] + n - i <= K) return 1;
return 0;
}
int main() {
n = read(), K = read();
for(int i = 1; i <= n; ++i) a[i] = read();
ll l = -1, r = 2e9 + 666;
while(r - l > 1) {
ll mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid;
}
writeln(r);
return 0;
}

CF1108F

题意

给出nn个点,mm条边的图。保证没有重边和自环。
每条边用(u,v,w)(u,v,w)表示。
它的最小生成树代价是kk,你每一次可以操作一条边使得其代价+1+1,问最小的操作次数使得这张图的最小生成树代价为kk且唯一。

题解

先求出MST,然后枚举不在MST上的边。若两点之间的最大边权=W=W,那么ans=ans+1ans=ans+1。否则这条边一定不在MST上

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
const int N = 3e5 + 666;
int n, m;
struct G {
struct Edge {
int u, v, nxt, w;
}e[N << 1];
int en, head[N];
void addl(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].w= z, e[en].nxt = head[x], head[x] = en;
}
int f[N][21], d[N], g[N][21];
void dfs(int x, int F) {
d[x] = d[F] + 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
f[y][0] = x;
g[y][0] = e[i].w;
for(int j = 1; j <= 20; ++j) {
f[y][j] = f[f[y][j - 1]][j - 1];
g[y][j] = max(g[y][j - 1], g[f[y][j - 1]][j - 1]);
}
dfs(y, x);
}
}
int get(int x, int y) {
if(d[x] > d[y]) swap(x, y);
int res = -1e9;
for(int i = 20; ~i; --i)
if(d[f[y][i]] >= d[x]) {
res = max(res, g[y][i]);
y = f[y][i];
}

if(x == y) return res;
for(int i = 20; ~i; --i)
if(f[x][i] != f[y][i]) {
res = max(res, max(g[y][i], g[x][i]));
// printf("x=%d,y=%d,i=%d,(%d,%d)\n", x, y, i, g[y][i], g[x][i]);
x= f[x][i];
y = f[y][i];
}
return max(res, max(g[x][0], g[y][0]));
}
}g;
struct Edge {
int u, v, w;
}e[N << 1];
bool ok[N];
bool cmp(Edge x, Edge y) {
return x.w < y.w;
}
int fa[N];
int Find(int x) {
return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
e[i].u = read();
e[i].v = read();
e[i].w = read();
}
for(int i = 1; i <= n; ++i) fa[i] = i;
sort(e + 1, e+1 +m,cmp);
for(int i = 1; i <= m; ++i) {
int x = e[i].u;
int y = e[i].v;
if(Find(x) != Find(y)) {
g.addl(e[i].u, e[i].v, e[i].w);
g.addl(e[i].v, e[i].u, e[i].w);
fa[Find(x)] = Find(y);
ok[i] = 1;
}
}
g.dfs(1, 0);
ll ans = 0;
for(int i = 1; i <= m; ++i)
if(!ok[i]) {
int v = g.get(e[i].u, e[i].v);
if(v == e[i].w )++ans;
}
writeln(ans);
return 0;
}

CF1132D

题意

nn个学生要打一场kk分钟的比赛(当然要用电脑)。

每个学生的电脑有初始电量aia_i和每分钟耗电量bib_i(电量在这一分钟的最后一刻结算,即在下一分钟时才会减少,电量允许为负)。

这样肯定是无法打完比赛的,所以学生们买了一个充电器,功率为任意值,每分钟可以使电量增加xx,结算规则与耗电量一样,它可以在任一分钟给任一学生的电脑充电任意时长。

问题:求最小的xx,使所有学生的电脑的电量在kk分钟内(不包括第kk分钟)都不为负。
( 1n21051 \le n \le 2 \cdot 10^5 , 1k21051 \le k \le 2 \cdot 10^5 )1ai10121 \le a_i \le 10^{12}1bi1071 \le b_i \le 10^7

题解

二分裸体

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;


const int N = 3e5 + 666;
int n, m;
ll a[N], b[N];
#define pa pair<ll,ll>
struct Node {
ll x, i, tim;
bool operator <(Node B) const {
return tim > B.tim;
}
};
bool check(ll x) {
priority_queue<Node> q;
for(int i = 1; i <= n; ++i) q.push({a[i], i, a[i] / b[i]});
ll tim = 0;
while(!q.empty()) {
Node now = q.top(); q.pop();
if(now.tim >= m - 1) return 1;
if(tim > now.tim) return 0;
now.x += x;
++tim;
now.tim = now.x / b[now.i];
q.push(now);
if(tim >= m) return 0; //careful
}
return 0;
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i) b[i] = read();
ll l = -1, r = 1e15; //be carefull of range
while(r - l > 1) {
ll mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid;
}
if(!check(r))puts("-1");
else
writeln(r);
return 0;
}

CF1132E

题意

你有一个容量为WW的背包,和88种物品,重量分别为11~88的整数,分别有cnt1,cnt2...cnt8cnt_1,cnt_2...cnt_8个。
求背包中最多能装上多大的重量。

题解

LCM(1,2,,8)=850LCM(1,2,\cdots , 8)=850,所以留下850+K(k850)850+K(k\leq 850)体积,然后做倍增背包即可。

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<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
ll w;
ll c[9], ans;
ll tw;
ll v[6666], tot;
ll f[6500];
int main() {
w = read();
for(int i = 1; i <= 8; ++i) c[i] = read();
ll sum = 0;
for(int i = 1; i <= 8; ++i) sum += c[i] * i;
if(sum <= w) { //carefull
writeln(sum);
return 0;
}
tw = max(0ll, w - 850);
w -= tw;
for(int i = 1; i <= 8; ++i) {
ll t = min(c[i], tw / i);
if(c[i] - t < 10) t = max(0ll, c[i] - 10);
ans += t * i;
c[i] -= t;
tw -= i * t;
}
w += tw;
for(int i = 1; i <= 8; ++i) {
ll t = 1;
for(int j = 0; c[i] > 0; ++j) {
ll cur = min(t, c[i]);
c[i] -= cur;
v[++tot] = cur * i;
t <<= 1;
}
}
for(int i = 1; i <= tot; ++i)
for(int j = w; j >= v[i]; --j)
f[j] = max(f[j], f[j - v[i]] + v[i]);
writeln(ans + f[w]);
return 0;
}

CF1099F

题意

MityaMityaVasyaVasya正在玩一个有趣的游戏 。

他们有一颗有根树,根节点的标号为1.对于标号为ii的节点(i2)(i≥2),他的父节点为pip_i

每个节点上有一些饼干,节点ii上有xix_i个饼干,MityaMitya在节点ii上每吃一块饼干需要tit_i时间。

对于标号为ii的节点(i2)(i≥2),通过连接他的父节点和他自己的路径需要花费lil_i时间。

MityaMityaVasyaVasya轮流进行游戏,MityaMitya先走。

在进行游戏的过程中,有以下两点规则:

  • MityaMitya每次可以从当前点走到自己的任意一个儿子节点

  • VasyaVasya每次可以在所有的连接MityaMitya所在点与其所在点的儿子的路径中选择一条,并移除它。每一回合,VasyaVasya都可以选择不删除任意一条路径。

MityaMitya可以在任意一个他的回合停止游戏。停止游戏后,他会沿着先前走过的路径回到根节点,并在沿路中吃掉一些饼干。

MityaMitya吃饼干,从根节点到别的节点以及从别的节点返回到根节点的总时间不能超过TT

问:MityaMitya最多能吃多少饼干。

注意:MityaMityaVasyaVasya都是绝顶聪明的

题解

树状数组、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
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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
const int N = 3e6 + 666;
int n;

ll T, X[N], t[N];
int L[N];
struct Tree {
ll c[N];
void add(int x, ll v) {
for(; x <= 1e6; x += x&-x)
c[x] += v;
}
ll query(int x) {
ll res = 0;
for(; x; x -= x & -x)
res += c[x];
return res;
}
}t1, t2;
vector<int> g[N];
ll f[N];
void dfs(int x, ll dis) {
if(T < dis*2) return;
t1.add(t[x], X[x] * t[x]);
t2.add(t[x], X[x]);
int l = 0, r = 1e6 + 1;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(t1.query(mid) <= (T - (dis << 1))) l = mid;
else r = mid;
}
// printf("x=%d,l=%d (%d,%d)\n", x, l, x[X], t[x]);
f[x] = t2.query(l);
ll val = T - (dis << 1) - t1.query(l);
if(l < 1e6)f[x] += val / (l + 1);
// printf("%d:%d\n", x, f[x]);
for(int y : g[x]) dfs(y, dis + L[y]);
t1.add(t[x], -X[x] * t[x]);
t2.add(t[x], -X[x]);
}
ll ans[N];
void dfs(int x) {
ll m1 = 0, m2 = 0;
for(int y : g[x]) {
dfs(y);
if(ans[y] >= m1) {
m2 = m1;
m1 = ans[y];
}else if(ans[y] >= m2) m2= ans[y];
}
if(x == 1) ans[x] = max(f[x], m1);
else ans[x] = max(f[x], m2);
}
int main() {
n = read(), T = read();
for(int i = 1; i <= n; ++i) X[i] = read();
for(int i = 1; i <= n; ++i) t[i] = read();
for(int i = 2; i <= n; ++i) {
g[read()].push_back(i);
L[i] = read();
}
dfs(1, 0);
dfs(1);
writeln(ans[1]);
return 0;
}

CF731E

题意

有长度为nn的序列,AABB轮流操作,AA是先手。
每一次操作,选一个长度2\ge 2的前缀,他们的和为ss,然后删掉他们,把ss加入到序列的左边。并且操作者得到分数ss
当序列的长度变成11后游戏结束。AABB都想让自己得的分更大。

题解

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
/*
f[i][0] 先手从i到n使得先手值-后手指最大
f[i][1] 后手从i到n使得先手值-后手值最小
*/
const int N = 210000;
ll a[N], n;
ll sum[N];
ll f[N][2];
int main() {
n = read();
for(int i = 1; i <= n; ++i) {
a[i] = read();
sum[i] = sum[i - 1] + a[i];
}
f[n][0] = sum[n];
f[n][1] = -sum[n];
for(int i = n - 1; i >= 1; --i) {
f[i][0] = max(f[i + 1][1] + sum[i], f[i + 1][0]);
f[i][1] = min(f[i + 1][0] - sum[i], f[i + 1][1]);
}
writeln(f[1][0]);
return 0;
}

CF850C

题意

给出nn个正整数aia_i,AABB两人轮流操作,AA是先手。每次选出一个素数pp和一个数kkpkp^k
如果该nn个数中有pkp^k的倍数,那么所有的这些数都除以pkp^k。不能操作者败,问先手是否必胜

题解

SG函数

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 110;
int a[N], n;
map<int,int> sg;
void solve(ll x) {
if(sg.count(x)) return;
vector<int> mex(30, 0);
for(int i = 0; x >> i; ++i) {
ll nx = ((x>>(i+1)) | (x & ((1 << i) - 1)));
solve(nx);
mex[sg[nx]] = 1;
}
int ret = 0;
for(; mex[ret]; ++ret);
sg[x] = ret;
}
int main() {
n = read();
set<int> p;
for(int i = 1; i <= n; ++i) {
a[i] = read();
int t = a[i];
for(int j = 2; j <= t / j; ++j) {
if(t % j == 0) {
p.insert(j);
while(t % j == 0) t /= j;
}
}
if(t > 1) p.insert(t);
}
sg[0] = 0;
int ret = 0;
for(auto y : p) {
int st = 0;
for(int i = 1; i <= n; ++i) {
int cnt = 0;
while(a[i] % y == 0) {
a[i] /= y;
++cnt;
}
if(cnt) st |= (1 << (cnt - 1));
}
solve(st);
ret ^= sg[st];
}
puts(ret ? "Mojtaba" : "Arpa");
return 0;
}

CF965E

题意

给出nn个两两不同的由26个小写字母组成的字符串,你可以给任意的某几个字符串只保留其前缀,这个前缀可以是自身,问最后能使得字符串依旧两两不同且所有字符串的总长度最小。

题解

CF490F

题意

给出一棵树,每个节点有一个权值,让你求它的最长上升子序列n6000n\leq 6000

题解

force

考虑从每一个点做一遍dfs,然后用nlognn \log n的复杂度做单次dfs。

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 6100;

int a[N], n;
vector<int> g[N];
int f[N];
int ans;
void dfs(int x, int F) {
int pos = lower_bound(f + 1, f + 1 + n, a[x]) - f;
int tmp = f[pos];
f[pos] = a[x];
int t = lower_bound(f + 1, f + 1 + n, 0x3f3f3f3f) - f - 1;
ans = max(ans, t);
for(int y : g[x]) if(y != F) {
dfs(y, x);
}
f[pos] = tmp;
}
int main() {
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i < n; ++i){
int x = read(), y = read();
g[x].push_back(y);
g[y].push_back(x);
}
memset(f, 0x3f, sizeof f);
for(int i = 1; i <= n; ++i) {

dfs(i, 0);
}
writeln(ans);
return 0;
}

std

fi,0,fi,1f_{i,0},f_{i,1}表示子树xx内,以ii
这个权值结尾的最长LISLISLDSLDS
然后用线段树合并

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 6100;

int a[N], n, b[N];
vector<int> g[N];
int tot;
int mx[2][N << 4];
int ls[N << 4], rs[N << 4];
int rt[N];
void ins(int &k, int l, int r, int x, int v, int id) {
if(!k) k = ++tot;
if(l == r) {
mx[id][k] = max(mx[id][k], v);
return;
}
int mid = (l + r) >> 1;
if(x <= mid) ins(ls[k], l, mid, x, v, id);
else ins(rs[k], mid + 1, r, x, v, id);
mx[id][k] = max(mx[id][ls[k]], mx[id][rs[k]]);
}
int query(int k, int l, int r, int ql, int qr, int id) {
if(!k) return 0;
if(ql <= l && qr >= r) return mx[id][k];
int mid = (l + r) >> 1;
if(qr <= mid) return query(ls[k], l, mid, ql, qr, id);
if(ql > mid) return query(rs[k], mid + 1, r, ql, qr, id);
return max(query(ls[k], l, mid, ql, qr, id), query(rs[k], mid + 1, r, ql, qr, id));
}
int ans = 0;
int merge(int l, int r) {
if(!l || !r) return l | r;
int rt = l;
mx[0][rt] = max(mx[0][l], mx[0][r]);
mx[1][rt] = max(mx[1][l], mx[1][r]);
// ans = max(ans, max(mx[0][ls[l]] + mx[1][rs[r]], mx[1][ls[l]] + mx[0][rs[r]])); // careful
ans = max(ans, max(mx[0][ls[l]] + mx[1][rs[r]],mx[0][ls[r]] + mx[1][rs[l]])); // careful
ls[rt] = merge(ls[l], ls[r]);
rs[rt] = merge(rs[l], rs[r]);
return rt;
}

void dfs(int x, int F) {
int mx1 = 0, mx2 = 0;
for(int y : g[x]) if(y != F) {
dfs(y, x);
int v1 = query(rt[y], 1, *b, 1, a[x] - 1, 0);
int v2 = query(rt[y], 1, *b, a[x] + 1, *b, 1);
ans = max(ans, max(mx1 + v2, mx2 + v1) + 1);
rt[x] = merge(rt[x], rt[y]);
mx1 = max(mx1, v1);
mx2 = max(mx2, v2);
}
ins(rt[x], 1, *b, a[x], mx1 + 1, 0);
ins(rt[x], 1, *b, a[x], mx2 + 1, 1);
}
int main() {
n = read();
for(int i = 1; i <= n; ++i) a[i] = read(), b[++*b] = a[i];
b[++*b] = -1e9;
b[++*b] = 1e9;
for(int i = 1; i < n; ++i){
int x = read(), y = read();
g[x].push_back(y);
g[y].push_back(x);
}
sort(b+1,b+1+*b);
*b = unique(b + 1, b + 1 + *b) - b - 1;
for(int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + *b, a[i]) - b;
dfs(1, 0);
writeln(ans);
return 0;
}

CF1132G

题意

对于一个数组CC,他的优秀子序列PP,满足1p1<p2<<plC1\leq p_1<p_2<\cdots <p_l\leq |C|,并且对于每一个i[1,l1]i\in[1,l-1]pi+1p_{i+1}是最小的整数满足pi+1>pip_{i+1}>p_i并且c[pi+1]>c[pi]c[p_{i+1}]>c[p_i]
对于每一个子段[1,k],[2,k+1],,[ck+1,c][1,k],[2,k+1],\cdots,[|c|-k+1,|c|],求出它的最长优秀子序列长度。

题解

对每一个点,向后第一个比它大的点连边,最后形成一个森林(可以建立虚点,向没有后继的点连边,成为树)。以虚点为根,建立线段树。加入一个点,那么他的子树每个点都+1+1,删一个点1-1
那么答案就是所有点的最大值了。

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>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 2e6 + 666;
int n, m;

int a[N];
vector<int> g[N];
int st[N], top;
void build() {
st[++top] = n + 1;
a[n + 1] = 1e9;
for(int i = n; i >= 1; --i) {
while(top && a[st[top]] <= a[i]) --top;
g[st[top]].push_back(i);
st[++top] = i;
}
}

int L[N], R[N], num;
int tran[N];
void dfs(int x, int F) {
L[x] = ++num;
tran[num] = L[x];
for(int y : g[x]) dfs(y, x);
R[x] = num;
}
int ls[N << 2], rs[N << 2];
int mx[N << 2], tag[N << 2];
#define lch (o<<1)
#define rch (o<<1|1)
void up(int o) {
mx[o] = max(mx[lch], mx[rch]);
}
void build(int o, int l, int r) {
ls[o] = l; rs[o] = r;
if(l == r) return;
int mid = (l + r) >> 1;
if(l <= mid) build(lch, l, mid);
if(r > mid) build(rch, mid + 1, r);
up(o);
}
void upd(int o, int v) {
tag[o] += v;
mx[o] += v;
}
void down(int o) {
if(tag[o]) {
upd(lch, tag[o]);
upd(rch, tag[o]);
tag[o] = 0;
}
}
void ins(int o, int l, int r, int v) {
if(l <= ls[o] && r >= rs[o]) {
upd(o, v);
return;
}
int mid = (ls[o] + rs[o]) >> 1;
down(o);
if(l <= mid) ins(lch, l, r, v);
if(r > mid) ins(rch, l, r, v);
up(o);
}



int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i)
a[i] = read();
build();
dfs(n + 1, 0);
build(1, 1, n + 1);
for(int i = 1; i <= n; ++i) {
if(i <= m) ins(1, L[i], R[i], 1);
else {
ins(1, L[i - m], R[i - m], - 1);
ins(1, L[i], R[i], 1);
}
if(i >= m) printf("%d ", mx[1]);
}
return 0;
}