社区讨论
求问:为什么这么写后两个点不输出
P4391[BalticOI 2009] Radio Transmission 无线传输参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m4o4dwqm
- 此快照首次捕获于
- 2024/12/14 19:54 去年
- 此快照最后确认于
- 2025/11/04 12:51 4 个月前
明明前8个都对
CPP#include<bits/stdc++.h>
#define ll long long
#define ull usigned long long
#define ld long double
#define rep(x,a,b) for(int x=(a);x<=(b);++x)
#define rop(x,a,b) for(int x=(a);x<(b);++x)
#define per(x,a,b) for(int x=(a);x>=(b);--x)
#define pb push_back
using namespace std;
const int N = 2e6 + 10;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
ll llread(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
char s[N];
int nxt[N], len;
int f[N];
int main(){
len = read();
cin >> (s+1);
nxt[0] = -1;
for( int i = 2 , j = 0 ; i <= len ; ++i ){
if( j && s[i] != s[j+1] )j = nxt[j];
if( s[i] == s[j+1] )j++;
nxt[i] = j;
}
f[1] = 1;
for( int i = 2 ; i <= len ; ++i ){
f[i] = i;
if( nxt[i] != 0 ){
if( nxt[i] <= f[i] ){
f[i] = f[i-1];
}
else{
int t = nxt[i];
if( t*2 > i && nxt[t] != 0 ){
t = nxt[t];
}
nxt[i] = t;
if( nxt[t] <= f[i] )f[i] = f[i-1];
}
}
}
cout << f[len] << "\n";
return 0;
}
/*
100
zzyyzyxxyzzzyxyzyzxxxxzxyyxzzzzxzxxyzyyxzxzxxzxyzyzzyxxyzxyyyzzxxyyzyyzxzxyzxxxzxzxyxzyzzyxxzyzyzxxz
*/
回复
共 0 条回复,欢迎继续交流。
正在加载回复...