can anyone give me some link to kopeliovich_diploma translation in englich or to some tutorial of the same ideas proposed for serguei kopeliovich?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | djm03178 | 152 |
can anyone give me some link to kopeliovich_diploma translation in englich or to some tutorial of the same ideas proposed for serguei kopeliovich?
please god of code, do not make me wait 9 days by a contest of codeforces
hello everyone, i want to study flow and its aplications, i already knows the basics, can anyone suggest me some literature and some problems, thanks
problem link ----> here
this is my solution, i can´t find something better
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define sf scanf
#define pf printf
#define ll long long
#define MAXN 10002
int d1[MAXN];
int d2[MAXN];
int manager(char *s, int n){
int cant=0;
int l,l2,r,r2,k,i;
l=l2=0; r=r2=-1;
for(i=0;i<n;i++){
k = (i>r ? 0 : min(d1[l+r-i],r-i)) + 1;
while(i+k<n && i-k>=0 && s[i-k]==s[i+k]) k++;
d1[i]=--k;
if(i+k>r) l=i-k, r=i+k;
k = (i>r2 ? 0 : min(d2[l2+r2-i+1],r2-i+1)) + 1;
while( (i+k-1)<n && (i-k)>=0 && s[i+k-1]==s[i-k] ) ++k;
d2[i]=--k;
if( (i+k-1)>r2 ) l2=i-k, r2=i+k-1;
cant+=(d1[i]+d2[i]);
}
return cant;
}
int K;
bool isP(int i,int j){
int x = i + ((j-i+1)/2);
return ((j-i+1)%2==0 ? (x-d2[x] <= i) : (x-d1[x] <= i) );
}
typedef pair<vector<int>,int> par;
par prefix_function(string s){
int n = (int)s.length();
vector<int> pi(n);
int maxpi = 0;
for(int i=1;i<n;i++){
int j = pi[i-1];
while(j>0 && s[i] != s[j])
j = pi[j-1];
if(s[i] == s[j]) j++;
pi[i] = j;
maxpi = max(maxpi,pi[i]);
}
return {pi,maxpi};
}
int solve(char *s, int n){//O(n^2)
int ans = 0, maxpi = 0;
vector<int> pi;
string ss = "";
for(int i = 0; i < n; i++){
ss = s[i] + ss;
par kmp = prefix_function(ss);//O(n)
pi = kmp.first;
maxpi = kmp.second;
int aux = max(K-1,maxpi);
aux++;
//O(n)
for(int j = i-aux+1, ind = aux-1 ; j>=0; j--,ind++){
int yy = (ind+1) - pi[ind];//compresion_line
if(isP(j,i) && yy < (ind+1))
if( (yy == 1 && ind+1 >= 4) ||
((ind+1) % yy == 0 && isP(i-yy+1,i)) )
ans++;
}
}
return ans;
}
char w[MAXN];
int main(){
sf("%d%s",&K,w);
int n = strlen(w);
manager(w,n);
pf("%d\n",solve(w,n));
return 0;
}
Название |
---|