Codeforces训练日记

我已经鏼了8


Round#415 Div.1

[Problem A] 把序列排序,那么这个点会作为最小值被减掉2^{n-i}次,但是会作为较优值被加上2^{i-1}次,于是按照这个算贡献即可。

[Problem B] 显然如果询问(i,i+1)的话,要么都在最右边,要么都在最左边,这样就可以二分了,然后在找出的第一个数的左右分别同样做一次即可。

[Problem C&D&E] 待续

 


Round#416 Div.2

[Problem C] f[i]表示前i个数的答案,那么根据题目,能进行转移的只可能是某种数出现的最后一次,转移的点应该是他出现的第一次的位置,但是到达那个位置中可能又遇到一些数,还需要往前,所以扫一次即可。

[Problem D] 在第一个点一定可以推出上下是否交换或者左右是否交换,然后按照已知信息走下去,直到可以推出新的信息。对原图进行一次BFS,按照BFS的路径输出即可

[Problem E] 考虑到只会有一整列一整列出现,实际上满足链性结构,考虑用一棵线段树去维护,单列直接暴力O(n)做,合并采用并查集去维护,检查左孩子的右端是否和右孩子的左端连通即可。


Educational Round #21

[Problem C] 简单贪心

[Problem D] 因为只有一位要移动,而移动只会向前向后移,分两种情况讨论,向前移的话,经过的会给右边,反之则相反。假设我们在i,向左移动到j,那么左边的和就是pre_{i-1}+a[i]-sum(j->i-1),由于数都是非负,我们直接二分j即可。

[Problem E] 由于物品的代价只有三类,考虑枚举第三类的总数w,那么第二类如果用了x个,那么第一类就只能有m-3\times w-2\times x个。对于数量相同的情况下我们肯定选价值大的,所以对于每类物品维护降序前缀和。我们发现,一定存在某一个点,两个一类的会不如一个第二类的,显然,之后也一定满足这个性质,那么我们就可以三分第二类的个数,直接计算即可。

[Problem F&G] 待续


Round#418 Div.2

[Problem A] 把b序列排序,按顺序插入A序列,检查A序列是否合法即可。

[Problem B] 很容易发现最多有两个地方不一样,那么分类讨论下即可。

[Problem C] 暴力预处理ans[c][d]数组,表示修改的字符是c,允许修改的次数是d的答案,这个可以暴力枚举起始点来完成,时间复杂度O(26n^{2}+q)

[Problem D] 圆的关系只有包含和分离,所以每个圆连向最小的,能包含他的圆,这样就形成了一棵树(弄一个超级大的圆在外面),考虑树上dp,设f[i][0/1][0/1]表示以i为根的子树,该节点如果分到白天或者黑夜,他的奇偶性是什么。首先,令g[a][b]=\sum f[son_i][a][b],那么有两种情况,a=1或者b=1,如果是0,则加上当前的圆,反之则减去。

[Problem E] 由于这题保证了最短路的唯一性以及递增性,那么点完全可以放到一棵树上来看待,这棵树与普通树不同的地方在于,同层之间可以互相连边。考虑设f[i][j]表示与第i个点同深度的点有j个。那么显然有f[i][j]=\sum f[i-j][k]\times g[j][c2][c3],其中g[i][j][k]表示本层有i个点,上一层有j个度为2k个度为3的点的情况的方案数。那么g分情况dp,再利用g算出f即可。详情参见https://loj.ac/article/37


Round#420 Div.2

[Problem A] SB模拟

[Problem B] SB模拟,式子不是智障都能推出来,暴力给放过了,然而可以三分,性质显然。

[Problem C] 一开始想用一个set维护,因为你每次的话显然会把他们按照升序安排,这样会最优,安排之后如果有打乱顺序的,那肯定直接把答案++,然后把这玩意丢到set里去,聪明的你发现,set并没有什么卵用,直接做就行了。

[Problem D] 一开始题目读错了。。然后就是经典题啊,构造点表示行,列,该点免费边连向该行or该列的关键点,然后跑下dijkstra+pq就行了。

[Problem E] 简单题,你设f[i][j]表示到达(i,j)的方案数,考虑到y这么小,那显然大概是矩阵乘法一下,你发现有n段,那么每段做一次矩乘,调整下基矩阵即可。


Round#419 Div.1

[Problem A] 暴力枚举第一行修改多少,这样就可以确定每一列修改多少,从而确定其他行需要多少。

[Problem B] 推式子题。。我抄了题解

[Problem C] 打折券的使用关系是个树,考虑在树上进行DP,设以第i个点为根的子树,我们已经购买了多少个物品,这个物品用不用优惠券的情况下,最少的花费,然后比较即可。转移的话采用树上枚举的技巧,虽然看上去是O(n^{3})但实际上O(n^{2})


Round#422 Div.2

[Problem A] SBT

[Problem B] SBT

[Problem C] 把按照长度分类,这样就在枚举某条线段的同时确定我们需要的另一个线段,然后在需要的那堆里按左端点排序,做一个后缀最小值,然后扫描的时候用二分加速即可,upperbound会蜜汁wa我换了手写二分才A掉的

[Problem D] 大力dp,时间复杂度利用调和级数可以证明是O(r\log r)的。

[Problem E] 大力dp,记f[i][j]表示A串前i个切了j段,最多能匹配到B串的哪里,显然转移我们希望贪心的选,即lcp,把两个串连起来用特殊字符隔开,后缀数组做即可。

[Problem F] 自古不会做概率题QAQ


Round#423 Div.1

[Problem A] 考虑问题等价于区间赋值,容易联想到疯狂的馒头那题,由于存在大量的重复,每个点实际有用被覆盖次数只有1次,我们用并查集维护每个位置,每次和右边的连通,移动的时候直接移动到连通块的末尾即可,时间复杂度O(n\alpha n)

[Problem B] 简单构造,为了最小化叶子之间的距离,我们随便选一个点当做这个图的centroid,然后把任意k个点连向他,考虑到还有一些点没有被arrange,我们逐次考察每层,连上每层的每个点,这样,答案就是最大的两个深度相加。

[Problem C] 考虑到查询的串长只有10,我们不妨记f[i][j][k][s]表示,假设询问串长为i时,原序列所在的位置是s,模了串长后的位置为j,字符是k的答案。显然这个支持前缀和。单点修改的话用树状数组维护即可。空间有点炸裂不过还是过得去的。

[Problem D] 先构造出这张图的任意一个MST,考虑不在MST上的边,那么他的价值一定是他两端的点在树上最短距离经过的最大边权-1。考察在MST上的边,我们先对于每个不在MST上的边,把这条边的权值赋值到两点的路径上的每条边上去,保留最小值。那么在MST上的边的价值一定是两点最小值-1,如果没有被考虑到就是-1,拆解最小值可以降序做倍增,最大值升序做倍增即可。

[Problem E&F] 妈呀这啥啊我不会FFT啊QAQ


 

发表评论

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