CFR608

CFR608 div2

D是真的难受

CF1271A Suits

看了十年题意+变量有点多写错了,code

CF1271B Blocks

想了足足6min

code

CF1271C Shawarma Tent

一开始脑残复制了个bit,除去看题可能10min

code

CF1271D Portals

可能看了20min题意woc

讲道理,这题面确实是没有把可能的歧义说明清楚,更重要的是他的动词也是感性地换来换去的,而我很多时候为了把握题意使用搜索高亮的,总之就是蛋疼


把E做完后,我瞪着这题的2100标签,它也瞪着我,瞪了一下午,人都傻了

为了防止是我看错题,还特地去luogu看了看中文题面,没毛病

死了一万年后看看题解,无fack说

题意中的lose,是不允许出现的,而我一直以为要在lose或占领最后一个,然后结算分数,然后怎么想都是n的3次方

请先思考后再展开

稍微说一下除了无脑dp外的做法

其实也没啥难度,就是最基本的后悔贪心,将限制条件转化为,前i个城堡,最多派出多少人,然后用个堆踢最小的即可,code

似乎还有些奇怪的贪心+线段树做法

CF1271E Common Number

请先思考后再展开

$$
(x0)=(x1)+(x00)+[x0 \le n],(x1)=(x10)+[x1 \le n] \\
即(x0)=(x00)+[x0 \le n]+(x10)+[x1 \le n],将最后一位忽略,就能看做一棵二叉树
$$
求出偶数里面最大的x后,只需要判断x+1

剩下自己想吧,复杂度是log的

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
32
33
34
35
36
37
38
39
40
41
42
map<ll,ll> F;
ll getdep(ll num){return log2(num);}
#define lc (x<<1)
#define rc (x<<1|1)
ll D[N],G[N];
void main()
{
ll n=qread(),K=qread();
if(K==1){ write(n);return; }
if(K==2 and n==1){ write(-1);return; }
if(K==2){ write(n&1?n-1:n-2);return; }
int mxD=getdep(n>>1);
G[mxD]=2;fd(i,mxD-1,0) G[i]=G[i+1]*2+2;
D[mxD-1]=2;fd(i,mxD-2,0) D[i]=D[i+1]*2+2;
F[n>>1]=1+(n&1);
for(ll x=(n>>2),lst=(n>>1);x>0;lst=x,x>>=1)
{
if(lc==lst)
{
if((rc<<1)<=n)
{
F[x]=F[lc]+D[getdep(rc)]+2;
if(D[getdep(rc)]+1>=K){write(x*2+1);return;}
}
else F[x]=F[lc]+2;
}
else
{
assert(rc==lst);
F[x]=G[getdep(lc)]+F[lst]+2;
if(F[lst]+1>=K){write(x*2+1);return;}
}
if(F[x]>=K){write(x<<1);return;}
if(x==1){write(1);return;}
if(getdep(x-1)==getdep(x) and G[getdep(x-1)]>=K)
{
if(G[getdep(x-1)+1]+1>=K) write((x-1)*2+1); else write((x-1)*2);
return;
}
}
}

CF1271F Divide The Students

咕咕咕

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