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];