Namomo Spring Camp 2022 Div1 每日一题记录 (Week 6)
Namomo Spring Camp 2022 Div1 每日一题记录 (2022.04.02-2022.04.08)
并行排序
1 s, 512 MB
题目描述
给定一个 \(n\) , 以及长度为 \(n\) 的排列 \(a\) , 如果两个点 $i \(,\) j$ 满足 \(i < j\) 并且 \(a[i] > a[j]\) , 那么这两个点之间存在一条边，现在请你对这 \(n\) 个点染色，要求任意一条边的两点颜色不同，且使用的颜色数量最少，输出最少使用的颜色数量
输入格式
第一行一行数字 \(T\) , 代表 \(T\) 组数据
每组数据第一行一个数字 \(n\)
接下来一行 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)
输出格式
一个数，表示最少需要的颜色数量
样例 1 输入
1 | 2 |
样例 1 输出
1 | 2 |
数据规模
所有数据保证 \(1\leq \sum n \leq 10^6\)
解题思路
复杂度
代码参考
Show code
丹钓战
1 s, 512 MB
题目描述
有 \(n\) 个二元组 \((a_i, b_i)\), 编号为 \(1\) 到 \(n\)
有一个初始为空的栈 \(S\), 向其中加入元素 \((a_i, b_i)\) 时，先不断弹出栈顶元素直至栈空或栈顶元素 \((a_j , b_j)\) 满足 \(a_i \neq a_j\) 且 \(b_i < b_j\), 然后再将其加入栈中
如果一个二元组入栈后栈内只有这一个元素，则称该二元组是 “成功的”
有 \(q\) 个询问 \([l_i, r_i]\), 表示若将编号在 \([l_i, r_i]\) 中的二元组按编号从小到大依次入栈，会有多少个二元组是 “成功的”
询问之间相互独立
输入格式
第一行两个正整数 \(n,q\)
第二行 \(n\) 个正整数表示 \(a_i\)
第三行 \(n\) 个正整数表示 \(b_i\)
接下来 \(q\) 行，每行两个正整数 \(l_i, r_i\) , 表示一组询问
输出格式
\(q\) 行，每行一个自然数表示一组询问的答案
样例输入
1 | 10 4 |
样例输出
1 | 3 |
样例解释
以第一次询问 \([1, 4]\) 为例
一开始栈为 \(\{\}\)
加入 \(1\) 号二元组后栈为 \(\{(3, 10)\}\), 栈中只有一个元素，该二元组是 “成功的”
加入 \(2\) 号二元组 \((1, 10)\) 时，栈顶的 \((3, 10)\) 的 \(b\) 值不大于 \(2\) 号二元组的，因此弹栈。此时栈空，\(2\) 号二元组入栈，栈为 \(\{(1, 10)\}\), 该二元组是 “成功的”
加入 \(3\) 号二元组 \((3, 2)\), 此时栈顶元素与之 \(a\) 值不同，\(b\) 值比它更大，因而不需要弹栈，直接将 \(3\) 号二元组入栈，栈为 \(\{(1, 10),(3, 2)\}\), 栈中有多个元素，该二元组不是 “成功的”
加入 \(4\) 号二元组 \((1, 9)\), 此时栈顶元素 \((3, 2)\) 的 \(b\) 值比它小，弹栈。弹栈后栈顶元素 \((1, 10)\) 与 \((1, 9)\) 的 \(a\) 值相同，继续弹栈。此时栈空，\(4\) 号二元组入栈，栈为 \(\{(1, 9)\}\), 该二元组是 “成功的”. 共有 \(3\) 个二元组是 “成功的”, 因而答案为 \(3\)
数据规模
\(1 \leq n, q \leq 5 \times 10^5,1 \leq a_i,b_i \leq n, 1 \leq l_i \leq r_i \leq n\)
解题思路
复杂度
代码参考
Show code
删数
1 s, 1024 MB
题目描述
给定一个长度为 \(n\) 的正整数序列 \(a_1, ... , a_n\)
你可以进行若干次操作，每次操作你可以选择一个位置 \(i \in [2, n - 1]\), 满足 \(a_i = \frac{a_{i-1} + a_{i+1}}{2}\), 然后将 \(a_i\) 删去，之后的数按顺序向前补空位
接下来的操作将在新序列上进行
求若干次操作后，最终序列的长度最小的是多少
输入格式
第一行一个正整数 \(T\), 表示数据组数
对于每组数据
第一行输入一个正整数 \(n\), 表示序列的长度
接下来一行输入 \(n\) 个正整数，分别表示 \(a_1, ... , a_n\)
输出格式
对于每组数据，输出一行一个正整数，表示答案
数据范围
对于所有数据，满足 \(1 \leq T \leq 10^3\), \(3 \leq n\), \(\sum{n} \leq 3 \cdot 10^5\), \(1 \leq a_i \leq 10^9\)
样例输入
1 | 3 |
样例输出
1 | 2 |
题目来源
题目与数据均来自 Public Round #1 http://pjudge.ac/contest/883
原题为 International Zhautykov Olympiad 2022, Computer Science, Day 1, Problem 1
解题思路
复杂度
代码参考
Show code
环的数量
1 s, 256 MB
题目描述
给定一张含有 \(n\) 个点，\(m\) 条边的简单图，求简单环的数量
输入格式
第一行，包含两个整数 \(n\) 和 \(m\). 第二行到第 \(m+1\) 行，包含两个整数 \(x,y\), 表示节点 \(x\) 和 \(y\) 之间连有一条边
输出格式
输出一行，表示图中含有的环数
样例输入
1 | 4 6 |
样例输出
1 | 7 |
数据限制
对于 \(100\%\) 的数据，保证 \(1\leq n \leq 19,m \leq \frac{n\times (n-1)}{2}\)
解题思路
复杂度
代码参考
Show code
Ayoub's function (CF1301C)
1 s, 128 MB
题目描述
定义函数 \(f(s)\) , s 为 01 字符串，\(f(s)\) 为字符串 s 中至少包含一个 1 的子串数量
现在存在一字符串 s, 给出字符串长度 \(n\) , 和它包含的 1 的数量 \(m\) , 求最大的可能的 \(f(s)\)
输入格式
输入由多组测试数据组成
第一行输入一个整数 \(T (1 \leq T \leq 10^5)\) 为数据组数
接下来 \(T\) 行，每行输入两个整数 \(n, m\) \((1 \leq n \leq 10^9, 0 \leq m \leq n)\)
输出格式
输出 \(T\) 行，每行一个整数做为答案
输入样例
1 | 5 |
输出样例
1 | 4 |
样例解释
第一组数据中，s=010 时，\(f(s)=4\)
第二组数据中，s=101 时，\(f(s)=5\)
第三组数据中，s=111 时，\(f(s)=6\)
第四组数据中，s=0000 时，\(f(s)=0\)
第五组数据中，s=01010 时，\(f(s)=12\)
解题思路
复杂度
代码参考
Show code
最大权值划分
1 s, 1024 MB
题目描述
对于一段序列，定义这段序列的权值为这段序列的极差，即序列的最大值与最小值之差
给定一个序列 \(a\), 你可以将它划分成任意段连续的序列，求出每一段的权值和的最大值
输入格式
第一行输入一个整数 \(n\), 表示序列的长度 $(1 n ^6) $
第二行输入 \(n\) 个整数 \(a_1 , a_2 , a_3 , \dots , a_n\) 表示给定的序列 .$(-10^9 a_i ^9) $
输出格式
输出一行一个整数表示每一段的权值和的最大值
样例输入
1 | 5 |
样例输出
1 | 10 |
样例解释
划分成 \([9,6] , [1,8,8]\) 的权值最大
解题思路
复杂度
代码参考
Show code
括号序列 (51Nod 1791)
1 s, 1024 MB
题目描述
合法括号序列的定义是:
- 空序列是合法括号序列
- 如果 S 是合法括号序列，那么 (S) 是合法括号序列
- 如果 A 和 B 都是合法括号序列，那么 AB 是合法括号序列
现在有一个括号序列，现在要计算一下它有多少非空子段是合法括号序列
PS: 为了方便给出了 5 个样例，但是丢在一个框框里
输入描述
一个字符串 S
输出描述
有多少个非空子段是合法括号序列
输入样例
1 | ( |
输出样例
1 | 0 |
数据范围
\(1 \leq |S| \leq 10^6\)