首页 > 其他分享 >CMO 2023 p6 省流版

CMO 2023 p6 省流版

时间:2023-12-19 17:45:29浏览次数:42  
标签:CMO lceil p6 包含 省流版 alpha rceil

题解

题目中要求, 位置 \(i\) 上的数要运动到位置 \(u_i = (p_i+k)\bmod n\), 其中 \(k\) 可以任选. 假设位置 \(i\) 上的数运动过程中, 它总共以逆时针方向运动了 \(x_i\) 个单位 (可为负数). 把全部的 \(x_i\) 均加上一个常数,仍然会是合法的.

通过调整法可证, 存在一种最优移动方案:

  • 不出现, 逆时针方向下,\(i\) 超过了 \(j\) \(2\) 次的情况;
  • (严格强于上一个条件) \(|x_i-x_j|<n\).

可设 \(0\le x_i<n\). 假设 \(i\) 逆时针走到 \(p_i\) 的弧为 \(\alpha_i\).

可以进行的操作有:

  • 交换 \(\alpha_i, \alpha_{i+1}\) 的终点 (代价为 \(1\));
  • 给所有 \(x_i\) 加上任意常数 (代价为 \(0\)).

(所有加法运算均在\(\bmod n\) 意义下进行.)

如果忽略操作 \(2\), 只需使 \(\forall i\ne j, \alpha_i \not \subset \alpha_j\). 而且,若存在这样的包含关系,必能用 \(1\) 次操作 \(1\) 去除恰好 \(1\) 对包含关系。

只需算出 \(\sum_{i\ne j} \alpha_i\subset \alpha_j\) 的最大值 \(mx\), 它是答案的上界. 发现, 相交关系可以均调整为包含关系. 包含关系有着内向树的结构,而任意子树大小不超过 \(\lceil n/2 \rceil\). 故:

\[\begin{split} mx &= \binom{\lfloor n/2\rfloor}{2} + \binom{\lceil n/2 \rceil}{2} \\ &= 2401 \end{split} \]

标签:CMO,lceil,p6,包含,省流版,alpha,rceil
From: https://www.cnblogs.com/alfalfa-w/p/17914326.html

相关文章

  • P6370 [COCI2006-2007#6] KAMEN 题解
    原题链接:P6370思路题意不多赘述。首先这道题的\(60\)分暴力很好打,直接按题目中的操作做即可,时间复杂度\(O(nr)\)。考虑优化暴力。我们会发现很多次石头的起始点为同一列的情况,其实每一次下落的轨迹是差不多的。具体来讲应该是第一次下落的轨迹一定包含了后面每一次的轨迹。......
  • SFP6006-ASEMI新能源功率器件SFP6006
    编辑:llSFP6006-ASEMI新能源功率器件SFP6006型号:SFP6006品牌:ASEMI封装:TO-247最大平均正向电流:60A最大重复峰值反向电压:600V产品引线数量:3产品内部芯片个数:2产品内部芯片尺寸:140MIL峰值正向漏电流:<10ua恢复时间:35ns浪涌电流:600A芯片材质:最大正向电压:0.98V~1.90V工作......
  • AP6212 是正基科技推出一种低成本、低功耗模块其中有所有的WiFi,蓝牙和FM功能
    AP6212 是正基科技推出一种低成本、低功耗模块其中有所有的WiFi,蓝牙和FM功能。高度集成模块使网页浏览,VoIP,蓝牙耳机,FM收音机功能的可能性应用及其他应用。具有无缝漫游功能和先进安全,也可以用不同的厂商支持802.11b/g/n无线接入点的作用局域网.无线模块符合IEEE802.11B/G/N......
  • P6入门:项目初始化9-项目详情之资源Resource
    前言使用项目详细信息查看和编辑有关所选项目的详细信息,在项目创建完成后,初始化项目是一项非常重要的工作,涉及需要设置的内容包括项目名,ID,责任人,日历,预算,资金,分类码等等,在接下来的博文中,我将结合官方帮助介绍这些基本设置,希望给对P6感兴趣的人带来帮助。涉及P6 项目详情设置包括:G......
  • P6入门:项目初始化5-项目支出计划Spending Plan
    前言使用项目详细信息查看和编辑有关所选项目的详细信息,在项目创建完成后,初始化项目是一项非常重要的工作,涉及需要设置的内容包括项目名,ID,责任人,日历,预算,资金,分类码等等,在接下来的博文中,我将结合官方帮助介绍这些基本设置,希望给对P6感兴趣的人带来帮助。涉及P6 项目详情设置包括:G......
  • P6入门:项目初始化3-项目详情之记事本Notebook
    前言使用项目详细信息查看和编辑有关所选项目的详细信息,在项目创建完成后,初始化项目是一项非常重要的工作,涉及需要设置的内容包括项目名,ID,责任人,日历,预算,资金,分类码等等,在接下来的博文中,我将结合官方帮助介绍这些基本设置,希望给对P6感兴趣的人带来帮助。涉及P6 项目详情设置包括:G......
  • P6入门:项目初始化4-项目详情之预算日志及汇总Budget
    前言使用项目详细信息查看和编辑有关所选项目的详细信息,在项目创建完成后,初始化项目是一项非常重要的工作,涉及需要设置的内容包括项目名,ID,责任人,日历,预算,资金,分类码等等,在接下来的博文中,我将结合官方帮助介绍这些基本设置,希望给对P6感兴趣的人带来帮助。涉及P6 项目详情设置包括:G......
  • tp6 composer安装workerman报错
    命令:composerrequiretopthink/think-worker错误信息:Problem1-Rootcomposer.jsonrequirestopthink/think-worker^4.0->satisfiablebytopthink/think-worker[v4.0.0].-topthink/think-workerv4.0.0requirestopthink/framework^8.0->foundtopth......
  • CMO 2023 P1 解题报告
    \zihao{4}\textbf{Problem:}\large求最小的实数$\lambda$,使得对任意正整数$n$,存在正整数$x_1,x_2,\dots,x_{2023}$,满足$n=x_1x_2\dotsx_{2023}$,且对于$i\in\{1,2,\dots,2023\}$,要么$x_i$为素数,要么$x_i\len^{\lambda}$。\\\zihao{......
  • P6859 蝴蝶与花 题解
    题意:有一个长度为$n$的序列$a$,其中所有元素都为$1$或$2$,要求进行$q$次操作,每次操作为以下之一:$A$$s$:询问是否存在$a$的连续子序列满足其中元素总和为$s$,若有合法的方案,输出这个方案的左右端点位置(多种方案时输出左端点最小的方案),否则输出$......