2018-07-26

newcoder contest3

newcoder cotest3

pbds

rolling hash
双hash还是单hash,

A

四维的01背包，因为有空间的限制，需要用short类型的数据类型减少空间的开销。

C

纸牌问题，splay来维护，需要学习一下

类似的题目 play with a chain

hdu3487

###
涉及到下面的操作

切出一段然后置换
翻转一段区间

求字符串的循环节

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1000010;
void getFail(char *P, int m, int f[]) {
    f[0] = f[1] = 0;
    for(int i = 1; i < m; ++i) {
        int j = f[i];
        while(j && P[i] != P[j]) j = f[j];
        f[i + 1] = (P[i] == P[j] ? j + 1 : 0);
    }
}
char s[MAXN];
int fail[MAXN], n;
int main() {
    while(scanf("%s", s) != EOF) {
        if(*s == '.') break;
        n = strlen(s);
        getFail(s, n, fail);
        if(n % (n - fail[n]) == 0) printf("%d\n", n / (n - fail[n]));
        else puts("1");
    }
}

I

听说随机化搞就行了，本地打表然后交表，不知道具体是怎么实现的。

J

圆与凸包的面积交，计算几何的板子。

未解决的问题

本文标题:newcoder contest3

文章作者:Babydragon

发布时间:2018-07-26, 16:22:13

最后更新:2018-07-28, 11:10:14

原始链接:http://baolintian.github.io/2018/07/26/newcoder-contest3/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。