Codeforces Beta Round #75 Div 1 (D无思路..)

A

就是加个Next[i][26]的数组来转移,基本上理清题意以后,5分钟内都出想法了吧

B

按a[i]排个序,然后顺序扫描,看最后的是谁就行了。= =脑抽写了线段树,本身线段树的话也不会写多久,但是又跑去尝试新写法。。。然后就写了巨久。。。

C

这个,看了watashi的代码,想了一下。

首先就是如果一个边集能符合题目,充要条件是每个点度数为偶数。

每当添加一条边连接两个不连通的块时,不可能会存在新的欧拉回路通过这条新加的边。所以显然答案不变。

而当添加一条边连接了两个本已连通的块时,假如是一开始只有一条边,答案必然还是0,然后接下来,每次出现这样的边,ans+=2^(k-1)。其中k代表这是第k条连接已连通的两个块的边。

为什么会这样呢?从结论往回看。。。本身的ans是不包含新加边的方案数,而2^(k-1)是包含新加边的方案数。

假设用一个mask代表那k-1条边的使用情况,那么极有可能是每个mask都对应了一种且仅一种方案。

继续YY

除去所有这k条边以后,其实图上是几棵树组成的森林!

然后假定现在这个第k条必取、、、然后前面k-1条组成的每个mask确实就唯一地对应了一种方案。

也就是说假设mask确定,我们森林边的取舍情况也就确定了。这个自行YY一下,明白过来会发现很显然

 

D

不会>.<

求指导。

 

E

这种放在省选NOI什么的就是送分题,裸考线段树

就是建一棵线段树,然后线段树每个节点里套一个线性表,以前我写这种比较疼,现在用vector简直好写到爆。。。

然后这个线性表的内容嘛,就是随着t的增长,看看这个线段里的老大是谁。

大概就是表示这样更替情况的一个队列。

然后嘛,假如区间里有i,j满足a[i]<=a[j] && b[i]<=b[j],那么i肯定就没用了。

剔除这些以后,按a[i]递减排序,变成了b[i]递增的序列。(我的Code中的Select())

然后就是利用决策单调弄这个队列了。由于b[i]递增,所以随着t的递增,必然是越来越倾向于选后面的。

我们现在构建一个栈,使得栈内元素满足Meet_Time(Q[i],Q[i+1])>Meet_Time(Q[i],Q[i-1]),其中Meet_Time(x,y)就是使得a[x]+b[x]*t=a[y]+b[y]*t的t值。

这个很容易扫一遍得出来。(我的Code中的Form())

构建完以后,对于每个询问l,r,t。

直接在线段树里找到l,r对应区间,然后可以三分得当前的t对应的老大是谁(我还是写得二分,Code中的Get_Best())。

按Solution Size排我的还是比较靠前的= =,我也觉得写得还是比较清楚,于是推荐一下。

时间复杂度O(n lg^2 n + q lg ^2 n)

【CODE】http://ideone.com/Aga48

【update】

按照猛犸学长的指示,构造部分可以通过归并排序避免那个sort的调用。

后面可以先对答案排序,然后用指针滑的方法得到均摊的n lg n。

于是总时间复杂度可以做到O(n lg n + q lg n)。

加入对话

8条评论

留下评论

回复 时光脱下旧袍子 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注