铅笔p1909 noip 2016

这篇博客是第二天赛时写的。（恼） T1 数学题。 肯定是想把 \(k\) 质因数分解，然后找一找规律，发现对于一个最小的 \(n\) 一定不包括除了 \(k\) 有的质因子以外的其他质因子，因为其他质因子对是不是 \(k\) 的倍数没有用。 \(n^2\) 相当于把 \(n\) 的所有质因子的指数乘 ......

NOIST2023 涂色游戏 对于每一行每一列记录一个时间戳，对于每个格子颜色即为时间戳较大的颜色。 幂次 考虑暴力，我们发现 \(O(\sqrt[3]{n})\) 的复杂度是可以接受的，所以可以枚举 \(\sqrt[3]{n}\) 内的数然后暴力往上乘，可以用一个 unordered_map 判重 ......

T1T2送的。 T3貌似有神仙优化方法，但是题解给的是容斥。（既然不好直接求满足条件的方案，就减去不满足条件的方案）。 T4的贪心就是：如果当前能走，就直接走，不然就向上或者向下走到第一个能走的地方。 证明： 假设之前贪心的方法能够取到一个最优解。 任意的走法为红色，贪心为蓝色。 然后你就发现可以通 ......

NOIP2023模拟9联测30 T4 金牌 LCA 还能 \(O(1)\)…… 思路 思路非常简单，可考试就是想歪成统计指数了…… 将一条穿过 \((x,y)\) 的路径 \((u,v)\) 分为 \(u \to x \to y \to v\)，所以说对答案的贡献为： \[2^{dis(u,x)+d ......

NOIP2023模拟9联测30 T3 高爸 三分啊，三分…… 思路 设现在的平均力量值为 \(x\)，大于 \(x\) 力量值的龙有 \(n\) 条，小于等于的龙有 \(m\) 条，花费为： \[a(n \times x-\sum_{i=1}^{n+m} p_i (p_i>x))+b(\sum_{i ......

虽然是正解，但是我三分敲挂了，悲 A. 上海 对于每个数，\(O(\sqrt n)\) 地分解质因数，对于每一个质数，符合要求的 \(n\) 最小需要为 \(\lceil num \rceil\)。 如果乘完后的 \(n\) 等于原数，那么无解。 code #include<bits/stdc++. ......

NOIP2023模拟9联测30 B. 华二 目录NOIP2023模拟9联测30 B. 华二题目大意思路code 题目大意 有一个数列 \(A = (a_1 ,\cdots ,a_n)\) ，其中 \(1\le a_i \le 9\) 。对于其中相邻的两项 \(a_i , a_{i + 1}\) ，满 ......

NOIP2023模拟9联测30 D. 金牌 目录NOIP2023模拟9联测30 D. 金牌题目大意思路code 题目大意 有一棵 \(n\) 个节点的树。 假设一条路径的长度为 \(d\) ，那么这条路径的价值为 \(2^d\) 现在有 \(k\) 个询问，每次给定两个整数 \(x , y\) ，询 ......

题目描述 参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 nn 个深埋在地下的宝藏屋， 也给出了这 nn 个宝藏屋之间可供开发的 mm 条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋 ......

11-02 NOIP练习赛 为什么休息的天还要打练习赛，这不公平！！！！！！！！！！ oh no！ 但是三道题确实挺简单，也少见的很有意思。 [USACO23OPEN] Milk Sum S 题面翻译 给定数组 \(a_1,...,a_N\) 在数组中依次选出一个元素构成排列 \(b_1,...,b ......

Description 在石头剪刀布中，一共有三种手势：\(R(Rock), P(Paper), S(Scissors)\)，其中 \(R\) 能赢 \(S\)，\(S\) 能嬴 \(P\)，\(P\) 能赢 \(R\)。 现在，我们定义 \(w(x, y)\) 是 \(x\) 和 \(y\) 中获 ......

破釜沉舟了。 最前線飛ばせ僕たちは，星もない夜 ただ東を目指して行く DAY -16 （11.1） B站6级号了。（仅仅靠点赞投币的经验攒出来的，可见我有多摆烂） DAY -15 （11.2） 打得最逆天的一场正睿，T1做了快2个小时才过，T2简单容斥题想了一个多小时不会。 最后一小时打完T2T4暴 ......

1到50列表，阶乘之和 S=1!+2!+3!+⋯+n!（n≤50） 1::1 2::3 3::9 4::33 5::153 6::873 7::5913 8::46233 9::409113 10::4037913 11::43954713 12::522956313 13::6749977113 ......

10-30 NOIP模拟赛 今天分数还看的过去，只是第二题没有正解，第三题没有35我表示很伤心。必须继续努力，保持内心纯净，心无杂念，知行合一，摒除恶念。 100 + 80 + 5 = 185 芜湖！ T1 新的阶乘(factorial) 题目描述 我们定义 \(f(x)=x^1×(x−1)^2×( ......

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3+10,inf = 0x3f3f3f3f; char A[N],B[N],C[N]; char words[N]; int cnt; ......

100+100+100+80，T4 \(O(n\log n)\) 没卡过，赛后没改 \(O(n)\)，加了 WX 超级快读。 为啥放了套简单题，题目出处好像是 22csp 7连 day1。 A.上海 对 \(k\) 质因数分解，\(k=\sum\limits p_i^{c_i}\)，使 \(n\) ......

2023NOIP A层联测22 差后队列 挺有意思的期望题，题解做法应该是 DP，但是我又双叒写出奇怪的做法…… 思路 除去最大值外的元素个数的倒数就是这一轮取到某个数的概率，而最大值是特殊的情况，在被替代之前或作为最后一个数被弹出之前，不参与计算。 对于操作 0 的输出和操作 1 的输出分开处理。 ......

10.31 NOIP模拟测试 赛时 先看题，T1 有一点思路，T2 是我不擅长的期望计数，但看起来还是可以试一试，T3 数据范围看起来是 NP，想了一下搜索但没有一下想出来，T4 一眼大数据结构，最后做。 T1 想了一下前缀和，去上了个厕所，中途想出后缀和和前缀和比较，回去写看打样例发现不仅要比较相 ......

思路 题目大意是：把一棵树按深度分层，每一层断掉一条边，是剩下的节点数最小。 其实，我们可以将问题转换为断掉的节点数最多。 首先，贪心不可行，很容易被卡。 因为数据只有300，直接搜索就行。 搜索时一层一层搜，枚举断掉哪条边，并标记后代。 #include<bits/stdc++.h> using ......

\(100+100+40+0\)，T3 卡时没卡对挂了 \(20\)。 后来发现赛时 T3 是时间复杂度和正确性都是对的，只是常数大导致我以为它跑不出来。 A.集合 给定一个序列，求有多少个子区间满足这个区间的数的集合的所有值域连续段长度都不超过 \(k\)。 答案满足单调性，双指针统计答案，权值线 ......

NOIP2023模拟8联测29 C. 蛋糕 目录NOIP2023模拟8联测29 C. 蛋糕题目大意思路code 题目大意 你现在得到了一个二维蛋糕，它从左到右可以分成 \(n\) 列，每列高为 \(a_i\) 。对于每一列，又可以从下到上分为 \(a_i\) 块，并且最上面一块权值为 \(1\) ， ......

[HNOI2016] 网络 题目描述 一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据的交互时，数据会经过连接这两个服务器的路径上的所有服务器（包括这两个服务器自身）。 由于这条路径是唯一的，当路径上的某个服务器出现故障，无 ......

T1 一眼序列分治，然后假了。。。。 可以发现：对于序列不是好的，当且仅当存在 \([l,r]\) 中的整数都在 \(r-l+1==k-1\) 发现规律，一定是大的区间容易不好。 不知道用不用可持久化并查集。 上个厕所，觉得权值线段树能行，先写QAQ。球球了，不要假啊QAQ T4 打个暴力先，怎么 ......

[SDOI2016] 储能表 - 洛谷 题目详情 - [SDOI2016] 储能表 - BZOJ by HydroOJ 一道很好的数位 dp 题 不过这题有一个比较有意思的性质：当 \(n,m\) 为 \(2^k\) 的形式时，最终得到的数组对每一行排序后为 \(0 \sim m-1\) 的排列，如 ......

NOIP2023模拟8联测29 B. 差后队列 题目大意 大意差后队列为一种数据结构，支持两种操作： push 插入一个数 pop 随机删除一个 不是 最大值的数。如果只有一个数则删除该数 给定操作序列，求每次删的数的期望，以及每个数期望被删的时间，答案 \(\mod 998244353\) 思路 ......

A. XOR Equation 最低位没有加法进位产生的影响，考虑从低位向高位 dp。 设 \(f_{i,0/1}\) 表示正在考虑第 \(i\) 位，前 \(i-1\) 位都满足限制，有无进位的方案数。 转移的时候枚举这一位两个数分别填 \(a,b\)，\(x_i\) 表示 \(x\) 在二进制下 ......

这个应该是大部分人学off-by-one的第一个例题，当时笔者也是只在本地去测试，最近重温又发现了一些有趣的东西 这里有个off-by-null,可以看到14行 如果i = a2就break，再让*a1 = 0,比如我们的size为10，正常我们被允许输入10个字节的数据，这里的i是从0开始的，所以 ......

构造题注意事项 一定要转化思路，不要总是盯着一个特殊点； 多注意特殊点的变化： 例如 P7115 [NOIP2020] 移球游戏，如果总是盯着一个全不是 \(c\) 的栈和一个空的栈对其他栈操作，就会使得步数要翻一倍，然而如果只操作一半，那么此时可以用当前栈作为新的空栈，原来的空栈作为新的全不是 \ ......

T1 看到了有向无环图，很容易让人想到拓扑。 设 \(f_i\) 表示经过节点 \(i\) 路径，这条路径上的关键点个数的最大值。 如果有一个点满足 \(f_i=k\)， 那么答案就是 \(Yes\)，否则就是 \(No\)，这个显然。 转移就是从所有能到达 \(i\) 的节点转移，取 \(\max ......

其实也可以说是承接日记写的吧 Day - 1 上午随机跳了两道题刷刷信心，顺带学了一下康托展开（之前不小心跳掉了） 下午帮忙搬了一下电脑，复习了一下BFS 晚上打了几把扫雷（输麻了），看dyx2021打扫雷看呆了 看了几道经典例题和博客 复习了一下模板，做了道随机跳的题，没开 long long 挂 ......