2019.2.15
长沙集训 $ Day 5 $
今天的题目还是比较简单的，但是我的程序却出现了许多严重的 $ bug $ ,最终让我获得了 $ 20 $ 分的“好成绩”…
T1 modeq
这题可以说是扩展欧几里得算法的板子题了，分别套用一次 $ exgcd $ 求出最小 $ x,y $ ，然而我调试时把绝对值删了，后来又忘了改回去，最后 $ 100 \to 0 $
求解方法：
对于方程 $ a \cdot x + b \cdot y = c $
- 只有在 $ c \ \ mod \ \ gcd(a,b) = 0 $ 时，方程才有解
- 若 $ exgcd $ 解出的 $ x $ 为负值，可用 $ x=(x+abs(b*n)) \ \ mod \ \ b $ 的方式将其变为正值
- $ \frac{(a \cdot x)}{m} +\frac{(b \cdot y)}{m} =\frac{c}{m} $ 此方程的解与原方程相同，所以可以先将方程化简在进行处理
程序
program modeq;
var t,x,y,gd:int64;
function gcd(a,b:int64):int64;
begin
if b=0 then exit(a);
gcd:=gcd(b,a mod b);
end;
procedure exgcd(a,b,c:int64);
var t:int64;
begin
if b=0 then begin
x:=c div a;
y:=0;
exit;
end;
exgcd(b,a mod b,c);
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
procedure main;
var i:longint;
a,b,c,ans_x,ans_y:int64;
begin
for i:=1 to t do begin
read(a,b,c);
gd:=gcd(a,b);
if c mod gd<>0 then begin
writeln('No');
continue;
end;
a:=a div gd;
b:=b div gd;
c:=c div gd;
if c mod b=0 then write('0',' ',c div b,' ')
else begin
exgcd(a,b,c);
ans_x:=(x+abs(b*1000000000)) mod b;
ans_y:=(c-a*ans_x) div b;
write(ans_x,' ',ans_y,' ');
end;
if c mod a=0 then writeln(c div a,' ','0')
else begin
exgcd(b,a,c);
ans_y:=(x+abs(a*1000000000)) mod a;
ans_x:=(c-b*ans_y) div a;
writeln(ans_x,' ',ans_y);
end;
end;
end;
begin
read(t);
main;
end.
T2 买卖
开始以为是个毒瘤 $ DP $ ，后来发现是贪心，只要找到能把当前可以买入的最便宜的物品卖出赚钱的商店就把物品卖出，如果之后又更优秀的方案，就进行更改：
| 编号 | 买入 | 卖出 |
|---|---|---|
| A | $ 7 $ | $ 1 $ |
| B | $ 10 $ | $ 8 $ |
| C | $ 12 $ | $ 12 $ |
- 在 $ A $ 处买入物品，在 $ B $ 出卖出价值 $ w=8-7=1 $ ，并将 $ A $ 处物品价格改为 $ 8 $
- 发现在 $ C $ 出卖出是更优方案，相当于重新将物品买入，并在 $ C $ 处卖出，价值 $ w=12-8+1=12-7=5 $
- 可买入物品的最小值可用小根堆/最小值线段树等数据结构维护
一定注意初始化
程序
program buy;
var
tree:array[0..400005]of int64;
a:array[0..100005,1..2]of int64;
n,tar,sum:longint;
function min(a,b:int64):int64;
begin
if a<b then exit(a) else exit(b);
end;
procedure re;
var i:longint;
begin
for i:=1 to n do read(a[i,1]);
for i:=1 to n do read(a[i,2]);
end;
function search(l,r,t,k:longint):boolean;
var mid:longint;
begin
search:=false;
if l=r then begin
tree[t]:=k;
exit(true);
end;
mid:=(l+r) shr 1;
if tree[t shl 1 + 1]=tar then search:=search(mid+1,r,t shl 1 + 1,k);
if search=false then search:=search(l,mid,t shl 1,k);
tree[t]:=min(tree[t shl 1],tree[t shl 1 + 1]);
exit(search);
end;
procedure change(l,r,t,x,k:longint);
var mid:longint;
begin
if (l=r) and (l=x) then begin
tree[t]:=k;
exit;
end;
mid:=(l+r) shr 1;
if x<=mid then change(l,mid,t shl 1,x,k);
if x>=mid+1 then change(mid+1,r,t shl 1 + 1,x,k);
tree[t]:=min(tree[t shl 1],tree[t shl 1 + 1]);
end;
procedure main;
var x,ans:int64;
i:longint;
begin
ans:=0;
for i:=1 to n do begin
change(1,n,1,i,a[i,1]);
if tree[1]<a[i,2] then begin
tar:=tree[1];
inc(ans,a[i,2]-tree[1]);
search(1,n,1,a[i,2]);
end;
end;
writeln(ans);
end;
begin
fillchar(tree,sizeof(tree),$5f);
read(n);
re;
main;
end.
T3 投资
这题看起来是个 $ DP $ ，其实是前缀和+小根堆。
两题都是小根堆，可以复制代码了！！！
设$ [l,r] $ 是连续天数的范围
$ ans=max(sum[i]-min(sum[j])) \ \ \ \ j \in [i-r,i-l]$
程序
program invest;
var
a:array[0..100005]of int64;
heap:array[0..100005,1..2]of int64;
n,l,r,tot:longint;
function max(a,b:int64):int64;
begin
if a>b then exit(a) else exit(b);
end;
function min(a,b:int64):int64;
begin
if a<b then exit(a) else exit(b);
end;
procedure re;
var i:longint;
begin
for i:=1 to n do read(a[i]);
end;
procedure insert(q,p:int64);
var i,j,t:int64;
begin
inc(tot);
heap[tot,1]:=q;
heap[tot,2]:=p;
i:=tot;
while i shr 1<>0 do begin
j:=i shr 1;
if heap[j,1]>heap[i,1] then begin
t:=heap[j,1];
heap[j,1]:=heap[i,1];
heap[i,1]:=t;
t:=heap[j,2];
heap[j,2]:=heap[i,2];
heap[i,2]:=t;
end
else break;
i:=j;
end;
end;
procedure del;
var i,j,t:longint;
begin
heap[1]:=heap[tot];
dec(tot);
i:=1;
while i shl 1<=tot do begin
j:=i shl 1;
if (j+1<=tot) and (heap[j,1]>heap[j+1,1]) then inc(j);
if heap[j,1]<heap[i,1] then begin
t:=heap[j,1];
heap[j,1]:=heap[i,1];
heap[i,1]:=t;
t:=heap[j,2];
heap[j,2]:=heap[i,2];
heap[i,2]:=t;
end
else break;
i:=j;
end;
end;
procedure main;
var sum:array[0..100005]of int64;
ans:int64;
i:longint;
begin
fillchar(sum,sizeof(sum),0);
ans:=-10000000000;
sum[1]:=a[1];
if l<=1 then ans:=sum[1];
for i:=2 to n do begin
sum[i]:=sum[i-1]+a[i];
if i-l>0 then insert(sum[i-l],i-l);
while i-heap[1,2]>r do del;
if i>=l then ans:=max(ans,sum[i]-heap[1,1]);
end;
writeln(ans);
end;
begin
fillchar(heap,sizeof(heap),$5f);
read(n,l,r);
re;
main;
end.
T4 游戏
先用 $ manacher $ 求出以每个位置为中心的最长回文串的半径，之后进行统计，半径为 $ t $ 的回文串个数 $ sum[t] $ 为半径大于等于 $ t $ 的回文串个数之和。统计个数后用快速幂计算答案，注意取模。
程序
program rehearse;
const p=19930726;
var
f:array[0..2000005]of longint;
sum:array[0..2000005]of int64;
s:array[0..2000005]of char;
len,n,k:int64;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure re;
var i:longint;
p:ansistring;
begin
readln(p);
len:=1;
s[0]:='#';
s[len]:='#';
for i:=1 to n do begin
inc(len);
s[len]:=p[i];
inc(len);
s[len]:='#';
end;
end;
procedure manacher;
var i,mid,mx:longint;
begin
mid:=1;
mx:=1;
for i:=1 to len do begin
if i<mx then f[i]:=min(mx-i,f[mid*2-i])
else f[i]:=1;
while s[i-f[i]]=s[i+f[i]] do inc(f[i]);
if f[i]+i>mx then begin
mx:=f[i]+i;
mid:=i;
end;
end;
for i:=1 to len do
if s[i]<>'#' then inc(sum[f[i]]);
end;
function mul(q,k:int64):int64;
var t:int64;
begin
t:=q;
mul:=1;
while k<>0 do begin
if k and 1<>0 then mul:=(mul mod p)*(t mod p) mod p;
t:=(t mod p)*(t mod p) mod p;
k:=k shr 1;
end;
end;
procedure main;
var i:longint;
ans,t:int64;
begin
ans:=1;
t:=0;
sum[(len div 2) + 3]:=0;
for i:=(len div 2) + 2 downto 1 do begin
sum[i]:=sum[i]+sum[i+1];
if (i-1) mod 2=1 then begin
inc(t,sum[i]);
if t<=k then ans:=(ans mod p)*(mul(i-1,sum[i]) mod p) mod p
else begin
ans:=(ans mod p)*(mul(i-1,k-t+sum[i]) mod p) mod p;
break;
end;
end;
end;
if t<k then writeln('-1')
else writeln(ans);
end;
begin
readln(n,k);
re;
manacher;
main;
end.