夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
Luogu P3535 [POI2012]TOU-Tour de Byteotia 题解
Link 题意 给定一个$n$个点$m$条边的无向图,问最少删掉多少条边能使得编号小于等于$k$的点都不在环上。 思路 要想让编号小于等于$k$的点都不在环上,那么就最好让所有编号大于$k$的边都在环上。 那么可以用并查集把所有编号大于$k$的边连起来,再判断编号小于等于$k$的边是否在环上即可。 Code [crayon-5e8cb3bcb207…
隔板法 学习笔记
前言 $2019.10.19$就$CSP$第一轮了(好慌 隔板法定义 在组合数学中,隔板法(又叫插板法)是排列组合的推广,主要用于解决不相邻组合与追加排列的问题。 隔板法就是在$n$个元素间插入$(b-1)$个板,即把$n$个元素分成$b$组的方法。——百度百科 普通隔板法 经典问题:求$x+y+z=10$的正整数解的个数。 这个问题与此问题相同:…
exgcd学习笔记
前言 今天膜你赛竟然要套$exgcd$ gcd [crayon-5e8cb3bcb2f23187222123/] exgcd 形如$ax+by=c$的方程,当$gcd(a,b)|c$时,存在整数解$x,y$。 也就是说$exgcd$可以解$ax+by=gcd(a,b)$的方程。 令$a=b,b=a\mod b$,那么$bx+a\mod b\time…
2019.10.6 CSP-S模拟赛T1
前言 考完以后感觉炸了,结果还好(大雾,竟然没有垫底 5+80+20=105(21/52) 题意 对于任意的$1\leq k \leq N$,求有多少个恰好有$k$个叶子节点的二叉树,满足每个节点要么没有子节点,要么有两个子节点,同时不存在一个叶子节点,使得根到它的路径上有不少于$M$条向左的边。 答案对$998244353$取模。 思路 此题发下…
BSGS&exBSGS 学习笔记
写在前面 在某次集训比赛时遇到了$esBSGS$毒瘤题,被大佬们暴捶,过了一个多月本蒟蒻才开始学习$BSGS\text{&}exBSGS$ BSGS $BabyStepGiantStep$算法,即大步小步算法,缩写为$BSGS$,而$esBSGS$,顾名思义,就是$BSGS$的拓展。 $BSGS$用来解决如下问题: 给定一个质数$P(2\l…
2019.9.15 CSP-S模拟赛
前言 一大波原题来袭!!!(大雾 考得不太好吧0+100+0=100(T3数据出锅了 T1-P5424 [USACO19OPEN]Snakes 题意 有$n$组蛇,每一组蛇有$a_i$条蛇,你有一张网,需要将蛇全部抓住。一次抓一组蛇,因此每次要使网比当前组的蛇的数量大。你可以改变$k$次网的大小,问抓住所有蛇的总浪费空间的最小值? 对于$100 \…
三校集训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$,所以考虑分层图…