20200611模拟-akc

akc的场

xgc过了AB,rose怒写220min10K,A的单log做法

除了我A快乐MLE外,基本都过了A

CF1007D Ants

题意:$n \le 1e5$点的无根树,$m \le 1e4$组路径,每组路径中选一个,使得边集不重

请先思考后再展开

写暴力花了宝贵的几十分钟(不太会快速判交,写错了挺久),后面才发现暴力是没用的,在程序里check就好了

而且对主席树优化建图也不太熟练,修了好几次锅,最后写完只剩20min了,后面题还没看过


一眼2-SAT,树剖(管他是不是边集,总能转成序列区间)后放到线段树上,然后线段树每个点指向孩子

将区间x放上去拆成log个位置,每个位置连向$oth(x)$表示碰到了x

然后再次把区间放上去,拆出的log个位置子树内就是被该区间包含的部分,所以连向这log个位置

另外路上经过的表示被那个覆盖,但肯定不能直接指向经过的每个位置,所以当时需要复制个点(实现时可以$copy(i)=MX-i$)

但直接这样搞会$x->…->oth(x)$,当时感觉m这么小,主席树前后缀各做一次,不就解决了吗(即去掉加入$oth(x)$那次),没有兴趣和时间再怎么去想更好的修锅方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void insert(int fl,int fr,int go,TOP)
{
++id;lc(id)=lc(x),rc(id)=rc(x),TAR::ins(M-1-id,M-1-x),TAR::ins(id,x);x=id;
if(fl==l and fr==r){ TAR::ins(x,go),TAR::ins(M-1-x,go);return; }
if(fr<=mid) insert(fl,fr,go,LC);
else if(fl>mid) insert(fl,fr,go,RC);
else insert(fl,mid,go,LC),insert(mid+1,fr,go,RC);
if(lc(x)) TAR::ins(x,lc(x));
if(rc(x)) TAR::ins(x,rc(x));
}
void ask(int fl,int fr,int fm,TOP)
{
if(!x) return;TAR::ins(fm,M-1-x);
if(l==fl and r==fr){ TAR::ins(fm,x); return; }
if(fr<=mid) ask(fl,fr,fm,LC); else if(fl>mid) ask(fl,fr,fm,RC);
else ask(fl,mid,fm,LC),ask(mid+1,fr,fm,RC);
}
fo(i,1,m) fd(op,1,0)
{
int cur=i*2-op,oth=i*2-(op^1);rt[0][cur]=rt[0][cur-1];
for(auto in:hh[i][op]) insert(in.FR,in.SE,oth,rt[0][cur]);
}
//反着做一次,类似
fo(i,1,m) fd(op,1,0)
{
int cur=i*2-op;
for(auto in:hh[i][op])
ask(in.FR,in.SE,cur,rt[0][cur-1]),
ask(in.FR,in.SE,cur,rt[1][cur+1]);
}
//可见时空常数巨大,差不多是log级别了

最后手贱把空间从1e7开到2e7,边因为是动态建的,再加上vc的空间常数,MLE了,改回去就ok

然而这做法经过主席树修锅后,考虑上常数,可以当做是$O(mlog^3)$了,在CF上会TLE


从头开始重新考虑,直接把每个区间挂上线段树上,则每个叶子向上碰到的所有东西,关系就是在其中只能选最多一个

相当于,每个x需要连往祖先路径和子树内每个y的oth(y)

拆成x连往祖先路径的每个y的oth(y),以及祖先路径的每个y连往oth(x)

经典的前缀优化建图,因为不太好描述,给出核心代码:

1
2
3
4
5
6
7
8
9
10
11
12
void build(int lsta=0,int lstb=0,TOP)//a=x,b=oth(x)两棵树
{
for(auto a:pt[x])//挂在上面的编号
{
int b=(a&1?a+1:a-1);//b即 oth
TAR::ins(a,lstb),TAR::ins(lsta,b);
id++;TAR::ins(lsta,id);TAR::ins(a,lsta=id);
id++;TAR::ins(id,lstb);TAR::ins(lstb=id,b);
}
int cura=lsta,curb=lstb;
if(l<r) build(cura,curb,LC),build(cura,curb,RC);
}

时空复杂度不变,常数降低为12(其实也不算小):完整code

CF1267G Game Relics

题意:$n \le 100$个物品,想全部购买。每次可以支付ci购买第i个,或者花费$x \le \forall c_i$抽奖,等概率随机获得n个中1个,如果已经获得,返还$x/2$(含小数),求最小期望花费,$\sum ci \le 1e4$

请先思考后再展开

首先核心观察应当是,抽奖的时候,是与物品的价格无关的

发现$x \le ci$比较微妙,猜一个结论:一定是先一直抽奖,然后再一直购买

感觉pb的证明思路很好:

如果某次购买后还有抽奖,考虑另一种策略,此次购买后,全部假装自己买了来决策(即考虑两种策略,除了购买那次操作外,发生的结果完全一样),直到假装发现买完了

  1. 如果此时其实并没买这个物品,则现在买,不会亏
  2. 如果之前碰巧抽中了,考虑两个策略的差,后者在抽中之前没碰到过所以不会有X/2的影响,在抽中后,两边是一样的,抽中时,前者花了X/2,后者花了X;然后购买本身前者花了C,所以后者一定不劣

emm所以感觉或许,$x \le 2ci$也是可行的?


假如结论是对的,购买的顺序可以任意调整,于是我们可以魔改:将购买操作,看作在剩余中随机一个

(我们不关心结论是否有被保证,只是允许任意顺序,而这样搞不可能比最优答案小)

那么因为始终是抽奖,一个已经获得k个物品的局面的发生概率就是$\frac{1}{ {n \choose k} }$,所以到各个局面的转移始终是等概率的

因此,$\sum_{后继状态} (后继代价+这次选择的代价)*p$的p是相当的,可以将选择代价提出

对于抽奖,一直抽奖(不可能中途换策略)得到下个新物品的期望代价显然为$\frac{x}{2}*( \frac{1}{(n-k)/n}+1 )$

对于购买,$\frac{剩余物品价格和sum}{n-k}$


进一步魔改:由始至终只有一种抽奖,过程为在剩余中随机一个,局面代价为,$\min{ \frac{x}{2}*( \frac{1}{(n-k)/n}+1 ), \frac{sum}{n-k} }$


由于概率和权值都只和k、sum有关,一次计算一类,$\sum_{n,sum} \frac{dp(n-k,sum)}{ {n \choose k} }*\min{ \frac{x}{2}*( \frac{1}{(n-k)/n}+1 ), \frac{sum}{n-k} }$

dp部分直接做裸的背包,$O(n^2C)$是可过的

1
2
3
4
5
6
7
8
9
10
11
12
cc[0][0]=1;fo(i,1,n){ cc[i][0]=1;fo(j,1,i) cc[i][j]=cc[i-1][j-1]+cc[i-1][j]; }
dp[0][0]=1;
fo(tim,1,n)
{
int c=qread();
fd(i,tim,0) fo(j,0,sum) dp[i+1][j+c]+=dp[i][j];
sum+=c;
}
double ans=0;
fo(k,0,n-1) fo(s,0,sum) if(cc[n][k]>eps)
ans+=dp[n-k][s]/cc[n][k]*min( X/2.0*(1.0*n/(n-k)+1) ,s*1.0/(n-k));
printf("%.10lf",ans);

「JOISC 2017 Day 2」门票安排

题意:长度为n的环,安排m个订单,从Ai到Bi有Ci个人,分配每人路线(同订单可以不同),最小化每条边经过次数的最大值

$n,m \le 2e5$

请先思考后再展开

鸽置

cty题解

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/f52c9b9c.html
转载请注明出处,谢谢!