noip模拟36
目录
T1 Dove打扑克
考场想到了正解，少了一个优化，少了20分。
思路：
既然是牌堆之间的合并操作，那么就用并查集来维护牌堆之间的关系。统计答案时把差值为0的情况特判一下就行。开一个数组存每个大小的牌堆数量，再开一个数组存每个牌堆的牌的个数。每一个牌堆对答案的贡献就是从1到当前大小-c的牌堆数量的前缀和×当前大小牌堆的数量。
这个优化就是用set来维护，set储存数量不为零的牌堆的大小，在合并牌堆时如果除了被合并的牌堆以外没有牌堆和它的数量相同了，就从set中吧这个数量删去。（整个过程相当于删除两个较小的牌堆，再插入一个较大的牌堆）插入是如果set中没有两个较小牌堆的大小之和这个数，就把这个数放进set里。最后统计答案是只需要遍历set即可（而不是枚举从1到最大大小）
Show you the 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
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 100010;
template<typename type>
type read() {
type s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int n, m;
int iee[maxn];
class dju {
public:
int fa[maxn];
void init() {
For(i, 1, n) fa[i] = i, iee[i] = 1;
}
int lookup(int a) {
if (fa[a] != a)
return fa[a] = lookup(fa[a]);
else
return fa[a];
}
} dj;
int nucnt[maxn];
set<int> hav;
int main() {
int mgcnt = 0;
int maxx = 1;
int maxxcnt = 0;
n = read<int>();
m = read<int>();
nucnt[1] = n;
hav.insert(1);
dj.init();
For(i, 1, m) {
int opt = read<int>();
if (opt == 1) {
int x, y;
x = read<int>();
y = read<int>();
int fax = dj.lookup(x);
int fay = dj.lookup(y);
// cout << fax << ' ' << fay << endl;
if (fay != fax) {
nucnt[iee[fax]]--;
if (nucnt[iee[fax]] == 0) {
set<int>::iterator it = hav.find(iee[fax]);
hav.erase(it);
}
nucnt[iee[fay]]--;
if (nucnt[iee[fay]] == 0) {
set<int>::iterator it = hav.find(iee[fay]);
hav.erase(it);
}
iee[fay] += iee[fax];
nucnt[iee[fay]]++;
if (hav.find(iee[fay]) == hav.end()) {
hav.insert(iee[fay]);
}
iee[fax] = 0;
dj.fa[fax] = fay;
}
mgcnt++;
} else {
int c = read<int>();
if (c > mgcnt) {
puts("0");
continue;
}
if (c == 0) {
long long qz = 0;
for(auto i : hav) {
qz += nucnt[i];
}
printf("%lld\n", qz * (qz - 1) / 2);
} else {
long long ans = 0;
long long qz = 0;
for(auto i : hav) {
qz = 0;
if (i < 1 + c) continue;
if (nucnt[i]) {
for (auto j : hav) {
if (j > i - c) break;
qz += nucnt[j];
}
ans += qz * nucnt[i];
}
}
printf("%lld\n", ans);
}
}
}
return 0;
}
T2 Cicada 与排序
是个骚题
我看了DeepinC学长的博客才明白，今天（08-13-2021）才A掉
这道题可以转化为两个数组合并，第一个数组的每一位在归并后位置的期望
设数组rk[i][j]为一开始位置在i的数完成归并后的位置，dp[i][j][0/1]表示归并排序时第一个数组弹掉了i个，第二个数组弹掉了j个，最后一次弹的来自于第一组还是第二组。转移时考虑两个数组有没有被弹干净，如果都没有弹干净，就瞎（？弹一个，否则哪个没空弹那个。
注意：vector的size成员函数的返回值为
unsigned int
0减1是个超大的数。用在循环中需要转为int类型见代码
Show you the 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
115
116
117
118
119
120
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 1010;
const long long mod = 998244353;
const long long inv = 499122177;
template<typename type>
type read() {
type s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
long long n;
long long rk[maxn][maxn], dp[maxn][maxn][2];
long long x[maxn], num[maxn * 2], tmp[maxn];
vector<long long> Lpos[maxn * 2], Rpos[maxn * 2];
void doit(long long l, long long r) {
long long mid = (l + r) / 2;
if (l == r) return;
doit(l, mid);
doit(mid + 1, r);
For(i, l, mid) {
Lpos[x[i]].push_back(i);
}
For(i, mid + 1, r) {
Rpos[x[i]].push_back(i);
}
For(i, 1, 1000) {
long long Lsz = Lpos[i].size(), Rsz = Rpos[i].size();
For(l, 0, Lsz) {
For(r, 0, Rsz) {
dp[l][r][0] = dp[l][r][1] = 0;
}
}
dp[0][0][0] = 1;
For(l, 0, Lsz) {
For(r, 0, Rsz) {
if (l != Lsz && r != Rsz) {
dp[l + 1][r][0] = (dp[l + 1][r][0] + (dp[l][r][0] + dp[l][r][1]) * inv) % mod;
// pop left
dp[l][r + 1][1] = (dp[l][r + 1][1] + (dp[l][r][0] + dp[l][r][1]) * inv) % mod;
//popright
} else {
if (l != Lsz) {
dp[l + 1][r][0] = (dp[l + 1][r][0] + dp[l][r][0] + dp[l][r][1]) % mod;
}
if (r != Rsz) {
dp[l][r + 1][1] = (dp[l][r + 1][1] + dp[l][r][0] + dp[l][r][1]) % mod;
}
}
}
}
for (long long j = 0; j < Lsz;j++) {
For(k, 1, Lsz) {
For(l, 0, Rsz) {
tmp[k + l] = (tmp[k + l] + rk[Lpos[i][j]][k] * dp[k][l][0]) % mod;
}
}
For(p, 1, Lsz + Rsz) {
rk[Lpos[i][j]][p] = tmp[p];
tmp[p] = 0;
}
}
for (long long j = 0; j < Rsz; j++) {
For(k, 1, Rsz) {
For(l, 0, Lsz) {
tmp[k + l] = (tmp[k + l] + rk[Rpos[i][j]][k] * dp[l][k][1]) % mod;
}
}
For(p, 1, Lsz + Rsz) {
rk[Rpos[i][j]][p] = tmp[p];
tmp[p] = 0;
}
}
Lpos[i].clear();
Rpos[i].clear();
}
}
int main() {
n = read<long long>();
For(i, 1, n) {
x[i] = read<long long>();
}
For(i, 1, n) {
rk[i][1] = 1;
}
doit(1, n);
For(i, 1, n) {
num[x[i]]++;
}
For(i, 1, 1000) {
num[i] += num[i - 1];
}
long long ans;
For(i, 1, n) {
ans = 0;
For(j, 1, num[x[i]] - num[x[i] - 1]) {
ans = (ans + j * rk[i][j]) % mod;
}
cout << ans + num[x[i] - 1] << ' ';
}
cout << endl;
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
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
117
118
119
120
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 1010;
const long long mod = 998244353;
const long long inv = 499122177;
template<typename type>
type read() {
type s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
long long n;
long long rk[maxn][maxn], dp[maxn][maxn][2];
long long x[maxn], num[maxn * 2], tmp[maxn];
vector<long long> Lpos[maxn * 2], Rpos[maxn * 2];
void doit(long long l, long long r) {
long long mid = (l + r) / 2;
if (l == r) return;
doit(l, mid);
doit(mid + 1, r);
For(i, l, mid) {
Lpos[x[i]].push_back(i);
}
For(i, mid + 1, r) {
Rpos[x[i]].push_back(i);
}
For(i, 1, 1000) {
long long Lsz = Lpos[i].size(), Rsz = Rpos[i].size();
For(l, 0, Lsz) {
For(r, 0, Rsz) {
dp[l][r][0] = dp[l][r][1] = 0;
}
}
dp[0][0][0] = 1;
For(l, 0, Lsz) {
For(r, 0, Rsz) {
if (l != Lsz && r != Rsz) {
dp[l + 1][r][0] = (dp[l + 1][r][0] + (dp[l][r][0] + dp[l][r][1]) * inv) % mod;
// pop left
dp[l][r + 1][1] = (dp[l][r + 1][1] + (dp[l][r][0] + dp[l][r][1]) * inv) % mod;
//popright
} else {
if (l != Lsz) {
dp[l + 1][r][0] = (dp[l + 1][r][0] + dp[l][r][0] + dp[l][r][1]) % mod;
}
if (r != Rsz) {
dp[l][r + 1][1] = (dp[l][r + 1][1] + dp[l][r][0] + dp[l][r][1]) % mod;
}
}
}
}
for (long long j = 0; j < Lsz;j++) {
For(k, 1, Lsz) {
For(l, 0, Rsz) {
tmp[k + l] = (tmp[k + l] + rk[Lpos[i][j]][k] * dp[k][l][0]) % mod;
}
}
For(p, 1, Lsz + Rsz) {
rk[Lpos[i][j]][p] = tmp[p];
tmp[p] = 0;
}
}
for (long long j = 0; j < Rsz; j++) {
For(k, 1, Rsz) {
For(l, 0, Lsz) {
tmp[k + l] = (tmp[k + l] + rk[Rpos[i][j]][k] * dp[l][k][1]) % mod;
}
}
For(p, 1, Lsz + Rsz) {
rk[Rpos[i][j]][p] = tmp[p];
tmp[p] = 0;
}
}
Lpos[i].clear();
Rpos[i].clear();
}
}
int main() {
n = read<long long>();
For(i, 1, n) {
x[i] = read<long long>();
}
For(i, 1, n) {
rk[i][1] = 1;
}
doit(1, n);
For(i, 1, n) {
num[x[i]]++;
}
For(i, 1, 1000) {
num[i] += num[i - 1];
}
long long ans;
For(i, 1, n) {
ans = 0;
For(j, 1, num[x[i]] - num[x[i] - 1]) {
ans = (ans + j * rk[i][j]) % mod;
}
cout << ans + num[x[i] - 1] << ' ';
}
cout << endl;
return 0;
}
T3 Cicada拿衣服
既然题目名是naive，那我就来个wallace
$$ _{{\frac{\large\text{注意 }}{\tiny{\text{Attention}}}}}\ \Large\text{这道题目极为玄学}\ \tiny - This\ Problem \ is \ very \ INTERESTING- $$
这道题需要用到特殊的卡常技巧
思路没啥好说的，就是固定左端点看最右可以到哪，原理就是第一个点只能向右拓展，在它所能拓展的范围内的点的l-i一定是拉满的，只需要计算r即可，而对于更新了的点，它所覆盖的点的左区间又是拉满的……
Show you the 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 <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 1000010;
template<typename type>
type read() {
type s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int n, wallace;
int a[maxn];
int getAns(int l, int r) {
int maxx = a[l], minn = a[l];
int orr = a[l], andd = a[l];
int mxr = -1;
for (int i = l + 1; i <= min(n, r); i++) {
if (a[i] < minn) minn = a[i];
if (a[i] > maxx) maxx = a[i];
orr |= a[i];
andd &= a[i];
if (n > 30000 && i - l > 800) break;
int now = minn - maxx + orr - andd;
if (now >= wallace)
mxr = i;
}
if (mxr == -1)
return -1;
else
return mxr - l + 1;
}
int maxans[maxn];
int main() {
n = read<int>();
wallace = read<int>();
For(i, 1, n) {
a[i] = read<int>();
}
For(i, 1, n) {
int tmp = getAns(i, i + 100001);
if (tmp == -1) {
if (!maxans[i]) {
maxans[i] = -1;
continue;
}
} else {
For(j, i, i + tmp - 1)
maxans[j] = max(maxans[j], tmp);
}
}
For(i, 1, n) {
cout << maxans[i] << ' ';
}
cout << endl;
return 0;
}