社区讨论

求问:为什么这么写后两个点不输出

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 条回复,欢迎继续交流。

正在加载回复...