2020-2021:teams:too_low:cf655ef_hj
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:too_low:cf655ef_hj [2020/09/02 09:34] jim 创建 |
2020-2021:teams:too_low:cf655ef_hj [2020/09/04 17:51] (当前版本) jim [E. Omkar and Last Floor] |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| ===== E. Omkar and Last Floor ===== | ===== E. Omkar and Last Floor ===== | ||
| + | |||
| + | * 题意：一个n*m矩阵，每一行被分割成了多个片段，每个片段中填一个1，使每列1个数的平方和最大。输出最大结果。m，n<100 | ||
| + | |||
| + | * 分类：dp、贪心 | ||
| 由于结果为每列1个数的平方，因此1需要尽可能多地集中到1列。 | 由于结果为每列1个数的平方，因此1需要尽可能多地集中到1列。 | ||
| - | dp[l][r] 表示水平区间[l,r]内的最优解，如果一个片段一部分在[l,r]外则不计入结果。 | + | dp[l][r] 表示水平区间[l,r]内的最优解，如果一个片段一部分在[l,r]外则不计入结果。考虑1尽可能集中到第i列，那么有dp[l][r] = dp[l, i-1] + dp[i+1, r] + 被i分割，且位于[l,r]区间内的的片段数 |
| - | dp[l][r] = max(dp[l, i-1] + dp[i+1, r] + 被i分割的片段数) | + | 对枚举i后取最大值即可得到dp[l][r] |
| + | |||
| + | * comment: 这道题m，n较小，可以容纳维度更高的dp。主要是需要确定dp时分割片段的标准。 | ||
| <code cpp> | <code cpp> | ||
| 行 13: | 行 19: | ||
| using namespace std; | using namespace std; | ||
| + | int tem = 0; | ||
| + | int ll[200][200], rr[200][200]; | ||
| + | int dp[200][200] = {}; | ||
| + | int n; | ||
| - | int a[200005]; | + | int dfs(int l, int r) { |
| - | map<int, int> mp; | + | if(l > r) return 0; |
| - | + | if (dp[l][r] >= 0)return dp[l][r]; | |
| - | + | int m = 0; | |
| - | int xx = 0, ff = 0; | + | for (int i = l; i <= r; ++i) { |
| - | + | int tot = 0; | |
| - | pair<int, int> chk(int l, int r, int prex, int pref) { | + | for (int j = 0; j < n; ++j) { |
| - | if (r < l) return {-1, -1}; | + | if (ll[j][i] >= l && rr[j][i] <= r) tot++; |
| - | if (!ff)printf("? %d %d\n", l, r); | + | } |
| - | fflush(stdout); | + | m = max(m, tot * tot + dfs(l, i - 1) + dfs(i + 1, r)); |
| - | int x = xx, f = ff; | + | |
| - | + | ||
| - | if (!ff) { | + | |
| - | scanf("%d", &x); | + | |
| - | assert(x != -1); | + | |
| - | scanf("%d", &f); | + | |
| } | } | ||
| + | return dp[l][r] = m; | ||
| + | } | ||
| - | + | int main() { | |
| - | xx = 0; | + | int m; |
| - | ff = 0; | + | cin >> n >> m; |
| - | + | for (int i = 0; i < n; ++i) { | |
| - | //x = 20784676, f = r - l + 1; | + | int k; |
| - | //x = l, f = 1; | + | scanf("%d", &k); |
| - | if (f >= r - l + 1) { | + | for (int j = 0; j < k; ++j) { |
| - | for (int i = l; i <= r; ++i) { | + | int l, r; |
| - | a[i] = x; | + | scanf("%d%d", &l, &r); |
| - | } | + | for (int i1 = l; i1 <= r; ++i1) { |
| - | if (!mp.count(x))mp[x] = 0; | + | ll[i][i1] = l; |
| - | mp[x] += r - l + 1; | + | rr[i][i1] = r; |
| - | } else if (x == prex) { | + | |
| - | for (int i = 0; i < f; ++i) { | + | |
| - | a[r] = x; | + | |
| - | r--; | + | |
| - | mp[x]++; | + | |
| - | } | + | |
| - | chk(l, r, 0, 0); | + | |
| - | } else { | + | |
| - | int oldx = mp.count(x) ? mp[x] : 0; | + | |
| - | chk(l, l + f - 1, x, f); | + | |
| - | int j = mp[x] - oldx; | + | |
| - | int i = l + f; | + | |
| - | if (!j) { | + | |
| - | xx = x; | + | |
| - | ff = f; | + | |
| - | chk(i, r, prex, pref); | + | |
| - | } else { | + | |
| - | int cnt = f - j; | + | |
| - | if (cnt < f) { | + | |
| - | if (!mp.count(x))mp[x] = 0; | + | |
| - | while (cnt-- > 0 && i <= r) { | + | |
| - | a[i] = x; | + | |
| - | mp[x]++; | + | |
| - | i++; | + | |
| - | } | + | |
| } | } | ||
| - | chk(i, r, prex, pref); | ||
| - | return {x, f}; | ||
| } | } | ||
| } | } | ||
| - | return {x, f}; | ||
| - | } | ||
| - | int main() { | + | for (int i = 0; i <= m; ++i) { |
| - | int n; | + | for (int j = 0; j <= m; ++j) { |
| - | cin >> n; | + | dp[i][j] = -1; |
| - | chk(1, n, 0, 0); | + | } |
| - | printf("! "); | + | |
| - | for (int i = 1; i <= n; ++i) { | + | |
| - | printf("%d ", a[i]); | + | |
| } | } | ||
| + | |||
| + | cout << dfs(1, m); | ||
| } | } | ||
| </code> | </code> | ||
| ===== F. Omkar and Modes ===== | ===== F. Omkar and Modes ===== | ||
| + | * 题意：存在一个不减的数列，每次询问可以返回区间内出现次数最多的数字和其个数，在4k-4个询问内确定这个数列 | ||
| + | |||
| + | * 分类：CDQ分治 | ||
| 显然需要用类似二分的方式询问，不过二分的次数为log k * k，log k可能会大于4 | 显然需要用类似二分的方式询问，不过二分的次数为log k * k，log k可能会大于4 | ||
| 行 98: | 行 77: | ||
| 另外，为了尽可能阻止出现左子区间和父区间结果完全相同，需要再次二分的情况，二分的中值设定为了父区间的数字最大重复个数。 | 另外，为了尽可能阻止出现左子区间和父区间结果完全相同，需要再次二分的情况，二分的中值设定为了父区间的数字最大重复个数。 | ||
| - | 因此大约每两次可以询问定位一个数字。 | + | 因此大约每两次询问可以定位一个数字。 |
| - | <code> | + | * comment：这道题的询问次数限制很少，分治时要特别注意log的消除 |
| + | |||
| + | <code cpp> | ||
| #include <bits/stdc++.h> | #include <bits/stdc++.h> | ||
| 行 107: | 行 88: | ||
| int a[200005]; | int a[200005]; | ||
| map<int, int> mp; | map<int, int> mp; | ||
| - | |||
| int xx = 0, ff = 0; | int xx = 0, ff = 0; | ||
2020-2021/teams/too_low/cf655ef_hj.1599010482.txt.gz · 最后更改: 2020/09/02 09:34 由 jim
