版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: Namomo Spring Camp 2022 Div1 每日一题记录 (Week 6) categories:
Namomo Spring Camp 2022 Div1 每日一题记录 (2022.04.02-2022.04.08)
<!-- more -->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$
一个数, 表示最少需要的颜色数量
2
4
1 3 4 2
2
1 2
2
1
所有数据保证 $1\leq \sum n \leq 10^6$
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$ 行, 每行一个自然数表示一组询问的答案
10 4
3 1 3 1 2 3 3 2 1 1
10 10 2 9 7 5 4 7 6 1
1 4
7 8
7 10
1 8
3
2
2
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$
1 s, 1024 MB
给定一个长度为 $n$ 的正整数序列 $a_1, ... , a_n$
你可以进行若干次操作, 每次操作你可以选择一个位置 $i \in [2, n - 1]$, 满足 $ai = \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$
3
5
1 2 3 4 5
7
1 3 5 6 7 8 10
3
1 1 1
2
4
2
题目与数据均来自 Public Round #1 http://pjudge.ac/contest/883
原题为 International Zhautykov Olympiad 2022, Computer Science, Day 1, Problem 1
1 s, 256 MB
给定一张含有 $n$ 个点, $m$ 条边的简单图, 求简单环的数量
第一行, 包含两个整数 $n$ 和 $m$. 第二行到第 $m+1$ 行, 包含两个整数 $x,y$, 表示节点 $x$ 和 $y$ 之间连有一条边
输出一行, 表示图中含有的环数
4 6
1 2
1 3
1 4
2 3
2 4
3 4
7
对于 $100\%$ 的数据, 保证 $1\leq n \leq 19,m \leq \frac{n\times (n-1)}{2}$
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$ 行, 每行一个整数做为答案
5
3 1
3 2
3 3
4 0
5 2
4
5
6
0
12
第一组数据中, 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$
1 s, 1024 MB
对于一段序列, 定义这段序列的权值为这段序列的极差, 即序列的最大值与最小值之差
给定一个序列 $a$, 你可以将它划分成任意段连续的序列, 求出每一段的权值和的最大值
第一行输入一个整数 $n$, 表示序列的长度 $( 1 \leq n \leq 10^6 ) $
第二行输入 $n$ 个整数 $a_1 , a_2 , a_3 , \dots , a_n$ 表示给定的序列 .$( -10^9 \leq a_i \leq 10^9 ) $
输出一行一个整数表示每一段的权值和的最大值
5
9 6 1 8 8
10
划分成 $[9,6] , [1,8,8]$ 的权值最大
1 s, 1024 MB
合法括号序列的定义是:
现在有一个括号序列, 现在要计算一下它有多少非空子段是合法括号序列
PS: 为了方便给出了 5 个样例, 但是丢在一个框框里
一个字符串 S
有多少个非空子段是合法括号序列
(
()
()()
(()
(())
0
1
3
1
2
$1 \leq |S| \leq 10^6$