回文1309 noip 1999
国庆NOIP储备营讲课笔记
Day1（基础算法） 讲师：余快 枚举法 例题1 给定一个数 \(x\)，判断 \(x\) 是不是质数。 朴素算法：枚举 \([2,x−1]\) 之间所有的整数 \(i\)，逐个判断 \(x\) 是否被 \(i\) 整除，若都不能整除则 \(x\) 是质数，时间复杂度 \(O(x)\)，搞个 \(1 ......
解题报告 P2680 [NOIP2015 提高组] 运输计划
P2680 [NOIP2015 提高组] 运输计划 题目链接 LCA的题，需要求最大值最小，考虑二分答案。 先存储每组询问的距离。 然后二分答案时找出所有比当前答案长的距离的重叠部分。 在这些重叠部分中找出权值最大的边。 判断最长链减去这条边是否小于等于当前答案。否则返回0 代码如下 /* * @A ......
济南 CSP-S NOIP 储备营笔记
Day 1 上午 —— 基础算法 模拟 + 枚举 小前言 碰到题目不会做 -> 先写个模拟压压惊（） 枚举法 枚举的思想是不断地猜测，从所有可能的集合中一一尝试，然后再判断是否符合题目的条件。 单独提到枚举时我们往往认为这是一个暴力做法，但事实上并非如此，恰当的枚举往往会是解题的关键步骤。 例题 1 ......
P5020 [NOIP2018 提高组] 货币系统
#include <cstdio> #include <algorithm> using namespace std; const int N = 105; const int A = 25005; int a[N]; bool dp[A]; int main() { int t; scanf("% ......
P1941 [NOIP2014 提高组] 飞扬的小鸟
#include <cstdio> #include <algorithm> using namespace std; const int N = 10005; const int M = 1005; const int INF = 1e9; int up[N], down[N], low[N], ......
PAM+回文串border理论
PAM板子 #include <bits/stdc++.h> using namespace std; const int maxn = 300000 + 5; namespace pam { int sz, tot, last; int cnt[maxn], ch[maxn][26], len[m ......
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 ......
力扣刷题笔记-05 最长回文子串
05 最长回文子串 半山腰有点拥挤，你要去山顶看看。 中心扩展法 什么是回文 从左边出发，字符的顺序和从右边出发是一样的，比如aba，abba。那么基于这个理论，我们就可以想到解决方案： 找一个中心点，向两边出发，左右两边各移动一位，如果相同就证明是回文子串，不相同就停止，找下一个中心点 中心点 我 ......
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]两个 ......
回文数
回文数 描述 若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。 例如：对整数56，将56加65（即把56从右向左读），得到121是一个回文数。 又如：对于整数87： STEP1：87+78= 165 STEP2：165+561= 726 STEP3：726+627= 13 ......
P1056 NOIP2008 普及组 排座椅
\(P1056\) [\(NOIP2008\) 普及组] 排座椅 题解 先想一下算法：因为题目里出现了 最优解 , 最好的方案 关键字，所以一定会用 贪心。然后从题目给的样例解释可以看到：如果相邻的两行有许多组说话的同学，那么在这两行中间加一条过道是非常划算的；同理，列也是如此。 恍然大悟，只要找出 ......
P2679 [NOIP2015 提高组] 子串
注意 \(A\) 中取相同位置子串划分方式不同也算作不同的方案。 令 \(f_{i,j,l,0/1}\) 表示 \(A\) 中前 \(i\) 个字符，取出 \(l\) 个子串，拼成了 \(B\) 中前 \(j\) 个字符，第 \(i\) 个字符取/不取的方案数。 不取直接累加 \(A\) 中上一个字 ......