【SCOI2013】【Bzoj3325】【Luogu3279】密码

Source and Judge

SCOI2013
Bzoj3325
Luogu3279

Problem

【Description】
已知一个字符串的:
1. 长度为N。
2. 仅含小写字母。
3. 以每一个字符为中心的最长回文串长度。
4. 以每两个相邻字符的间隙为中心的最长回文串长度。

输出满足条件的字符串中字典序最小的。
【Input】
输入由三行组成。
第一行仅含一个整数N,表示长度。
第二行包含N 个整数,表示以每个字符为中心的最长回文串长度。
第三行包含N - 1 个整数,表示每两个相邻字符的间隙为中心的最长回文串长度。
【Output】
输出答案,保证有解
【Limited conditions】
对于20% 的数据,1 <= n <= 100。
另有30% 的数据,1 <= n <= 1000。
最后50% 的数据,1 <= n <= 10^5。
【Sample input 1】
3
1 1 1
0 0
【Sample output 1】
abc
【Sample input 2】
3
1 3 1
0 0
【Sample output 2】
aba
【Sample input 3】
3
1 3 1
2 2
【Sample output 3】
aaa
【Sample explanation】

Record

2h

Analysis

请先思考后再展开

一开始想贪心乱搞,然后显然是不可靠の玄学的
怎样稳一点呢?相等性和互斥性,而且不是二分图,那不就是并查集了嘛!
但是我们并不能单单处理相同的,然后去合并,也不能像某些二分图的时候那样拆成两个对立点,把所有对立的合并起来,因为字母不只2个。
有种非常妙的办法:建边!
把与该点所在集合存在互斥关系的集合连上边,然后分配的时候,因为要求字典序最小,则必须选择一个【没有被在前面的,与当前互斥】的字母。
注意一定要从整个集合来看,网上有人直接从当前点出发,显然是不正确的,虽然说数据比较水
这样,我们就有50分辣!激动吗?(雾

首先,通常来说,如果一个正规比赛题面有非常类似某个算法的裸题的描述的话,通常来说其实不是用这种算法。。。
然鹅今天连做两道题都是要用到那个算法。。(另一个是动物园。。kmp)
所以我们还是要借鉴一下manacher的神奇线性做法滴

例如这种情况,就造成了重复,虽然并不是那么直观。

manacher的跳过,是不需要验证相同。
这道题的跳过,是不需要使它们相同。
操作的类似使复杂度也是O(n)的。

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=210000;
//*******************全局定义*******************
int n;
int ma[MAXN],g[MAXN];
int v[30];//时间戳
int c[MAXN];//分配
//*******************实现*******************
int fa[MAXN];
int findfa(int x) {return (x==fa[x])?x:fa[x]=findfa(fa[x]);}
void merg(int x,int y)
{
int fx=findfa(x),fy=findfa(y);
if(fx!=fy) fa[fx]=fy;
}
int hou[MAXN];
struct Edge
{
int y,g;
}e[MAXN*2];//互斥关系
int ln=0;
void ins(int x,int y)
{
if(!(1<=x and x<=n)) return;
if(!(1<=y and y<=n)) return;
e[++ln]=(Edge){y,hou[x]};hou[x]=ln;
e[++ln]=(Edge){x,hou[y]};hou[y]=ln;
}
//*******************主函数*******************
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&g[2*i]),++g[2*i];
for(int i=1;i<=n-1;i++) scanf("%d",&g[2*i+1]),++g[2*i+1];
n=n*2;ma[1]=1;
for(int i=1;i<=n;i++) fa[i]=i;//debug 在后面
int md=1,rx=md+ma[md]-1;
for(int i=2;i<=n;i++)
{
ma[i]=(i>rx)?1:mymin(ma[2*md-i],rx-i+1);
for(;ma[i]<g[i];ma[i]++) merg(i-ma[i],i+ma[i]);
//ins(i-g[i],i+g[i]);//必须不同
if(i+ma[i]-1>rx) md=i,rx=md+ma[md]-1;
}
for(int i=2;i<=n;i++) ins(findfa(i-g[i]),findfa(i+g[i]));//必须不同
//奇数位已经无意义
for(int i=2;i<=n;i+=2)
{
int fx=findfa(i);
if(!c[fx])//不能占用0……
{
for(int k=hou[fx];k>0;k=e[k].g) v[ c[findfa(e[k].y)] ]=i;
for(int j=1;j<=26;j++) if(v[j]<i) {c[fx]=j;break;}
}
putchar('a'+c[fx]-1);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/密码.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%