首页 > 其他分享 >2024.7.28 test

2024.7.28 test

时间:2024-07-28 21:31:37浏览次数:16  
标签:10 le 2024.7 28 直径 test 操作 2n 我们

A

你有长度为 \(2n\) 的排列,每次操作是:把 \(a_1,a_2,...,a_{2n}\) 变成 \(a_1,a_{n+1},a_2,a_{n+2},...,a_{n},a_{2n}\)。
问多少次操作后序列回到最初的状态。\(n\le 10^{14}\)。

我们先把 \(1\) 开始标号改成 \(0\) 开始。那么操作是这样的:
若 \(x<n\),那么移动到 \(2x\),若 \(x\ge n\),那么移动到 \(2(x-n)+1=2x-(2n-1)\).
我们的操作需要分讨是及其麻烦的,所以我们尝试把操作归为同类。
发现取模 \(2n-1\) 即可,那么现在只需要求 \(2^{t}=1\pmod {2n-1}\) 的最小正整数解。
我们枚举 \(\varphi(2n-1)\) 的约数即可。

B

对于序列 \(A,B\),你可以对序列 \(A\) 进行若干次操作,每次你可以选定一个 \(A_u\),使 \(A_u\gets \otimes_{i=1}^n A_i\)。
问最少多少次操作使得 \(A=B\)。\(n\le 10^5\)。

我们发现每次操作就是交换 \(A_u\) 和异或和。
我们把置换环建出来,如果有相同的权值就合并两个环。每个环的代价是大小 \(+1\)。
我们用并查集维护这个过程。
还要注意的是如果一开始异或和存在于 \(B\) 中,那么答案 \(-1\)。

C

在一棵树上随机黑白染色,问白点的最长距离和黑点的最长距离的最大值的期望。\(n\le 10^5\)。

我们先考虑 \(n\le 10^3\),我们拆贡献枚举这个最大值是多少,设最大值为 \(s\)。
那么距离 \(\le s\) 的点对是可以随便填黑白的,但是 \(>s\) 的点对必须满足颜色不同,这是个二分图染色。
现在考虑正解,由于是最长的距离,我们先把直径拿出来,如果两端颜色相同那么答案就是直径。
我们默认直径两端颜色不同。那么新的最长的距离是多少呢?
根据树的直径的性质,新的最长的距离一定有一个端点是直径的端点。
于是求出 \(f_k\) 表示答案 \(\le k\) 的方案数,那么距离两个端点都 \(\le k\) 的点可以随便填。
答案 \(=k\) 的方案数差分一下即可。

D

在树上你要从 \(1\) 走到 \(n\),移动的方式是拿出一个点 \(u\),并向 \(u\) 的方向移动一步。
问最少经过的点集大小最小是多少。\(n\le 1e5\)。

与绝对众数有关。

标签:10,le,2024.7,28,直径,test,操作,2n,我们
From: https://www.cnblogs.com/Simon-Gao/p/18328891

相关文章

  • Contest5408 - 数论函数
    Agcd\[\begin{aligned}&\sum\limits_{i=1}^n\sum\limits_{j=1}^n[\gcd(i,j)\inP]\\=&\sum\limits_{d=1}^n[d\inP]\sum\limits_{i=1}^n\sum\limits_{j=1}^n[\gcd(i,j)=d]\\=&\sum\limits_{d=1}^n[d\in......
  • 2024/07/28 每日一题
    LeetCode699掉落的方块方法1:暴力classSolution:deffallingSquares(self,positions:List[List[int]])->List[int]:n=len(positions);ans=[0]*n#记录每个方块落下后的高度fori,(left0,widen0)inenumerate(positions):......
  • 大创项目个人周报(2024.7.22—2024.7.28)
    本周个人情况汇报我本周主要学习了安卓开发的内容,根据《第一行代码Android》开展了学习。一、分析自己的第一个Android程序通过看书,我对项目的各个文件的功能有了大致了解,除app目录外,大多数文件和目录是自动生成的,app目录是今后开发工作主要涉及的部分。app的结构如下。......
  • abtest相关知识
    步骤:1.确认改动点(只能是单一因素)2.设计核心指标(点击率/转化率,一般分为直接值和比率值)3.计算实验所需最少样本流量(防止影响过大)基于大数定律(次数多了,频率就等于概率)和中心极限定律(抽样的均值和方差服从整体),前提是样本量足够大,这个足够大是多少,公式如下:(组间指的是预期组......
  • Adobe Illustrator 2024 v28.6 (macOS, Windows) - 矢量绘图
    AdobeIllustrator2024v28.6(macOS,Windows)-矢量绘图Acrobat、AfterEffects、Animate、Audition、Bridge、CharacterAnimator、Dimension、Dreamweaver、Illustrator、InCopy、InDesign、LightroomClassic、MediaEncoder、Photoshop、PremierePro、AdobeXD什么是......
  • 7月28日 竞彩足球!哈马比vs米亚尔比 维京vs莫尔德
    昨日复盘今日扫盘哈马比队,作为瑞典超级联赛的传统强队,凭借其在斯德哥尔摩索德尔体育场的主场优势,一直展现出强大的竞争力。本赛季,球队以稳定的表现,近6场联赛中取得了4胜1平1负的佳绩,防守端表现尤为出色,主场进攻力同样强劲。不过,在与米亚尔比队的交锋中,哈马比队本赛季首次对......
  • AtCoder Beginner Contest 363 题解 A-D(待补充)
    A-PilingUp1.1思路其实就是向上取百位的整,需要增加多少,123则为200-123=177;1.2代码voidsolve(){intn;cin>>n;intt=n/100;cout<<(t+1)*100-n;}B-JapaneseCursedDoll 2.1思路就是判断最少需要多少天,会有大于等于P个人......
  • AtCoder Beginner Contest 363
    比赛地址添加链接描述A-PilingUp算法:模拟题目大意在AtCoder竞赛平台中,用户的等级通过正整数分数表示,并根据分数显示相应数量的^符号。分数与^符号显示的规则如下:当分数在1到99(包括99)之间时,显示一个^。当分数在100到199(包括199)之间时,显示两个^。......
  • 在课堂上使用 JWT 令牌编写 pytest
    我有一个类TestSecured,其中有一些方法可以获取受保护的端点,因此您需要一个jwt来发出请求。我正在尝试优化我的测试类,这样我就不需要登录过程3次,而只需要1次,并在我的3个测试方法中使用相同的令牌。@pytest.mark.usefixtures("client","auth","setup_user_and......
  • 【嵌入式DIY实例-ESP8266篇】- LCD ST7789显示BME280传感器数据
    LCDST7789显示BME280传感器数据文章目录LCDST7789显示BME280传感器数据1、硬件准备2、代码实现本文将介绍如何使用ESP8266NodeMCU开发板(ESP12-E模块)和BME280气压、温度和湿度传感器构建一个简单的气象站。NodeMCU微控制器(ESP8266EX)从BME280......