题目描述&＃xff1a;
首先看到这题应该知道该怎么裸吧…………以每个字符和间隙为中心可以建立若干个等和不等关系。相等关系可以用并查集合并&＃xff0c;不等关系之间连边。然后对每一位贪心地选取合适的字典序最小的字符就可以了。
然后我们发现&＃xff0c;这样是会T的&＃xff08;废话&＃xff09;&＃xff0c;为什么&＃xff1f;因为我们进行了太多无意义的关系判定&＃xff0c;设想有一个非常长的回文串&＃xff0c;它的左半边有一些小的回文串&＃xff0c;我们已经为它们建立好了关系&＃xff0c;那么右半边何必再做一遍呢&＃xff1f;&＃xff1f;也就是说我们一边处理关系&＃xff0c;一边记录当前最右覆盖的端点&＃xff0c;每次只对覆盖端点以外进行关系的建立&＃xff0c;这样由于右端点是单调的&＃xff0c;不难推出复杂度为O(n)&＃xff0c;于是就可以通过了。
ps.这种思想其实就是Manachar算法&＃xff0c;一种线性求回文的算法的运用&＃xff0c;有关该算法的具体内容可自行google。
ps ps考试的时候这道题是我最悲剧的……………………………………打错了一个变量……………………………………瞬间从100分变成了20分…………………………弱炸天了有木有……………………
ps ps ps再次证明了电子科大的样例出得之好……
代码&＃xff1a;
1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6
7 const int MAXN&＃61;100010;
8 const int MAXM&＃61;1000010;
9
10 struct Node
11 {
12 int end;
13 Node *next;
14 }edge[MAXM],*head[MAXN],*head_clr[MAXN];
15
16 int all,x,n,rmost,fa[MAXN],used[MAXN];
17 char str[MAXN];
18
19 int find_set(int u)
20 {
21 if (fa[u]&＃61;&＃61;u) return u;
22 return fa[u]&＃61;find_set(fa[u]);
23 }
24 void union_set(int a,int b)
25 {
26 int f1&＃61;find_set(a);
27 int f2&＃61;find_set(b);
28 if (f1!&＃61;f2) fa[f1]&＃61;f2;
29 }
30 void add_diff(int a,int b)
31 {
32 edge[all].end&＃61;b,edge[all].next&＃61;head[a],head[a]&＃61;edge&＃43;(all&＃43;&＃43;);
33 }
34 void add_color(int a,int b)
35 {
36 edge[all].end&＃61;b,edge[all].next&＃61;head_clr[a],head_clr[a]&＃61;edge&＃43;(all&＃43;&＃43;);
37 }
38 int main()
39 {
40 freopen("password.in","r",stdin);
41 freopen("password.out","w",stdout);
42 scanf("%d",&n);
43 for (int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)
44 fa[i]&＃61;i;
45 for (int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)
46 {
47 scanf("%d",&x);
48 x>>&＃61;1;
49 for (int j&＃61;max(rmost-i,1);j<&＃61;x;&＃43;&＃43;j)
50 union_set(i&＃43;j,i-j);
51 if (i-x-1>&＃61;1 && i&＃43;x&＃43;1<&＃61;n) add_diff(i-x-1,i&＃43;x&＃43;1),add_diff(i&＃43;x&＃43;1,i-x-1);
52 rmost&＃61;max(i&＃43;x,rmost);
53 }
54 rmost&＃61;0;
55 for (int i&＃61;1;i
56 {
57 scanf("%d",&x);
58 x>>&＃61;1;
59 for (int j&＃61;max(rmost-i,1);j<&＃61;x;&＃43;&＃43;j)
60 union_set(i-j&＃43;1,i&＃43;j);
61 /*就是这里的j打成x了………………永远的痛啊………………*/
62 if (i-x>&＃61;1 && i&＃43;x&＃43;1<&＃61;n) add_diff(i-x,i&＃43;x&＃43;1),add_diff(i&＃43;x&＃43;1,i-x);
63 rmost&＃61;max(i&＃43;x,rmost);
64 }
65 for (int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)
66 add_color(find_set(i),i);
67 char x;
68 for (int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)
69 {
70 if (!str[i])
71 {
72 x&＃61;&＃39;a&＃39;;
73 for (Node *p&＃61;head[i];p;p&＃61;p->next)
74 used[str[p->end]]&＃61;i;
75 while (used[x]&＃61;&＃61;i) &＃43;&＃43;x;
76 str[i]&＃61;x;
77 for (Node *p&＃61;head_clr[find_set(i)];p;p&＃61;p->next)
78 str[p->end]&＃61;x;
79 }
80 }
81 puts(str&＃43;1);
82 return 0;
83 }
京公网安备 11010802041100号