codeforces round375(div.2)题解
2024-09-24 12:33:34
首先吐槽一下这套题。。。为什么EF全是图论QAQ
过了ABCD四个题。。。F的并查集死磕了好久。。。
不过似乎rank还算乐观。。。（因为ABC都是一次过的QAQ）
Problem A：
啥都不想说QAQ。。。
代码如下：
var a,b,c,d,max,min,ans:longint;
begin
readln(a,b,c);
max:=a;
min:=a;
if (b>max) then max:=b;
if (c>max) then max:=c;
if (b<min) then min:=b;
if (c<min) then min:=c;
d:=a+b+c-max-min;
ans:=abs(a-d)+abs(b-d)+abs(c-d);
writeln(ans);
end.
Problem B：
统计字符串的题，注意一下括号里面的各种细节，以及各种单词统计的处理就可以了。
代码如下：
var n,i,j,max,ans,now:longint;
flag:boolean;
ch:array[..] of char;
function flagg(x:char):boolean;
begin
if (<=ord(x)) and (ord(x)<=+) then exit(true);
if (<=ord(x)) and (ord(x)<=+) then exit(true);
exit(false);
end;
begin
readln(n);
for i:= to n do
read(ch[i]);
readln;
max:=;
ans:=;
flag:=true;
i:=;
now:=;
while (i<=n) do
begin
if flagg(ch[i]) then inc(now);
if not(flagg(ch[i])) then
begin
if flag then
begin
if (now>max) then max:=now;
now:=;
end
else
begin
if (now>) then inc(ans);
now:=;
end;
end;
if (ch[i]='(') then flag:=false;
if (ch[i]=')') then flag:=true;
inc(i);
end;
if (now>) then
begin
if not(flag) then inc(ans);
if flag and(now>max) then max:=now;
end;
writeln(max,' ',ans);
end.
Problem C：
这题的题意需要好好理解一下。。。
首先需要看出，第一个答案就是n div m，
接下来方案只需要按照类似贪心来模拟就可以了，注意一下边界的细节。
代码如下：
var n,m,i,j,ans,ans1:longint;
a,flag,flag1,anss:array[..] of longint;
begin
readln(n,m);
fillchar(a,sizeof(a),);
for i:= to n do
read(a[i]);
readln;
write(n div m,' ');
ans:=n div m;
fillchar(flag,sizeof(flag),);
for i:= to n do
if (a[i]<=m) then inc(flag[a[i]]);
ans1:=;
for i:= to m do
if (flag[i]<ans) then ans1:=ans1+ans-flag[i];
writeln(ans1);
fillchar(flag1,sizeof(flag1),);
fillchar(anss,sizeof(anss),);
for i:= to n do
begin
if (a[i]<=m) then
begin
if (flag1[a[i]]<ans) then
begin
inc(flag1[a[i]]);
anss[i]:=a[i];
end;
end;
end;
i:=;
j:=;
while (j<=m) and (flag1[j]>=ans) do inc(j);
while (i<=n) do
begin
if (anss[i]=) then
begin
if (j<>m+) then
begin
anss[i]:=j;
inc(flag1[j]);
while (j<=m) and (flag1[j]>=ans) do inc(j);
end else anss[i]:=a[i];
end;
inc(i);
end;
for i:= to n do
write(anss[i],' ');
writeln;
end.
Problem D：
这题题意似乎也没写好QAQ
这题其实就是一个DFS就可以了，由于最开始的内陆湖个数大于等于k，所以直接贪心处较小的那几个内陆湖面积，然后加起来就可以了。
注意细节，比如周围一圈算海洋，不属于内陆湖。
代码如下：
const tx:array[..] of longint=(,,,-);
ty:array[..] of longint=(,-,,);
var n,m,k,i,j,tot,now,ans,ii,jj:longint;
flag:boolean;
ch:array[..,..] of char;
vis:array[..,..] of boolean;
r:array[..,..] of longint;
area,b:array[..] of longint;
procedure qsort(lx,rx:longint);
var i,j,m,t:longint;
begin
i:=lx;
j:=rx;
m:=area[(i+j) div ];
repeat
while (area[i]<m) do inc(i);
while (area[j]>m) do dec(j);
if (i<=j) then
begin
t:=area[i];
area[i]:=area[j];
area[j]:=t;
t:=b[i];
b[i]:=b[j];
b[j]:=t;
inc(i);
dec(j);
end;
until (i>j);
if (i<rx) then qsort(i,rx);
if (j>lx) then qsort(lx,j);
end;
procedure tryit(x,y:longint);
var i,j,a,b:longint;
begin
r[x,y]:=tot+;
vis[x,y]:=true;
inc(now);
if (x=) or (x=n) or (y=) or (y=m) then flag:=false;
for i:= to do
begin
a:=x+tx[i];
b:=y+ty[i];
if (<=a) and (a<=n) and (<=b) and (b<=m) then
if not(vis[a,b]) and (ch[a,b]='.') then tryit(a,b);
end;
end;
procedure trycolor(t:longint);
var i,j:longint;
begin
for i:= to n do
for j:= to m do
if (r[i,j]=t) then ch[i,j]:='*';
end;
begin
readln(n,m,k);
for i:= to n do
begin
for j:= to m do
read(ch[i,j]);
readln;
end;
fillchar(area,sizeof(area),);
fillchar(b,sizeof(b),);
fillchar(r,sizeof(r),);
tot:=;
fillchar(vis,sizeof(vis),false);
for i:= to n- do
for j:= to m- do
if (ch[i,j]='.') and not(vis[i,j]) then
begin
now:=;
flag:=true;
tryit(i,j);
if flag then
begin
inc(tot);
area[tot]:=now;
end
else
begin
for ii:= to n do
for jj:= to m do
if (r[ii,jj]=tot+) then r[ii,jj]:=;
end;
end;
for i:= to tot do
b[i]:=i;
qsort(,tot);
ans:=;
for i:= to tot-k do
begin
trycolor(b[i]);
ans:=ans+area[i];
end;
writeln(ans);
for i:= to n do
begin
for j:= to m do
write(ch[i,j]);
writeln;
end;
end.
Problem E：
这是一道欧拉混合回路。。。
首先，你需要大胆猜出结论，就是所有度数为偶数的最后都可以满足条件。
然后跑欧拉回路迭代构造方案就可以了。（很传统的做法）
代码如下：
var t,l,m,n,i,j,ans,u,v,tot:longint;
deg:array[..] of longint;
r:array[..,..] of longint;
vis:array[..] of boolean;
next,last,other:array[..] of longint;
procedure insert(x,y:longint);
begin
inc(tot);
next[tot]:=last[x];
last[x]:=tot;
other[tot]:=y;
inc(tot);
next[tot]:=last[y];
last[y]:=tot;
other[tot]:=x;
end;
procedure dfs(x:longint);
var i,j:longint;
begin
i:=last[x];
while (i>) do
begin
if not(vis[i div ]) then
begin
vis[i div ]:=true;
dfs(other[i]);
if (i div <=m) then
begin
r[i div ,]:=x;
r[i div ,]:=other[i];
end;
end;
i:=next[i];
end;
end;
begin
readln(t);
for l:= to t do
begin
readln(n,m);
fillchar(vis,sizeof(vis),false);
fillchar(deg,sizeof(deg),);
fillchar(r,sizeof(r),false);
fillchar(next,sizeof(next),);
fillchar(last,sizeof(last),);
fillchar(other,sizeof(other),);
tot:=;
ans:=;
for i:= to m do
begin
readln(u,v);
insert(u,v);
inc(deg[u]);
inc(deg[v]);
end;
for i:= to n do
if (deg[i] mod =) then insert(i,n+) else inc(ans);
for i:= to n do
dfs(i);
writeln(ans);
for i:= to m do
writeln(r[i,],' ',r[i,]);
end;
end.
Problem F：
本场最细节的题目了。。。
首先，这是一道并查集。。。
然后就是一堆细节了，各种地方需要注意。（比如在第一次联通之后，在清除关系之前需要保留数据）
具体细节都可以看代码。
代码如下：
var n,m,s,t,ds,dt,i,j,now1,now2,now3,now4,x:longint;
a,b,father,fatherr,cs,ct:array[..] of longint;
flag1,flag2,flag,vis:array[..] of boolean;
flagg,flagt:boolean;
function tryit(i:longint):longint;
var k,t,p:longint;
begin
k:=i;
while (father[k]<>k) do k:=father[k];
t:=i;
while (t<>k) do
begin
p:=father[t];
father[t]:=k;
t:=p;
end;
exit(k);
end;
function tryit1(i:longint):longint;
var k,t,p:longint;
begin
k:=i;
while (fatherr[k]<>k) do k:=fatherr[k];
t:=i;
while (t<>k) do
begin
p:=fatherr[t];
fatherr[t]:=k;
t:=p;
end;
exit(k);
end;
procedure mdf(a1,b1:longint);
var i,j:longint;
begin
i:=tryit(a1);
j:=tryit(b1);
if (i<>j) then father[j]:=i;
end;
begin
readln(n,m);
fillchar(a,sizeof(a),);
fillchar(b,sizeof(b),);
fillchar(cs,sizeof(cs),);
fillchar(ct,sizeof(ct),);
for i:= to m do
readln(a[i],b[i]);
readln(s,t,ds,dt);
for i:= to n do
father[i]:=i;
flagg:=false;
for i:= to m do
begin
if (a[i]<>s) and (a[i]<>t) and (b[i]<>s) and (b[i]<>t) then mdf(a[i],b[i]);
if (a[i]=s) and (b[i]=t) then flagg:=true;
if (a[i]=t) and (b[i]=s) then flagg:=true;
end;
fillchar(flag1,sizeof(flag1),false);
fillchar(flag2,sizeof(flag2),false);
fillchar(flag,sizeof(flag),false);
for i:= to n do
if (i<>s) and (i<>t) then flag[tryit(i)]:=true;
for i:= to m do
begin
if (a[i]=s) then
begin
flag1[tryit(b[i])]:=true;
cs[tryit(b[i])]:=b[i];
end;
if (b[i]=s) then
begin
flag1[tryit(a[i])]:=true;
cs[tryit(a[i])]:=a[i];
end;
if (a[i]=t) then
begin
flag2[tryit(b[i])]:=true;
ct[tryit(b[i])]:=b[i];
end;
if (b[i]=t) then
begin
flag2[tryit(a[i])]:=true;
ct[tryit(a[i])]:=a[i];
end;
end;
now1:=;
now2:=;
now3:=;
now4:=;
for i:= to n do
if (i<>s) and (i<>t) and flag[i] then
begin
if flag1[i] and not(flag2[i]) then inc(now1);
if flag2[i] and not(flag1[i]) then inc(now2);
if flag1[i] and flag2[i] then inc(now3);
if not(flag1[i]) and not(flag2[i]) then inc(now4);
end;
if (now3>) and ((now1+now2+now3+>ds+dt) or (now1+>ds) or (now2+>dt)) then
begin
writeln('No');
halt;
end
else if (now3=) and (not(flagg) or (now1+now2+now3+>ds+dt) or (now1+>ds) or (now2+>dt)) then
begin
writeln('No');
halt;
end
else
begin
writeln('Yes');
fatherr:=father;
fillchar(father,sizeof(father),);
for i:= to n do
father[i]:=i;
flagt:=true;
for i:= to n do
if (i<>s) and (i<>t) and flag[i] then
begin
if flag1[i] and not(flag2[i]) then
begin
dec(ds);
writeln(s,' ',cs[tryit1(i)]);
mdf(s,i);
end
else if flag2[i] and not(flag1[i]) then
begin
dec(dt);
writeln(t,' ',ct[tryit1(i)]);
mdf(t,i);
end;
end;
for i:= to n do
if (i<>s) and (i<>t) and flag[i] then
begin
if flag1[i] and flag2[i] then
begin
if flagt and (ds>) and (dt>) then
begin
dec(ds);
dec(dt);
writeln(s,' ',cs[tryit1(i)]);
writeln(t,' ',ct[tryit1(i)]);
mdf(s,i);
mdf(t,i);
flagt:=false;
end else
if (ds>) then
begin
dec(ds);
writeln(s,' ',cs[tryit1(i)]);
mdf(s,i);
end else
begin
dec(dt);
writeln(t,' ',ct[tryit1(i)]);
mdf(t,i);
end;
end;
end;
if flagg and flagt then
begin
dec(ds);
dec(dt);
writeln(s,' ',t);
mdf(s,t);
end;
for i:= to m do
begin
if (tryit(a[i])<>tryit(b[i])) and (a[i]<>s) and (b[i]<>s) and (a[i]<>t) and (b[i]<>t) then
begin
writeln(a[i],' ',b[i]);
mdf(a[i],b[i]);
end
end;
end;
end.
完结撒花！～～～
最新文章
- js无刷新上传图片，服务端有生成缩略图，剪切图片，iphone图片旋转判断功能
- sso demo mysql ( cas )
- java事务理解
- fastjson 常用api
- 关于C++类中的成员
- Centos系统使用代理上网时 yum的代理设置
- vim插件：latex-suite 使用方法
- ArcGIS Engine Style文件操作
- sublime前端编辑器入门与个人使用经验分享
- QT在构造函数中退出程序
- Unity3D中如何计算场景中的三角面和顶点数
- java中String s = new String("abc")创建了几个对象?
- MyEclipse中好用的快捷键汇总
- MyBatis学习---逆向工程 Mybatis Generator代码生成
- 华为4K机顶盒EC6108V9U从原联通更换为电信的IPTV账号成功经验
- iOS 通知推送APNS
- spring boot 与 spring cloud 关系
- Linux命令行使用
- 《Android进阶之光》--Material Design
- C#图像处理:截图程序(包含鼠标)