铅笔p1909 noip 2016
NOIP 2022 考前学习日记
前言 学习记录本写太乱了,所以在这里打个草稿 顺便记录一下学习过程,后面总结的时候康康有没有问题 11月2日(今日运势:中平) 上午: 再次做了一下CSP-S 2022的题,除了T4以外的都订正完了 听yjy讲了一下 kruskal重构树,还没做练习 下午: 看线性代数看的想睡觉; 尝试做了一下【模 ......
NOIP 2023 考前学习日记
前言 e92a191c-9fae-4364-882b-0c91fb88c3aa 属于是闲着没事干,看到自己去年写过一次,所以再写一次。 10 月 23 日(今日运势:大吉) 上午: 调联考异或,没调出来。 消消乐,想想想。 消消乐,写写写。 消消乐,卡卡卡。 消消乐,寄寄寄。 详见记录:link。 ......
2023NOIP A层联测20 点餐
2023NOIP A层联测20 点餐 题目很好,可惜考试没想到。 思路 可以按照 \(b\) 从小到大排序,固定选择个数 \(k\),枚举选择的盘子 \(x\) 的 \(b\) 最大,最优解肯定是贪心的在前 \(x-1\) 个盘子里选择 \(k-1\) 个最小的,使用权值主席树可以在 \(O(\lo ......
NOIP2023模拟6联测27 C. 点餐
NOIP2023模拟6联测27 C. 点餐 题目大意 有 \(n\) 种菜品,每样菜品有 \(a_i , b_i\) 假设有某位顾客点了 \(k\) 样菜品,那么价格为 \(\sum_{i = 1}^k a_{p_i}+\max_{i = 1}^kb_{p_i}\) 询问所有的 \(k \in(1 ......
20231029NOIP训练赛
20231029NOIP训练赛 时间安排 7:50-9:10 写T1 9:10-10:10写T2 10:10-11:20写T3 11:20-11:50写T4 总结 T1看了一个多小时不会做,导致T4没写完 题解 T1 发现每一个操作在差分数组里只是交换两个数的位置,于是如果两个数组的差分数组排序后相 ......
20231028NOIP训练赛
20231028NOIP训练赛 时间安排 7:50-8:20 写T1 8:20-9:20写T2 9:20-10:20写T4 10:20-11:50写T4 总结 题解 T1 模拟题,按照题意二分模拟即可 T2 DP题,设\(f_{i,j}\)表示前i个笔画为奇数的字中有j个出现了偶数次,\(g_{i, ......
P8868 [NOIP2022] 比赛
传送门 我们容易想到预处理区间 \([l, r]\) 中的 \(m_a \times m_b\)。 这样算出来的是一个二维的矩阵,每次的答案就是红色部分: 但是这样的问题是二维的,无论如何都不是正解。 考虑把列这一维压掉,也就是令 \(w'_i \leftarrow w_{i,i} + w_{i,i ......
题解:「NOIP2022 提高组」种花
题解:「NOIP2022 提高组」种花 题目大意:给定一个 \(n \times m\) 的01矩阵,0表示可以种花,1表示土坑(无法种花),现在要在图上种出一个C型或F型(C,F横着的两条线的长度都可以不同,但一定是面向右边的),现在问你种C和F分别有多少种方案(除了这个形状外不能在任何地方种花) ......
【梦熊联盟】10月28日 NOIP十连测 第五场 题解
目录T1 男女排队简要题意:题解:T2 树上最多不相交路径简要题意:题解:T3 生日T4 组队比赛简要题意:题解: T1 男女排队 简要题意: 求长度为 \(n\) 的01序列不包含字串101或111的个数。 \((n\leqslant 10^{18})\) 题解: 一开始往容斥的思路去想,但是在推 ......
NOIP2018 赛道修建
观察题目不难想到二分答案。 考虑二分所有赛道的最小长度值,那么我们可以去判断最后修建出来的赛道数是不是大于等于 \(m\) 条即可。 用 \(f_{i}\) 表示当前以 \(i\) 为根,最长的未被赛道占用的链的长度。 但是有很多链,匹配的过程不好进行,所以改为用 multiset 来维护当前点的链 ......
NOIP[区间数据结构类问题]
平面最近点对 经典的分治问题,把所有的点按照 \(x\) 排序,然后分治处理两个子区间,然后枚举离中心少于已知最小值的点,判断能否出现更小值。 int n,temp[250000]; struct node{ int x,y; }a[500500]; bool cmp(node l,node r){ ......
考场(NOIP2023模拟5联测26)
T1 题目好评,但是hanzelic小姐是大主播啊。 对于 \(a_1\) ^ \(a_2\) ^ \(a_3\) ^ \(a_4\) ......来说,要让 \(a_2\) ^ \(a_3\) ^ \(a_4\) 最小。 啊,为什么我觉得运算顺序不会对这个题造成影响啊QAQ,我是菜狗QAQ。 奥, ......
loj2737. 「JOISC 2016 Day 3」电报
最终形态一定是 \(n\) 个点形成的一个大环。 故每个点的入度一定为 \(1\),我们考虑保留每个点入度中 \(c_i\) 最大的边,剩下的删除,此时原图一定变成一堆链加一些环。 对于环,我们是需要拆开的,此时我们可以枚举环上每个点,考虑将其反悔,反悔代价为环边代价减去其次大入边(最大入边一定为环 ......
NOIP2023模拟5联测26 题解
NOIP2023模拟5联测26 题解 感觉我这场的官方题解写的是真的挺好的,所以我只能作少量补充。你可以直接去看官方题解,如果你想的话。 T1 x 题解 \(n = 2\) 没啥可说的。\(\color{white}{这档分你要是没拿到那你还是蛮强的。}\) \(n = 3\) 的时候,我们需要比较 ......
[清华集训2016] 组合数问题
题目链接1、题目链接2 这道题的难点在于 \(k|C_{i}^{j}\) 这个特殊限制。 由于 \(n,m\) 的范围很大,再加上式子中有组合数,我们自然而然地想到了 \(\text{lucas}\) 定理: \[C_{n}^{m}={C_{\lfloor\frac{n}{k}\rfloor}^{\ ......
NOIP冲刺之超市T2计划(upd on 1028)
超市T2计划总结 目录超市T2计划总结声明:刷题:三国游戏:T1尼克的任务:T2卖萝卜:T1剔除多余括号:T2引水入城:T3Medium Design :T3加工生产调度:T2方圆幂积:T3打地鼠:T1取相片:T3总结: 声明: 本贴用于总结对于csps-noip T2左右难度的题目。 会选择一些N ......
20231027NOIP训练赛
20231027NOIP训练赛 时间安排 7:40-9:20 写T1 9:20-10:20写T2 10:20-11:10写T3T4 11:10-11:50写T5 总结 T1写挂了,T3的set超时了 题解 T1 简单DP题 T2 把加转化为差分,差分数组进行区间加操作,用线段树维护 T3 用一个栈维 ......
2023NOIP A层联测19(未完成)
2023NOIP A层联测19 T2 多边形 首先考虑这样一个结论:如果整个多边形中某种颜色只在一个顶点 \(x\) 存在,那么只需将 \(x\) 与每个不与它相邻的顶点连边即可。这是因为两个相邻的顶点颜色不同,而这两种颜色又都与 \(x\) 的颜色不同。 再考虑这样一个结论:整个多边形中必然存在相 ......
[NOIP 2013提高组]货车运输 题解
[NOIP 2013提高组]货车运输题解 前置知识 Kruskal 重构树(内含讲解)+任意一种LCA 题目翻译 \(n\)座城市,\(m\)条道路,\(q\)次询问,每次求两个点\(x,y\)之间所有路径的最小值的最大值。 题目分析 其实学了Kruskal重构树差不多看到这个题目就知道怎么写了。 ......
P4069 SDOI2016 游戏
传送门 solution 树剖后一段路径变成了若干链拼起来。自上而下和自下而上分别维护两棵李超线段树,每条链就是一段数轴,提前处理每个点两种方向上的在链内的横坐标。以最近公共祖先为界,把路径分成两段。从一个点向链的顶端跳就是区间加线段。每次跳完要把线段的截距增加一个横坐标偏移量乘上斜率,因为不同链横 ......
NOIP 习题合集
前言 临近 NOIP,打算把往年的能做的题目尽量做做。 以后的就都发布到文章里了,都挤在随笔里有点难看。 22年的不改是因为我懒 2022 P8865 [NOIP2022] 种花 题解 P8867 [NOIP2022] 建造军营 2021 ......
考场(NOIP2023模拟4联测25)
T1 peter的烟的加强版,算水题吧,一眼顶针 T2 从小的推到大的???从一个点的合法情况推多个点的合法情况??? 也许和菜狗可爱内一场的菜一样用个链表维护???】 发现性质当两个点连边,则两个点中间的点可以直接扔去不管 也许是将大问题一点一点缩小到小问题??? 转化题意为:对于一个序列,每次消 ......
P5336 [THUSC2016] 成绩单
这得是区间 dp。还需要限制一下值域。因此 dp 状态时 \(f_{l, r, x, y}\) 表示使 \([l, r]\) 区间所有值都处于 \([x, y]\) 的最小花费。设 \(g_{l, r} = \min\{f_{l, r, x, y} + a + b (x - y) ^ 2\}\)。 ......
P8867 [NOIP2022] 建造军营
缩点 首先考虑对于一个边双内的边是可以任意看守或者不看守的,所以可以缩点,这样缩完点的图就成了一棵树。 对于缩完点后的每一个边双,我们设 \(E_{i}\) 表示边双 \(i\) 内的边的个数,\(siz_{i}\) 表示边双内点的个数。 那么只考虑一个边双的情况的话,边能任选的方案数就是 \(2^ ......
P8865 [NOIP2022] 种花 题解
前言 去年多测不清空导致即便 CCF 放过了我的 \(O(n^2 m)\) 的代码但依然挂成了 \(0pts\)。 当时看清空数组后能过 CCF 数据就没再管。 时隔 \(1\) 年,重做这道题写了 \(O(nm)\) 的正解,终于完成了当年的心愿。 \(O(n^2 m)\) 思路 想到计算方案的话 ......
NOIP2023模拟3联测24-博弈树
NOIP2023模拟3联测24-博弈树 目录NOIP2023模拟3联测24-博弈树题目大意思路code 题目大意 \(Alice\) 和 \(Bob\) 又开始玩游戏了: 给定一颗 \(n\) 个节点的树,\(Alice\) 和 \(Bob\) 随机选择一个节点作为起点放上棋子,由 Alice 先手 ......
NOIP 2020
NOIP 2020 xjb乱做 时间:7:30~9:50 分数:100+80+0+40 T1 [NOIP2020] 排水系统 根据题目所给信息 有若干点没有出度 有若干点没有入度 且图不成环 一眼拓扑 直接做就可以了 (感觉应该不会炸long long罢 但为了保险起见仍然用的__int128) # ......
NOIP 模拟赛合集
CSP考完打算写题解了 写题解有啥用呢,大抵是总结吧。。 总不能让博客一直没东西 第一场走丢了(确信) 10.25 模拟2 mp场 100+70+0+0=170 pts rk13 T3暴力 INT_MAX,给我输出了mp的题解密码(蚌),T4暴力没时间测就交了。 T1挺能签的,大部分时间花在 T2 ......
「NOIP2016 提高组」天天爱跑步题解
题目背景NOIP2016 提高组 Day1 T2 题目描述小 C 同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。 这个游戏的地图可以看作一一棵包含 n 个结点和 n-1 条边的树, 每条边连接两个结点,且任意两个结 ......