|
|
November 18 今年的题太简单了,只要有一点小失误就死得很惨,自己觉得发挥得确实不好,不过分数还过得去,至少没和最高分差太多,选拔赛还是挺有希望的. November 12 type
ss=array[1..100]of longint;
var
f:array[0..10000]of ss;
a,w:array[1..10000]of longint;
v,i,j,n,k:longint;
function max(a,b:ss;x:longint):ss;
var
i,j,l:longint;
c:ss;
begin
i:=1;j:=1;l:=0;
while l<k do
begin
inc(l);
if a[i]<b[j]+x then
begin
c[l]:=b[j]+x;inc(j);
end
else
begin
c[l]:=a[i];inc(i);
end;
end;
exit(c);
end;
begin
read(k,v,n);
for i:=1 to n do
readln(a[i],w[i]);
for i:=0 to v do
for j:=1 to k do
f[i,j]:=-maxlongint;
f[0,1]:=0;
for i:=1 to n do
begin
for j:=v downto a[i] do {如果是完全背包则变成 for j:=a[i] to v 即可}
f[j]:=max(f[j],f[j-a[i]],w[i]);
for j:=a[i]+1 to v do {如果是"一定装满"则直接去掉此for语句即可}
f[j]:=max(f[j],f[j-1],0);
end;
for i:=1 to k do
if f[v,i]<0 then break
else write(f[v,i],' ');
writeln;
end.
递推式（不加高精，不加记忆化）
var
n,r:longint;
function C(n,r:longint):longint;
begin
if (n=r)or(r=0) then exit(1)
else exit(C(n-1,r-1)+C(n-1,r));
end;
begin
readln(n,r);
writeln(C(n,r));
end.
通项式-直接高精
var
a:array[0..100000]of integer;
n,r,i,j,k,l,o:longint;
begin
readln(n,r);
if r>n-r then r:=n-r;
a[0]:=1;a[1]:=1;
for i:=n-r+1 to n do
begin
k:=0;
inc(a[0],trunc(ln(i)/ln(10))+1);
for j:=1 to a[0] do
begin
o:=a[j]*i+k;
a[j]:=o mod 10;
k:=o div 10;
end;
while a[a[0]]=0 do dec(a[0]);
end;
for i:=2 to r do
begin
o:=0;
for j:=a[0] downto 1 do
begin
o:=o*10+a[j];
a[j]:=o div i;
o:=o mod i;
end;
while a[a[0]]=0 do dec(a[0]);
end;
for i:=a[0] downto 1 do
write(a[i]);
writeln;
end.
通项式-分解质因数
type
ss=record
i,x:longint;
end;
var
h:array[1..100000]of boolean;
g,f:array[1..100000]of ss;
a:array[0..100000]of integer;
r,i,j,k,l,n:longint;
x,o:int64;
function bp(b,p:longint):int64;
var
x:int64;
begin
if p=0 then exit(1)
else
begin
x:=sqr(bp(b,p shr 1));
if (p and 1)=1 then x:=x*b;
exit(x);
end;
end;
begin
readln(n,r);
if r>n-r then r:=n-r;
l:=0;
for i:=2 to n do
if not h[i] then
begin
h[i]:=true;
inc(l);f[l].i:=i;
g[i].i:=i;g[i].x:=1;
if i<=r then f[l].x:=-1
else if i>n-r then f[l].x:=1;
for j:=2 to n div i do
begin
h[j*i]:=true;
g[j*i].i:=i;
if g[j].i<>i then
g[j*i].x:=1
else g[j*i].x:=g[j].x+1;
if j*i<=r then dec(f[l].x,g[j*i].x)
else if j*i>n-r then inc(f[l].x,g[j*i].x);
end;
end;
a[0]:=1;a[1]:=1;
for i:=1 to l do
begin
x:=bp(f[i].i,f[i].x);
k:=0;
inc(a[0],trunc(ln(x)/ln(10))+1);
for j:=1 to a[0] do
begin
o:=a[j]*x+k;
a[j]:=o mod 10;
k:=o div 10;
end;
while a[a[0]]=0 do dec(a[0]);
end;
for i:=a[0] downto 1 do
write(a[i]);
writeln;
end.
November 11 把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是O(V*Σn[i])。
方法：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。 for i=1..N
for v=0..V
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
g[i][v]=0
if(f[i][v]==f[i-1][v])
inc(g[i][v],g[i-1][v]
if(f[i][v]==f[i-1][v-c[i]]+w[i])
inc(g[i][v],g[i-1][v-c[i]])
November 09 01背包 for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 完全背包 for i=1..N for v=0..V f[v]=max{f[v],f[v-c[i]]+w[i]}; type
ss=record
i,x:longint;
end;
var
f:array[0..100000]of ss;
a,b,c:array[1..100000]of longint;
w,i,j,n:longint;
function find(x,l,r:longint):longint;
begin
if l=r then
if x>=f[l].x then
exit(l+1)
else exit(l)
else
if x<f[(l+r)div 2].x then
exit(find(x,l,(l+r)div 2))
else exit(find(x,(l+r)div 2+1,r));
end;
begin
read(n);
f[1].x:=maxlongint;w:=1;
for i:=1 to n do
begin
read(a[i]);
j:=find(a[i],1,w);
f[j].x:=a[i];f[j].i:=i;b[i]:=f[j-1].i;
if j>w then inc(w);
end;
writeln(w);
i:=f[w].i;j:=0;
while i<>0 do
begin
inc(j);c[j]:=a[i];
i:=b[i];
end;
for i:=w downto 1 do
write(c[i],' ');
writeln;
end.
|
Tools 
