TJOI2015题解

（转载前请标明出处，谢谢）

打算来做一波TJOI2015，来写题解啦！

Day1:

T1:［bzoj3996］

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3996

首先我们对题目中的式子化简一下，得到

；

于是这就成了一个最小割模型：

S和(i,j)连边，权值为b[i,j]
(i,j)和i，j分别连边，权值为inf
i和T连边，权值为c[i]

于是跑一下最小割就可以了；

（然而不知道发生了什么。。。最小割跑不过去。。。似乎bzoj把p党卡常数了QAQ）

（cyand神犇说他在省选的时候贪心了一发，就过了，至今找不出反例，于是我水过去了）

最小割代码如下：

  1 uses math;
  2 var s,t,n,i,j,tot,w,cnt:longint;
  3     last,pre,other,flow:array[0..2600000] of longint;
  4     l,q:array[0..3000000] of longint;
  5     ans:int64;
  6 procedure insert(a,b,c,d:longint);
  7 begin
  8   pre[tot]:=last[a];
  9   last[a]:=tot;
 10   other[tot]:=b;
 11   flow[tot]:=c;
 12   inc(tot);
 13   pre[tot]:=last[b];
 14   last[b]:=tot;
 15   other[tot]:=a;
 16   flow[tot]:=d;
 17   inc(tot);
 18 end;
 19 function bfs:boolean;
 20 var s1,t1,u,v,q1:longint;
 21 begin
 22   fillchar(q,sizeof(q),0);
 23   for i:=0 to n do
 24     l[i]:=-1;
 25   s1:=0;
 26   t1:=1;
 27   l[s]:=1;
 28   q[t1]:=s;
 29   while (s1<t1) do
 30   begin
 31     inc(s1);
 32     u:=q[s1];
 33     q1:=last[u];
 34     while (q1>=0) do
 35     begin
 36       v:=other[q1];
 37       if (flow[q1]>0) and (l[v]=-1) then
 38       begin
 39         inc(t1);
 40         q[t1]:=v;
 41         l[v]:=l[u]+1;
 42       end;
 43       q1:=pre[q1];
 44     end;
 45   end;
 46   if (l[t]=-1) then exit(false) else exit(true);
 47 end;
 48 function find(u,int:longint):longint;
 49 var w,v,q1,t1:longint;
 50 begin
 51   if (u=t) then exit(int);
 52   w:=0;
 53   q1:=last[u];
 54   while (q1>=0) and (w<int) do
 55   begin
 56     v:=other[q1];
 57     if (l[v]=l[u]+1) then
 58     begin
 59       t1:=find(v,min(flow[q1],int-w));
 60       flow[q1]:=flow[q1]-t1;
 61       flow[q1 xor 1]:=flow[q1 xor 1]+t1;
 62       w:=w+t1;
 63     end;
 64     q1:=pre[q1];
 65   end;
 66   if (w>=int) then l[u]:=-1;
 67   exit(w);
 68 end;
 69 function dinic:int64;
 70 var e:longint;
 71   ans:int64;
 72 begin
 73   ans:=0;
 74   while bfs do
 75   begin
 76     e:=find(s,maxlongint);
 77     ans:=ans+e;
 78   end;
 79   exit(ans);
 80 end;
 81 begin
 82   readln(n);
 83   s:=n*n+n+1;
 84   t:=n*n+n+2;
 85   tot:=0;
 86   for i:=0 to t do
 87     last[i]:=-1;
 88   cnt:=n;
 89   ans:=0;
 90   for i:=1 to n do
 91   begin
 92     for j:=1 to n do
 93     begin
 94       read(w);
 95       inc(cnt);
 96       insert(s,cnt,w,0);
 97       insert(cnt,i,maxlongint,0);
 98       if (i<>j) then insert(cnt,j,maxlongint,0);
 99       ans:=ans+w;
100     end;
101     readln;
102   end;
103   for i:=1 to n do
104   begin
105     read(w);
106     insert(i,t,w,0);
107   end;
108   readln;
109   n:=t;
110   writeln(ans-dinic);
111 end.
112

贪心代码如下：

 1 var n,i,j,s,ans,max,max1:longint;
 2     b:array[0..1000,0..1000] of longint;
 3     c,inc:array[0..1000] of longint;
 4 begin
 5   readln(n);
 6   for i:=1 to n do
 7   begin
 8     for j:=1 to n do
 9         read(b[i,j]);
10     readln;
11   end;
12   for i:=1 to n do
13     read(c[i]);
14   readln;
15   fillchar(inc,sizeof(inc),0);
16   s:=0;
17   ans:=0;
18   for i:=1 to n do
19   begin
20     s:=0;
21     for j:=1 to n do
22         s:=s+b[i,j]+b[j,i];
23     inc[i]:=b[i,i]-s+c[i];
24   end;
25   for i:=1 to n do
26     for j:=1 to n do
27         ans:=ans+b[i,j];
28   for i:=1 to n do
29     ans:=ans-c[i];
30   while true do
31   begin
32     max:=-1;
33     max1:=-1;
34     for i:=1 to n do
35       if (max<inc[i]) then
36       begin
37         max:=inc[i];
38         max1:=i;
39       end;
40     if (max1=-1) then break;
41     ans:=ans+max;
42     for i:=1 to n do
43       inc[i]:=inc[i]+b[i,max1]+b[max1,i];
44     inc[max1]:=-1;
45   end;
46   writeln(ans);
47 end.
48

T2:［bzoj3997］

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3997

本题要用一个Dilworth定理：DAG最小链覆盖＝最大独立子集，

于是发现最大独立子集显然符合题目，于是直接跑DP就可以了，方程如下：

f[i,j]=max{f[i-1,j+1]+a[i,j],f[i-1,j],f[i,j+1]}

代码如下：

 1 var t,l,n,m,i,j:longint;
 2     a,f:array[0..1005,0..1005] of int64;
 3 begin
 4   readln(t);
 5   for l:=1 to t do
 6   begin
 7     readln(n,m);
 8     fillchar(a,sizeof(a),0);
 9     fillchar(f,sizeof(f),0);
10     for i:=1 to n do
11     begin
12       for j:=1 to m do
13         read(a[i,j]);
14       readln;
15     end;
16     for i:=1 to n do
17         for j:=m downto 1 do
18         begin
19           f[i,j]:=f[i-1,j+1]+a[i,j];
20           if (f[i-1,j]>f[i,j]) then f[i,j]:=f[i-1,j];
21           if (f[i,j+1]>f[i,j]) then f[i,j]:=f[i,j+1];
22         end;
23     writeln(f[n,1]);
24   end;
25 end.

T3:［bzoj3998］

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3998

这题把我快写哭了QAQQQ。。。

这题是一个裸的后缀自动机，（然而我并不会，于是去看hzwer的博客）

于是写啊写啊写。。。然后狂WA不止。。。

问题在于，pascal党这里自动机建完以后千万不能写递归DFS。。。（C＋＋党随意）

pascal党可以改成非递归形式或者拓扑排序，就可以了QAQQQ。。。

终于AC了，撒花撒花！！！

代码如下：

  1 var ch:array[0..500005] of char;
  2     x:char;
  3     n,i,j,tt,k,last,cnt,tot:longint;
  4     a:array[0..1000005,0..25] of longint;
  5     fa,mx,val,v,q,sum:array[0..1000005] of int64;
  6 procedure extend(c:longint);
  7 var p,np,q,nq,i,j:longint;
  8 begin
  9   p:=last;
 10   inc(cnt);
 11   last:=cnt;
 12   np:=last;
 13   mx[np]:=mx[p]+1;
 14   val[np]:=1;
 15   while (a[p,c]=0) and (p<>0) do
 16   begin
 17     a[p,c]:=np;
 18     p:=fa[p];
 19   end;
 20   if (p=0) then fa[np]:=1
 21   else
 22   begin
 23     q:=a[p,c];
 24     if (mx[p]+1=mx[q]) then fa[np]:=q
 25     else
 26     begin
 27       inc(cnt);
 28       nq:=cnt;
 29       mx[nq]:=mx[p]+1;
 30       a[nq]:=a[q];
 31       fa[nq]:=fa[q];
 32       fa[q]:=nq;
 33       fa[np]:=fa[q];
 34       while (a[p,c]=q) do
 35       begin
 36         a[p,c]:=nq;
 37         p:=fa[p];
 38       end;
 39     end;
 40   end;
 41 end;
 42 procedure pre;
 43 var i,j:longint;
 44     t:int64;
 45 begin
 46   for i:=1 to cnt do
 47     inc(v[mx[i]]);
 48   for i:=1 to n do
 49     v[i]:=v[i]+v[i-1];
 50   for i:=cnt downto 1 do
 51   begin
 52     q[v[mx[i]]]:=i;
 53     dec(v[mx[i]]);
 54   end;
 55   for i:=cnt downto 1 do
 56   begin
 57     t:=q[i];
 58     if (tt=1) then val[fa[t]]:=val[fa[t]]+val[t] else val[t]:=1;
 59   end;
 60   val[1]:=0;
 61   for i:=cnt downto 1 do
 62   begin
 63     t:=q[i];
 64     sum[t]:=val[t];
 65     for j:=0 to 25 do
 66       sum[t]:=sum[t]+sum[a[t,j]];
 67   end;
 68 end;
 69 procedure dfs(x:longint);
 70 var i:longint;
 71     flag:boolean;
 72 begin
 73   while (k>val[x]) do
 74   begin
 75     k:=k-val[x];
 76     flag:=false;
 77     for i:=0 to 25 do
 78     begin
 79     if (a[x,i]>0) and not(flag) then
 80     begin
 81       if (k<=sum[a[x,i]]) then
 82       begin
 83         write(chr(i+97));
 84         x:=a[x,i];
 85         flag:=true;
 86       end
 87           else
 88       k:=k-sum[a[x,i]];
 89     end;
 90     end;
 91   end;
 92 end;
 93 begin
 94   n:=0;
 95   read(x);
 96   while not((ord(x)>=48) and (ord(x)<=57)) do
 97   begin
 98     if (ord(x)>=97) and (ord(x)<=97+25) then
 99     begin
100       inc(n);
101       ch[n]:=x;
102     end;
103     read(x);
104   end;
105   while not((ord(x)>=48) and (ord(x)<=57)) do read(x);
106   tt:=ord(x)-48;
107   read(x);
108   readln(k);
109   last:=1;
110   cnt:=1;
111   fillchar(fa,sizeof(fa),0);
112   fillchar(mx,sizeof(mx),0);
113   fillchar(val,sizeof(val),0);
114   fillchar(sum,sizeof(sum),0);
115   fillchar(v,sizeof(v),0);
116   fillchar(q,sizeof(q),0);
117   for i:=1 to n do
118     extend(ord(ch[i])-97);
119   pre;
120   tot:=0;
121   if (k>sum[1]) then write('-1') else dfs(1);
122   writeln;
123 end.

Day2:

(T1留个坑，之后补）

T2:[bzoj4000]

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4000

这一题真心有毒QAQQQ

首先题目意思理解继续要读10遍题目QAQQQ注意行数是从0开始的QAQQQ

然后就是一个状态压缩DP。。。

显然过不了TATTT。。。

那就来一发矩阵乘法！

这就是正解了。。。然后作为pascal党的我木有过。。。这题bzoj上面pascal要用double（卡精度）。。。于是TLE。。。

不过介于cojs上面过了，所以一样贴过来了。

代码如下：

  1 type arr=array[0..70,0..70] of int64;
  2 var n,m,p,k,i,j,x,max:longint;
  3     a:arr;
  4     f:array[0..70] of longint;
  5     mp:array[0..2,0..100] of longint;
  6     ans,modp:int64;
  7 function time(a:arr;b:longint):arr;
  8 var ans,now,anss:arr;
  9     i,j,k,r:longint;
 10 begin
 11   fillchar(ans,sizeof(ans),0);
 12   for i:=0 to max do
 13     ans[i,i]:=1;
 14   now:=a;
 15   r:=b;
 16   while (r>0) do
 17   begin
 18     if (r mod 2=1) then
 19     begin
 20       fillchar(anss,sizeof(anss),0);
 21       for i:=0 to max do
 22         for j:=0 to max do
 23             for k:=0 to max do
 24                 anss[i,j]:=(anss[i,j]+(int64(ans[i,k]*now[k,j])));
 25       ans:=anss;
 26     end;
 27     r:=r div 2;
 28     fillchar(anss,sizeof(anss),0);
 29     for i:=0 to max do
 30       for j:=0 to max do
 31         for k:=0 to max do
 32             anss[i,j]:=anss[i,j]+(int64(now[i,k]*now[k,j]));
 33     now:=anss;
 34   end;
 35   exit(ans);
 36 end;
 37 function tryit(a,b:longint):boolean;
 38 var i,j,t,k:longint;
 39 begin
 40     for i:=0 to m-1 do
 41     begin
 42       if ((a shr i) and 1<>0) then
 43       begin
 44         for j:=1 to mp[1,0] do
 45         begin
 46           k:=i+mp[1,j];
 47           if (k>=0) and (k<=m-1) and ((a shl k) and 1<>0) then exit(false);
 48         end;
 49         for j:=1 to mp[2,0] do
 50         begin
 51           k:=i+mp[2,j];
 52           if (k>=0) and (k<=m-1) and ((b shr k) and 1<>0) then exit(false);
 53         end;
 54       end;
 55     end;
 56     for i:=0 to m-1 do
 57     begin
 58       if ((b shr i) and 1<>0) then
 59       begin
 60         for j:=1 to mp[1,0] do
 61         begin
 62           k:=i+mp[1,j];
 63           if (k>=0) and (k<=m-1) and ((b shr k) and 1<>0) then exit(false);
 64         end;
 65         for j:=1 to mp[0,0] do
 66         begin
 67           k:=i+mp[0,j];
 68           if (k>=0) and (k<=m-1) and ((a shr k) and 1<>0) then exit(false);
 69         end;
 70       end;
 71     end;
 72     exit(true);
 73 end;
 74 begin
 75   modp:=1;
 76   for i:=1 to 32 do
 77     modp:=int64(modp*2);
 78   readln(n,m);
 79   readln(p,k);
 80   max:=1 shl m;
 81   dec(max);
 82   fillchar(mp,sizeof(mp),0);
 83   for i:=0 to 2 do
 84   begin
 85     for j:=0 to p-1 do
 86     begin
 87       read(x);
 88       if (x=1) and not((i=1) and (j=k)) then
 89       begin
 90         inc(mp[i,0]);
 91         mp[i,mp[i,0]]:=j-k;
 92       end;
 93     end;
 94   end;
 95   fillchar(a,sizeof(a),0);
 96   fillchar(f,sizeof(f),0);
 97   for i:=0 to max do
 98     for j:=0 to max do
 99         if tryit(i,j) then a[i,j]:=1 else a[i,j]:=0;
100   for i:=0 to max do
101     f[i]:=a[0,i];
102   a:=time(a,n);
103   ans:=0;
104   for i:=0 to max do
105   begin
106     if (f[i]<>0) then ans:=(ans+a[i,0]) mod modp;
107     while (ans>=modp) do ans:=ans-modp;
108     while (ans<0) do ans:=ans+modp;
109   end;
110   writeln(ans);
111 end.
112

T3:[bzoj4001]

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4001

这一题一定是这次省选最友善的一个题。。。

首先我们可以打暴力（或者手算），于是找到了规律，

可以用组合数学证明一发（然而我不会。。。）QAQQQ

总之就是个结论题QAQQQ

代码如下：

1 var n:longint;
2     x:real;
3 begin
4   readln(n);
5   x:=n/(2*n-1);
6   x:=x*(n+1)/2;
7   writeln(x:0:9);
8 end.