<center>
长沙集训 $ Day 3 $ 2019-08-21 </center>
得分:$ 193/300 $
T1 $ Matrix $
基本思路
此题可以用枚举解决,分别枚举每一列作为矩形中间点统计答案,最后取最大值。每次统计答案时,分别算出每一列相邻的 $ 1 $ 的个数 $ sum $:
之后从该列向两边查找(其实只向一边也可以),如果当前枚举的列为 $ k $ ,查找到的列为 $ i $ ,则答案为 $ |i-j| \cdot sum[i] $ 。
直接暴力查找的时间复杂度时 $ O(n \cdot m^2) $ ,为了加快速度,可以预处理出以 $ i $ 为中心的每行连续 $ 1 $ 的左右端点,之后计算 $ sum $ 时用前缀和处理。使时间复杂度降低为 $ O(n \cdot m) $ 。
程序
program matrix;
type tp=record
l,r:longint;
end;
var
f:array[0..1005,0..1005]of tp;
a:array[0..1005,0..1005]of integer;
sum:array[0..1005]of longint;
n,m:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
procedure re;
var i,j:longint;
s:ansistring;
begin
for i:=1 to n do begin
readln(s);
for j:=1 to m do
if s[j]='0' then a[i,j]:=0
else a[i,j]:=1;
end;
end;
procedure first;
var i,j,loc:longint;
t:boolean;
begin
for i:=1 to n do begin
loc:=1;
t:=false;
for j:=1 to m do
if a[i,j]<>0 then begin
if t=true then begin
f[i,j].l:=f[i,j-1].l;
f[i,j].r:=f[i,j-1].r;
end
else begin
while a[i,loc]<>0 do inc(loc);
t:=true;
f[i,j].l:=j;
f[i,j].r:=loc;
end;
end
else begin
t:=false;
inc(loc);
end;
end;
end;
function ans(x:longint):longint;
var i,t:longint;
begin
fillchar(sum,sizeof(sum),0);
for i:=1 to n do
if a[i,x]=1 then begin
inc(sum[f[i,x].l]);
dec(sum[f[i,x].r]);
end;
for i:=1 to n do
sum[i]:=sum[i]+sum[i-1];
ans:=0;
t:=0;
for i:=x+1 to n do
if sum[i]=sum[i-1] then inc(t)
else break;
for i:=x downto 1 do begin
inc(t);
ans:=max(ans,sum[i]*t);
end;
t:=0;
for i:=x-1 downto 1 do
if sum[i]=sum[i+1] then inc(t)
else break;
for i:=x to n do begin
inc(t);
ans:=max(ans,sum[i]*t);
end;
end;
procedure main;
var i,j,anss:longint;
begin
anss:=0;
for i:=1 to m do
anss:=max(anss,ans(i));
writeln(anss);
end;
begin
readln(n,m);
re;
first;
main;
end.
T2 $ Present $
基本思路
刚看到题面,第一反应:“这不是背包板子吗!”。看到数据范围:“。。。”。
这三天的 $ T2 $ 都异常巧妙,昨天考了最小生成树,今天的 $ T2 $ 则是一个最短路径。从原题上完全看不出和图论的联系,但是却能根据题目的特点进行转化:
假设所有的物品中,价值最小为 $ p_{min} $ 。如果一个值 $ W = \sum_{i=1}^n p_i \cdot k_i $ 可以被组成,那么 $ W = \sum_{i=1}^n p_i \cdot (k_i + p_{min} \cdot s_i) $ 也一定能被组成。
可以借此降低背包的上界,将最大容量从 $ 4 \times 10^7 $ 降为 $ p_{min} \cdot \sum_{i=1}^n p_i $ ,时间复杂度为 $ O(n \cdot p_{min} \cdot \sum_{i=1}^n p_i ) $ 。可以通过 $ 60 $% 的数据。
接下来,解决方法就非常巧妙了。由上可知,对于每一个询问 $ Q = C + p_{min} \cdot k $ ,只要判断 $ Q \mod p_{min} $ 能否被组成即可。所以我们只要知道能够被组成的数 $ K(K \mod p_{min} = C) $ ,的最小值是否小于 $ Q $ 即可。而解决这个问题,可以将 $ [0,p_{min}-1] $ 的每个数当成一个点,对于点 $ f $ ,将其向 $ (f + p_i) \mod p_{min} $ 的点连一条权值为 $ p_i $ 的无向边,最后算出从 $ 0 $ 到 $ i $ 的最短路便是 $ K(K \mod p_{min} = i) $ 的最小值。
程序
program present;
var
dis:array[0..10005]of longint;
a:array[0..505]of longint;
n,m,w:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a)
else exit(b);
end;
procedure re;
var i:longint;
begin
w:=maxint;
for i:=1 to n do begin
read(a[i]);
w:=min(w,a[i]);
end;
end;
procedure spfa;
var i,head,tail,f,v:longint;
p:array[0..10005]of longint;
tf:array[0..10005]of boolean;
begin
fillchar(dis,sizeof(dis),$3f);
fillchar(tf,sizeof(tf),0);
dis[0]:=0;
head:=0;
tail:=1;
p[tail]:=0;
tf[0]:=true;
while head<tail do begin
inc(head);
head:=head mod 10000;
f:=p[head];
for i:=1 to n do begin
v:=(f+a[i]) mod w;
if (a[i]<>w) and (dis[f]+a[i]<dis[v]) then begin
dis[v]:=dis[f]+a[i];
if tf[v]=false then begin
inc(tail);
tail:=tail mod 10000;
p[tail]:=v;
tf[v]:=true;
end;
end;
end;
tf[f]:=false;
end;
end;
procedure main;
var i,ans,x:longint;
begin
spfa;
ans:=0;
for i:=1 to m do begin
read(x);
if dis[x mod w]<=x then inc(ans);
end;
writeln(ans);
end;
begin
read(n,m);
re;
main;
end.
T3 $ Mahjong $
基本思路
这是三天中最水的 $ T3 $ ,没有任何算法,就是按照题意模拟和枚举。主意好细节就可以,注意要先确定雀头,再查找顺子和刻子。对特殊牌型先行处理。
这题说明了看题是多重要,我没看到“字牌不能成顺子”,结果 $ 100 \to 63 $ 。
程序
program mahjong;
type arr=array[1..15]of longint;
type tp=record
a:longint;
b:char;
end;
var
m,s,p,c:arr;
ans:array[0..105]of tp;
t:longint;
procedure re;
var ss:string;
i,t:longint;
begin
readln(ss);
i:=1;
while i<=length(ss) do begin
val(ss[i],t);
case ss[i+1] of
'm':inc(m[t]);
's':inc(s[t]);
'p':inc(p[t]);
'c':inc(c[t]);
end;
inc(i,3);
end;
end;
function sc(m,s,p,c:arr):boolean;
var i,sum:longint;
begin
//找刻子和顺子
sum:=0;
for i:=1 to 9 do
if m[i]>0 then begin
if m[i]<3 then while (m[i]>0) and (m[i+1]>0) and (m[i+2]>0) do begin
inc(sum);
dec(m[i]);
dec(m[i+1]);
dec(m[i+2]);
end;
if m[i]>=3 then begin
inc(sum);
dec(m[i],3);
end;
while (m[i]>0) and (m[i+1]>0) and (m[i+2]>0) do begin
inc(sum);
dec(m[i]);
dec(m[i+1]);
dec(m[i+2]);
end;
end;
for i:=1 to 9 do
if s[i]>0 then begin
if s[i]<3 then while (s[i]>0) and (s[i+1]>0) and (s[i+2]>0) do begin
inc(sum);
dec(s[i]);
dec(s[i+1]);
dec(s[i+2]);
end;
if s[i]>=3 then begin
inc(sum);
dec(s[i],3);
end;
while (s[i]>0) and (s[i+1]>0) and (s[i+2]>0) do begin
inc(sum);
dec(s[i]);
dec(s[i+1]);
dec(s[i+2]);
end;
end;
for i:=1 to 9 do
if p[i]>0 then begin
if p[i]<3 then while (p[i]>0) and (p[i+1]>0) and (p[i+2]>0) do begin
inc(sum);
dec(p[i]);
dec(p[i+1]);
dec(p[i+2]);
end;
if p[i]>=3 then begin
inc(sum);
dec(p[i],3);
end;
while (p[i]>0) and (p[i+1]>0) and (p[i+2]>0) do begin
inc(sum);
dec(p[i]);
dec(p[i+1]);
dec(p[i+2]);
end;
end;
for i:=1 to 9 do
if c[i]>=3 then begin
inc(sum);
dec(c[i],3);
end;
if sum<4 then exit(false)
else exit(true);
//
end;
function check(m,s,p,c:arr):boolean;
var i,sum:longint;
tf:boolean;
begin
//七对子
sum:=0;
for i:=1 to 9 do
if m[i]>=2 then inc(sum);
for i:=1 to 9 do
if s[i]>=2 then inc(sum);
for i:=1 to 9 do
if p[i]>=2 then inc(sum);
for i:=1 to 9 do
if c[i]>=2 then inc(sum);
if sum=7 then exit(true);
if sum=0 then exit(false);
//
//国士无双
tf:=true;
for i:=2 to 8 do
if m[i]<>0 then tf:=false;
for i:=2 to 8 do
if s[i]<>0 then tf:=false;
for i:=2 to 8 do
if p[i]<>0 then tf:=false;
for i:=1 to 7 do
if c[i]=0 then tf:=false;
if (tf=true) and (m[1]>0) and (m[9]>0) and (s[1]>0) and (s[9]>0) and (p[1]>0) and (p[9]>0) then exit(true);
//
//找对子
for i:=1 to 9 do
if m[i]>=2 then begin
dec(m[i],2);
if sc(m,s,p,c)=true then exit(true);
inc(m[i],2);
end;
for i:=1 to 9 do
if s[i]>=2 then begin
dec(s[i],2);
if sc(m,s,p,c)=true then exit(true);
inc(s[i],2);
end;
for i:=1 to 9 do
if p[i]>=2 then begin
dec(p[i],2);
if sc(m,s,p,c)=true then exit(true);
inc(p[i],2);
end;
for i:=1 to 7 do
if c[i]>=2 then begin
dec(c[i],2);
if sc(m,s,p,c)=true then exit(true);
inc(c[i],2);
end;
//
exit(false);
end;
procedure main;
var i,t:longint;
begin
t:=0;
for i:=1 to 9 do
if m[i]+1<5 then begin
inc(m[i]);
if check(m,s,p,c)=true then begin
inc(t);
ans[t].a:=i;
ans[t].b:='m';
end;
dec(m[i]);
end;
for i:=1 to 9 do
if s[i]+1<5 then begin
inc(s[i]);
if check(m,s,p,c)=true then begin
inc(t);
ans[t].a:=i;
ans[t].b:='s';
end;
dec(s[i]);
end;
for i:=1 to 9 do
if p[i]+1<5 then begin
inc(p[i]);
if check(m,s,p,c)=true then begin
inc(t);
ans[t].a:=i;
ans[t].b:='p';
end;
dec(p[i]);
end;
for i:=1 to 7 do
if c[i]+1<5 then begin
inc(c[i]);
if check(m,s,p,c)=true then begin
inc(t);
ans[t].a:=i;
ans[t].b:='c';
end;
dec(c[i]);
end;
if t=0 then writeln('Nooten')
else begin
write(t,' ');
for i:=1 to t do
write(ans[i].a,ans[i].b,' ');
writeln;
end;
end;
begin
readln(t);
while t>0 do begin
fillchar(m,sizeof(m),0);
fillchar(s,sizeof(s),0);
fillchar(p,sizeof(p),0);
fillchar(c,sizeof(c),0);
dec(t);
re;
main;
end;
end.