当前位置:网站首页>cf:C. The Third Problem【关于排列这件事】
cf:C. The Third Problem【关于排列这件事】
2022-07-06 00:38:00 【白速龙王的回眸】
分析
这是一道排列的题
看起来花里胡哨的
说到排列,我们就要找到这个排列0到n对应的下标位置
我们这里的MET定义是除字串外最小的数,所有的字串都要满足这个最小的数相同
于是,我们遵循“最小”,从最小的0开始一个个找对应的索引
首先0的位置肯定变不了,其次1也变不了(否则总能找到一个区间使得MET不等)
然后看2后面的数,用lr维护当前索引区间的左右,然后如果2在lr中的话,它就有r - l + 1 - 2种选择
如果它在索引区间lr外,那么必定有一种区间的选择使得MET不等,为了更形象,举个例子:
+++2+++1+++0+(1)
++2++++1+++0+(2)
----+++++++++++
如果我们选上一行+的区间,那显然MET(1) > 2而 MET(2) = 2
因此当我们选第k个数的时候,上一个lr索引区间长度是r - l + 1
我们只有当id[i]在索引区间内才可以相似,这时候它能选的位置个数共有r - l + 1 - i
用ans 连乘就可以了
ac code
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
id = [0] * n
for i, v in enumerate(a):
id[v] = i
# we judge from v = 0,1,...
ans = 1
l = r = id[0]
for i in range(1, n):
# if id[i] outside [l, r], no other choice
# cause there must be a choice MET not equal
if id[i] < l or id[i] > r:
l, r = min(id[i], l), max(id[i], r)
else:
ans = ans * (r - l + 1 - i) % MOD
print(ans)
总结
排列 + 排序 + 区间内外模拟
通过排除一些情况从而猜测合理的情况
边栏推荐
- Intranet Security Learning (V) -- domain horizontal: SPN & RDP & Cobalt strike
- anconda下载+添加清华+tensorflow 安装+No module named ‘tensorflow‘+KernelRestarter: restart failed,内核重启失败
- State mode design procedure: Heroes in the game can rest, defend, attack normally and attack skills according to different physical strength values.
- Analysis of the combination of small program technology advantages and industrial Internet
- KDD 2022 | EEG AI helps diagnose epilepsy
- [groovy] compile time meta programming (AST syntax tree conversion with annotations | define annotations and use groovyasttransformationclass to indicate ast conversion interface | ast conversion inte
- Problems and solutions of converting date into specified string in date class
- Anconda download + add Tsinghua +tensorflow installation +no module named 'tensorflow' +kernelrestart: restart failed, kernel restart failed
- AtCoder Beginner Contest 254【VP记录】
- How spark gets columns in dataframe --column, $, column, apply
猜你喜欢
Room cannot create an SQLite connection to verify the queries
notepad++正則錶達式替換字符串
KDD 2022 | EEG AI helps diagnose epilepsy
Data analysis thinking analysis methods and business knowledge - analysis methods (III)
State mode design procedure: Heroes in the game can rest, defend, attack normally and attack skills according to different physical strength values.
如何利用Flutter框架开发运行小程序
The third season of ape table school is about to launch, opening a new vision for developers under the wave of going to sea
Spark SQL空值Null,NaN判断和处理
猿桌派第三季开播在即,打开出海浪潮下的开发者新视野
Atcoder beginer contest 254 [VP record]
随机推荐
Keepalive component cache does not take effect
Global and Chinese markets of POM plastic gears 2022-2028: Research Report on technology, participants, trends, market size and share
Atcoder beginer contest 258 [competition record]
新手入门深度学习 | 3-6:优化器optimizers
如何制作自己的机器人
Meta AI西雅图研究负责人Luke Zettlemoyer | 万亿参数后,大模型会持续增长吗?
Common API classes and exception systems
The third season of ape table school is about to launch, opening a new vision for developers under the wave of going to sea
notepad++正则表达式替换字符串
notepad++正則錶達式替換字符串
LeetCode 1598. Folder operation log collector
云导DNS和知识科普以及课堂笔记
OS i/o devices and device controllers
Arduino六足机器人
Go learning --- read INI file
[Chongqing Guangdong education] reference materials for Zhengzhou Vocational College of finance, taxation and finance to play around the E-era
Data analysis thinking analysis methods and business knowledge - analysis methods (III)
synchronized 和 ReentrantLock
MIT博士论文 | 使用神经符号学习的鲁棒可靠智能系统
Lone brave man