地毯noip 2011
noip前的记录
9.26 今天打的比赛一道题也没做出来，但好像大家都考得不是很好，所以也没挨吵。考试的时候窗外运动会的声音很大，一开始还觉得有些有趣，但后来发现自己没有办法专注思考题目后就很讨厌。第一题用了一个糊的做法拿了80分，被离散化卡了，不然我这个糊做法说不定能满分（。第二题一开始想的是DP，但是想的是每加一 ......
P1002 [NOIP2002 普及组] 过河卒
P1002 [NOIP2002 普及组] 过河卒 基础DP 卒只能向右/向下 由此可得转移方程 dp[i][j] = dp[i -1][j] + dp[i][j - 1] 卒不能走马能到的地方和马所在的地方 则用一个数组标记马能到的地方和马所在的地方，在经过该点的时候跳过即可 注意判断边界问题以及d ......
P1060 [NOIP2006 普及组] 开心的金明
P1060 [NOIP2006 普及组] 开心的金明 简单的01背包问题 点击查看代码 #include<bits/stdc++.h> using namespace std; int f[30005]; int main() { int n, m; cin >> n >> m; for (int ......
P3514 [POI2011] LIZ-Lollipop
很神奇的题 题意：给你一个由 \(0\) 和 \(1\) 组成的序列，给出 \(q\) 个询问，每次询问是否有原序列是否有总和为 \(x\) 的子段。 考虑递推，但是小答案对大答案的影响不好算。 考虑大区间对小区间的影响。 设当前区间为 \([l,r]\) ,总和为sum，有 \(4\) 种情况 \ ......
NOIP2023板刷记录
目录NOIP2023板刷记录CodeforcesCodeforces Round 895 (Div. 3)Pinely Round 2 (Div. 1 + Div. 2) A~ECodeforces Round 425 (Div. 2)Codeforces Round 888 (Div. 3)AtC ......
P1967 [NOIP2013 提高组] 货车运输
P1967 [NOIP2013 提高组] 货车运输 因为可能成环，这样可能导致到达点的最小权值不一，所以用最小生成树的方法重新建图 然后我是利用倍增的思想建立从i点开始，到上面点的距离ff和最小权值ww 因为最小权值不好直接建立，所以不如最后统一建立 最后就是寻找最近公共祖先的模板了 一组hack： ......
洛谷P1058 [NOIP2008 普及组] 立体图
写在前面 题解更新较少，请勿嗔怪。 本文粗鄙而简陋，要获得更好的阅读体验，请移步https://www.luogu.com.cn/problem/solution/P1058。 NOIp普及组2008的第四题，题目网站https://www.luogu.com.cn/problem/P1058。 关 ......
noip Template (to be continued)
\(noip\ Templates\) \(Part 1 \ Graph\) Toposort Dijkstra SPFA Floyd Kruskal Prim Tarjan LCA \(Graph\) 0. 链式前向星存图 int h[N], e[N], ne[N], idx; // 对于每个点k ......
NOIP训练赛#12
时间安排 7:50~8:20 写完 T1的暴力,想了一个做法但是假了 8:20~9:50 写完T2 T4的暴力,开始想T2的DP(肝了很长时间,搞了很多种假做法) 9:50~10:15 写完T3暴力 10:20~11:30 检查代码正确性以及想想剩下的几道题(主要还是想T2) 11:30~11:50 ......
NOIP 训练赛#13
时间安排 题解 T1 考虑 \(a\) 在为奇数的时候一定有一组解满足 \(a^2+b^2+(b+1)^2\) 移项,得到 \(b=\frac{a^2-1}2\),对于偶数的话考虑不断除以 \(2\) ,得到解后再乘回去即可 注意特判 \(a<3\) 和\((\log_2a)^2\in Z\) T2 ......
20230921 NOIP 模拟赛总结
时间安排 7:55~8:36 思考 T1~T4，感觉 T1 和 T3 能做，其他没思路。 8:36~8:50 写 T1。 8:50~10:00 写 T3 暴力，感觉能少建很多点，尝试写了一下，发现写不出来，忘了写特殊性质（flag1）。 10:00~11:30 写 T2 暴力，但是怎么写都写不出来， ......
P8867 [NOIP2022] 建造军营
这道题想了很久，终于想出来了，非常抽象。 经过一番无脑推导，我们发现u里面有没有军营，是否与根连通，u的子树有没有军营，……都对方案数有影响，然后我就一直修修改改，事实证明，当发现越来越多题目条件中被忽略的细节时，一定不要嫌麻烦，要从头开始设置状态。 首先我们发现，子树中有没有军营对于与子树相连的边 ......
「解题报告」NOIP 2020
总分：90 + 32 + 5 + 35 = 162。 [NOIP2020] 排水系统 题目描述 对于一个城市来说，排水系统是极其重要的一个部分。 有一天，小 C 拿到了某座城市排水系统的设计图。排水系统由 \(n\) 个排水结点（它们从 \(1 \sim n\) 编号）和若干个单向排水管道构成。每一 ......
NOIP2023-div2模拟赛4
2023.9.22 期望得分：\(100+100+50+0\) 实际得分：\(100+100+50+0\) A. 整数 我们把每一个实数转化成分数。因为小数位不超过 \(9\) 位，所以实数乘上 \(10^9\) 一定变成了一个实数，可以将一个实数 \(x\) 表示成 \(\dfrac{x \tim ......
P1075 [NOIP2012 普及组] 质因数分解
算法一 根据唯一分解定理，小于 \(n\) 的最大的能整除 \(n\) 的整数一定就是答案，可以暴力枚举。 时间复杂度 \(O(n)\)，实际得分 \(60\)。 算法二 发现算法一不能通过的原因是较大的那个质数可能的取值范围太大了。 而较小的那个质数一定小于等于 \(\sqrt n\)，我们枚举它 ......
[NOIP2012 普及组] 摆花
[NOIP2012 普及组] 摆花 [NOIP2012 普及组] 摆花 题意 有 \(n\) 个数，每种可以选 \(0 \le x_i \le a_i\) 个，问有多少种方法可以使得 \(\sum_{i=1}^n x_i = m\) 。 Solution 1. 深搜 \(dfs\) 显然可以先暴力深 ......
「解题报告」NOIP 2021
[NOIP2021] 报数 题目描述 报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数，但如果下一个报的数是 \(7\) 的倍数，或十进制表示中含有数字 \(7\)，就必须跳过这个数，否则就输掉了游戏。 在一个风和日丽的下午，刚刚结束 SPC20nn 比赛的小 r 和小 z ......
P3958 [NOIP2017 提高组] 奶酪 - 洛谷题解
题目链接 ：[P3958] NOIP2017 提高组] 奶酪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 这道题可以用并查集求解，我参考了一些大佬的题解，判断底层和顶层是否连通的条件可以为 find(0) == find(n + 1) 其中0为底层，n+1为顶层。 #inclu ......
P1024 [NOIP2001 提高组] 一元三次方程求解
因为精度要求很低，所以有一个暴力的想法就是枚举区间内相差很小的两个数然后判断。保留两位小数后记得判重。 考虑优化。发现根与根差的绝对值大于等于 \(1\) 这个条件没有利用。有了这个条件我们发现相邻两个整数之间（不包含端点）最多有一个根。 于是可以先判掉整数然后在区间内有根的两个相邻整数之间二分。根 ......
CWOI NOIP 真题训练专题
链接：link 希望能苟到这些题发挥用处的时候。 A - 排水系统 topsort。 B - 报数 埃筛。 C - 种花 模拟。 D - 涂色游戏 link E - 字符串匹配 我会 hashing！考虑枚举 \(AB\) 和 \(i\)，hash 判断是否相同，于是 \(C\) 是剩下的，可以得到 ......
NFLS-NOIP模拟 排序
题面 Link 小Z是一位热爱优化算法的同学。 一天他在研究归并排序，并想到，如果在归并排序的过程中提前return，对正确率的影响并不会很大。 于是他写了如下部分代码： void merge_arr(int l,int mid,int r)//此函数表示将S[1,mid],S[mid+1,r]两个 ......
P1056 NOIP2008 普及组 排座椅
\(P1056\) [\(NOIP2008\) 普及组] 排座椅 题解 先想一下算法：因为题目里出现了 最优解 , 最好的方案 关键字，所以一定会用 贪心。然后从题目给的样例解释可以看到：如果相邻的两行有许多组说话的同学，那么在这两行中间加一条过道是非常划算的；同理，列也是如此。 恍然大悟，只要找出 ......
P2679 [NOIP2015 提高组] 子串
注意 \(A\) 中取相同位置子串划分方式不同也算作不同的方案。 令 \(f_{i,j,l,0/1}\) 表示 \(A\) 中前 \(i\) 个字符，取出 \(l\) 个子串，拼成了 \(B\) 中前 \(j\) 个字符，第 \(i\) 个字符取/不取的方案数。 不取直接累加 \(A\) 中上一个字 ......
P1082 [NOIP2012 提高组] 同余方程
转载自这里 问题转化 题目问的是满足 \(ax \bmod b = 1\) 的最小正整数 \(x\)。（a,b是正整数） 但是不能暴力枚举 \(x\)，会超时。 把问题转化一下。观察 \(ax \bmod b = 1\)，它的实质是 \(ax+by=1\)：这里 \(y\) 是我们新引入的某个整数， ......
P2669 [NOIP2015 普及组] 金币
题目背景 NOIP2015 普及组 T1 题目描述 国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当 ......
P1009 [NOIP1998 普及组] 阶乘之和
题目描述 用高精度计算出 S = 1! + 2! + 3! + \cdots + n!S=1!+2!+3!+⋯+n!（n \le 50n≤50）。 其中 ! 表示阶乘，定义为 n!=n\times (n-1)\times (n-2)\times \cdots \times 1n!=n×(n−1)×( ......
【22NOIP提高组】建造军营(barrack)
include<bits/stdc++.h> using namespace std; using ll=long long; const ll M = 1e9+7; ll fast_pow(ll a,ll b){ ll res = 1; while(b>0){ if(b&1)res=(resa)% ......
P8868 [NOIP2022] 比赛
https://www.luogu.com.cn/problem/P8868 我学会了历史和！ 在一阵扫描线过后，你会发现，\([l,r]\) 的所有子区间的答案，就一定是扫到 \(i\) 的时候，加上 \([k,i]\) 的答案，\(k\le i,i\in[l,r]\)，然后又因为只有当 \(i\ ......
P3214 [HNOI2011] 卡农
原题 首先我们先简化一下题意。为什么呢？因为这个题如果不简化题意是不太好做的 我们考虑用二进制表示集合，这样题意为：有\(2^n - 1\)个数，我们要从中选一个大小为\(m\)的无序子集，满足以下条件： 集合中所有数的异或和为\(0\) 集合中元素不可重复 首先无序子集是吓人的，因为我们可以先考虑 ......