题解sorting 11714 blind
【题解】CF1852C Ina of the Mountain
我们先从题目的一部分入手。 如果说,我们没有当一个数为 $0$ 时,让这个数变成 $k$ 的性质,我们如何求答案呢? 很简单,在图上就是: 绿色线段的长度加起来即为答案(本图中是 $6$) 我们考虑很显然地,将一个数从 $0$ 变为 $k$ 即为将一个数一开始加上 $k$ 我们如果要让第 $i$ 列 ......
2023短学期0905场题解
1.挖地雷 Description 在一个地图上有N个地窖(N 点击查看代码 ``` #include using namespace std; const int N = 20; int connect[N][N], mark[N], a[N], n;//mark用于标记该地窖是被访问过 int ......
AT_abc310_g 题解
一、题目描述: 有 $n$ 个人,第 $i$ 个人一开始有 $a_i$ 个球。每个人都有一个自己的传球目标。 有一个正整数 $k$,从 $1\sim k$ 中随机选择一个数作为游戏的进行轮数。 在游戏的每一轮,所有人同时都把自己手上的球全部传给自己的传球目标。 求游戏结束之后,每个人手上的期望球的数 ......
ES中reverse_nested+sum+bucket_sort
`{ "aggregations": { "agg_entity_a": { "aggregations": { "filter_product_agg": { "aggregations": { "agg_entity_b": { "aggregations": { "reverse_nested ......
【题解】CF1852B Imbalanced Arrays
我们假设当前出长度为 $len$,那么我们在序列中一定有一个 $len/0$,因为一定有一个绝对值最大的数,如果这个数是正数在原序列中就是 $len$,是负数在原序列中即为 $0$。 由上文,我们可以得到,一定不能有 $len$ 和 $0$ 同时出现的情况,也一定不能有 $len$ 和 $now$ ......
【题解】ABC318
## [AtCoder-ABC318A Full Moon](https://atcoder.jp/contests/abc318/tasks/abc318_a) 暴力枚举判断。 提交记录:[Submission - AtCoder](https://atcoder.jp/contests/abc3 ......
【题解】Educational Codeforces Round 145(CF1809)
## A.Garland ### 题目描述: 有 $4$ 只灯泡,第 $i$ 只灯泡的颜色为 $s_i$ 。 一开始,所有灯泡都是关着的,你需要把它们都打开。你可以进行数次操作,每次操作改变一个灯泡的状态,即打开原本关着的灯泡或关上原本亮着的灯泡。第一次操作可选择任何灯泡,此后每一次被操作的灯泡的颜 ......
Sort a N sorted array
Given an array of n elements, where each element is at most k away from its target position, you need to sort the array optimally. Example 1: Input: n ......
题解 [BJOI2014] 大融合
[题目链接](https://www.luogu.com.cn/problem/P4219) 可以发现,一条边 $(x,y)$ 的答案,就是 $x$ 不经过该边可达的点的数量(记作 $cnt_x$) $\times$ $y$ 不经过该边可达的点的数量(记作 $cnt_y$)。 尝试将这个式子转化,若 ......
python内置函数 - map, reduce, filter, sort
1, map(fn, 可迭代对象) 参数fn为一个参数的函数 lambda方式 my_list = [2, 3, 4, 5] result = map(lambda x: x * x, my_list) # 返回元素平方值的迭代器 print(type(result)) # <class 'map' ......
[ABC318E] Sandwiches 题解
# [ABC318E] Sandwiches 题解 ## 题意简述 给定包含 $n$ 个整数的序列 $a$,其中任意元素的值 $a_i \in [1,n]$,统计包含三个元素的满足以下条件有序三元组数量:满足下标严格递增;满足第一个和最后一个元素相等,而中间的元素和两端的元素不相等。 记录三元组 $ ......
CF1854 题解
# CF1854 题解 ### A 首先考虑只有非负的情况,次数完全可以接受 $19$ 次,所以直接用 $19$ 次做一次前缀和就可以保证单调不降了。 现在有了负数,考虑将负数变成正数,选出正数当中的最大值,然后用 $a_i + a_i \to a_i$ 这样自增的方式让它的绝对值大于负数最大值,因 ......
CF1852 题解
# CF1852 题解 ## A Ntarsis' Set ### 题意 有一个集合,初始状态里面有数字 $1$、$2$、$3$、$4$、$5$、......、$10^{1000}$。 现在给你一个长度为 $n$ 数组 $a (1\leq a_i \leq 10^9 )$,要进行 $k$ 次操作,每 ......
$9.5$ 短学期题解
## $a$ 一个简单的坐标转换,原来的 $a[i][j]$ 会变为 $b[j][n-i+1]$ ```cpp int b[N][N]; void solve(){ int n=read(),m=read(); for(int i=1;i0?"YES":"NO"); //puts(ans>0?"Ye ......
【题解】CF1852A Ntarsis' Set
考虑我们先手模一下样例: $$ \begin{cases} 1&3&5&6&7\\ 2&8&10&11&12\\ 4&13&15&16&17 \end{cases} $$ ???一脸疑惑,有什么规律吗?真有,但是很难看出来捏。 正难则反,我们考虑如果知道操作一次后一个数的位置,我们可以很容易推出,操 ......
【题解】NOIP2022
怎么看 T3 也不是那么难,可是为啥赛时就是被卡死了[难过] 不补 $B$ 题了,ad-hoc。 ## A.种花 ### 题目描述: 小 C 决定在他的花园里种出 $\texttt{CCF}$ 字样的图案,因此他想知道 $\texttt C$ 和 $\texttt F$ 两个字母各自有多少种种花的方 ......
AT318 A-G 题解
### A 枚举 $1\sim n$ 的每个数,判断是否有 $i-M\equiv 0\pmod P$ 即可。 [赛时代码](https://atcoder.jp/contests/abc318/submissions/45128240) ### B 暴力覆盖即可,注意 $x,y$ 均是左开右闭。 [ ......
湖北省选模拟 2023 部分题解
质量不错。 为什么湖北会有这么 hard 的省选啊 /fn。 ### [D1T1](https://www.luogu.com.cn/problem/P9542) $\color{Gold}\bigstar$ 第一题就不会是我没想到的。 考虑一下简单情况,一条链咋做,每次操作相当于把一个空隙的大小减 ......
XOR and Favorite Number题解
## XOR and Favorite Number题解 ### 思路引导 这一道题主要是为了说明莫队算法和分块之间的联系。 先主要讲讲莫队的用处吧。 它是个离线算法,维护两个指针l,r。 移动l和r的时候顺便进行更改,维护好l-r区间内的某个值。 对于询问区间的排序,遵循l所在的分块相同,其次是r ......
[CF1830E] Bully Sort
## 题目描述 On a permutation $ p $ of length $ n $ , we define a bully swap as follows: - Let $ i $ be the index of the largest element $ p_i $ such that ......
弹飞绵羊题解
## 弹飞绵羊题解: ### 思路: 先注意一下装置编号是0到n-1,坑了我半天 先思考为什么可以用分块做? 总所周知,要是我不存在修改操作的话,我直接o(1)就结束了。 具体做法的话,就是从后往前扫一遍,cnt[u]=cnt[to]+1。然后直接查询就好了,特别地,直接跳出去的cnt[i]=1。 ......
CF1894 H Asterism Stream题解
### 题意 给定一个 $n$ , 有一个初始为 $1$ 的整数 $x$ , 每次有相同概率进行以下两个操作的其中一种: - 使 $x$ 加 $1$ - 使 $x$ 乘 $2$ 问期望多少步操作可以使 $x$ 大于 $n$ , 输出期望步数模 $998244353$ 的值。 其中 $1 \leq n ......
B0831 模拟赛题解
[**原题链接**](https://local.cwoi.com.cn:8443/contest/C0300/problem/A) ## 前言 先说点闲话。 本来是 8.15~8.19 放假的,由于我是借读,分校这边 23 号军训,之前军训的时候我又去复习中考了,所以得参加。我家住在外地,考虑到折 ......
CF1861C Sorting By Multiplication
## 思路 机翻害人,我还以为是 $1$ 和 $0$ 是对原序列排序,害得我比赛的时候都没对,恼。 首先,对于新加入的数字,我们可以先不确定是否有序,而是等到后续的 $1$ 或 $0$ 出现,再确定。 用 $num$ 表示目前有多少数字,用 $so$ 表示确定有序的数字中最后一位的位置,$nso$ ......
CF1861D Sorting By Multiplication
## 思路 先考虑不能把数变为负数的情况。 显然,当 $a_i\ge a_{i+1}$ 时,需要对 $[i+1,n]$ 的数都要乘以一个很大的数。 所以答案是 $a_i\ge a_{i+1}$ 的个数。 但是可以变为负数,考虑把一部分变为递减的,再变成负数,另一部分正常计算。 因为负数一定小于正数, ......
洛谷P3808 【模板】AC 自动机(简单版)题解 AC自动机模板题
题目链接:[https://www.luogu.com.cn/problem/P3808](https://www.luogu.com.cn/problem/P3808) AC自动机模板题。 示例程序: ```c++ #include using namespace std; const int m ......
【题解】P3648 [APIO2014] 序列分割
# 【题解】P3648 [APIO2014] 序列分割 对于这道题,我们很容易想出一个暴力 `DP`: 设 $f_{i,j,k}$ 表示将区间 $[i,j]$ 切割 $k$ 次的最大得分,$s_i$ 表示 $a_i$ 的前缀和。 我们可以得到一个式子: $$ f_{i,j,k} = \max_{i\ ......
CF786c分块题解
## CF786c分块题解 ### 思路: 首先思考一下如果直接硬着头皮做会怎么样? 对于每一个k,我都要遍历一遍数组贪心求解ans,导致n方时间复杂度 要发现一下性质: 1. 答案最多为ceil(n/k)。 2. 随着k的增加,答案单调不增。 3. 随着k的增加,答案越不容易改变(连续相同的答案越 ......
【牛客周赛 Round 10】A-D题解
### A https://ac.nowcoder.com/acm/contest/64272/A **题意** 游游定义一个数组为“稳定的”,当且仅当数组相邻的两个元素之差的绝对值不超过1。例如[2,3,2,2,1]是稳定的,而[1,3,2]则不是稳定的。 游游拿到了一个数组,她想求出该数组的最长 ......