一次简单的div2...还以为可以一举上紫名...然而

传送门：http://codeforces.com/contest/557

A. Ilya and Diplomas

一道阅读题（英语是硬伤啊！）贪心水过

B. Pasha and Tea

同上

C. Arthur and Table

一开始并不会做，然后经提醒注意到d<=200,所以直接枚举最大长度，然后在小于这个长度的部分贪心取值

D. Vitaly and Cycle

题意：一张不保证联通的无向图，求至少添加几条边是这张图出现一个有奇数条边的环。

先对图进行搜索并黑白染色，然后按照添加0,1,2,3条边进行分类。

1）ans1=0 就是出现了奇数环的情况

2）ans1=1 有某个联通块的点数多于二，ans2=Σ各个联通块选取同色点的种数

3) ans1=2 在这种情况上，只会出现1或2个点的联通快，ans2=num(double node)*(n-2)

4) ans1=3 ans2=c(n,3)

E. Ann and Half-Palindrome

直接上原题解：

This problem can be solved with help of dynamic programming.

At first we calculate matrix good[][]. In good[i][j] we put true, if substring from position i to position j half-palindrome. Else we put ingood[i][j]false. We can do it with iterating on "middle" of half-palindrome and expanding it to the left and to the right. There are 4cases of "middle" but we omit it because they are simple enough.

Now we need to use Trie and we will put in it suffixes of given string. Also we will store array cnt[]. In cnt[v] we will store number of half-palindromes which ends in vertex v of our Trie. Let now we put in tree suffix which starts in position i, current symbol of string which we put is in position j and we go in vertex v of out Trie. Then if good[i][j] = true we add one to cnt[v].

Now with help of dfs let calculate for every vertex sum[v] — sum of numbers which stored in array cnt[] for vertex v and for vertices in all subtrees of vertex v.

It is left only to restore answer. Start from root of our Trie. We will store answer in variable ans. In variable k store number of required substring. Let now we in vertex v, by letter 'a' we can go in vertex toa and by letter 'b' — in vertex tob.

Then if sum[toa] ≤ k we make ans +  = 'a' and go in vertex toa of our Trie. Else we need to make as follows: k —  = sum[toa],ans +  = 'b' and go in vertex tob of our Trie.

When k will be  ≤ 0 print resulting string ans and finish algorithm.

Asymptotic behavior of this solution — O(szalph * n2) where szalph — size of input alphabet (in this problem it equals to two) and n — length of given string.

附我自己写的：

var
	u,k,i,j,tot,n,h:longint;
        ch:array[0..25001000,0..1] of longint;
        v,sum:array[0..25001000] of longint;
	dp:array[0..5500,0..5500] of boolean;
	s:ansistring;
procedure add;
var
	i,u,xx:longint;
begin
	for j:=1 to n do
	begin
	u:=0;
	for i:=j to n do
	begin
		xx:=ord(s[i])-97;
		if ch[u,xx]=0 then
		begin
			inc(tot);
			ch[u,xx]:=tot;
		end;
		u:=ch[u,xx];
		if dp[j,i] then inc(v[u]);
	end;
	end;
end;

procedure dfs(x:longint);
begin
	if ch[x,0]<>0 then begin dfs(ch[x,0]); sum[x]:=sum[x]+sum[ch[x,0]]; end;
	if ch[x,1]<>0 then begin dfs(ch[x,1]); sum[x]:=sum[x]+sum[ch[x,1]]; end;
	sum[x]:=sum[x]+v[x];
end;

begin
		readln(s); read(k);
                n:=length(s);
		for i:=1 to n do
		begin
			dp[i,i]:=true;
			h:=i-1; while (h>0)and(i*2-h<=n)and(s[h]=s[i*2-h]) do begin   dp[h,2*i-h]:=true; h:=h-2;end;
			h:=i-2; while (h>0)and(i*2-h<=n)and(s[h]=s[i*2-h]) do begin   dp[h,2*i-h]:=true; h:=h-2;end;
			h:=i-1; while (h>0)and(i*2+1-h<=n)and(s[h]=s[i*2+1-h]) do begin dp[h,i*2+1-h]:=true; h:=h-2; end;
			if (i<>n)and(s[i]=s[i+1]) then
			begin
                 dp[i,i+1]:=true;
				h:=i-2; while (h>0)and(i*2+1-h<=n)and(s[h]=s[i*2+1-h]) do begin   dp[h,i*2+1-h]:=true; h:=h-2; end;
			end;
		end;
                add();
		dfs(0);
		u:=0;
		while k>0 do
		begin
			if (ch[u,0]<>0)and(sum[ch[u,0]]>=k) then
			begin
				write('a'); u:=ch[u,0]; k:=k-v[u];
			end
			else
			begin
				write('b'); if ch[u,0]<>0 then k:=k-sum[ch[u,0]]; u:=ch[u,1];  k:=k-v[u];
			end;
		end;
end.

Fractal128