显然，有多少个和中位数相等的数就加多少次。
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 <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;
int n, m, k, q;
void work()
{
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.end());
int pos = (n - 1) / 2, cnt = 1;
while (pos < n - 1 && a[pos] == a[pos + 1])
pos++, cnt++;
cout << cnt << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t --> 0)
{
work();
}
}
|
很显然，如果没有插入操作的话，答案显然就是最大子段和\(sum\)。
如果有插入操作的话，我们只需要把这个最大子段和的值插在最大子段的旁边，答案就变成了\(2\times
sum\)。如是，我们重复k次，答案就变成了\((1+2+4+\ldots +2^k)\times sum=(2^{k+1}-1)\times
sum\)。
因为k比较小，直接暴力算就好。最后答案还要加上整个数列的和。
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
|
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;
int n, m, k, q;
const ll mod = 1e9 + 7;
void work()
{
cin >> n >> k;
ll ans = 0;
ll sum = 0, maxsum = 0, numsum = 0;
vector<ll> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
numsum += a[i];
numsum %= mod;
}
for (int i = 0; i < n; i++)
{
sum += a[i];
if (sum < 0)
sum = 0;
maxsum = max(maxsum, sum);
}
for (int i = 1; i <= k; i++)
{
ans += maxsum;
ans %= mod;
maxsum += maxsum;
maxsum %= mod;
}
cout << (ans + numsum + 2LL * mod) % mod << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t --> 0)
{
work();
}
}
|
看到最小连通块的最大值，很容易想到用二分解决。关键在于设计check(lim)。
在有lim限制的情况下，一个贪心的策略是，我们使每个连通块都在满足限制的情况下尽可能小。
我们设两个变量cnt[x]和rest[x]，分别表示以x为根的子树能够凑出多少个不包含x的连通块个数，以及在去除这些连通块后，包含x的最大连通块的大小。
对于当前节点x，我们先遍历每个子树，然后对答案进行处理。
对于其子节点y，若rest[y] >= lim，则显然，可以凑出一个包含y的连通块个数，我们将cnt[x]加上1。反之，凑不出时，这些节点就应该与x呆在一个连通块里，将其累加到rest[x]里。除此之外，cnt[x]显然包括cnt[y]，直接累加上。
这样就完成了check(lim)的构造。
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
|
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;
int n, m, k, q;
vector<int> son[N];
int rest[N], cnt[N];
void dfs(int x, int f, int lim)
{
cnt[x] = 0;
rest[x] = 1;
for (auto y : son[x])
{
if (y == f)
continue;
dfs(y, x, lim);
cnt[x] += cnt[y];
if (rest[y] >= lim)
{
cnt[x]++;
rest[y] = 0;
}
rest[x] += rest[y];
}
}
void work()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
son[i].clear();
for (int i = 1, x, y; i < n; i++)
{
cin >> x >> y;
son[x].push_back(y);
son[y].push_back(x);
}
int l = 1, r = n, mid, ans = 1;
auto check = [&](int x)
{
dfs(1, 0, x);
int ans = cnt[1] + (int)(rest[1] >= x);
return ans >= k + 1;
};
while (l <= r)
{
mid = (l + r) / 2;
if (check(mid))
l = mid + 1, ans = mid;
else
r = mid - 1;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t --> 0)
{
work();
}
}
|
看到这种奇奇怪怪的二进制题，第一考虑二进制位的拆分。
我们令\(a_i\)的前缀异或和为\(s_i\)，第\(i\)段的异或和为\(L_i\)，则有 \[
L_i=s_{r_i}\oplus s_{r_{i-1}}
\] 注意，这里我们讨论的是二进制拆分后的结果。
那么，对于这一位分组后的答案\(s\)，显然有 \[
s=L_1 | L_2 | \ldots|L_k
\] 我们发现，要使\(s\)等于0，就有 \[
L_1=L_2=L_3=\ldots=L_k=0
\] 也即 \[
s_{r_1}=s_{r_2}=s_{r_3}=\ldots=s_{r_k}=0
\] 也就是说，只要我们能选出k个等于0的\(s_{r_i}\)，这一位的答案就能够等于0。
接下来考虑答案的具体取法。对于二进制下某一位来说，有2种情况
1. \(x=1\)
在这种情况下，如果我能在\(s_{r_i}\)凑到k个0，我就能使这一位答案变成0，显然存在合法的划分方法。
倘若凑不到，也没关系，直接对比下一位就好。
2. \(x=0\)
在这种情况下，如果我凑不到k个0，答案只能为1，无论如何也不可能使答案小于x了，显然不合法。
如果能凑到，那我们将结果与上一位的结果合并，比较下一位。
经过这样一番讨论后，我们发现，有两种情况可以直接结束判断，另外两种需要结合更高位的选择进行判断。
对此，我们可以设\(S_1\)为之前的轮数中，使答案和x相等的\(r_i\)集合，\(S_2\)为当前位上满足\(s_{r_i}=0\)的\(r_i\)的集合，\(S_3=S_1 \cap S_2\)。
如果\(S_3\)中集合大小大于等于\(k\)且其中包含\(n\)，我们就认为这一位满足使这一位答案为0的要求；反之则不满足。这样就完成了判断是否能划分出\(k\)段满足要求子段了。剩下的二分一下就能解决。
结合这个操作以及上面分类讨论的内容，就可以顺利写出代码。
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
|
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;
int n, m, k, q;
void work()
{
ll x;
cin >> n >> x;
vector<int> a(n + 1);
vector<bool> s(n + 1), p(n + 1), q(n + 1);
auto clear = [&](vector<bool> &s)
{
for (int i = 0; i <= n; i++)
s[i] = false;
};
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] = a[i - 1] xor a[i];
}
auto check = [&](int lim)
{
for (int i = 1; i <= n; i++)
s[i] = true;
for (ll bit = 32; bit >= 0; bit--)
{
clear(p);
for (int i = 1; i <= n; i++)
if (!(a[i] & (1LL << bit)))
p[i] = true;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
q[i] = s[i] & p[i];
cnt += q[i];
}
if (x & (1LL << bit))
{
if (cnt >= lim && q[n])
return true;
}
else
{
if (cnt < lim || !q[n])
return false;
for (int i = 1; i <= n; i++)
s[i] = q[i];
}
}
return true;
};
ll l = 0, r = n, mid, ans = 0;
while (l <= r)
{
mid = (l + r) / 2;
if (check(mid))
{
l = mid + 1;
ans = mid;
}
else
r = mid - 1;
}
if (ans != 0)
cout << ans << endl;
else
cout << -1 << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t --> 0)
{
work();
}
}
|
对于数字n，很显然没有比他更大的数了，所以他一定同时是suffix max和prefix max。
而且，在n之后的位置不可能是prefix max，在之前的位置不可能是suffix max，所以合法的排列中，n的位置一定是prefix max中最大的，suffix max中最小的。这样，prefix max和suffix max就被n分为了两部分，问题就转化为已知prefix max求合法的排列数。
结论：\(ans=\prod_{i不是prefix\
max}{i-1}\)。下面是证明：
设当前位为\(i\)，前面共有\(i-1\)个数。我们用\(R\)表示前面确定的各位置上数的大小。
如果当前位为prefix max，那么这个数比前面\(i-1\)个数都要大，也就是说，只能在\(R\)的最后插入\(i\)，只有一种可能。
如果当前位不为prefix max，则\(i\)有可能插入R的除最后一位以外的任意位置，共有\(i-1\)个位置。
由此，可以得出结论。
根据结论，我们分别计算出n左边和右边的答案\(ans_1, ans_2\)。令\(n\)左边有\(k\)个数，最后答案就为 \[
ans=ans_1 \times ans_2 \times \binom{n}{k}
\]
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
|
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;
int n, m, k, q;
const int64_t mod = 1e9 + 7;
int64_t fac[N], facRev[N];
auto quickPow(int64_t base, int32_t k)
{
int64_t ans = 1LL;
while (k)
{
if (k & 1)
ans = (ans * base) % mod;
base = (base * base) % mod;
k >>= 1;
}
return ans;
}
void init()
{
fac[0] = facRev[0] = 1;
for (int64_t i = 1; i < N; i++)
fac[i] = fac[i - 1] * i % mod;
for (int64_t i = 1; i < N; i++)
facRev[i] = quickPow(fac[i], mod - 2);
}
int64_t C(int n, int m)
{
return fac[n] * facRev[m] % mod * facRev[n - m] % mod;
}
void work()
{
int s1, s2;
cin >> n >> s1 >> s2;
vector<int> a(s1 + 1), b(s2 + 1), vis(n + 1);
for (int i = 1; i <= s1; i++)
{
cin >> a[i];
vis[a[i]] = 1;
}
for (int i = 1; i <= s2; i++)
{
cin >> b[i];
vis[b[i]] = 1;
}
sort(a.begin() + 1, a.end());
sort(b.begin() + 1, b.end());
if (*a.rbegin() != *(b.begin() + 1))
{
cout << 0 << endl;
return;
}
int pos = *(b.begin() + 1);
ll ans = 1LL;
for (int i = 1; i < pos; i++)
if (!vis[i])
ans = (ans * (i - 1)) % mod;
for (int i = pos + 1; i <= n; i++)
if (!vis[i])
ans = (ans * (n - i)) % mod;
ans = (ans * C(n - 1, pos - 1)) % mod;
cout << ans << endl;
}
int main()
{
init();
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
fac[0] = 1;
for (ll i = 1; i < N; i++)
fac[i] = fac[i - 1] * i % mod;
int t;
cin >> t;
while (t --> 0)
{
work();
}
}
|