Luogu2375 [NOI2014]动物园 （KMP）
2024-10-20 13:38:07
写炸，上网，不同KMP形态。
无力，照该，一换写法就过。
横批：我是垃圾
求\(next\)时\(DP\)出\(num\)，路径压缩防卡\(n^2\)
AC
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); a <= (c); ++ a)
#define nR(a,b,c) for(register int a = (b); a >= (c); -- a)
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Abs(a) ((a) < 0 ? -(a) : (a))
#define Swap(a,b) a^=b^=a^=b
#define ll long long
#define ON_DEBUG
#ifdef ON_DEBUG
#define D_e_Line printf("\n\n----------\n\n")
#define D_e(x) cout << #x << " = " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt","r",stdin);
#else
#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#endif
struct ios{
template<typename ATP>ios& operator >> (ATP &x){
x = 0; int f = 1; char c;
for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
x*= f;
return *this;
}
}io;
using namespace std;
const int N = 1000007;
const int mod = 1000000007;
int nxt[N], num[N];
char str[N];
int main() {
//FileOpen();
int n;
io >> n;
while(n--) {
scanf("%s", str);
int len = strlen(str);
int ans = 1;
R(i,1,len) nxt[i] = 0;
nxt[0] = -1;
num[0] = 0, num[1] = 1;
int i = 0, j = -1;
while(i < len){
if(j == -1 || str[i] == str[j]){
nxt[++i] = ++j;
num[i] = num[j] + 1;
}
else
j = nxt[j];
}
i = 0, j = -1;
while(i < len){
if(j == -1 || str[i] == str[j]){
++i, ++j;
while((j << 1) > i + 1) j = nxt[j];
ans = ans * 1ll * (num[j] + 1) % mod;
}
else
j = nxt[j];
}
printf("%d\n", ans);
}
return 0;
}
全\(WA\)的原始代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); a <= (c); ++ a)
#define nR(a,b,c) for(register int a = (b); a >= (c); -- a)
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Abs(a) ((a) < 0 ? -(a) : (a))
#define Swap(a,b) a^=b^=a^=b
#define ll long long
#define ON_DEBUG
#ifdef ON_DEBUG
#define D_e_Line printf("\n\n----------\n\n")
#define D_e(x) cout << #x << " = " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt","r",stdin);
#else
#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#endif
struct ios{
template<typename ATP>ios& operator >> (ATP &x){
x = 0; int f = 1; char c;
for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
x*= f;
return *this;
}
}io;
using namespace std;
const int N = 1000007;
const int mod = 1000000007;
int nxt[N], num[N];
char str[N];
int main() {
//FileOpen();
int n;
io >> n;
while(n--) {
scanf("%s", str);
int len = strlen(str);
int ans = 1;
R(i,1,len) nxt[i] = 0;
nxt[0] = -1;
num[0] = 0, num[1] = 1;
int i = 0, j = -1;
while(i < len){
if(j == -1 || str[i] == str[j]){
nxt[++i] = ++j;
num[i] = num[j] + 1;
}
else
j = nxt[j];
}
i = 0, j = -1;
while(i < len){
if(j == -1 || str[i] == str[j]){
++i, ++j;
while((j << 1) > i + 1) j = nxt[j];
ans = ans * 1ll * (num[j] + 1) % mod;
}
else
j = nxt[j];
}
printf("%d\n", ans);
}
return 0;
}
最新文章
- php+mysql
- 【转】解决eclipse无法设置NDK问题
- POJ 2838 单调队列
- 日常css和js小知识点记录
- ZOJ 3644 Kitty's Game dfs,记忆化搜索,map映射 难度:2
- struts2上传下载
- PAT (Advanced Level) 1066. Root of AVL Tree (25)
- js原生拓展网址——mozilla开发者
- EMC题
- 说一说MVC的CompressActionFilterAttrubute（五）
- Linux基础命令---uname显示计算机名称
- Android--小游戏
- 初学Python——文件操作第二篇
- 吉特日化MES-日化生产称料基本步骤
- windows10 vs2017 C++连接MySQL
- luogu 4401 矿工配餐 多维dp
- Hadoop – The Definitive Guide Examples,,IntelliJ
- 课程一(Neural Networks and Deep Learning)，第四周（Deep Neural Networks）—— 1.Practice Questions: Key concepts on Deep Neural Networks
- poj3208 Apocalypse Someday 数位dp+二分 求第K(K <= 5*107)个有连续3个6的数。
- HDU 6153 A Secret（扩展kmp）