题解1359a cf

题意 令 $p$ 是一个 $1\dots n$ 的排列，记 $f(p)=|{p_i-p_{(i\bmod n)+1}|1\le i\le n}|$，即 $p_i-p_{(i\bmod n)+1}$ 中不同数的个数。 给定 $n,m,s,t$，设 $w=\min{f(p)|p\in \operator ......

设 $f(u, d)$ 表示以 $u$ 为中心距离不超过 $d$ 的点集 考虑对每个点分别统计答案，令当前处理的点 $u$ 是当前树根 令 $mx(u)$ 为 $u$ 所有子树中，与 $u$ 最远距离最 大值， 令 $se(u)$ 为 $u$ 所有子树中，与 $u$ 最远距离的次大值， 我们只在 $ ......

需要构造一个符合如下条件的字符串： 长度为 n，并且只包含字符 1∼m (n≤1e15,m≤52) 满足 K 个要求，第 i 个要求为 xi 后面不能是 yi 现在问你，有多少种字符串符合条件。 F[ i ][ j] += F[i -1] [lk ]* a[k][j] 用矩阵快速幂优化 即 F[1] ......

脑筋急转弯 https://leetcode.cn/problems/minimum-impossible-or/ https://leetcode.cn/problems/minimum-score-by-changing-two-elements/ 1200 找规律？ https://codef ......

传送门 「Gym102759L」Steel Slicing 2 题目大意 给定一个只有水平边和竖直边的铁片，每次可以水平或竖直方向把一个铁片分成两个部分。注意只能是两个部分。求最少切多少刀才能使得每一个部分都是长方形。 铁片形状如下图，以输入 $h,l$ 的方式给出。 思路 手玩几组数据之后，我们可 ......

CF1806F GCD Master Div. 2 的 2900，还是非常有难度的，看了题解才有思路。 这题是一个结论题，我们一步步来观察。不难发现每次操作相当于合并两个已经操作的集合，那么最终的问题就是把序列划分成了 $(n-k)$ 个集合。 结论一：考察最小值所在的集合 $S_0$，假设从小到大 ......

没动脑子就 gf 一路写下来了......实际上就是把插板法的 gf 写了一下/zk 首先考虑一下一个 $X$ 合法是什么情况，那就是总和是 $2n-2$ 并且保证 $0<X_i<n$。 证明就考虑贪心构造一下，每个 $1$ 挂在一个 $\geq 2$ 的上面，不断挂使得最后只剩下两个 $1$ 和一 ......

今天题比较简单的一次。T1 数组爆了是我小丑。 为啥离线测的时候 T2 t 了啊。我题库上边跑 1300ms 也挺健康的吧。 居然 nealchen 老师的课件。 EmoCosine！这曲曲绘输血袋插耳机上） 图案 原题：CF526D。 发现 $k+1$ 个 $B$ 和 $k$ 个 $A$ 交错排列 ......

简述题意：给你一棵树，每个点有一个被选为起点的概率和一个被选为终点的概率，从起点开始随机遍历子树，问到达终点的期望步数。 直接计算答案很难，考虑对一对 $(S,T)$ 来说，以 $S$ 为根，那么有： 对 $T$ 的子树里的点：显然不会被遍历到，贡献为 $0$。 对 $S\to T$ 路径上的点：显 ......

比赛地址 A.Showstopper 题意：给两个数组a和b，可以进行任意次操作：交换a[i]和b[i]，问能否使得a[n]和b[n]分别是数组a和b的最大值 Solution 假设a[n]和b[n]固定，对于每一个i，a[i]和b[i]只能选其中之一，并且必须选择比a[n]或者b[n]小的，如果只 ......

掉大分补提 D 点击查看代码 #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> PLL; #define IOS cin.tie(nullptr)->sync_with_s ......

为什么我只会一堆大众题啊！！ 还没更完的：假装更完了.jpg Day1 T1 显然取链上代价前最小的若干个付银币，于是主席树上二分即可。 Day1 T2 首先想一个 dp 做法出来。 考虑做一个线头 dp 类似的东西。从左到右扫，状态中记录现在还没有结束的线头个数。 仔细思考一下，要记录 Fake ......

试题链接：https://pintia.cn/problem-sets/1639265448375771136/overview ......

[ABC294] vp 题解 A B C D 略 E - 2xN Grid 双指针模拟 考虑 $L$ 太大了，无法直接把压缩后的表示法展开，那么我们直接一块一块地考虑即可。 用两个指针 $i, j$ 表示当前走到了哪一格（解压后），分类讨论。 $i > j$，将第二行往后拓展一块，判断第一行当前块 ......

状压 dp，2 hd 4 me/ng。 题意 开始你有一个全 $0$ 矩阵，你可以随意执行如下操作： 选择任意一行，将其从最左端开始的连续一段染成 $1$。 选择任意一列，将其从最上端开始的连续一段染成 $1$。 如果一个矩阵可以由此得到，那么这个矩阵被称为好的。 现在你有一个 01? 矩阵 $a$ ......

我是菜鸡！我是菜鸡！我是菜鸡！ 虽说挺不想承认的，但是必须得承认了，我是菜鸡，真的，一道题写了两天了，还是wa的结果！恨！！！ 看看那道题目· 原题传送门 洛谷镜像 题目描述 You are playing some computer game. One of its levels puts you ......

给出nn个整数a1,a2,...,an，现在需要对其进行分组，使其满足以下条件： 每个数都必须恰好分入一组中 每一组中必须至少包含K个数 在每一组中，整数的权值之差的绝对值<=D。 请判断是否存在满足条件的分组方案，若有请输出"YES",否则输出"NO"。 直接的贪心是错误的,但要魔改一下，双指针+ ......

比赛地址 A.Probably English 1 void solve() 2 { 3 int n;cin>>n; 4 set<string>st; 5 st.insert("and"); 6 st.insert("not"); 7 st.insert("that"); 8 st.insert(" ......

在随机跳一点 CF 的紫题做。为什么随机一跳就是 CNR。 感觉这能 *2900 有点震撼。不过我不是也没独立做出来嘛。 尝试只为行或列构造，很容易想到直接逐一交换，但是这样会破坏另一维的结构。 怎么做呢，怎么做呢。你忽然注意到这是个方阵诶，可以试着递归弄掉一行一列。 那每次只能放第一行与第一列并起 ......

感觉有的歌确实不适合中午刚起来脑袋晕晕乎乎的就去听。太舒缓或者太激烈都不太好。太舒缓容易让人想睡回去，比如我今天中午打了半个小时哈欠。太激烈的……想象一下中午如果放 VIS::CRACKED 会怎样。反正要我我会晕一下午。那我得好好思考一下什么东西能卡在这两个界之间。那我寻思着不如来点 Eurobe ......

一、题目描述： 给你一个由数字 0~9 组成的字符串，长度为 N ( 1<=N<=500000 ) 。求出满足 1<=l<=r<=N 且在 l~r 区间内所有数字都出现了偶数次的整数对 l,r 有多少对。 二、做题思路： Atcoder 不会卡你的时间，所以这题应该是 O(N) 的时间复杂度。用二进 ......

Solution 容易发现答案就是 $[b+1,a]$ 所有数的质因子个数和。 考虑到多次询问，首先预处理出前缀质因子个数和，询问时直接输出 $sum_b-sum_a$ 即可。 如何快速对一个数 $x$ 分解质因子，首先我们可以进行一遍线性筛，因为每个合数只会被它最小质因子筛，于是可以处理出 $f_ ......

题意简述 给定一个长度不超过$5\times 10^5$的，仅有数字构成的字符串，问存在多少段子串，使得子串内字符重新排序后，前半段与后半段相同？ 做法分析 重组后前后两部分相同，其实也就意味着，这一子串内所有数字出现的次数都为偶数次。 考虑暴力竹筏，枚举左端点和右端点，统计子串内每个数字出现次数， ......

DAY3共2题： 旅游 tokitsukaze and Soldier 🎈 作者：Eriktse 🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀 🎈 原文链接（阅读原文获得 ......

上个世纪做过这题，然后今天比赛（abc295）出了道弱化没做出来，被 pty 喷了一遍后爬来写个题解/kk 首先这种期望/总和题都有个套路，就是通过另外一种角度来计算每个元素的贡献。对于此题，我们有： $$ ans=\sum_{i=1}^mi\cdot c(=i)=\sum_{i=1}^mc(\ge ......

继续。仍然按照谷题号。 [省选联考 2020 A/B 卷] 冰火战士 简单题。 离散化一下，温度显然取到某个战士的温度。对于一个温度我们要知道温度小于等于它的冰系战士的能量和和大于等于它的火系战士的能量和。容易发现冰系战士能量随温度升高单调不降，火系单调不升。那么一定有一个交点。两个树状数组分别维护 ......

题目大意 给定一个由数字组成字符串$S$,求$S$中每个数字均出现偶数次的子串个数 思路 考虑到每个数字的状态非奇即偶，可以用01串来表示状态。 即：二进制状态压缩，用0来表示这位数字出现次数为偶数次，用1来表示这位数字出现次数为奇数次。然后考虑如何转移即可。 我们从左到右扫描字符串，用一个变量$t ......

A-Probably English 共有$n$个单词，如果出现过and, not, that, the,you其中一个单词至少一次，输出$Yes$，否则，输出$No$。(输入的单词均为小写) 按题意模拟即可： #include<iostream> using namespace std; #def ......

ARC125D 题意 给定长度为 $n$ 的序列中，求其中只出现过一次的非空子序列的个数，对 $998244353$ 取模。 题解 不难发现，一个只出现过一次的子序列合法的充分必要条件是： 头部元素 $a_i$ 是原序列中下标最小的（即最左边的）值为 $a_i$ 的元素 由对称性，该子序列最后一个元 ......

一个序列A， 每次可以 相邻的数相加为一个数字，求最少次数使得序列非降 f[i ]= min{ f [ j ] + i-j-1 } ，s[i]-s[j] >= s[j] -s[mn[j-1] ] 维护下前缀最小值mn[ i] #include <iostream> #include <queue> ......