题解codeforces round 871

题目链接 C 核心思路 这个题目其实我们可以转换为把当前串转换为完美串有多少种方案呢，也就是我们从前往后一步一步往完美串去构造我们的方案。 这个思路非常巧妙，我刚开始的思路局限于算贡献去了。 完全就脱离了正确的思路。 集合定义 $f[i][0/1]表示的是处理了前i个位置，并且当前位置是0的方案数$ ......

题意： 我们给定包含n个正整数的数组，我们可以对这个数组执行一些操作之后，可以让数组内元素的和成为我们想要的数。 我们对数组的执行操作一共分为三个步骤，第一个步骤是我们首先计算出数组的中间值mid。这里mid的定义不是中位数也不是均值，而是最大值和最小值的均值。也就是mid = (min + max ......

W1 # 怪兽训练计划1 ## 题目描述 小明有一个怪兽训练计划。 初始时，怪兽充满能量，能量值为8800。如果训练怪兽，每分钟损耗能量值400；如果让怪兽休息，每分钟增加能量值200。能量的损耗和增加都是均匀变化的。 小明打算让怪兽训练一分钟、休息一分钟、再训练一分钟、再休息一分钟……如此循环，如 ......

偶然间翻到三个月前写的这个题，发现现有的题解均未给出解法的正确性证明，只是不明不白地写了一些对理解做法毫无帮助的话。我认为解法的正确性并不显然，因此这篇题解主要给出正确性证明，补上逻辑漏洞。 解法与其他题解一样，即：建反图，然后跑拓扑排序，每次优先取出可以取出的编号最大的点，从 $n$ 到 $1$ ......

更差的阅读体验（bushi） 其实 2022 年省选前联考出过类似的套路，但当时太鸽了就没有总结。 阶梯网格计数问题是指以下一类问题： 问题：给定一个 $n$ 列阶梯状网格图，第 $i$ 列高度为 $c_i$（保证 $c_i$ 不降），每次可以向上或向右走一步，不能超出网格边界（即所有经过的点 $( ......

luogu P2568 题解 description 求 $\sum\limits_{x=1}^{n} \sum\limits_{y=1}^{n} [\gcd(x,y)\in \mathbb{P}]$ $\mathbb{P}$ 为素数集合 $n \leq 10^7$ solution $\begin ......

A - How many prime numbers #include<iostream> using namespace std; bool isprime(int x)//判断素数（朴素版方法） { if(x<2) return false; for(int i=2;i<=x/i;i++) if ......

CF1714D 题解 description 给定黑色文本 $t$ 和 $n$ 个字符串 $s_1,s_2...s_n$. 一次操作可以将 $t$ 中与 $s_i$ 相等的子串涂成红色。 一个位置多次涂色后仍是红色。$s_i$ 可以使用多次。 求将 $t$ 涂成红色的最小次数，并输出方案。 无解输出 ......

题目链接 根据期望的线性性，一次操作使得接下来要递归处理 $|G|$ 个点，将这些贡献分摊到 $|G|$ 个点上，这样我们接下来只需要计算概率。 首先考虑如果是树怎么做。操作等价于随机一个排列，顺次删掉排列中的点，并求出删掉当前点之前其所处的连通块的大小。记当前 $x$ 为点分治中心，点对 $(x, ......

题目描述 Dark 是一个无向图，图中有 $n$ 个结点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark 有 $n-1$ 条主要边，并且 Dark 的任意两个结点之间都存在一条只由主要边构成的路径。另外，Dark 还有 $m$ 条附加边。 你的任务是把 Dark 斩为不连通的两部分。一开 ......

Math.ceil，Math.round，Math.floor区别 //向上取整 System.out.println("amt1=" + Math.ceil(71.01)); //四舍五入 System.out.println("amt2=" + Math.round(71.01)); //向下取 ......

GCD Partition 这道题首先要解决一个问题，要把区间分成几块，可以证明分成两块是更优 首先我们假设把区间分成了m（>= 2)块 b1, b2, b3, ...,bm,则答案是gcd(b1, b2, b3,..., bm),则b1，b2是 gcd(b1, b2, b3,..., bm)的倍数 ......

前言 题目传送门！ 更好的阅读体验？ 题解区的代码都好丑啊，嘲讽。 思路 对于这种概率题，正常人都能反应到这是 dp。 所以：$dp_{t, i, j}$ 表示：当前是第 $t$ 回合，Tak 在 $i$ 位置，Aok 在 $j$ 位置，概率。 如果这样设状态的话，转移方程就会非常一眼（刷表）： $ ......

P8766 [蓝桥杯 2021 国 AB] 异或三角 题目描述 分析 题目中给出了三个限制 首先我们不妨设$a,b \lt c$，则 而由于我们把$c$作为了最大值，原题需要有序对$(a,b,c)$ 所以$ans \ast 3$ 1.$1 \leq a,b,c \leq n$ 2.$a \oplus ......

一、题目描述： 给你一个网格棋盘，a,b,c,d 表示了对应边长度，也就是对应格子数。 例如，当 a=b=c=d=2 时，对应如下面这样一个棋盘： 想要在这个棋盘上放 k 棋子，也就是这 k 个棋子没有两个在同一行，也没有两个在同一列，问有多少种方案。 数据保证 0 <= a,b,c,d,k <=  ......

A. Matching 题意： 　　给定一个字符串，将其中的 ‘？’ 替换成数字，不含前导0，如果字符串前导为0，输出0.。 分析： 　　每个地方有10种可能方案，在特判一下第一位就行了。 ......

Educational Codeforces Round 147 (Rated for Div. 2) 链接 Educational Codeforces Round 147 (Rated for Div. 2) A题 如果第一位数是0,直接打印0 如果第一位数是'?',有9个数可以选择,如果其他位 ......

小清新构造题。 首先 $K=1$ 的情况是 trival 的，直接格雷码即可。 对于 $K>1$，我们发现题目的约束相当于 $\operatorname{popcount}(P_i\oplus P_{(i+1)\bmod 2^N})=K$，考虑 $P_i$ 的差分序列 $D_i$，那么 $D_i$ ......

思路 L1-064 估值一亿的AI核心代码 题意有一点不太清晰的，就是原文中的'I'，无论是否是单独的，都不能变为小写。如果是单独的'I'再被转化为'you'。 这种模拟题就需要每个的分分清清楚楚的，不要都揉到一块儿，容易写错。具体还有些需要注意的在代码里注释着了。 代码 #include <ios ......

A: 思路： 首字母如果是0，直接输出0。 如果首字母是?,提供九种方案，之后每一个？提供10种方案。 void solve(){ string s; cin>>s; if(s[0]=='0'){ cout<<"0"<<endl; return ; } int ans=1; for(int i=0; ......

一、题目描述： 给你 n 个正整数，求这些数能凑成的第 k 大的数字（如果多种方式凑成同一个数，只算一次）。每个数可以选择无限次，且至少选择一个数。n<=10，k<=2e5 。 二、解题思路： 一开始想了好多错误思路。（话说这个题学校 OJ 上是不是遇到过，怎么感觉这么熟悉？） 很容易想到有用一个优 ......

#6029. 「雅礼集训 2017 Day1」市场 题目描述 数据范围1e5 题解 对于这种数据貌似可以快速缩小的题目，我们可以用势能分析来证明其某暴力或者什么做法的复杂度。 设某节点的势能函数是点内数的极差，每次除一个数极差一定会减半，总共会被除 $\log$ 次。 然而有特殊情况，如果考虑下取整 ......

原题链接：https://codeforces.com/contest/900/problem/D 求序列a的个数，满足$\sum_{i=1}^{len}=y$并且$gcd(a_1,a_2...a_{len})=x$ 其中序列的长度不限 答案对$1e9+7$取模 首先可以分析出，当$x$不整除$y$ ......

题目描述 Alice 和 Bob 在玩一个游戏。 游戏在一棵有 $n$ 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 $123456789123456789$。 有时，Alice 会选择一条从 $s$ 到 $t$ 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 $r$ ......

P5327 [ZJOI2019] 语言 题目描述 九条可怜是一个喜欢规律的女孩子。按照规律，第二题应该是一道和数据结构有关的题。 在一个遥远的国度，有 $n$ 个城市。城市之间有 $n - 1$ 条双向道路，这些道路保证了任何两个城市之间都能直接或者间接地到达。 在上古时代，这 $n$ 个城市之间处 ......

注意到对于全局最小值 $x$ ，一旦我们可以合并它，我们一定会优先合并，因此 $x$ 和与 $x$ 相邻且更靠近起点的位置构成一个决策整体，定义为广义节点。 合并一个广义节点的贡献为 $x\times sz+c$，然后会让 $x\gets x+a$。 考虑比较先后合并两个广义节点 $x,y$ 的决策 ......

「八云紫」无数次痛苦地询问，为什么我们还活着？ ……而「古明地恋」从不会回答。 恋恋闭上了觉之眼。 思路 容斥 + dp. $\gcd$ 相关，考虑 $\mu$ 反演或者 $\varphi$ 反演。 本质上都和容斥差不多，不如直接一步到位考虑容斥。 把权值拆成 $\gcd$ 和对应的方案数两部分，考 ......

打的很烂的一场 C想了很久 D的贪心没有贪好 赛后一小时补起来了 谁是nc 我是nc！ A. Matching 问有多少种情况能匹配 就计算？的个数 x10x10...... 如果第一个是？ 那么就是9x10x10... 如果第一个是0 不能有前导0 就输出0 #include<bits/stdc+ ......

比赛链接：Dashboard - 2022年中国大学生程序设计竞赛女生专场 - Codeforces A. 减肥计划（模拟） 模拟，如果队列第一个人体重是最大的了，则这个人的位置不会再变，直接输出即可。 #include <bits/stdc++.h> using namespace std; us ......

思考如何将到 $u$ 距离短的和到 $v$ 距离短的节点分别处理出来。发现对于一次询问 $(u,v)$，可以将所有节点分成三类： 除 $u$ 和 $v$ 的 LCA 的子树外的所有节点。 将 $u$ 至 $v$ 的最短路径的最中间的边删掉后组成的两棵树中的其中一棵树中的所有节点。 不属于以上两类节点 ......