【Codeforces 804C】Ice cream coloring

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 600009;

vector<int> vis[N],lst[N];
set<int> que[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void AddEdge(int u, int v) {
static int E = 1;
}

inline void solve(int w, int f) {
int cur = 1;
for (int jj=0;jj<lst[w].size();jj++) {
int j = lst[w][jj];
if (!col[j]) {
while (!que[w].empty() && cur == *que[w].begin()) {
++cur;
que[w].erase(que[w].begin());
}
col[j] = cur;
for (int k=0;k<vis[j].size();k++) {
que[vis[j][k]].insert(cur);
}
}
}
if (to[i] != f) {
solve(to[i], w);
}
}
}

int main() {
ans = 1;
for (int i=1;i<=n;i++) {
ans = max(ans, sz[i]);
for (int j=1,p;j<=sz[i];j++) {
vis[p].push_back(i);
lst[i].push_back(p);
}
}
for (int i=1;i<n;i++) {
}
solve(1, 1);
cout<<ans<<endl;
for (int i=1;i<=m;i++) {
printf("%d ",col[i]? col[i]: 1);
}
return 0;
}


【BZOJ 3103】[ONTAK2010] Palindromic Equivalence

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000009;
const int M = N << 1;
const int MOD = 1000000007;

char pat[N],s[N];
int n,ans=1,fa[N],rid[N],col[N];
vector<pair<int,int> > e;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int find(int x) {
return x == fa[x]? x: fa[x] = find(fa[x]);
}

inline void manacher() {
for (int i=1,r=1,p=1,t;i<=n*2;i++) {
t = min(r - i, rid[p - (i - p)]);
while (s[i+t+1] == s[i-t-1]) t++, fa[find(i+t)] = find(fa[i-t]);
if ((rid[i] = t) + i > r) r = t + i, p = i;
e.push_back(make_pair(i - t - 1, i + t + 1));
}
}

inline void AddEdge(int u, int v) {
static int E = 1;
if (u == v || !(u & 1) || !(v & 1)) return;
}

int main() {
scanf("%s",pat+1); n = strlen(pat+1);
s[0] = '#'; s[n*2] = '@';
for (int i=1;i<=n;i++) s[i*2-1] = pat[i], s[i*2] = '*';
for (int i=1;i<=n*2;i++) fa[i] = i;
manacher();
for (int i=1,cnt;cnt=26,i<=n*2;i+=2) {
if (find(i) != i) continue; col[i] = 1;
if (col[to[j]] && vis[to[j]] < i)
--cnt, vis[to[j]] = i;
}
if (cnt <= 0) ans = 0;
else ans = (LL)ans * cnt % MOD;
}
cout<<ans;
return 0;
}


—————————— UPD 2017.4.26 ——————————

【BZOJ NOI十连测】KMP

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define LL long long
using namespace std;

char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}

const int MAXN = 200000+9;
const LL MOD = 1000000000+7;

int n,c,cnt,fail[MAXN],p[MAXN],Ord[MAXN];
int tot,mx,used[MAXN],pos[MAXN],ord[MAXN];
queue<int> que[MAXN];

inline void AddEdge(int u, int v){
}

inline void MCS(){
tot = 0; mx = 0;
for (int i=1;i<=n;i++)
que[0].push(i);

while (tot < n){
while (!que[mx].empty()&&used[que[mx].front()])
que[mx].pop();
if (que[mx].empty()) mx--;
else {
int w = que[mx].front(); que[mx].pop();
ord[++tot] = w; used[w] = 1;
que[++pos[to[i]]].push(to[i]),
mx = max(mx, pos[to[i]]);
}
}
}

int main(){
for (int i=2;i<=n;i++) fail[i] = read();

p[1] = cnt = 1;
for (int i=1,j;i<n;i++){
if (fail[i+1]) p[i+1]=p[fail[i+1]];
else {
int j = fail[i]; p[i+1]=++cnt;
while (j) {
if (Ord[p[j+1]] < i+1 )
j=fail[j];
}
if (Ord[p[j+1]] < i+1 )
}
}

MCS();

LL vout = 1;
memset(used,0,sizeof(used));
for (int j=1,i=ord[j],sum;j<=cnt;i=ord[++j]){
sum = 0;
if (used[to[k]]) sum++;
sum = c-sum; used[i] = 1;
vout = (vout*(LL)sum)%MOD;
}
printf("%lld\n",vout);

return 0;
}


%%% YJQ 的利用kmp特殊性质的神代码：

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const LL MOD = 1000000000+7;
const int MAXN = 200000+9;
int n,m,fail[MAXN],go[MAXN];

int main(){
cin>>n>>m;
for (int i=2;i<=n;i++)
scanf("%d",&fail[i]);
go[0]=1; int ans=m;
for (int i=1;i<n;i++){
if (fail[i+1]) go[i] = go[fail[i]];
else go[i] = go[fail[i]]+1,
ans = 1LL*ans*(m-go[fail[i]])%MOD;
}
printf("%d\n",ans);
return 0;
}


Chordal_Graph