PKUSC2018

PKUSC2018

真实排名

我竟然做出来了签到题,感动哭了。

分两种情况:自己翻倍,自己不翻倍。(如果为零单独考虑)

设当前考虑的是第\(i\)个数字。

自己不翻倍:

在小于等于\(\left\lfloor\frac{a_i-1}{2}\right\rfloor\)和大于\(a_i\)的数字中选择\(k\)个。

自己翻倍:

设翻倍后的排名上升了\(del\),我们要在大于等于\(a_i\)小于等于\(2 \times a_i\)的数字里选择\(del\)个,在小于\(a_i\)大于\(2\times a_i\)的数字中选择\(k-del\)个就好了。

代码:

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
/*
* 6432.cpp
* This file is part of 6432
*
* Copyright (C) 2019 - ViXbob
*
* 6432 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 6432 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 6432. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))
#define Rank(x) (n - (lower_bound(pos + 1, pos + 1 + n, x) - pos) + 1)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, k, a[maxn], fac[maxn], ifac[maxn], pos[maxn];

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int C(int n, int m) { if(n < m || n < 0 || m < 0) return 0; return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); k = read(); fac[0] = 1;
rep(i, 1, n) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[n] = inv(fac[n]);
dep(i, n - 1, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
rep(i, 1, n) a[i] = pos[i] = read();
sort(pos + 1, pos + 1 + n);
rep(i, 1, n) {
int ge = Rank(a[i]) - 1;
int le = upper_bound(pos + 1, pos + 1 + n, a[i] - 1 >> 1) - pos - 1;
int ans = C(le + ge, k);
if(a[i] == 0) printf("%d\n", pls(ans, C(le + ge, k - 1)));
else {
int to = a[i] * 2, eq = 0, del;
ge = Rank(to);
le = upper_bound(pos + 1, pos + 1 + n, to - 1 >> 1) - pos - 1;
eq = n - ge - le - 1;
del = Rank(a[i]) - (Rank(to) + 1);
ans = pls(ans, 1ll * C(eq, del) * C(le + ge, k - del - 1) % P);
printf("%d\n", ans);
}
}
return 0;
}

最大前缀和

比较巧妙的\(\text{dp}\)

我们首先找出来一个集合\(S\)钦定它为最大前缀和,那么合法的序列一定满足将这个前缀砍掉后的后缀的每个前缀都是小于零等于的。那么我们设:

\(f[S]\)表示考虑\(S\)这个集合,并且最大前缀和为\(\sum_{i\in S}a_i\)的方案数。

\(g[S]\)表示考虑\(S\)这个集合,用这个集合内的数构成的序列的每个前缀都小于零的序列的个数。

那么答案为: \[ \sum_{S\cap T=\emptyset, S\cup T=U}f[S]\times g[T]\times \sum_{i\in S}a_i \]

\(sum[S]=\sum_{i\in S}a_i\),有转移: \[ \begin{aligned}f[S] &\to f[S\cup i], i\not\in S, sum[S]>0\\g[S]&\to g[S \cup i], i\not\in S,sum[S\cup i]<=0\end{aligned} \] \(f\)的转移相当于直接将\(i\)放在的序列的最前端。

复杂度\(O(2^nn)\)

代码:

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
/*
* 6433.cpp
* This file is part of 6433
*
* Copyright (C) 2019 - ViXbob
*
* 6433 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 6433 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 6433. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 5e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, f[1 << 20], g[1 << 20], a[maxn], U, nt[1 << 20], ans;
ll sum[1 << 20];

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); U = (1 << n) - 1;
rep(i, 1, n) a[i] = read(), f[1 << i - 1] = 1;
rep(i, 1, n) nt[1 << i - 1] = i;
rep(i, 1, U) nt[i] = nt[i & -i];
rep(S, 1, U) sum[S] = sum[~(S & -S) & S] + a[nt[S]];

rep(S, 0, U) if(sum[S] > 0) for(int tmp = ~S & U, k = nt[tmp]; tmp; k = nt[tmp &= ~(1 << k - 1)])
f[S | 1 << k - 1] = pls(f[S | 1 << k - 1], f[S]);

g[0] = 1;
rep(S, 0, U) if(sum[S] <= 0) for(int tmp = S, k = nt[tmp]; tmp; k = nt[tmp &= ~(1 << k - 1)])
g[S] = pls(g[S], g[S ^ (1 << k - 1)]);

rep(S, 1, U) ans = pls(ans, 1ll * f[S] * g[U ^ S] % P * pls(P, sum[S] % P) % P);
cout << ans << endl;
return 0;
}

主斗地

看到这三个字就虚,先挖坑吧。实则就是咕咕咕

星际穿越

神仙题啊。(至少我是这么认为的)

到现在都还只会\(70\),极其自闭。

\(45\)分显然就是线段树优化建图,然后\(\text{Dijkstra}\)就好了。复杂度\(O(n^2\log^2n)\)

考虑一下这到题优秀的性质。

首先有\(l_i < r_i <x_i\)并且\(L_i < i\),由这个两个我们可以知道我们只会往右走一步,并且如果走的话一定是第一步的时候向右走。其次就是如果出发点为\(x\),设\(x\)到它左边的点\(i\)的最短路为\(dis[x][i]\)。那么如果\(i < j<x\)则有\(dis[x][i]\le dis[x][j]\)

知道了这几个性质,我们设\(f[i][j]\)表示从\(i\)点向右走走\(j\)步能到达最左边的点的编号。那么则有: \[ \begin{cases}f[i][j]=L[i], &j=1\\f[i][j]=\min_{f[i][j-1] \le k \le n}(L[k])&j>1\end{cases} \]

\[ dis[x][i]=k,f[x][k] \le i < f[x][k-1] \]

这样两个数组我们可以在\(O(n^2)\)的时间内预处理出来,然后对\(dis\)搞个前缀和就可以\(O(1)\)回答询问了。

总复杂度\(O(n^2+q)\)

代码:

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
/*
* 6435.cpp
* This file is part of 6435
*
* Copyright (C) 2019 - ViXbob
*
* 6435 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 6435 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 6435. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 5e3 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, l[maxn], q, f[maxn][maxn], d[maxn][maxn];

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read();
rep(i, 2, n) l[i] = read();
int suf = inf;
memset(f, 0x3f, sizeof(f));
dep(i, n, 1) {
suf = min(suf, l[i]);
f[i][0] = i;
f[i][1] = l[i]; f[i][2] = suf;
int now = i, p = 1;
while(now) {
while(now >= f[i][p] && now) f[i][p + 1] = min(f[i][p + 1], l[now]), now--;
p++;
}
rep(j, 1, p) d[i][f[i][j - 1] - 1]++;
dep(j, i - 1, 1) d[i][j] += d[i][j + 1];
rep(j, 1, i - 1) d[i][j] += d[i][j - 1];
}
q = read();
rep(i, 1, q) {
int L = read(), R = read(), x = read(), sum = d[x][R] - d[x][L - 1];
int GCD = __gcd(sum, R - L + 1);
printf("%d/%d\n", sum / GCD, (R - L + 1) / GCD);
}
return 0;
}

神仙的游戏

神仙游戏海星

设串长为\(n\),我们发现如果存在一个长度为\(len\)\(\text{border}\),那么在膜\(n -len\)同余的位置必须同时为一或者同时为零。不过这样考虑还是有点麻烦,正难则反嘛,也就是只要存在一个零一对在膜\(x\)下同余,那么\(n-x\)就不可能是这个串的\(\text{border}\),反之一定是这个串的\(\text{border}\)

那么这样我们就得到了一个\(O(n^2)\)的算法:我们枚举一个零一对\((i,j)\),记\(x=|i-j|\)那么对于\(x\)的因子\(d\),\(n-d\)都不可能是\(\text{border}\)

好像随机数据和问号数量大于\(n-5000\)\(subtask\)都可以过。

考虑优化这个过程设生成函数: \[ [x^i]A(x)=[s[i]=1] \]

\[ [x^{n-i}]B(x)=[s[i]=0] \]

如果对于一个\(x\),存在一个二元组\((i,j)\)使得\(s[i]\oplus s[j]=1,|i-j|=x\)那么也就是说\([x^{n-x}](A(x)B(x))>0\)或者\([x^{n+x}](A(x)B(x))>0\)。复杂度为\(O(n\log n)\)

代码:

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
115
116
/*
* 6436.cpp
* This file is part of 6436
*
* Copyright (C) 2019 - ViXbob
*
* 6436 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 6436 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 6436. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 5e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const int maxm = maxn << 2;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, f[maxn];
ll ans = 0;
char s[maxn];

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

namespace NTT {
const int G = 3, invG = inv(G);
int rev[maxm], E[maxm], H[maxm], s, l, inv;

inline void init(int n) {
s = 2; l = 1;
while(s <= n) s <<= 1, l++; inv = inv(s);
rep(i, 0, s - 1) rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
memset(E, 0, sizeof(int) * (s + 5));
memset(H, 0, sizeof(int) * (s + 5));
}

inline void dft(int *a, int n, int f) {
rep(i, 0, n - 1) if(i < rev[i]) swap(a[i], a[rev[i]]);
for(int i = 1; i < n; i <<= 1) {
int Wn = ksm(f, (P - 1) / (i << 1));
for(int j = 0; j < n; j += (i << 1)) {
int w = 1;
for(int k = 0; k < i; k++, w = 1ll * w * Wn % P) {
int A1 = a[j + k], A2 = 1ll * a[j + k + i] * w % P;
a[j + k] = pls(A1, A2); a[j + k + i] = dec(A1, A2);
}
}
}
}

inline void conv() {
dft(E, s, G); dft(H, s, G);
rep(i, 0, s - 1) E[i] = 1ll * E[i] * H[i] % P;
dft(E, s, invG);
rep(i, 0, s - 1) E[i] = 1ll * E[i] * inv % P;
}
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
scanf("%s", s + 1);
n = strlen(s + 1);
NTT :: init(n << 1);
rep(i, 1, n) NTT :: E[i] = (s[i] == '0');
rep(i, 1, n) NTT :: H[n - i] = (s[i] == '1');
NTT :: conv();
rep(i, 0, n << 1) f[abs(i - n)] |= (NTT :: E[i] > 0);
for(int i = 1; i <= n; i++) for(int j = i; j <= n; j += i) f[i] |= f[j];
rep(i, 1, n) if(!f[i]) ans ^= (1ll * (n - i) * (n - i));
cout << (ans ^ 1ll * n * n) << endl;
return 0;
}

PKUSC

计算几何,先咕着。