Noip
LY1371 [ 20231007 NOIP 模拟赛 T0 ] 十一之争
题意 给定一个长度为 \(n\) 的数字串 \(s\) 和只包含 yo 的字符串 \(t\)，yoimiya 会和 oimiya 玩 \(n\) 轮游戏，初始有一个数字串 \(x\) 为 \(0\)，每次： 如果 \(t_i\) 是 y 则是 yoimiya 操作，如果是 o 则是 oimiya 操 ......
Ynoi2012 NOIP2016 人生巅峰
Day \(\text{XXX}\)。 注意到修改是易于复合的立方操作，而且值域非常小，所以可以直接 \(O(v\log m)\) 预处理出对每个 \(i\in[0,v)\) 操作了 \(2^{j}\le m\) 次的结果，维护出每一位被修改了多少次，查询某一位的值直接倍增 \(O(\log m)\ ......
33dai NOIP2023模拟赛35 赛后总结
做题历程 8:00 ~ 8:40 写A。 8:40 ~ 9:40 看B,C想B，写B。 9:40 ~ 10:40 手玩了一下C，推出了那个规律。 10:40 ~ 11:20 写C。 11:20 ~ 12:00 看了看D，尝试写dp暴力，没空，最后随便写了写。 总结 写代码要注意细节，不然容易挂。 题 ......
2023年石门中学NOIP模拟测试(2023.10.6)
原题大战 T1 范围 \(n\leq 10^{14}\)。 不用动脑，打个表找找规律。 考虑一个数 \(x\)，在 \(1\sim n\) 中包含 \(x\) 这个约数的个数为 \(\left\lfloor \dfrac{n}{x} \right\rfloor\)，那么既然是异或，只需要判断奇偶性算 ......
【基环树 | 题解】P5022 [NOIP2018 提高组] 旅行
前言 一日知基环树弱，固补题。 关于基环树 基环树定义 一个环，环上每个点都有一颗以该点为根的树，如下图为一棵基环树 关于基环树常规思路 通常来说基环树常规思路是先处理环上树的结果，后通过树的结果来处理换上结果。 具体处理方式依照题目来定。 然而只是通常来说 因为基环树的问题灵活性强且就算没专门学过 ......
10-04 NOIP模拟赛
10-04 NOIP模拟赛 喜提80+30+10=120分 T1 水管（flow） 题目描述 某国有 \(n\) 个城市，水利调配非常有问题，这导致部分地区出现严重的缺水，而部分地区却全年洪灾泛滥。政府请你来做些调整和规划。 你打算将原有的但是已经废弃了的 \(m\) 条水管重新使用。第 \(i\) ......
2023NOIP A层联测 5
恼了，Rating 是按照比赛结束前 40 分钟排行榜算的，直接掉大分。 漂亮大厨 教主的魔法 + 高橋君 前半部分直接暴力分块就可以，整的块打标记。 高橋君莫队转移。 给定 \(T\) 个询问，对于每个询问，给出 \(n,k\)，求出 \[\sum^{k}_{i=0}{n \choose i} \ ......
NOIP A层联测5
T1 漂亮大厨(cook) 教主的魔法+高橋君=漂亮大厨。 先求出每次询问有多少个数小于等于 \(y\)，再统计答案。 区间加，区间查小于等于某个数个数，考虑分块，块内再维护一个有序序列。 区间加：散块直接加，暴力排序重构有序序列；整块打标记。 区间小于等于某个数个数：散块暴力累加；整块在有序序列中 ......
P1025 [NOIP2001 提高组] 数的划分 题解
题目传送门 本题共有两种方法，分别是递归深搜和动态规划 方法一：递归深搜 Solution 从小到大一一枚举每一个划分的数，。只要找到一种方案就记录，具体细节代码中有注释。 Code #include <bits/stdc++.h> using namespace std; int n,k,ans; ......
P1054 [NOIP2005 提高组] 等价表达式
P1054 [NOIP2005 提高组] 等价表达式 这个题在计算表达式时可能会出现高次方，比如在某一数据中就出现了 2^7^10 也就是 \(2^{70}\) 自然溢出会寄，所以要取模 自然溢出 \(80\) 分 ull quick_pow (ull x, ull p) { ull res = 1 ......
NOIP2022 比赛
Day \(2^2+3^2+4^2\)。 HNOI2016 序列的加强版。我去年怎么这么菜啊，虽然现在也是就是了。 \[\sum\limits_{[l,r]\in [L,R]}\left(\max\limits_{i\in [l,r]}a_i\right)\left(\max\limits_{i\i ......
NOIP2023 国庆集训 A 组 Day7
T1 思路:因为只有三个串故枚举其中一个为调换的串，再枚举k验证即可。 T2 思路:正着不好做，考虑反着做。这样就不会覆盖之前的。赛时没想到这个常见套路，正难则反。 T3 事实上只有一种情况，故只需倒着枚举遇到a统计答案。使用一个变量sum来记录遇到下一个a的次数 如果枚举到b,sum+=1。如果遇 ......
【题解】洛谷 P1003 [NOIP2011 提高组] 铺地毯
原题链接 解题思路 如果直接按照题意开一个二维数组来模拟每个点最上面的地毯编号，会发现所占空间最坏情况下约为 (2*105)2*4B=4*1010*4B=1.6*1011B≈149GB，程序完全无法运行。 但实际上没有必要将每一个点的信息记录下来，只需要记录每一块地毯能覆盖哪些点，再依次判断哪那些地 ......
我个人今年csp/noip赛前复习列表：
Part1、图论： 1*、3种tarjan 2、dij算法：暴力写法和heap优化 3*、Prim算法：暴力与heap优化 4、Floyd算法+矩阵 5、直径求法（dp+dfs）与性质 6、树的重心（dp求法） 7*、差分约束系统建模方式 8*、二分图相关问题 9*、Dinic算法板子（骗分） 10 ......
P5015 [NOIP2018 普及组] 标题统计
题目描述 传送门 凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？ 注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。 输入格式 输入文件只有一行，一个字符串 \(s\)。 输出格式 输出文件只有一行，包含一个整数，即作文标题的字符数 ......
P3956 [NOIP2017 普及组] 棋盘
传送门 P3956 [NOIP2017 普及组] 棋盘 不清楚曾师为什么把这个神奇的题目放在搜索 \(search\) 专栏，反正我用 \(dijkstra\) 水过去了，虽然 \(dijkstra\) 严格来说也是一种能够解决一般性最短路问题的算法。 然后考虑这道题的建图。这道题来看首先是去除魔法 ......
P1514 [NOIP2010 提高组] 引水入城
link 搜索。 首先先用 \(dfs\) 判断一下对于每一个点来说对应的可以覆盖的 \(L,R\) . 假设题目一定存在一个解，所以一定会有该点覆盖的区间连续。设该区间为 \(L,R\) ， 若不是每一个点均会被覆盖 ，那么题目不会存在任何一个解。 判断是否有解：跑一遍 \(dfs\) ，记录每一 ......
P1037 [NOIP2002 普及组] 产生数
P1037 [NOIP2002 普及组] 产生数 解法1： 利用floyd寻找每位数字可变化的点 点击查看代码 #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; string s; int d[20][20]; ......
20230712 NOIP模拟(1)
20230712 NOIP模拟(1) 目录20230712 NOIP模拟(1)总结T1 前缀和 (pre)题意分析代码T2 构造完全图 (gouzao)题意分析代码T3 独木桥 (bridge)题意分析代码另T4 放石子 (stone)题意分析 总结 暑期第一次模拟赛 预估得分：40 分 实际得分： ......
P1075 [NOIP2012 普及组] 质因数分解
因为n是两个质数的乘积，所以直接暴力枚举，只要能被整除，直接输出 因为是要求大的那个，所以从小到大枚举，输出商即可 点击查看代码 #include<bits/stdc++.h> using namespace std; #define LL long long int main() { LL n; ......
国庆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], ......
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 ......
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 ......