http://codeforces.com/contest/1330
B. Dreamoon Likes Permutations
题意：给定一个数列，分成两部分，问有几种分割方式使得两部分都是一个排列。
遍历数列，判断左边是否是排列，右边是否是排列。
是排列则不能有相同的数，所以要记录vis，如果已知都不相同，且个数又是一定的，如果是排列，那么总和一定是唯一的，先预处理出每个排列的和，再直接判断即可。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int T;
int a[N], n, c1[N], c2[N], vis[N];
ll sum[N];
void ck() {
fill(vis, vis + n + 1, 0);
ll tmp = 0;
for (int i = 1; i <= n; i++) {
if (vis[a[i]])break;
vis[a[i]] = 1;
tmp += a[i];
if (sum[i] == tmp)c1[i] = 1;
}
tmp = 0;
fill(vis, vis + n + 1, 0);
for (int i = n; i >= 1; i--) {
if (vis[a[i]])return;
vis[a[i]] = 1;
tmp += a[i];
if (sum[n - i + 1] == tmp)c2[i] = 1;
}
}
typedef pair<int, int>pii;
vector<pii>vc;
int main() {
scanf("%d", &T);
for (int i = 1; i < N; i++)sum[i] = sum[i - 1] + i;
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
fill(c1, c1 + n + 1, 0);
fill(c2, c2 + n + 1, 0);
ck();
vc.clear();
for (int i = 1; i <= n; i++)
if (c1[i] && c2[i + 1])
vc.push_back(pii(i, n - i));
printf("%d\n", (int)vc.size());
for (pii p : vc)printf("%d %d\n", p.first, p.second);
}
return 0;
}
|
C. Dreamoon Likes Coloring
题意：有长为m的操作序列，按顺序选择，任选一个位置，给后面长为 li 的区间图上颜色 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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
ll l[N];
ll ans[N];
ll sum[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%lld", &l[i]);
sum[i] = sum[i - 1] + l[i];
}
if (sum[m] < n || l[m] + m - 1>n) { puts("-1"); return 0; }
ans[1] = 1;
for (int i = 2; i <= m; i++) {
ans[i] = max(ans[i - 1] + 1, n - (sum[m] - sum[i - 1]) + 1);
if (ans[i - 1] + l[i - 1] - 1 + sum[m] - sum[i - 1] < n || l[i] + ans[i - 1] - 1 >= n) {
puts("-1"); return 0;
}
}
for (int i = 1; i <= m; i++)printf("%lld%s", ans[i], i == m ? "\n" : " ");
return 0;
}
|
D. Dreamoon Likes Sequences
题意：构造数列，满足严格递增，且最大值小于等于d，最小值大于等于1，并且前缀异或和也严格递增，问有几种构造方式。
dp+组合数学
首先要发现数列的每个数最高位一定要不同，可以从第一二个元素如果最高位相同，则异或和一定更小来判断，再类推到后面。
再枚举数列长度，确定长度n的情况下，就是要选出n个位置作为最高位，一个数字确定最高位后，可能的取值个数就是 2i，那么用乘法原理把每个数可能的取值个数乘起来，就是当前最高位的情况下，数列的个数。再用加法原理得到其它最高位情况的值。再改变数列长度，得到最终的结果。
问题就在于已知要取n个，有几种数列，可以dp来做，dp[i][j] 表示前i位，取j位的情况数。
dp[i][j]=(dp[i−1][j]+dp[i−1][j−1]∗2i−1)
注意要满足小于等于d，所以取d的最高位时要特殊处理。
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>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int T;
ll dp[40][40], d, m, p[40];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%lld%lld", &d, &m);
ll n = 0, tmp = d;
while (tmp) {
n++;
tmp >>= 1;
}
ll rs = ((d ^ (1ll << (n - 1))) + 1) % m;
p[0] = 1;
for (int i = 1; i <= n; i++)p[i] = p[i - 1] * 2 % m;
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= n; i++)dp[i][0] = 1;
for (int i = 1; i <= n; i++) {
ll tp = (i == n ? rs : p[i - 1]);
for (int j = 1; j <= i; j++)
dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * tp % m) % m;
}
ll ans = 0;
for (int i = 1; i <= n; i++)ans = (ans + dp[n][i]) % m;
printf("%lld\n", ans);
}
return 0;
}
|
E. Drazil Likes Heap
题意：有一棵树每个节点大于左右儿子的高度位h的满二叉树，要求删除成为高度为g的满二叉树，且剩下的值之和最小。
贪心
删除的时候把重儿子提上来，再依次提重链，直到最后，可以发现删除后仍然是每个节点大于左右儿子，也就是个大顶堆，那么每次都删树根一定能使得剩下的值和最小，但是可能最终不是个满二叉树。
那么就要尽可能地删除根，直到根的重链长度小于等于g，这里的重链指按照点权值，而非结点数，所以重链的长度可以始终logn得到。
对于所有节点都是这样，从上向下遍历，尽可能地删除，直到重链的长度小于等于g，由于左右子树之间没有影响，所以左右儿子都要dfs。
每次删除和查询长度的复杂度都为 logn，复杂度为 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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e7 + 10;
const int INF = 0x3f3f3f3f;
int T;
int h, g, a[N];
#define lson (u<<1)
#define rson (u<<1|1)
#define bson (a[lson]>a[rson]?lson:rson)
int dep(int u) {
if (a[u] == 0)return 0;
return dep(bson) + 1;
}
void del(int u) {
if (!a[u])return;
a[u] = a[bson];
del(bson);
}
vector<int>vc;
void dfs(int u, int d) {
if (!a[u])return;
while (dep(u) + d > g)vc.push_back(u), del(u);
dfs(lson, d + 1); dfs(rson, d + 1);
}
int main() {
scanf("%d", &T);
while (T--) {
vc.clear();
scanf("%d%d", &h, &g);
fill(a, a + (1 << (h + 1) + 2), 0);
for (int i = 1; i < (1 << h); i++)
scanf("%d", &a[i]);
dfs(1, 0);
ll sum = 0;
for (int i = 1; i < (1 << g); i++)sum += a[i];
printf("%lld\n", sum);
for (int v : vc)printf("%d ", v);
puts("");
}
return 0;
}
|
