[数据结构与算法]2021牛客寒假算法基础集训营3

2021牛客寒假算法基础集训营3

【题解】2021年牛客寒假集训营第三场题解

I序列的美观度

线性DP

题目判断错误，看了那么多模拟题，还以为这也是模拟题，没看透题哦

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
int a[N], last[N];
LL f[N];
/*
这是一道DP，你还以为是一个模拟呢。
用DP的方法来做，线性DP。
让f[i]表示走到底i个元素，他的美观程度最大是多少
那么我们可以分为两种情况
1.f[i] = f[last] + 1, 与前面出现过的元素的位置的值+1
这是用当前这个元素来匹配
2.f[i] = f[i - 1]我们不用当前元素来匹配
*/
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

for (int i = 1; i <= n; i ++ ) {
if (last[a[i]]) {
f[i] = f[last[a[i]]] + 1;

}
f[i] = max(f[i - 1], f[i]);
last[a[i]] = i;
}

cout << f[n] << endl;

return 0;
}

F匹配串

思维题，若一个字符串的前缀可以包含所有前缀，还有一个字符串（可以是同一个）后缀可以包含所有后缀，那答案就是-1否则就是0

（因为前缀F后面就是#，后缀前面就是#，#可以任意变化，所以，我们反过来看是否有不满足前缀和后缀的，只要有一个，就是0）

就像trie树一般，用一维存起来出现了的前缀和后缀，不过改进的是，我们不让trie树有分支，不在这个树干上的全给他当成错误来处理咯

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
char sl[N], sr[N];
char s[N];

int main() {
scanf("%d", &n);

int tot1 = 0, tot2 = 0;
while (n -- ) {
scanf("%s", s);
for (int i = 0; s[i]; i ++ )
  if (s[i] != '#') {
    if (i >= tot1) sl[tot1 ++ ] = s[i];
    else if (s[i] != sl[i]) return 0 * puts("0");
    //cout << s[i] << ' ' << sl[i] << ' ' << i << endl;
  }
  else break;

int len = strlen(s);
for (int i = 0; i < len; i ++ ){
  int t = len - i - 1;
  if (s[t] != '#') {
    if (len - tot2 - 1 >= t && len > tot2) sr[tot2 ++ ] = s[t];
    else if (s[t] != sr[i]) return 0 * puts("0");
    //cout << s[t] << ' ' << sr[i] << ' ' << i << endl;
  }
  else break;
}

}

puts("-1");

return 0;
}

J加法和乘法

博弈论。

特判n==1

若n为奇数，最后操作的为牛妹，她一定可以将最后两个数组成偶数

若n为偶数，如果其中偶数的个数大于等于2，每次牛牛消灭一个偶数，但是牛妹可以每次消灭两个奇数，所以综合起来，两人都操作一次，会一直让偶数处于大于等于2的状态，那到了最后一步，牛牛操作，一定会剩下两个偶数，牛牛必输。

只有当n为偶数，且其中的偶数个数为0，或1时牛牛才可能获胜。