2020-2021:teams:too_low:cfedu94_hj
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:too_low:cfedu94_hj [2020/08/28 16:11] jim 创建 |
2020-2021:teams:too_low:cfedu94_hj [2020/08/28 16:17] (当前版本) jim [C. Binary String Reconstruction] |
||
|---|---|---|---|
| 行 29: | 行 29: | ||
| <code cpp> | <code cpp> | ||
| #include <bits/stdc++.h> | #include <bits/stdc++.h> | ||
| - | |||
| using namespace std; | using namespace std; | ||
| typedef long long LL; | typedef long long LL; | ||
| - | |||
| int main() { | int main() { | ||
| int t; | int t; | ||
| 行 50: | 行 48: | ||
| tot += j + min(cs, (f - j * w) / s); | tot += j + min(cs, (f - j * w) / s); | ||
| } | } | ||
| - | |||
| else{ | else{ | ||
| j = min(cs, f/s); | j = min(cs, f/s); | ||
| 行 64: | 行 61: | ||
| ===== C. Binary String Reconstruction ===== | ===== C. Binary String Reconstruction ===== | ||
| 这道题相当于对s做一个卷积操作后，由结果反推s | 这道题相当于对s做一个卷积操作后，由结果反推s | ||
| - | 原字符串中一个字符可以对应至多两个新字符串字符，对应2个时原字符串字符为1当且仅当对应的2个字符均为1。对应一个时，与新字符串相同。根据此规则生成原支付查后再做检查即可。 | + | 原字符串中一个字符可以对应至多两个新字符串字符，对应2个时原字符串字符为1当且仅当对应的2个字符均为1。对应一个时，与新字符串相同。根据此规则生成原字符串后再做检查即可。 |
| <code cpp> | <code cpp> | ||
| 行 98: | 行 95: | ||
| } | } | ||
| } | } | ||
| - | |||
| for (int i = 0; i < n; ++i) { | for (int i = 0; i < n; ++i) { | ||
| if (s[i] == '1') { | if (s[i] == '1') { | ||
| 行 105: | 行 101: | ||
| } | } | ||
| } | } | ||
| - | |||
| if(ok) { | if(ok) { | ||
| for (int j = 0; j < n; ++j) { | for (int j = 0; j < n; ++j) { | ||
| 行 113: | 行 108: | ||
| } | } | ||
| else puts("-1"); | else puts("-1"); | ||
| - | |||
| - | |||
| } | } | ||
| } | } | ||
| </code> | </code> | ||
| - | ===== Zigzags ===== | + | |
| + | |||
| + | |||
| + | ===== D. Zigzags ===== | ||
| 求1≤i<j<k<l≤n，ai=ak 且 aj=al;的四元组(i,j,k,l)的数量。 | 求1≤i<j<k<l≤n，ai=ak 且 aj=al;的四元组(i,j,k,l)的数量。 | ||
| 二维dp，先求出ai = aj且i<j的二元组(i,j)数量。对于每一个满足ai = aj的(i,j),可以找到dp[i-1][j-1]-dp[i-1][i]个符合条件的四元组。 | 二维dp，先求出ai = aj且i<j的二元组(i,j)数量。对于每一个满足ai = aj的(i,j),可以找到dp[i-1][j-1]-dp[i-1][i]个符合条件的四元组。 | ||
| 结果最大为sum n2，需要开long long | 结果最大为sum n2，需要开long long | ||
| - | <code> | + | <code cpp> |
| #include <bits/stdc++.h> | #include <bits/stdc++.h> | ||
| - | |||
| using namespace std; | using namespace std; | ||
| typedef long long LL; | typedef long long LL; | ||
| 行 170: | 行 165: | ||
| 因此最优情况只可能为尽可能多地进行第二种操作直到不连续，或全部进行第一种操作。 | 因此最优情况只可能为尽可能多地进行第二种操作直到不连续，或全部进行第一种操作。 | ||
| - | 在区间最小值处进行分割，再对子区间深搜答案即可。 | + | 在区间最小值处进行分割，比较两种情况，再对子区间深搜得到答案。 |
| <code cpp> | <code cpp> | ||
2020-2021/teams/too_low/cfedu94_hj.1598602273.txt.gz · 最后更改: 2020/08/28 16:11 由 jim
