NOI2014 Day1 废话题解 - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
BZOJ1509 NOI2003 Hookey
NOI2014 Day2 废话题解

NOI2014 Day1 废话题解

Hoblovski posted @ 2014年8月07日 02:25 in Solutions with tags bzoj NOI2014 , 1100 阅读
今年Day1没有去年一样丧心病狂了,不会出现一题都不会的情况.
王仓出一天NOIP题什么心态!!!!!!Au线540了啊啊啊啊啊啊啊啊啊啊!!
感觉题确实有点简单,不过超过三分之一上200是什么情况...Orz膝盖跪烂.
我就是蒟蒻啊...丧心病狂的集训队对A,B队分开对待....
 
T1 给定一个位运算操作序列,你需要给定一个不超过M的输入值使得最大化输出值
 
全场超过一半的人A掉
不写对拍的人是什么心态!!!!!!!
退役了可以尽情黑人了不用担心rp了.
不写对拍是什么心态逗比么!(虽然感谢你们不写对拍233)
...把每一位分开考虑发现最终每一位只可能被强制置为某个值,取反或不变.
我们可以按数位DP的思路枚举M的二进制表示的1位然后O(N+lg^2M)解决.
也可以像正解一样从高位贪心到低位,O(N+lgM).
 
T2 给定一个无向图G,每条边上有两种权值w1和w2
   你需要找一条ST路最小化其上max{w1}+max{w2}
 
考场上推出来是LCT.介于我在THUSC的时候立下的Flag,我不怎么会LCT....于是A掉此题233
 
有个显然的思路是枚举最大的w1和w2然后在导出子图中判连通.
然后我们显然发现最大的w1确定的时候w2是可以二分的.
不过还是会TLE,然后我们把w1确定的时候的最优w2打出表来
发现对于很长的一段w1,其最优的w2都是一个不变的值....
于是我们可以找到这一段的开头之后二分这一段的结尾
我们就不用在枚举的时候一次只跳1而是一次跳很多步的了
然后我们发现通过这两个优化之后他给的极限数据我们已经从不可忍受的时间跑到了10s左右
恩...接下来就是卡常数的战争了呢.......
首先我们不需要MST只需要一颗MBST,最小瓶颈生成树,而MBST是可以线性求得的...
然后大概是5s左右的了...为什么我们每次都要扫一遍所有边来搞连通性呢...
于是我们想到了break大法...把有用的边挑出来按w2排个序之后每次使用break大法
然后我们就可以在1.5s左右跑出他给的极限数据了呢...
还是对拍大法保佑万岁!!!
 
T3 提答题,给一个0..9矩阵,每次选一条路要求路上的数构成的数是回文数/素数,之后可以消去路上的数之后上方的数下落,要求你通过他给的规则得分最大
 
第一个点手算2333333..
然后就是各种乱搞233随机大法好只是不会写...
然后所有点都是手算的呢233333人类智慧2333333...
Orz jc大爷70+,Orz xyz大爷50+...Orz膝盖跪烂...蒟蒻太蒟蒻了呢2333333
 
然后得分220,不算好,Au有压力....已滚出23333

于是以下是乱搞代码

 

program bzoj3668;
 
const maxd=31;
 
var op:array[0..maxd] of longint;
    n,m:longint;
 
function max(i,j:longint):longint; begin if i>j then exit(i) else exit(j); end;
function trans(i,j:longint):longint; begin case j of 2:exit(i); 3:exit(i xor 1); else exit(j); end; end;
 
function getop(var i:longint):longint;
var ch:char;
begin
read(ch); case ch of 'A':getop:=1; 'O':getop:=2; 'X':getop:=3; end;  while ch<>' ' do read(ch); readln(i);
end;
 
procedure init;
var i,j,k:longint;
begin
filldword(op,length(op),2); readln(n,m); for i:=1 to n do case getop(j) of
        1:for k:=0 to 31 do if j>>k and 1=0 then op[k]:=0;
        2:for k:=0 to 31 do if j>>k and 1=1 then op[k]:=1;
        3:for k:=0 to 31 do if j>>k and 1=1 then op[k]:=op[k]xor 1;
end;
end;
 
function f(n:longint):longint;
var i:longint;
begin
f:=0;
for i:=0 to n do f:=f or(max(trans(0,op[i]),trans(1,op[i]))<<i);
if n>-2 then f:=f or(trans(0,op[n+1])<<(n+1)); for i:=n+2 to maxd do f:=f or(trans((m>>i)and 1,op[i])<<i);
end;
 
function dp:longint;
var i:longint;
begin
dp:=f(-2); for i:=0 to maxd do if m>>i and 1=1 then dp:=max(dp,f(i-1));
end;
 
begin
init;
writeln(dp);
end.
{$INLINE ON}
program bzoj3669;
 
const maxn=50017;
      maxm=100017;
      maxint=longint($3f3f3f3f);
 
var e:array[0..maxm,1..4] of longint;
    e1:array[0..maxm,1..3] of longint;
    p,p0:array[0..maxn] of longint;
    n,m,m1,mw1,mw2:longint;
 
function min(i,j:longint):longint; inline; begin if i<j then exit(i) else exit(j); end;
function max(i,j:longint):longint; inline; begin if i>j then exit(i) else exit(j); end;
 
function find(u:longint):longint;                            begin
if p[u]<0 then exit(u); p[u]:=find(p[u]); exit(p[u]);        end;
 
procedure union(u,v:longint);                                                                        begin
if p[u]<p[v] then begin inc(p[u],p[v]); p[v]:=u; end else begin inc(p[v],p[u]); p[u]:=v; end;        end;
 
procedure qsort1(l,r:longint);
var i,j,k,o:longint;
begin
i:=l; j:=r; k:=e[l+random(r-l+1),3];
repeat
        while e[i,3]<k do inc(i);
        while e[j,3]>k do dec(j);
        if i<=j then begin
                o:=e[i,1]; e[i,1]:=e[j,1]; e[j,1]:=o;
                o:=e[i,2]; e[i,2]:=e[j,2]; e[j,2]:=o;
                o:=e[i,3]; e[i,3]:=e[j,3]; e[j,3]:=o;
                o:=e[i,4]; e[i,4]:=e[j,4]; e[j,4]:=o;
                inc(i); dec(j); 
        end;
until i>j;
if i<r then qsort1(i,r);
if j>l then qsort1(l,j);
end;
 
procedure qsort2(l,r:longint);
var i,j,k,o:longint;
begin
i:=l; j:=r; k:=e1[l+random(r-l+1),3];
repeat
        while e1[i,3]<k do inc(i);
        while e1[j,3]>k do dec(j);
        if i<=j then begin
                o:=e1[i,1]; e1[i,1]:=e1[j,1]; e1[j,1]:=o;
                o:=e1[i,2]; e1[i,2]:=e1[j,2]; e1[j,2]:=o;
                o:=e1[i,3]; e1[i,3]:=e1[j,3]; e1[j,3]:=o;
                inc(i); dec(j); 
        end;
until i>j;
if i<r then qsort2(i,r);
if j>l then qsort2(l,j);
end;
 
function con(l1,l2:longint):boolean;
var i,u,v:longint;
begin
fillchar(p,sizeof(p),$ff); for i:=1 to m do if e[i][3]>l1 then break else if e[i][4]<=l2 then begin
        u:=find(e[i][1]); v:=find(e[i][2]); if u<>v then union(u,v); if find(1)=find(n) then exit(true);
end; exit(false);
end;
 
function getl2(l1,l,r:longint):longint;
var i,mid,u,v:longint;
begin
if not con(l1,r) then exit(maxint); fillchar(p,sizeof(p),$ff); fillchar(p0,sizeof(p0),$ff); m1:=0;
for i:=1 to m do if e[i][3]>l1 then break else if e[i][4]<=r then begin
        inc(m1); move(e[i],e1[m1],8); e1[m1][3]:=e[i][4];
end; qsort2(1,m1); l:=1; r:=m1; while l<>r do begin
        mid:=(l+r)>>1; for i:=l to mid do begin
                u:=find(e1[i][1]); v:=find(e1[i][2]); if u<>v then union(u,v); 
        end; if find(1)=find(n) then begin p:=p0; r:=mid; end else begin p0:=p; l:=mid+1; end;
end; exit(e1[l][3]); 
end;
 
procedure init;
var i,j,k:longint;
begin
readln(n,m); mw1:=0; mw2:=0; for i:=1 to m do begin
        readln(e[i,1],e[i,2],e[i,3],e[i,4]); mw1:=max(mw1,e[i][3]); mw2:=max(mw2,e[i][4]);
end; qsort1(1,m);
end;
                                         
function ans:longint;
var l1,l2,l,r,mid:longint;
begin
if not con(mw1,mw2) then exit(-1); 
ans:=maxint; l:=1; r:=mw1; while l<>r do begin
        mid:=(l+r)>>1; if con(mid,mw2) then r:=mid else l:=mid+1; 
end; l1:=l; l2:=mw2; while l1<=mw1 do begin
        l2:=getl2(l1,1,l2); ans:=min(ans,l1+l2); 
        l:=l1; r:=mw1; while l<>r do begin
                mid:=(l+r)>>1+1; if getl2(mid,1,l2)=l2 then l:=mid else r:=mid-1; 
        end; l1:=l+1;
end;
end;
 
begin
init;
writeln(ans);
end.

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter