首页 > 其他分享 >CF1534(模拟赛记录)

CF1534(模拟赛记录)

时间:2024-09-06 19:24:55浏览次数:11  
标签:CF1534 le 记录 max sum mid dfrac mx 模拟

比赛页面

ABCD 都打的可以,然而 E 的 +10 直接葬送了大概率过的 F1 ……

先猜了个 \(n-k+1\) 的结论,但是没有写搜索查正确性(事实上确实不正确),于是两次罚时,第一次是交互格式错了。
然后又猜了个 \(\min(n-k+1,(n-1)/(k-1))\) 的结论,过了几个小的搜索数据(\(n\le 6\))的,大一点的没跑,于是又两次罚时。
五分钟后发现 7 3 都跑不过去,立刻全部删掉重新想。想出来的解法是对的,但依然吃了五发罚时。
猜 \(n-k+1\) 的时候写了个搜索做对拍,因为玩的小样例次数都 \(\le n-k+1\),搜索设定了只会搜出来次数 \(\le n-k+1\) 的解,导致把 4 3 这种虽然两次不行,但是四次可以的情况判定为无解,再加上 5 2 这种确实是无解的,误以为 \(n,k\) 奇偶性不同就无解。
这个错误的判无解方式沿用到我的正确解法里面,吃了五发罚时才发现这个问题 ……

警示:猜结论最好能证明出来。猜结论至少跑个中等强度的数据。猜的结论测出错时,要立刻把所有基于这个结论的东西都视作未证明的东西,包括搜索。

下面记录一下 E 的正确解法。

题目转化为 \(n\) 个杯子,每次翻 \(k\) 个,要求全部翻面,最少几次。

考虑每个杯子被翻的次数 \(c_i\),有:\(2\not\mid c_i\)、\(\sum c_i=k\cdot times\),这是比较显然的。

因为每个杯子的地位是相同的,考虑构造一个 \(\{c_i\}\),记 \(sum=\sum c_i\),目标是让这个 \(c_i\) 满足上面两个条件的同时,让能达成 \(c\) 的操作次数最小。

对于一个序列 \(c\),显然要至少 \(\max c_i\) 次操作才可行(因为不能一次操作重复翻杯子)。因为 \(\dfrac{sum}{k}\) 是操作次数,所以必须有 \(\max c_i\le \dfrac{sum}{k}\) 才有可能可行。赛时直接数学直觉,猜这个也是充分条件过了。

如果这个结论成立,目标就是构造一个 \(c\) 满足:\(2\not\mid c_i\)、\(k\mid\sum c_i\)、\(\max c_i\le \dfrac{\sum c_i}{k}\) 这些条件,然后使 \(\sum c_i\) 最小。

初始设定 \(c_i=1\),因为必须是奇数,所以改变 \(c_i\) 只能 \(+2\)。因为要让最大值小于平均数,肯定是尽量平均的 \(+2\),如此循环直到 \(k\mid \sum c_i\)。

于是得到算法:令 \(p=1\),每次令 \(c_p+2\),然后 \(p\leftarrow p+1\)(\(p=n\) 则 \(p\leftarrow 1\)),直到 \(k\mid sum\),找到最优的 \(c\) 数组。判无解可以在这个过程中做:当 \(sum/k>500\) 则无解。

然后是怎么通过 \(c\) 还原操作:每次取 \(c\) 最大的 \(k\) 个位置,然后全部 \(-1\) 即可。

最后一个问题:为什么一个 \(c\) 数组在满足 \(2\not\mid c_i\)、\(k\mid \sum c_i\)、\(\max c_i\le \dfrac{sum}{k}\) 就能构造出合法序列?

按照 \(\max c_i\) 的大小归纳。

当 \(\max c_i=1\),显然。

当 \(\max c_i>1\),记 \(mx=\max c_i\),因为 \(mx\le sum/k\),所以 \(sum\ge k\cdot mx\ge 3k>2k\);同时 \(n=\sum \dfrac{c_i}{c_i}\ge \sum \dfrac{c_i}{mx}=\dfrac{sum}{mx}\ge k\)。所以一定可以进行两次操作都包含 \(mx\)。于是 \(mx\rightarrow mx-2\),由归纳假设知可行。


官方题解:我们只关心当前奇数次的杯子个数,建立 \(0\sim n\),第 \(i\) 个点表示当前有 \(i\) 个奇数,求 \(0\rightarrow n\) 的最短路即可。

另外 F 是个没有技术含量的缩点。

标签:CF1534,le,记录,max,sum,mid,dfrac,mx,模拟
From: https://www.cnblogs.com/FLY-lai/p/18400800

相关文章

  • 2024.9.6 CF1307 模拟赛记录
    A:各捆干草间互相独立,所以优先移动距\(1\)近的。点击查看代码#include<bits/stdc++.h>#defineintlonglong#definepsbkpush_back#definefstfirst#definescdsecond#defineumapunordered_map#definepqueuepriority_queue#definevcvector#defineendl'\n'......
  • Git使用经验总结6-删除远端历史记录
    删除远端的历史记录但是不影响最新的仓库内容是笔者一直想实现的功能,有两个很不错的用处:有的历史提交不慎包含了比较敏感的信息,提交的时候没注意,过了一段时间才发现。这个时候已经有了很多新的历史提交,无法再回退了。有时候会拿Git仓库存储代码文件以外的内容,比如美术资源、依......
  • C语言——使用回调函数模拟实现qsort
    同学们还记得之前我们已经学过一种排序方法叫“冒泡排序“嘛。代码直接附上咯voidbubble_sort(intarr[],intsz){ inti=0;//趟数 for(i=0;i<sz-1;i++) { intj=0; for(j=0;j<sz-i-1;j++) { if(arr[j]>arr[j+1]) { inttmp=......
  • 『模拟赛』CSP-S模拟1
    Rank1BADA.喜剧的迷人之处在于签。正好早上还在改一个要分解质因数的题,所以一眼就出思路了。首先将\(a\)的平方因子全部除去,剩下的就是\(b\)必须的因数,即若设将平方因子全部除去后的\(a\)为\(a'\),则\(b\)应表示为\(a'\timesx^2\),从\(L\)这个下界开始只用找......
  • 使用flask进行Mock Server模拟接口操作及问题解决
    1.flask介绍flask是一个轻量级的pythonweb微框架2.MockServer介绍MockServer是一个开源的模拟服务器,它可以定义和记录API交互,支持各种http方法(get、post、put、delete),可以自定义响应内容,例如返回静态文件可以使用flask来搭建一个mock模拟服务3.模拟接口先安装flaskpip......
  • 秋招/春招投递公司记录表格
            最近在准备秋招,在各个平台投递秋招简历,什么官网,邮箱,boss,应届生各个平台上,投递的平台比较多,比较乱,因此自己想将这些平台投递记录都收集到一个表格上,所以在腾讯文档上自己做了一个表格,用来记录秋招在各个平台上的简历投递这个是整体预览图1、公司名称   ......
  • Luogu8990 做题记录
    link比较喜欢的题目。考虑合法的条件,从点亮的灯的角度难以维护。反过来看,从未点亮的灯角度考虑,条件相当于这些灯形成了一个包含\(1\)号灯的连通块。如何判定这些灯形成一个连通块?点减边!设\(c_i\)为操作前\(i\)次后,未点亮的灯的\(|V|-|E|\)的值,那么\(c_i=1\)即合......
  • 2024年9月26日记录网站安全性配置优化
    1、修改apache配置httpd.conf文件 #关闭trace-methodTraceEnableoff#隐藏Apache版本信息ServerSignatureOffServerTokensProductOnly2、修改网站配置文件,不允许777目录执行任何可执行脚本<VirtualHost*:801>ServerNamewww.website.comServe......
  • 记录BUUCTF 中 的一道hook掉函数地址的题目
    题目[Zer0pts2020]easystrcmp1https://files.buuoj.cn/files/2961ba55f464e750aca703838dfca234/easy_strcmp_e1a6208fde4f52fd0c653c0b7e8ff614.tar.gz刚开始在main函数中发现if(!strcmp(a2[1],"zer0pts{********CENSORED********}"))puts("Correct!......
  • 记录 ThreadPoolExecutor任务队列放入任务的方式
    众所周知,ThreadPoolExecutor内部任务队列属性类型定义为:privatefinalBlockingQueueworkQueue;而其有三种提交任务方式:add、put和offer,好奇其内部用的哪个,又不想查资料,故而跳到源码内部一看。结果如下:三种提交任务方式:put(Eelement):将指定元素插入队列,如果队列已满,则阻塞......