首页 > 其他分享 >Codeforces Round 951 (Div. 2)

Codeforces Round 951 (Div. 2)

时间:2024-06-08 14:21:44浏览次数:13  
标签:这个 一个点 相同 正方形 951 样例 Codeforces 公倍数 Div

A题没什么好说的。

B题目读懂了基本就会了。
首先很明显,如果x和y的某一位不一样,那这两位异或同一个数字自然也是不一样的。
所以要做的就是找到二进制里面最长的连续相同的数量。
这个时候看看样例,1 4 8 全是2的整数次方,33554432,计算器算一下,发现居然也是。那就非常明显了。
直接从低位向高位,一位一位的找是否相同,这一位相同就继续找下一位,如果不同就退出。
找到最多几位相同,设为\(ans\),\(2^{ans}\)就是答案。

C题做起来就更炸裂了。\(n\leq 50\) , $k\leq 20 $
看看样例,发现7,9,13,17,5,2,3这种数字出现的比例有点高,盲猜一手答案和质数相关。
20以下的质数最大19 。
尝试先摸一下贪心,做cf题日常贪心起手。
发现倍率大的肯定要压的少。
那就考虑一个做法,最大的位置先钦定为压一块钱,然后去填写下一位。如果超过了这一位的承受能力,就回来给他加上钱。
很明显会T,而且无解的情况需要再推导。
但是这个某种程度上给出了这个形成的思路。
首先5个5是做不到的,而2个3是能够做到的。
而为什么第一个做不到,因为收益率总是无法覆盖付出。而是否存在一种最优分配方案呢。对于上面说的两种,就存在,全填1 。
看看样例。发现似乎所有的填写都和最大公倍数是强相关的。
mmsd,不就是最大公倍数吗。先按照最大公倍数填,如果做不到覆盖,就是无解。样例过了。ac了。
抽象。

想想怎么证明,其实思路就是那个最优策略的存在性。
要写式子证明。。大体的思路就是先假设最优解就是让所有的点在赢的时候得到的回报是一个相同的数字,然后论证这个相同的数字小于你的支出的时候,不管如何调整,总是无法达到答案要求。如何就证明了上面的这个最大公倍数的解法是正确的。
我懒得写。awa

D题,其实巨简单。。简单的有点无聊。
题目给的限制太严格了。其实每次能够调整的只有中间的一个部分和尾部。
用\(x\)表示字符串尾部相同的字符数量。
当\(x=k\)的时候,前面的部分可以截取一个长度为\(2k\)连续相同的串的中间。或者这个串本身就是完美的。
当\(x<k\)的时候,需要找到前面的一个连续相同,并且字符和这个相同的位置,且长度为\(k-x\)或者\(2k-x\),截取过来。
当\(x>k\)的时候,无解了。

总体就3种情况。这题。。恶心归恶心,但是不得不说确实很考验分类讨论的能力,和代码的思路构建。如果不是按照这个办法构建思路,可能会代码写的很恶心。

唉。要是写的快,能rank100 。然后我rank1000 。难绷。

5题确实是一个大瓶颈啊。

E题,很有意思。

赛时没时间写了,考虑了一下。主要还是赛后想的。
曼哈顿距离相同,是在一个竖着的正方形上的。这个正方形的边长是\(d+1\)
然后先钦定一个点在三角形上,另一个点也必须在他的矩形上。
画出这两个矩形的交点。发现只有两个点!

标签:这个,一个点,相同,正方形,951,样例,Codeforces,公倍数,Div
From: https://www.cnblogs.com/HLZZPawa/p/18238597

相关文章

  • 纯CSS+单个div实现抖音LOGO
    纯CSS+单个div就能绘制抖音LOGO关键点:主要借助了两个伪元素实现了整体结构,借助了drop-shadow生成一层整体阴影drop-shadow只能是单层阴影,所以另一层阴影需要多尝试contrast(150%)brightness(110%)则可以增强图像的对比度和亮度,更贴近抖音LOGO的效果预览结果如下:在线......
  • [Tkey] CodeForces 1267G Game Relics
    太神了这题,膜拜出题人orz。思考一首先是大家都提到的一点,先抽卡再买。这里来做个数学分析。假设我们还剩\(k\)种没有买,其实我们是有式子来算出它的花费期望的。WIKI上提到,假设一个事件的概率为\(p\),则遇到它的期望为\(\frac{1}{p}\),因此,对于这个题,抽到一个新物品的概率显......
  • Codeforces Round 950 (Div. 3)G. Yasya and the Mysterious Tree(字典树处理区间异或
    Problem-G-Codeforces存个字典树板子。1#include<bits/stdc++.h>23usingi64=longlong;45constexprintN=1E7;67inttrie[N][2];8intcnt[N][2];910inttot=0;11intnewNode(){12intx=++tot;13trie......
  • Codeforces Round 949 (Div. 2)D. Turtle and Multiplication(欧拉路径、线性筛、思维
    Problem-D-Codeforces  按照官方正解做即可,顺带存个jiangly板子。1#include<bits/stdc++.h>23usingi64=longlong;4std::vector<int>minp,primes;56voidsieve(intn){7minp.assign(n+1,0);8primes.clear();910......
  • Codeforces Round 950 (Div. 3) A B C D E
    A.ProblemGeneratortimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputVladisplanningtoholdm......
  • Codeforces Round 951 (Div. 2)
    A.GuesstheMaximum题意:给定一个数组,求一个k值,k满足对于任意的这个数组的区间的最大值max,k<max。求满足条件的最大k。思路:只考虑长度为2的区间即可。参与到比较中的数值一定是两个数中的大数,从所有大数中选出最小的一个即可。总结:赛时很快就A掉了,但是思考的不够细节,思维太......
  • codeforces round 961题解(A、B、C)
    A.GuesstheMaximum因为\(i<j\),所以所有的\([i,j]\)区间中都至少包含两个相邻元素,所以只要求出所有相邻元素中较大值的最小值即可。intn;inta[N];voidsolve(){cin>>n;intmin_v=1e9+1;for(inti=1;i<=n;i++){cin>>a[i];......
  • CodeForces Round #951(Div. 2) 补题记录(A~D)
    A容易发现对于任意一个长度为\(n\),下标从\(1\)开始的序列\(a\),若\(1\lel\ler<n\),则必然有\(\max\limits_{i=l}^ra_i\le\max\limits_{i=l}^{r+1}a_i\)。若\(1<l\ler\len\),则必然有\(\max\limits_{i=l}^ra_i\le\max\limits_{i=l-1}^ra_i\)。很显然Bob希望......
  • codeforces 1442 D Codeforces Round 681 (Div. 1, based on VK Cup 2019-2020 - Fina
    链接大意就是给你n组物品,这n组物品里面每组有\(t_i\)个,且他们是按照价值不降的顺序排列的。现在允许取k个物品,每个物品必须取在数组的开头处,每个物品在被取用后就会消失。问你最大能够拿到多少价值的物品。其中\(n,k\leq1500,\sumt_i\leq1e6,a_i\leq1e8\)很背包吧。可......
  • Codeforces Round 949题解(A、B、C)
    A.TurtleandPiggyArePlayingaGame首先\(p\)选\(2\)的话除得最慢,得的分多。考虑二进制表示,如果\(x=(1000000000)_{bin}\),则每次除以\(2\)都是相当于右移一位,除完之后仍然是\(2\)的倍数,变成\(1\)的步数就是把最高位的\(1\)移动到\(0\)位的步数。因为\(2l\ler\),所以\(l......