月份:2019年8月

篇文章

三校集训Part2 NBCX Day11 bracket 题解
题意 现在有一个长度为$ n $且合法的括号序列,每次询问将会翻转其中一个括号(左括号与右括号互相变换),你要对于每个询问,再翻转一个括号(可以与讯问中的相同),使得括号序列仍旧合法,且翻转的位置尽量靠前。 询问和回应的效果都是是叠加的,也就是括号序列在某个询问后,会按照询问和回应永久改变。 对于$100\text{%}$的数据,满足$ 2 \le…
三校集训Part2 NBCX Day8 Cloud 题解
题意 给出每个云的位置及大小以及移动方向,它们的移动速度均为$1$个单位长度每单位时间,在时刻0,所有的云没有重叠,问在所有时刻中(从负无穷到正无穷)中,云重叠层数最多是多少? 思路 非常显然,答案只有可能是$1$或$2$。 所以,直接$rand()\text{%}2$(逃: 咳咳,进入正题。 所以只要能判断是不是能有一片横着走的云和一片竖着走的云…
Luogu P3515 [POI2011]Lightning Conductor 题解
题意 题目传送门 已知一个长度为$n$的序列$a_1,a_2,...,a_n$。 对于每个$1\leq i\leq n$,找到最小的非负整数$p$满足 对于任意的$j$,$ a_j \leq a_i + p - \sqrt{| i-j | }$ 思路 首先先把题目中的式子化简一下: $p\geq a_j+\sqrt{|i-j|}-a_i$ 原来就是…
三校集训Part2 NBCX Day7 timegate 题解
题意 原题链接 订正链接 构造一个图,图的所有边权等于$1$,求使$1$到$n$的最短路距离为$k$的方案数。 对于$ 100\text{%}$的数据$n,k \leq 100$ 思路 (为了图(wo)方(tai)便(cai),下文的$m$代表上文题意中的$k$,下文的$k$详见下文) 考虑$dp$。 因为这张图的最短路距离为$k$,所以考虑分层图…
三校集训Part2 NBCX Day3 course 题解
题意 神秘男子的学校安排了$ N $门课,每门从时间$ start_i $上到时间$ end_i$。神秘男子一次只能上一门课。神秘男子想法很多,他想知道$ Q $个时间段$ planstart_j $到$ planend_j $内, 他分别最多上几节课。 对于$100\text{%}$的数据,$1\leq N,Q \leq 10^5,0\leq s…
三校集训Part2 NBCX Day2 XVII 题解
题意 有$n$个长度为$32$的只包含小写字母的字符串,问每个字符串读入时它之前有没有出现过? 输出$n$行,每行输出$Yes$或$No$。 时间限制:$6s$ 空间限制:$2M$ 思路 出题人好心地帮我们把$2M$标红了... 考虑使用$map$,虽然$map$的准确性高,但是不仅常数大(但出题人好心地给了$6s$)空间上也会$MLE$。 考虑使…