Difference between revisions of "2018 Yandex.Algorithm - Elimination Stage, Online Round 1"
Jump to navigation
Jump to search
(Created page with "== ultmaster == === Problem D === 套路： * 小的时候暴力，排个序。 * 大的时候肯定可以，所以随机。 === Problem F === 想到不敢写，错过了...") |
|||
| Line 3: | Line 3: | ||
=== Problem D === | === Problem D === | ||
| − | + | 题意：给一张贴好的邮票。问有哪些小邮票最后可以贴出这个图案。 | |
| − | + | 题解：枚举所有子串。然后 check。check 的方法：题解的没看懂，自己想了一种：$dp(i+1,0)$ 表示到 $i$ 为止，左边的那段还没结束，也就是说不能接一段中间开始的（一定要接从头开始的）。可行为 1，不可行为 0；$dp(i+1,1)$ 表示到 $i$ 为止，左边的那段已经结束，可以接一段从中间开始的。这个一定要画个图理解一下！刚开始 $dp(0,0)=1$，最后如果 $dp(n,1)=1$ 则可行。更新的时候要利用最长公共后缀来更新，注意处理 min 和 max。 | |
| − | |||
| − | === | + | <syntaxhighlight lang='cpp'> |
| − | + | dp[0][0] = 1; | |
| − | + | for (int i = 0; i < n; ++i) { | |
| + | for (int j = 0; j < 2; ++j) { | ||
| + | if (!dp[i][j]) continue; | ||
| + | if (j == 0) { | ||
| + | step = min(lcs[i][st], ed - st); | ||
| + | if (step == ed - st) dp[i + step][1] = 1; | ||
| + | } else { | ||
| + | step = 0; | ||
| + | for (int k = st; k < ed; ++k) { | ||
| + | int now_step = min(lcs[i][k], ed - k); | ||
| + | if (now_step == ed - k) dp[i + now_step][1] = 1; | ||
| + | step = max(step, now_step); | ||
| + | } | ||
| + | } | ||
| + | for (int k = 1; k <= step; ++k) | ||
| + | dp[i + k][0] = 1; | ||
| + | } | ||
| + | } | ||
| + | return dp[n][1]; | ||
| + | </syntaxhighlight> | ||
Latest revision as of 15:44, 11 March 2018
ultmaster
Problem D
题意：给一张贴好的邮票。问有哪些小邮票最后可以贴出这个图案。
题解：枚举所有子串。然后 check。check 的方法：题解的没看懂，自己想了一种：$dp(i+1,0)$ 表示到 $i$ 为止，左边的那段还没结束，也就是说不能接一段中间开始的（一定要接从头开始的）。可行为 1，不可行为 0；$dp(i+1,1)$ 表示到 $i$ 为止，左边的那段已经结束，可以接一段从中间开始的。这个一定要画个图理解一下！刚开始 $dp(0,0)=1$，最后如果 $dp(n,1)=1$ 则可行。更新的时候要利用最长公共后缀来更新，注意处理 min 和 max。
dp[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
if (!dp[i][j]) continue;
if (j == 0) {
step = min(lcs[i][st], ed - st);
if (step == ed - st) dp[i + step][1] = 1;
} else {
step = 0;
for (int k = st; k < ed; ++k) {
int now_step = min(lcs[i][k], ed - k);
if (now_step == ed - k) dp[i + now_step][1] = 1;
step = max(step, now_step);
}
}
for (int k = 1; k <= step; ++k)
dp[i + k][0] = 1;
}
}
return dp[n][1];