首页 > 其他分享 >Codeforces Round 947 (Div. 1 + Div. 2)

Codeforces Round 947 (Div. 1 + Div. 2)

时间:2024-05-26 12:33:55浏览次数:30  
标签:度数 WA 947 Codeforces 正确性 权值 Div

Solve : A~E

Rank : 425

Rating : \(1744+195=1939\)(\(1894+95=1989\))

发挥评价:Normal

本场问题:E 先 WA on 4,较快找出问题后修改 WA on 27,就又急了(重现上午),开始怀疑做法正确性未果,结果 1h 后才发现是代码出现问题。

注意先检查代码漏洞而不是先怀疑正确性(尤其是错在后面时候,要是正确性有问题能过前面那么多点吗)

CF1975E

  • (me *2300)

树上点染黑白色,每次修改一个点的染色状态,每次修改后询问黑点是否成链。

如何判定链?这题给了一个很好的 Trick。

发现链的每个中间点度数为 \(2\),端点度数为 \(1\)。

但是黑色度数不好处理,改为本节点权值 \(-1\),父亲节点 \(+1\),然后发现此时链对应权值中有且仅有少量 \(-1\) 和 \(1\),简单分讨即可。

CF1975F

咕咕咕。

标签:度数,WA,947,Codeforces,正确性,权值,Div
From: https://www.cnblogs.com/FunStrawberry/p/18213525

相关文章

  • CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!)
    切5道。A\([a_1=1]\)B\(\max(\max(xy),\max(x^2),\max(y^2))\)第一部分可以选整个数组,第二部分和第三部分是最大连续0段和1段。C操作等价于\(a_{l\simr}\oplus1\),\(b_{l\simr}\oplus1\),\(b_{1\simn}\oplus1\)。考虑先把\(a\)全部变成\(0\),使用ii......
  • Codeforces Global Round 12 C2. Errich-Tac-Toe (Hard Version) 题解 构造
    Errich-Tac-Toe(HardVersion)题目描述TheonlydifferencebetweentheeasyandhardversionsisthattokensoftypeOdonotappearintheinputoftheeasyversion.ErrichtogaveMonogonthefollowingchallengeinordertointimidatehimfromtakingh......
  • CF Round946 (Div. 3)C:map的map<pair<int,int>int>映射 + 性质
    BeautifulTriplePairs题目描述Polycarpwasgivenanarray$a$of$n$integers.Hereallylikestriplesofnumbers,soforeach$j$($1\lej\len-2$)hewrotedownatripleofelements$[a_j,a_{j+1},a_{j+2}]$.Polycarpconsidersapa......
  • Codeforces Round 946 (Div. 3) G Money Buys Less Happiness Now(反悔贪心)
    MoneyBuysLessHappinessNow1.题目大意:有n天,每天可以赚x块钱,然后每天可以通过花\(C_{i}\)块钱购买1点快乐值,然后每天赚的钱至少要在下一天才能用,问最多能获得多少快乐值。2.解题思路:我们发现天数变得很多,不能像e题那样dp了,所以要用贪心。具体来讲,我们碰到当前能买的就直接......
  • Codeforces Round 946 (Div. 3)
    C.BeautifulTriplePairs题意:优美组的定义是一共三对有且只有一对对应的数字不相同,求有多少个优美三元组思路:对于只有三对,而且只有一对不同,首先看前面遍历过的三元组会对后面的三元组产生影响,若是不记录前面对后面三元组的次数,那么我们要进行两次循环O(n^2)会寄的,因此我们......
  • LeetCode Greatest Common Divisor of Strings All In One
    LeetCodeGreatestCommonDivisorofStringsAllInOneLeetCode1071errorsfunctiongcdOfStrings(str1:string,str2:string):string{letresult=``;lettemp=[];if(str1.length>str2.length){letreg=newRegExp(str2,'g'......
  • CodeForces 1965F Conference
    洛谷传送门CF传送门考虑题目可以看成天和人的匹配,因此判断单个日期区间\([l,r]\)可以考虑Hall定理,设\(N(S)\)为在\(S\)这些天有空的人的数量,定义\(S\)合法当且仅当\(|N(S)|\ge|S|\),那么\([l,r]\)合法当且仅当\(\forallS\subseteq[l,r]\),\(S\)合法。猜......
  • Topcoder SRM616-Div1-Lv2 ColorfulCoins
    涉及知识点:奇妙Ad-hoc前言一道很不常规的题目,思维难度大代码简单,而且这种思路很难在赛时想到,故记录一下。题意某国的货币系统硬币有\(n\(\leq60)\)种面额\(val_i\(\leq10^{18})\),其中最小的面额为\(1\),并且所有的面额之间都保证两两有倍数关系,每种面额的硬币有独一无......
  • CF Round946 (Div. 3)B:如何写映射
    SymmetricEncoding题目描述Polycarphasastring$s$,whichconsistsoflowercaseLatinletters.Heencodesthisstringusingthefollowingalgorithm:first,heconstructsanewauxiliarystring$r$,whichconsistsofalldistinctlettersofthestrin......
  • Codeforces 1974G Money Buys Less Happiness Now
    考虑到有一种贪心的思路就是能选就选。显然这是错的,因为可能存在后面更优的情况,即当\(c_i>c_j(i<j)\)时,选\(j\)肯定比选\(i\)更优,因为后面剩下的更多且中间也留下了一些。于是考虑反悔贪心。还是一样的,如果能选就一定选上。否则来说,考虑对于当前已经选了的中的最大......