首页 > 其他分享 >【题解】CF1944

【题解】CF1944

时间:2024-11-07 13:18:59浏览次数:1  
标签:le 题意 题解 CF1944 Alice Solution 答案 oplus

CF1944A

简要题意

给定完全图
删k条边使得从一号点开始的可达点最少

Solution

注意到最多需要删 n-1 条边就可以使得任意一个其他点都到达不了
又注意到只要删的边少于 n-1 就可以从一号点走出去,主要走出去就可以走到任何点
所以这题答案只有两种
如果k≤n-1 答案为n
否则答案为 1

CF1944B

简要题意

给定一个长度为 \(2n\) 的序列 \(a\),包含 \(1\) ~ \(n\) 每个数恰好两次。
对 \(a\) 的前 \(n\) 个元素和后 \(n\) 个元素分别求出长度为 \(2k\) 的子序列 \(l,r\),使得 \(l\) 与 \(r\) 中所有元素的异或和相等,即 \(l_1\oplus l_2\oplus...\oplus l_{2k}=r_1\oplus r_2\oplus...\oplus r_{2k}\)。

Solution

  • 我们称前n个数为左边,后n个数为右边
  • 注意到对于每一种数,只有两种分配方案
    第一种 左右各一个
    第二种 都在左或右
  • 不难证明左右两边两种数的个数分别相等
  • 对于第一种,左右同时取即可
    对于第二种,一种一定合法的构造方案是两边都同时取两个,由于2k一定是偶数,所以这种构造一定合法。
  • 到这就很清晰了,无脑按照第一/第二种方法构造就可以了,任意一种数不够用了换另一种即可

CF1944C

简要题意

  • Alice 和 Bob 在大小为 \(n\) 的数组 \(a\) 上玩一个游戏:Alice 有一个空数组 \(c\) 开始。两位玩家轮流进行游戏,Alice 先开始。
  • 在 Alice 的回合中,她从 \(a\) 中选择一个元素,将该元素添加到 \(c\) 中,然后从 \(a\) 中删除该元素。
    在 Bob 的回合中,他从 \(a\) 中选择一个元素,然后从 \(a\) 中删除该元素。
  • 当数组 \(a\) 为空时游戏结束,游戏的得分定义为 \(c\) 的 MEX。
  • Alice 希望最大化得分,而 Bob 希望最小化得分。
  • 找出如果两位玩家都采取最佳策略时的游戏最终得分。

Solution

  • 显然数的顺序不重要,数的个数重要,直接存桶
  • 假定最终答案是 \(x\),那么 \(0\) 到 \(x-1\) 之间的所有数都需要取到
  • 显然这 \(x\) 个数都至少得有一个
  • 如果一个数有两个,那么 A 可以在 B 拿走一个数之后立刻拿走另一个
    也就是说,至少一个数至少有两个,那么 A 一定可以拿到这个数
  • 这 \(x\) 个数中,可以有一个数只有一个,它将被 A 一开始就拿走
  • 实现:从 0 开始遍历桶,直到第一个位置计数为 0 或者 第二个位置计数为 1,这个位置的下标即为答案 (这是第一个取不到的数)

CF1944D

简要题意

  • 定义一个字符串是 \(k\)-good 的,当且仅当该字符串存在长为 \(k\) 的非回文子串。
  • 对于字符串 \(t\),定义 \(f(t)\) 为满足 \(t\) 是 \(k\)-good 的正整数 \(k\) 的总和。
  • 对于给定的一个长为 \(n\) 的字符串 \(s\),你需要回答 \(q\) 个询问,每次询问给出两个正整数 \(l,r\),求 \(f(s_ls_{l+1}\dots s_r)\) 的值。每个测试点 \(t\) 组测试用例。
  • \(1\le t\le 2\cdot 10^4;1\le n,q,\sum n,\sum q\le 2\cdot 10^5;1\le l<r\le n\)

Solution

  • 注意到不是 \(k-g\) 的条件很苛刻,考虑什么时候不是 \(k-g\)
  • \(k=1\) : 永远不kg
    \(k=|S|\):不 kg 当且仅当 S 回文
    \(k=奇数\) : 如果不 kg,说明分别从第一,第二个位置开始截取长度为 k 的字串都是回文的,容易推导出这一段一定是形如 ABABA 交替,进而推广到整个串都是 ABABA 交替
    \(k=偶数\) : 如果不 kg,类似的,可以推广到整个串都是 AAAAAAAA
  • 综上所述,我们只需要判断一个串:
  1. 是否回文
  2. 是否形如 ABABAB
  3. 是否形如 AAAAA
  • 判后两个是容易的,判回文马拉车即可

CF1944E

简要题意

  • 给定树 \(n\leq 5e3\)
  • 初始时所有节点都是白色
  • 定义操作:选择一个节点,把距离这个节点距离为 \(d\) 的点都变成黑色 \((0\leq d \leq n-1)\)
  • 问最少多少次操作把所有点都染成黑的,并输出方案

Solution

  • 容易想到直径
  • 考虑直径这条链,一次最多染链上的两个点
  • 得到答案下界 : \(ceil(n/2)\)
  • 注意到染整棵树和染直径所需次数相同,于是只考虑直径
  • 得到答案上界:\(n/2+1\) (如果直径上点数是偶数可以取到,如 6)
  • 注意到:如果直径上有奇数个点,答案上界等于答案下届,没什么优化空间,直接选定直径中点一层一层染即可
  • 考虑长度为 4 的链用于启发:发现长度为 4 的链实际上只需要两次操作
  • 如果链上点数是 4 的倍数,那么一定可以取到答案下届(反复按照长度为 4 的链构造即可)
  • 现在只剩一种情况:点数是 4 的倍数+2,发现无论如何都不能取到下届(考虑长度为 6 的链)
    答案为 \(n/2+1\) 构造方法同上,只需单独染最后两个多出来的点即可

CF1944F

标签:le,题意,题解,CF1944,Alice,Solution,答案,oplus
From: https://www.cnblogs.com/yeyou26/p/18531955

相关文章

  • 题解:P11248 [GESP202409 七级] 矩阵移动
    题目传送门题目大意给出一个nnn行mmm列的只包含0、1、?的矩......
  • 【记录】Cordial Sync具身智能协作源码复现及问题解决
    论文简要总结智能体需要合作将家具移动到客厅的指定位置。这个任务与现有的任务不同,它要求智能体在每个时间步都必须进行协调。模型部分1.SYNC-policies(SynchronizeYourActionsCoherently)为了解决智能体在每个时间步都需要协调的问题,研究者提出了SYNC-policies。这......
  • AtCoder Beginner Contest 284题解
    AtCoderBeginnerContest284A没有什么难点,反着输出一遍就可以了。#include<bits/stdc++.h>usingnamespacestd;stringa[2000];intmain(){ intn; cin>>n; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=n;i;i--)cout<<a[i]<<'\n';......
  • 题解:HDU5628 Clarke and math
    数学题可爱捏~HintAnalysis注意到形式很好看,猜测是某种神奇迭代。考虑特殊情况\(k=1\),于是有:\(g(i)=\sum_{i_1\midi}f(i_1)=(f*1)(i)\)$即\(g=f*1\)。于是猜测\(g=f*1^k\),这里的幂运算表示多次Dirichlet卷积。简单证明一下,采用数学归纳法:基本情况\(k=1\),已经证过,......
  • CF 1438 题解
    CF1438题解ASpecificTastesofAndre考虑一种非常简单的构造:\(a_i=1\).不难发现满足条件.BValeriiAgainstEveryone结论:符合条件当且仅当有两个一样的元素.证明:充分性显然,下证必要性.若不存在两个一样的元素,则由于无法进位,故没有办法得到两个区间和在相......
  • 【考试题解】NOIP2024加赛2
    目录A.新的阶乘(factorial)题目内容部分分?pts正解思路代码B.博弈树(tree)题目内容部分分80pts正解思路代码C.划分(divide)题目内容部分分10pts14pts正解思路代码D.灯笼(lantern)A.新的阶乘(factorial)题目内容定义运算\(f(x)=x^1\times(x-1)^2\times(x-2)^3\dots2^{x-1......
  • CF2001 题解
    A给定循环数组,每次操作时,设当前大小为m。选择$i\in[0,m)$,若满足$a_i\lea_{i+1\bmodm}$,则可删除$a_i,a_{i+1\bmodm}$中的任意一个。求最小的操作次数,使得数组中所有元素都相等。$n\le100$操作非常强,除了两个相邻位置相等的情况,可以删除任意元素。然而所有位置都......
  • 暂存的题解
    P4011孤岛营救问题感觉其实我能想出来,但是对难题产生了恐惧,直接看题解了,确实简单,很抱歉浪费了一道题。数据范围很小,搜索bfs,钥匙直接状态压缩,找到答案立即返回,否则就无解。我们要彻底的分析问题,为什么我想不到,以后我要怎么总结,首先看到题之后要先看数据范围,看到数据范围非常小......
  • [USACO22JAN] Minimizing Haybales P 题解
    [USACO22JAN]MinimizingHaybalesP随机化?五分。显然对于任意\(a_i,a_j\),若\(|a_i-a_j|>K\),则这两堆草的先后顺序永远不会改变。所以易得暴力:对于所有这样的\(i,j\),不妨设\(i<j\),则连一条\(i\toj\)的边,答案就是这个图字典序最小的拓扑排序,优先队列即可。voidtoposort(......
  • [USACO21DEC] Tickets P 题解
    [USACO21DEC]TicketsP首先我们思考暴力的\(O(n^2)\)怎么做。显然比起每次以\(i\)为起点跑\(n\)遍最短路,建反图后分别以\(1\)和\(n\)为起点跑两遍最短路是更加经济的方式。然后你可能会以为\(\text{dis}(1,i)+\text{dis}(n,i)\)就是答案了,之后你就会发现连样例都过......