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

打算来做一波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
     
      =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) 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 do104   begin105     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 do13     read(c[i]);14   readln;15   fillchar(inc,sizeof(inc),0);16   s:=0;17   ans:=0;18   for i:=1 to n do19   begin20     s:=0;21     for j:=1 to n do22         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 do26     for j:=1 to n do27         ans:=ans+b[i,j];28   for i:=1 to n do29     ans:=ans-c[i];30   while true do31   begin32     max:=-1;33     max1:=-1;34     for i:=1 to n do35       if (max

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 do11     begin12       for j:=1 to m do13         read(a[i,j]);14       readln;15     end;16     for i:=1 to n do17         for j:=m downto 1 do18         begin19           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     begin100       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 do118     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 do101     f[i]:=a[0,i];102   a:=time(a,n);103   ans:=0;104   for i:=0 to max do105   begin106     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 begin4   readln(n);5   x:=n/(2*n-1);6   x:=x*(n+1)/2;7   writeln(x:0:9);8 end.