开始以为是DP，但是仔细一想，动作k创造的价格只取决于它第一次出现的时间Sk和最后一次出现的时间Ek，则它创造的价值只可能为(Ek+Sk)*Ck。所以我们每次找最大价值的动作放在两侧直到放不下为止。
program p2697; var x:array[1..500] of longint; i,j,k,n,k1,max,where,tot:longint; begin readln(n,k); for i:=1 to k do read(x[i]); k1:=n+1; tot:=0; for i:=1 to k do begin k1:=k1-2; if k1<=0 then break; max:=-1; for j:=1 to k do if max<x[j] then begin max:=x[j]; where:=j; end; x[where]:=-1; tot:=tot+k1*max; end; writeln(tot); end.
类似于那道BZOJ1221软件开发，把每天拆成两个，分别记为Xi，Yi，从S向Yi连一条流量Ai，费用为0的边。从Yi向Yi+1连一条流量maxint。对于每一个医院从Yi向Xi+Dk+1连一条流量为maxint，费用为Qk的边。从Xi向T连一条流量为k，费用为0的边。再对于每个大学都建一个节点Mi，从Mi向X1连一条流量为maxint，费用为Pi的边，从S向Mi连一条流量为Li，费用为0的边。这个网络的最小费用最大流的费用就是答案。开始数组开太大，估计是fillchar花了太多时间就T了。后来把数组改小就A了。
program p3280;
const
maxn=1000000000;
modd=100000;
type
bian=record
next,point,w,f:longint;
end;
var
ii,t,tt,i,j,n,m,k,len,totpoint,totflow,totw,totnum:longint;
a,l,pp,q,d:array[1..10000] of longint;
b:array[0..200000] of bian;
p,after,dis:array[0..10000] of longint;
x:array[1..100000] of longint;
pd:array[0..10000] of boolean;
function min(k1,k2:longint):longint;
begin
if k1<k2 then exit(k1) else exit(k2);
end;
procedure ade(k1,k2,k3,k4:longint);
begin
inc(len);
b[len].point:=k2;
b[len].next:=p[k1];
b[len].f:=k3;
b[len].w:=k4;
p[k1]:=len;
end;
procedure add(k1,k2,k3,k4:longint);
begin
ade(k1,k2,k3,k4);
ade(k2,k1,0,-k4);
end;
function spfa:boolean;
var
head,i,j,now:longint;
begin
fillchar(x,sizeof(x),0);
fillchar(pd,sizeof(pd),false);
fillchar(dis,sizeof(dis),$3f);
fillchar(after,sizeof(after),-1);
x[1]:=0; head:=1; now:=0; pd[0]:=true; dis[0]:=0;
while head<>now do begin
now:=now mod modd+1;
i:=p[x[now]];
while i<>-1 do begin
j:=b[i].point;
if (b[i].f>0) and (b[i].w+dis[x[now]]<dis[j]) then begin
dis[j]:=b[i].w+dis[x[now]];
after[j]:=i;
if pd[j]=false then begin
pd[j]:=true;
head:=head mod modd+1;
x[head]:=j;
end;
end;
i:=b[i].next;
end;
pd[x[now]]:=false;
end;
if after[totpoint]>-1 then exit(true) else exit(false);
end;
function change:longint;
var
k,ans,tot,num,i,j:longint;
begin
i:=totpoint; j:=after[i]; k:=maxn;
while j<>-1 do begin
k:=min(k,b[j].f);
i:=b[j xor 1].point;
j:=after[i];
end;
ans:=0; i:=totpoint; j:=after[i];
while j<>-1 do begin
ans:=ans+k*b[j].w;
dec(b[j].f,k);
inc(b[j xor 1].f,k);
i:=b[j xor 1].point;
j:=after[i];
end;
totflow:=totflow+k;
exit(ans);
end;
function dinic:longint;
var
ans:longint;
begin
ans:=0;
while spfa do
ans:=ans+change;
exit(ans);
end;
begin
readln(t);
for tt:=1 to t do begin
totnum:=0;
readln(n,m,k);
len:=-1;
fillchar(p,sizeof(p),-1);
fillchar(b,sizeof(b),0);
for i:=1 to n do begin
read(a[i]);
totnum:=totnum+a[i];
end;
for i:=1 to m do
read(l[i],pp[i]);
for i:=1 to k do
read(d[i],q[i]);
for i:=m+1 to m+n-1 do
add(i,i+1,maxn,0);
for i:=1 to m do begin
add(0,i,l[i],0);
add(i,m+1,maxn,pp[i]);
end;
for i:=1 to n do begin
add(0,i+n+m,a[i],0);
for j:=1 to k do
if i+d[j]+1<=n then
add(i+n+m,m+i+d[j]+1,maxn,q[j]);
end;
totpoint:=n+n+m+1;
for i:=1 to n do
add(m+i,totpoint,a[i],0);
totflow:=0;
totw:=dinic;
if totflow<totnum then
writeln('Case ',tt,': impossible')
else
writeln('Case ',tt,': ',totw);
end;
end.
线性筛一下欧拉函数，然后加起来×2加3即可。
program p2190; var x:array[1..400000] of boolean; prime,phi:array[1..400000] of longint; len,n,i,j,tot:longint; begin readln(n); dec(n); fillchar(x,sizeof(x),false); len:=0; for i:=2 to n do begin if x[i]=false then begin inc(len); phi[i]:=i-1; prime[len]:=i; end; j:=1; while (j<=len) and (prime[j]*i<=n) do begin x[i*prime[j]]:=true; if i mod prime[j]=0 then begin phi[prime[j]*i]:=phi[i]*prime[j]; break; end else phi[prime[j]*i]:=phi[i]*(prime[j]-1); inc(j); end; end; tot:=0; for i:=1 to n do tot:=tot+phi[i]; tot:=tot*2+3; writeln(tot); end.
看起来很神，看到数据范围就呵呵了。
program p1800; var x:array[1..4] of longint; d:array[1..20,1..20] of int64; i,j,n,tot:longint; procedure dfs(k1,k2:longint); var i,j:longint; begin if k2>4 then begin if (d[x[1],x[2]]=d[x[3],x[4]]) and (d[x[2],x[3]]=d[x[4],x[1]]) then inc(tot); exit; end; for i:=k1 to n do begin x[k2]:=i; dfs(i+1,k2+1); end; end; begin readln(n); for i:=1 to n do read(d[i,i mod n+1]); for i:=1 to n do begin j:=(i+1) mod n+1; while j<>i do begin d[i,j]:=d[i,(j-2+n) mod n+1]+d[(j-2+n) mod n+1,j]; j:=j mod n+1; end; end; tot:=0; dfs(1,1); writeln(tot); end.
先画成一个堆，然后就可以YY出递推式F[I]=F[I*2]*F[I*2+1]*C(C[I]-1,C[I*2])，C[I]是指以I为根的子树的节点个数，然后只需要把阶乘预处理出来，然后用逆元瞎搞搞就水过了。
program p2111; var c:array[0..2000000] of longint; x,num:array[0..2000000] of int64; i,j,n,q:longint; function quick(k1,k2:int64):int64; var i,j,tot:int64; begin i:=k2; j:=k1; tot:=1; while i<>0 do begin if i and 1=1 then tot:=tot*j mod q; i:=i shr 1; j:=j*j mod q; end; exit(tot); end; function dfs(k1:longint):int64; begin if num[c[k1]]<>-1 then exit(num[c[k1]]); if (c[k1]<=1) then begin num[c[k1]]:=1; exit(1); end; num[c[k1]]:=x[c[k1]-1]*quick(x[c[k1*2]],q-2) mod q*quick(x[c[k1]-1-c[k1*2]],q-2) mod q; num[c[k1]]:=num[c[k1]]*dfs(k1*2) mod q*dfs(k1*2+1) mod q; exit(num[c[k1]]); end; begin readln(n,q); fillchar(c,sizeof(c),0); fillchar(x,sizeof(x),0); for i:=n downto 2 do begin inc(c[i]); inc(c[i div 2],c[i]); end; inc(c[1]); fillchar(num,sizeof(num),-1); x[0]:=1; for i:=1 to n do x[i]:=x[i-1]*i mod q; writeln(dfs(1)); end.
YY一下就可以得到最后的答案（因为有些并一起啊什么的全部都喜闻乐见消掉）为N*M^(K-1)-M*(M+1)/2*M^(K-2)*(K-1)，开始推了个式子貌似跪了，原因是中途要DIV个二好像有点问题，然后就索性重推了一遍。然后就A了，喜闻乐见。
program p3142; var n,m,k,p,i,j:int64; function quick(k1,k2:int64):int64; var i,j,k,tot:int64; begin k:=k1; j:=k2; tot:=1; while j<>0 do begin if j and 1<>0 then tot:=tot*k mod p; j:=j shr 1; k:=k*k mod p; end; exit(tot); end; begin readln(n,k,m,p); dec(k); i:=quick(m,k-1); writeln(int64(n mod p*m-m*(m+1) div 2 mod p*k+p*1000000000) mod p*i mod p); end.
语文挂科了，所以来除草了。
program p2007;
type
d=record
w,po:int64;
end;
bian=record
next,point,w:int64;
end;
var
b:array[1..1000000] of bian;
i,j,n,k1,k2,len:longint;
x:array[1..1000000] of d;
p,f:array[0..1000000] of int64;
pd:array[0..1000000] of boolean;
maxn:int64;
procedure add(k1,k2,k3:longint);
begin
inc(len);
b[len].next:=p[k1];
b[len].point:=k2;
b[len].w:=k3;
p[k1]:=len;
end;
function mi(k1,k2:longint):longint;
begin
if x[k1].w>x[k2].w then exit(k2) else exit(k1);
end;
function min(k1,k2,k3:longint):longint;
begin
exit(mi(mi(k1,k2),k3));
end;
procedure press(k:longint);
var
k1:longint;
k2:d;
begin
k1:=min(k,k*2,k*2+1);
if k1=k then exit;
k2:=x[k1];
x[k1]:=x[k];
x[k]:=k2;
press(k1);
end;
procedure find(k:longint);
var
k1:d;
begin
if k=1 then exit;
if x[k div 2].w>x[k].w then begin
k1:=x[k];
x[k]:=x[k div 2];
x[k div 2]:=k1;
find(k div 2);
end;
end;
function dijstra:longint;
var
k1,k2,k3,i,j,now,len:longint;
k:d;
begin
fillchar(pd,sizeof(pd),true);
fillchar(x,sizeof(x),$7f);
maxn:=x[1].po; len:=1;
fillchar(f,sizeof(f),$3f);
x[1].po:=0; x[1].w:=0; f[0]:=0;
while len>0 do begin
len:=len-1;
k:=x[1];
if len>0 then begin
x[1]:=x[len+1];
x[len+1].w:=maxn;
press(1);
end;
if pd[k.po]=false then continue;
pd[k.po]:=false;
k2:=p[k.po];
while k2>0 do begin
k1:=b[k2].point;
if f[k.po]+b[k2].w<f[k1] then begin
f[k1]:=f[k.po]+b[k2].w;
inc(len);
x[len].po:=k1; x[len].w:=f[k1];
find(len);
end;
k2:=b[k2].next;
end;
end;
exit(f[n*n+1]);
end;
begin
fillchar(b,sizeof(b),0);
fillchar(p,sizeof(p),0);
len:=0;
readln(n);
for i:=1 to n+1 do
for j:=1 to n do begin
readln(k1);
if i=1 then
add(j,n*n+1,k1)
else if i=n+1 then
add(0,n*(n-1)+j,k1)
else add(n*(i-1)+j,n*(i-2)+j,k1);
end;
for i:=1 to n do begin
readln(k1);
add(0,n*i-n+1,k1);
for j:=1 to n-1 do begin
readln(k1);
add(n*i-n+j,n*i-n+j+1,k1);
end;
readln(k1);
add(n*i,n*n+1,k1);
end;
for i:=1 to n+1 do
for j:=1 to n do begin
readln(k1);
if (i<>1) and (i<>n+1) then add(n*(i-2)+j,n*(i-1)+j,k1);
end;
for i:=1 to n do begin
readln(k1);
for j:=1 to n-1 do begin
readln(k1);
add(n*i-n+j+1,n*i-n+j,k1);
end;
readln(k1);
end;
fillchar(x,sizeof(x),$3f);
fillchar(f,sizeof(f),$3f);
maxn:=x[1].po;
writeln(dijstra);
end.
一眼就可以看出来是最小割，因为显而易见每个点的高度只可能是0或1，那么它们必有一个交接面，而这个就需要用最小割了。但是最小割会T80，所以要用对偶图+最短路来解决最小割问题，就如BZOJ1001。而这题恶心的把SPFA卡了，我又都比的把DJ+堆敲炸了，这道题就坑了我一个晚上QAQ（虽然有OSU和CS的因素）。
O(NK^2)的算法是果果的，O(NK)的算法只要用一个TOT来计算前缀和就可以了，边界+-1搞了一会儿就A了。
program p2431; var x:array[0..1,0..1000] of longint; n,k,i,j,tot,k1,k2:longint; begin readln(n,k); fillchar(x,sizeof(x),0); x[0,0]:=1; for i:=1 to n do begin k1:=i mod 2; k2:=1-k1; x[k1,0]:=x[k2,0]; tot:=x[k2,0]; for j:=1 to k do begin if j<i then tot:=(tot+x[k2,j]) mod 10000 else tot:=(tot-x[k2,j-i]+x[k2,j]+10000) mod 10000; x[k1,j]:=tot; end; end; writeln(x[k1,k]); end.
我的第一道计算几何，OLE了好多次。先以A为第一关键字，B为第二关键字SORT一下。从小到大进栈，然后每次比较头三条直线L1，L2，L3如果L1L2交点不在L2L3交点之后则删除L2，再比较删除L2以后的头三条直线直到不满足条件或者无法再删除则停止。最后留在栈中的直线就是可以看见的直线。接下来是我惨烈无比的AC历程
program p1007; type line=record k,b:extended; num:longint; end; var x,s:array[0..50100] of line; pd:array[0..50100] of boolean; i,j,n,head:longint; k1,k2:extended; procedure sort(first,en:longint); var i,j:longint; begin i:=first; j:=en; x[0]:=x[i]; while i<j do begin while (i<j) and ((x[j].k>x[0].k) or ((x[j].k=x[0].k) and (x[j].b<x[0].b))) do dec(j); if i<j then x[i]:=x[j]; while (i<j) and ((x[i].k<x[0].k) or ((x[i].k=x[0].k) and (x[i].b>x[0].b))) do inc(i); if i<j then x[j]:=x[i]; end; x[i]:=x[0]; if i>first+1 then sort(first,i-1); if i<en-1 then sort(i+1,en); end; function find(k1,k2:line):extended; begin exit((k2.b-k1.b)/(k1.k-k2.k)); end; begin readln(n); for i:=1 to n do begin readln(x[i].k,x[i].b); x[i].num:=i; end; sort(1,n); head:=0; fillchar(pd,sizeof(pd),true); for i:=1 to n do begin if head=0 then begin inc(head); s[head]:=x[i]; continue; end; if (x[i].k=s[head].k) then begin pd[x[i].num]:=false; continue; end; if head=1 then begin inc(head); s[head]:=x[i]; continue; end; while true do begin if head=1 then begin inc(head); s[head]:=x[i]; break; end; k1:=find(x[i],s[head]); k2:=find(s[head-1],s[head]); if k1<=k2 then begin pd[s[head].num]:=false; dec(head); end else begin inc(head); s[head]:=x[i]; break; end; end; end; for i:=1 to n do if pd[i]=true then write(i,' '); end.
由于只能向下走，这样路线就不可能达成一个环，而且又鉴于每个点只能到达一遍，每一次的代价只存在于重设出发点，于是很容易的就想到了最小路径覆盖，赤果果的网络流。把每个节点拆成两个，i入和i出。如果i可以到达j，那么就连一条i出到j入的边，再由源向每一个出连一条边，由入向汇连一条边。上述边的流量都为1。答案就是总的点数减最大流。当然这道题也可以用匈牙利算法做。
program p03;
type
bian=record
next,point,f:longint;
end;
var
b:array[0..5000000] of bian;
p,dst,s:array[0..500000] of longint;
pd:array[0..500000] of boolean;
bo:array[1..600,1..600] of boolean;
tot,len,i,j,n,m,r,c:longint;
ch:char;
procedure getchar(var ch:char);
begin
read(ch);
while (ch<>'.') and (ch<>'x')do
read(ch);
end;
function min(k1,k2:longint):longint;
begin
if k1<k2 then exit(k1) else exit(k2);
end;
function change(k1,k2:longint):longint;
var
i,j,k,num:longint;
begin
if (k1=n*m*2+1) or (k2=0) then exit(k2);
num:=0;
i:=p[k1];
while i<>-1 do begin
j:=b[i].point;
if (b[i].f>0) and (dst[j]=dst[k1]+1) then begin
k:=change(j,min(k2,b[i].f));
k2:=k2-k; num:=num+k;
dec(b[i].f,k); inc(b[i xor 1].f,k);
if k2=0 then break;
end;
i:=b[i].next;
end;
if num=0 then dst[k1]:=-1;
exit(num);
end;
function bfs:boolean;
var
i,j,head,now:longint;
begin
fillchar(dst,sizeof(dst),-1);
fillchar(pd,sizeof(pd),false);
head:=1; now:=0; pd[0]:=true; s[1]:=0; dst[0]:=0;
while head>now do begin
inc(now);
i:=p[s[now]];
while i<>-1 do begin
j:=b[i].point;
if (pd[j]=false) and (b[i].f>0) then begin
dst[j]:=dst[s[now]]+1;
pd[j]:=true;
if j=n*m*2+1 then exit(true);
inc(head);
s[head]:=j;
end;
i:=b[i].next;
end;
end;
exit(pd[n*m*2+1]);
end;
procedure ade(k1,k2,k3:longint);
begin
inc(len);
b[len].point:=k2;
b[len].next:=p[k1];
b[len].f:=k3;
p[k1]:=len;
end;
procedure add(k1,k2,k3:longint);
begin
ade(k1,k2,k3);
ade(k2,k1,0);
end;
function dinic:longint;
var
num:longint;
begin
num:=0;
while bfs=true do
num:=num+change(0,maxlongint);
exit(num);
end;
begin
readln(n,m,r,c);
fillchar(p,sizeof(p),-1);
fillchar(b,sizeof(b),0);
len:=-1;
for i:=1 to n do
for j:=1 to m do begin
getchar(ch);
if ch='.' then bo[i,j]:=true else bo[i,j]:=false;
end;
for i:=1 to n do
for j:=1 to m do begin
if (i+c<=n) and (j+r<=m) and (bo[i,j]=true) and (bo[i+c,j+r]=true) then
add(i*m+j-m,(i+c)*m-m+j+r+n*m,1);
if (i+r<=n) and (j+c<=m) and (bo[i,j]=true) and (bo[i+r,j+c]=true) then
add(i*m+j-m,(i+r)*m-m+j+c+n*m,1);
if (i+c<=n) and (j-r>0) and (bo[i,j]=true) and (bo[i+c,j-r]=true) then
add(i*m+j-m,(i+c)*m-m+j-r+n*m,1);
if (i+r<=n) and (j-c>0) and (bo[i,j]=true) and (bo[i+r,j-c]=true) then
add(i*m+j-m,(i+r)*m-m+j-c+n*m,1);
end;
tot:=0;
for i:=1 to n do
for j:=1 to m do
if bo[i,j]=true then begin
inc(tot);
add(0,i*m-m+j,1);
add(i*m-m+j+n*m,n*m*2+1,1);
end;
writeln(tot-dinic);
end.
Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com
