地毯noip 2011
2023年石门中学NOIP模拟测试(2023.10.12)
又被打爆... T1 \(n\leq 10^3,q\leq 3\times 10^5\) 签到。竖着和斜着差分一下,最后从左往右扫一遍做完。 T2 做不出来这个显得很弱智...其实可以将整个游戏看成二叉树,然后每次的分左右儿子取决于 \(b_i\) 的倍数与否,接下来每一层的取值就看奇偶是 \(\t ......
T2【noip赛前20天冲刺集训 day4】正在打模拟赛
@@ 【noip赛前20天冲刺集训 day4】正在打模拟赛 @@ 题目描述 给定一棵包含 n 个点的树,每条边都有权值,同时给定一个整数 k。定义一个树上连通块的权值为其中边权之和。你需要求解满足以下条件的树上连通块的权值最大值:这个连通块至多包含一个度数大于 k 的点。 注意,这里的度数指的是连通 ......
【noip赛前20天冲刺集训 day4】正在出模拟赛
题目描述 想象学竞赛网站 CodeFancy 举办了 \(m\) 场比赛。你在 CodeFancy 上关注了 \(n\) 个账号,编号为 \(1\) 到 \(n\)。你知道这 \(n\) 个账号分别参加了 \(m\) 场比赛中的哪些。但是你发现可能存在一个人使用多个账号的情况,你想知道这 \(n\) ......
NOIP2021 棋局
推销:Everyday DS | Day \(S_{\text{fib}}(7)\)。 历时 5.5h 写 + 调,真的有人会在场上写正解吗。/oh/oh 考虑以某些同种种类的边组成的若干连通块,注意到放一个棋子可能会将棋盘分割成不同的连通块,于是倒序考虑将分裂变成合并,每次相当于删去一个棋子。 \ ......
【noip赛前20天冲刺集训 day3】矩阵挑战
NOIP比赛前的冲刺训练 - 第3天:矩阵挑战 问题描述 您有一个 n×m 矩阵,行编号从 0 到 n−1,列编号从 0 到 m−1。最初,第i行第j列的元素是 i*m+j。系统支持三种类型的操作: 交换两行。 交换两列。 交换两个特定的元素。 任务是确定执行 q 次操作后矩阵的状态。 输入格式 为 ......
noip赛前20天冲刺集训 day2 ###寻找有向图中的最小疲惫路径###
T1 ###寻找有向图中的最小疲惫路径### 题目描述 有一张 n 个点 m 条边的有向图,每条边上有一个正整数边权,你要顺着图上的有向边从 1 号点走到 n 号点。 假设你经过的边边权依次为 (w_1, w_2, \dots, w_t),则你的疲惫程度为 \[\ f(w) =\max_{i=1}^ ......
2023NOIP A层联测9
A.长春花 简单题。打表发现情况并不多,记录下平方后模 \(p\) 对应的值,然后枚举 \(a\),用链表维护即可。 点击查看代码 #include<bits/stdc++.h> using ll=long long;using ull=unsigned long long; int a[10000 ......
20231010NOIP训练赛
20231010NOIP训练赛 时间安排 7:50-8:10 写T1 8:10-8:40 写T2 9:40-10:40 写T3 10:40-11:50 写T4 总结 没时间写T5,T4和T3没写对 题解 T1 简单题,用两个桶记录一下,然后再做两遍前缀和 T2 二分+哈希 T3 分组背包 T4 双指 ......
2023NOIP A层联测9 T3 天竺葵
2023NOIP A层联测9 T3 天竺葵 题面及数据范围 Ps:连接为accoderOJ。 看题大概是一个最长上升子序列的带权版本,于是想到 dp。 设 \(dp[i][j]\) 为到第 \(i\) 项,选出 \(j\) 个数的 \(c_j\) 最小值,不难想到转移: \[dp[i][j]=\mi ......
【noip赛前20天冲刺集训 day3】 砝码比较问题
砝码比较问题 问题描述 有 n 个砝码,根据材质不同,质量只有 1g, 2g, 3g 三种。 现在砝码上的质量标签都遗失了,由于只有材质不同,从外表难以分辨。但所幸还有一个天平,可以用这个天平秤量砝码之间的重量关系。 某些砝码之间的重量关系已经称出来了,但其它的还不知道。 现在已经选了两个放在了天平 ......
P6348 [PA2011] Journeys
Description 一个星球上有 \(n\) 个国家和许多双向道路,国家用 \(1 \sim n\) 编号。 但是道路实在太多了,不能用通常的方法表示。于是我们以如下方式表示道路: \((a, b),(c, d)\) 表示,对于任意两个国家 \(x, y\),如果 \(a \leq x \leq ......
NOIP A层联测9 & CSP模拟52
我的评价是三道傻逼题和一道牛逼题。 T4 上厕所时想了个奇怪东西打了一个半个小时 170 行结果剩 10 分钟发现假了,最后 \(k=1\) 都没来得及写就直接交了暴力。没想到 HZOJ 过了 50pts,喜了。但是 Accoders 上只过了 35pts,恼了。 T1 长春花 \(b^2\bmod ......
【多校联考NOIP#2】比赛复盘 && 题解
A. 黑白染色 这类题没有做过,第一次做,很有新意。 染色的时候,如果一个点的出边中有2个同色点,那么就有一条路中有三个同色点,是不合法的。 不妨先把所有点染成一个颜色,然后再选点染成另一个颜色。 使用一个队列,先把所有的点入队。 每次取出队头 \(u\) ,如果发现他不合法: 1.自己颜色取反 2 ......
CSP/NOIP 2020,2021,2022
CSP-S 2020 儒略历 可以发现不管是缺的 \(10\) 天还是什么特殊规定,前面的天数都比较少,直接暴力模拟前头就行。 可以直接暴力模拟 \(3\times 10^6\) 天,然后接下来考虑如果要连着跳 \(k\) 天,首先如果 \(k\le 400\) 就暴力跳 \(k\) 次,否则我们先 ......
正如ioi2023noip二十连游寄
day 1 抽象场。 T1是诈骗题,剩下三题都是撒币概率期望。赛事没有人过t3t4。 毫无意义。 T2想不到可以把相似的状态归在一起。从 \(O(2^{3n})\) 到 \(O({\begin{pmatrix}n+m\\n\end{pmatrix}}^3)\),很难想到。不过foi的时候甚至听说过拆 ......
P5309 [Ynoi2011] 初始化
题目传送门 本来不想写这道 \(shabi\) 卡肠题的,但还是写了。 分块+根号分治。 考虑对 \(x\) 的大小分类讨论: 若 \(x>=\sqrt{n}\),很明显最多只会加 \(\sqrt{n}\) 次,暴力加即可,用分块维护每个块内的 \(sum\),查询就直接散块加上整块即可。 若 \( ......
P1540 [NOIP2010 提高组] 机器翻译
传送门 题目背景 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 题目描述 这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会 ......
[NOIP2011 提高组] 铺地毯
题目描述 为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 \(n\) 张地毯,编号从 \(1\) 到 \(n\)。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。 地毯铺设完成后,组 ......
LY1376 [ 20231008 NOIP 模拟赛 T0 ] 递增路径
题意 \(A\), \(B\) 两人轮流在一张图上移动一个点。要求这次移动的边权必须大于上次的。 \(A\) 希望游戏进行的轮数多,\(B\) 希望游戏进行的轮数少。 对于每个 \(s = 1, 2, ..., n\) 作为起点,若双方都采用最优策略,游戏会进行多少轮。 Sol 考虑将所有边按照从大 ......
LY1380 [ 20231009 NOIP 模拟赛 T1 ] AK 神
题意 给定长度为 \(n\) 的序列 \(S\)。 \(A\),\(B\) 两人轮流取连续 \(k\) 个数,保证 \(n \equiv 1\pmod k\)。 \(A\) 使最终数字更小,\(B\) 使最终数字更大。 问取到数的和。 Sol 直接考虑每次选哪些数,怎么选显然是不好做的。 不难发现 ......
NOIP A层联测8
感觉以后模拟赛都应该认真改题。 \(100+100+0+100\),开题顺序 \(1-4-2-3\),以为打到12:00结果只打到11:30导致 T3 特殊性质和暴力都没写,后来也懒得写了。 T4 前一天刚做过究极弱化版,跟偷了题一样,切得挺顺利;T2 由于忘了 \(k\) 相等耽误了好久,幸好做出 ......
地垫/毛绒地毯出口美国GCC清关认证亚马逊gcc认证
出口美国地垫GCC清关认证美国联邦法律规定,地毯和垫子要符合易燃性标准和其它要求, 包括2008年《美国消费品安全改进法》的要求。在地毯和垫子经过检测或合理检测项目后,作为一般用途的 地毯和垫子的生产商和进口商必须在一般合规证书(GCC) 中认证,地毯和垫子符合适用标准,确保合规和/或按照标准 贴上 ......
解题报告P2486 [SDOI2011] 染色
P2486 [SDOI2011] 染色 题目链接 分两段,最后靠同一条重链合 树剖加线段树,典中典。 这题的线段树维护比较新颖。 线段树中维护这个区间左右端点的颜色和颜色段数量。 建树和查询和修改时要判断左区间的右端点和右区间的左端点是否颜色相同。 如果不相同,直接将段数相加,否则减一。 然后就是查 ......
LY1366 [ 20231005 NOIP 模拟赛 T0 ] 加固
题意 设 \(T\) 是由 \(26\) 小写英文字母排列得到的字符串。 \(T'\) 由 \(T\) 复制若干次得到。 给定字符串 \(S\) 为 \(T'\) 的子序列,求 \(T'\) 的最小复制次数。 保证出现的不同字母不超过 \(20\) 种 \(1 \le |S| \le 10^5\) ......
LY1374 [ 20231008 NOIP 模拟赛 T2 ] 机房惨案
题意 给定一棵树,每次操作将一个点染成黑色。 求询问的点到所有黑点的路径编号最小值。 ** 数据保证第一次为染色操作 ** Sol 注意到保证第一次为染色。 考虑钦定根节点为染色的点。 那么对于所有染色操作,暴力记录染色的点到根节点的路径上所有点的贡献。 每个点只会贡献一次,这部分是 \(O(n)\ ......
P1003 [NOIP2011 提高组] 铺地毯
第一思路: 开一个N*N的数组,每次都扫一遍地毯范围并标记编号 然后你会发现:喜提MLE 为什么呢? 我们来看看数据范围 0 ≤ n ≤ 1e4 n的范围是1e4,数组总大小为1e16,大约需要4000TB的内存空间 服务器也不带这么玩的 正解: 将地毯信息用结构体存储 struct node{ i ......
2023NOIP A层联测5
A. T1(cook) 复合题,考场上只做出来了分块的部分,没有想到那个组合数求和可以用莫队 分块部分具体不说了 ,对散块部分加权时,可以采用归并优化时间复杂度(因为我北卡长哩,卡到了晚饭之后,卡了一下午,好欸!) 现在考虑问题 \(\sum_{i=0}^{k} \dbinom{x}{i}\) 令$ ......
洛谷 P1969 [NOIP2013 提高组] 积木大赛 - 小思维
洛谷 P1969 [NOIP2013 提高组] 积木大赛 [NOIP2013 提高组] 积木大赛 题目描述 春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 \(n\) 的大厦,大厦可以看成由 \(n\) 块宽度为 \(1\) 的积木组成,第 \(i\) 块积木的最终高度需要是 ......
2023NOIP A层联测6
A. 万花筒 考虑发现 每次 相当于 把 x 和 x+d 连边 ,不难发现最后一定是一些环 证明可以看 白简 B . 冒泡排序趟数期望 写一下我曾经比较疑惑的点 为什么 inv 和 p 一定一一对应,因为我们发现只要给出我们一个 inv 我们就可以倒推出唯一确定的 p ,所以它们是一一对应的关系 这 ......