首页 > 其他分享 >Codeforces Round 900 (Div. 3)

Codeforces Round 900 (Div. 3)

时间:2023-09-27 12:56:14浏览次数:44  
标签:900 32 Codeforces Round Div 节点

昨天晚上生病,没比(血亏)

A: 就是看k有没有在序列里

B: 随便放一个大的号码然后加 i,应该就可以过了

C: 就是我们最少要拿 k*(k+1)/2, 最多可以拿 k*(n+n-k+1)/2。 啊,你问我怎么证明在这两个值里就一定可以拿到(当然是猜的!!)

D: 让f[x]表示当前出了多少次。然后就没个k看l[i],r[i]和j有没有符合题目所说的。然后就算过了。

E: 啊怎么线段树在这里(手打了十分钟),简单二分(因为他是非严格递减的)就可以了。

F: 我自己做的好乱,就不解释了(jiangly大佬做的方法好帅 https://codeforces.com/contest/1878/submission/225309795)

G: 啊好题! 就是用last[i][x]来表示x上一个有bit i的节点是在哪儿。那么我们可以看的出就是最多有32个节点我们需要考虑。

那么就是找lca啊, 打表啊, 然后枚举那32个节点, 那个u和v的都要哦。程序好慢(1000ms左右)!!!!!

标签:900,32,Codeforces,Round,Div,节点
From: https://www.cnblogs.com/yonglicp/p/17732442.html

相关文章

  • Codeforces Round 742 Div2 A-D题解
    CodeforcesRound742Div2A-D题解A.DominoDisaster这题就是说给出一些2x1tile,然后给出2xn的第一行构造,问第二行这个刚开始想着是啥dp,一看那么多人过了果断改思路,发现这题就是个模拟题,就是把U换成D,D换成U,L和R不影响,然后输出就行了代码#include<bits/stdc++.h>using......
  • Codeforces Round 899 (Div. 2)
    Preface好久没现场打CF了(玩CC玩的.jpg),但这场久违的打的还不错,把Kusanagi_Misuzu这个小号也打上橙了虽然开场的时候状态不佳写的巨慢,但后面还是靠着ztc带我做出E1成功题数反超上大分接下来要考虑启动第三个小号了,只敢打Div2的FW是这样的A.IncreasingSequence比赛时候降智了......
  • Codeforces Round 738 (Div. 2) A. Mocha and Math
    给一个数组\(a_1,a_2,\cdots,a_n\)。可以执行以下操作任意次:选择\(l,r(1\leql<r\leqn)\),对于任意\(l\leqi\leqr\),同时执行所有\(a_{l+i}=a_{l+i}\&a_{r-i}\)。希望经过若干次操作后,\(a\)的最小的最大值。性质:\(x\&y\leqmin(x,y)\)。......
  • Codeforces Round 898 (Div. 4)
    这是我的vp,不是正真的contest. A:不想多说,读者应该可以做到的!!! B:让g=product(移除掉0的a):如果有多过1个0答案肯定是0。如果只是有1个0答案就是g。没有0,答案就是max(g/a[i]*(a[i]+1))任何i。 C:没有仔细想那个profit的formula.手打表,sum就可以了。 D:就是双......
  • Codeforces Round 899 (Div. 2)
    赛后四题B题直接枚举不存在的元素即可C题的trick有点像之前abc的某道题,对于奇数位置它一定可以贡献,对于偶数位置,如果它有数选了,那么它就能够贡献。\(f[i]\)表示到前i个且至少选了一个的最大答案。#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#de......
  • Codeforces Round 738 (Div. 2) B. Mocha and Red and Blue
    给一个字符串,包含字符\(B\),\(R\),\(?\)。其中\(?\)可能为\(B\)或\(R\)。规定不完美数为字符串中相同字符连续出现的次数,询问一个字符串的最少可能不完美数。观察到\(BR\)或\(RB\)需要尽可能多,于是考虑尽可能让相邻字符不同。容易证明从左往右扫和从右往左扫贡献......
  • Codeforces Round 750 (Div. 2) B. Luntik and Subsequences
    给一个数组\(a_1,a_2,\cdots,a_n\),定义\(s=\sum_{i=1}^{n}a_i\)。询问有多少个\(a\)的子序列满足\(\suma_{i_k}=s-1\)。显然要选出一个\(1\)不加入子序列,任意一个\(0\)可以加入或不加入子序列。于是\(ans=\binom{cnt1}{1}\cdot2^{cnt0}\)。vi......
  • CF1882 div.2 做题记录
    A题面扫一遍,令\(b_i\rightarrowb_{i-1}+1\),若\(b_i=a_i\),\(b_i\rightarrowb_i+1\)。点击查看代码#include<bits/stdc++.h>#defineullunsignedlonglong#definelllonglong#definepiipair<int,int>#definepdipair<double,int>#definepb......
  • Codeforces Round 899 (Div. 2)
    CodeforcesRound899(Div.2)A.IncreasingSequence解题思路:从左往右一个个看,从1开始,如果当前位相同\(+2\),否则\(+1\)。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=1e6+10;constintM=2*M;constintmod=1e9+......
  • Educational Codeforces Round 155 D (CF1879_D)
    题目大意给一个长度为\(n\)的数组,求\(\Sigma_{i=1}^{n}\Sigma_{j=i}^{n}区间异或和\times(j-i+1)\)其中\(n\leq3e5,~a[i]\leq1e9\)分析首先注意到由\(l\)到\(r\)的区间异或和可以转化为\(sum_{l-1}~XOR~sum_r\)因此,对于每一个点\(x\),无论它作为上述的\(sum......