真题 历年noip

题目描述 对于一个 \(1\) 到 \(n\) 的排列 \(p_1, p_2, \ldots, p_n\)（即 \(1\) 到 \(n\) 中每一个数在数列 \(p\) 中出现了恰好一次），令 \(q_i\) 为第 \(i\) 个位置之后第一个比 \(p_i\) 值更大的位置，如果不存在这样的位置， ......

原题 题意 有一块 \(n\times m\) \((1\le n,m\le 14)\) 的蛋糕，每个位置上有一个权值 \(a_{i,j}\) \((1\le a_{i,j}\le 1000)\)，现在你要把它切开。每次你可以平行与某一边界把蛋糕切开，所以共有 \(n-1\) 个可以竖着切的位置，以 ......

香蕉公司 题意：维护 \(n\) 的排列 \(a_0\) 与 \(p\)。\(q\) 次操作，交换 \(a_0\) 中两个值或 \(p\) 中两个值，或者比较 \(a_x\) 与 \(a_y\) 的字典序大小，其中 \(a_{k,i}=a_{k-1,p_i}\)。 \(n,q\le10^5\)，\( ......

[NOIP2003 普及组] 乒乓球 题目背景 国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中 11 分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白 11 分制和 21 ......

视频链接： Luogu P1080 [NOIP2012 提高组] 国王游戏 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct node{ ......

1309：【例1.6】回文数(Noip1999) 时间限制: 1000 ms 内存限制: 65536 KB提交数: 24068 通过数: 10153 【题目描述】 若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个 10进制数 56，将 56加 65（即把5 ......

### Day -5 跟高二学长一起打模拟赛，然后被吊打。前两道水题甚至没看出正解，结果25+20+4=49，被机房巨佬吊打qwq ### Day-4 教练找校长帮我们申请了停课，然后我们就全天搞竞赛，然后我们化学老师兼竞赛处主任就开始发表圣经：《化竞的逃月考是明智的选择，信竞的逃月考是愚蠢的选择》 ......

[题目链接](https://www.luogu.com.cn/problem/P5021) 挺综合的一道题目。 询问最小值最大，考虑二分最小值，二分上下界是 $[最小边权,树的直径]$，但是为了方便我们直接设为 $[1,5\times 10^8]$ 即可。 考虑如何 $check$，可以采用类似树 ......

# NOIP2011 提高组 解题报告 本次测试题目： - [D2T1 铺地毯](https://www.luogu.com.cn/problem/P1003) - [D1T2 聪明的质检员](https://www.luogu.com.cn/problem/P1314) - [D2T2 选择客栈] ......

[原题](https://www.luogu.com.cn/problem/P8866) 看了三遍忘了三遍，后来决定写博客 首先看$k=2n-2$的情况，显然我们只需要空出一个栈，如果牌堆里的牌在栈顶出现过，则直接消去；如果牌堆里的牌在栈底出现，则我们把牌放到空栈中后再消去即可 然后我们考虑$k=2 ......

## T1 以下哪一种设备属于输出设备 - A. 扫描仪 - B. 键盘 - C. 鼠标 - D. 打印机 答案 **D** ## T2 下列四个不同进制的数中，与其它三项数值上不相等的是 - A. $(269)_{16}$ - B. $(617)_{10}$ - C. $(1151)_8$ - D ......

【2015统考真题】假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写方式，则能存放4K字数据的Cache的总容量的位数至少是() 正确答案：148K 有件事我一直有些纠结，那就是在计算中，诸如脏位、标记位这些位应该怎么处理。但是至少在这 ......

1. 解析： 送分题，按题意模拟即可 代码： #include<bits/stdc++.h> #define ll long long #define x first #define y second using namespace std; const int N = 39+7; int a[N] ......

如下示例： 1：共0种分解方法； 2：共0种分解方法； 3：3=2+1 共1种分解方法； 4：4=3+1=2+1+1 共2种分解方法； 5：5=4+1=3+2=3+1+1=2+2+1=2+1+1+1 共5种分解方法 6：6=5+1=4+2=4+1+1=3+2+1=3+1+1+1=2+2+1+1=2+ ......

怎么看 T3 也不是那么难，可是为啥赛时就是被卡死了[难过] 不补 $B$ 题了，ad-hoc。 ## A.种花 ### 题目描述： 小 C 决定在他的花园里种出 $\texttt{CCF}$ 字样的图案，因此他想知道 $\texttt C$ 和 $\texttt F$ 两个字母各自有多少种种花的方 ......

1. 解析： 对于一道题可以先模拟一下他的样例，通过模拟样例发现，总次数正好是每个数与前一个数的差之和，所以就可以得到O(n)复杂度的代码 代码： #include<bits/stdc++.h> #define ll long long using namespace std; const int ......

咕咕咕的东西总是要补的。 ## A.报数 ### 题目描述： 报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数，但如果下一个报的数是 $7$ 的倍数，或十进制表示中含有数字 $7$，就必须跳过这个数，否则就输掉了游戏。 在一个风和日丽的下午，刚刚结束 SPC20nn 比赛的小 ......

1. 错误原因：想的太复杂 正解： 10^k轮，会使x号小伙伴变到(x+m*10^k)%n号，直接套用公式 代码： #include<bits/stdc++.h> #define ll long long using namespace std; ll n,m,k,x; ll quickPow(ll ......

一.7. 错误原因：不知道 解析： 快速排序在理论上最低的时间复杂度为O(n),但实际最低的时间复杂度为O(n log n) 二.1. 错误原因：漏项了 解析： 这棵树最少有12层，但题目是问可能是几层，所以还可能是2011层 5. 错误原因：漏了一种情况 解析： 这道题的树有两种，所以答案也有两种 ......

一.3. 错误原因：忘记了 解析： Intel是全球最大的CPU厂商，AMD是世界上首个研发出7纳米CPU的厂商 6. 错误原因：忘记了 解析： ENIAC是世界上首台计算机，属于第一代计算机，即电子管计算机 10. 错误原因：选项理解错误 解析： A由蝙蝠，发明雷达是正确的，B因特网的发明与蜘蛛网 ......

### D2T3 树的重心 当年我做这道题时还太嫩了，只能想到暴力。其实如果会了更高的科技这道题只要稍微对暴力优化一下就能 AC（我也不会含泪拼满暴力了）。 废话不说了，暴力的思路就是枚举每一条边然后求两个子树的重心。 直接求重心的复杂度是 $O(n)$ 的，我们考虑优化到 $O(\log{n})$ ......

1.计算系数 题目：https://www.luogu.com.cn/problem/P1313 解析： 直接套用二项式定理，使用快速幂计算组合数 代码： #include<bits/stdc++.h> #define ll long long using namespace std; const ......

# [NOIP2012 提高组] 疫情控制 ## 题意： 给定一棵树，边有边权，有一些结点上有军队（可能不止一支），军队可移动。求最短的时间，使得军队移动后，从根到每个叶子结点的路径上都有军队驻扎。军队可以同时移动。 ## 思路： ~~咳咳咳我当时读错题了以为这题虚高，然后才意识到边境结点只有叶子结 ......

# [NOIP2013 提高组] 华容道 ## 题意： 一个棋盘上，每个格子上都有一个 $1 \times 1$ 的棋子，有些棋子固定，剩下的可以移动。棋子只能移动到空白的格子里。$Q$ 次询问，每次给出空白格子的位置、目标棋子的位置以及终点的位置，问把目标棋子移动到终点的最小步数。无解输出 $-1 ......

[洛谷链接](https://www.luogu.com.cn/problem/P1003) [FZQOJ](https://qoj.fzoi.top/problem/167) ##First 这一题的题面看似很长， 但是实际上归纳下来可以总结为： (1)：告诉你有i张地毯 (2)：第2行~第i+1 ......

## T1 幸运数字Ⅱ 有 $Q$ 个询问,每次给定一个区间 $L,R$ 求区间内满足如下条件的 $x$ 的个数: $x$ 为质数或者 为两个质数的积 **【数据范围】** $L,R\leq 10^7,Q \leq 10^5$ ### 题解 欧拉筛预处理出 $10^7$ 以内满足条件的数的个数,做一 ......

# P1013 [NOIP1998 提高组] 进制位 [P1013题目传送门](https://www.luogu.com.cn/problem/P1013) 这是一道提高+/省选-的蓝题，~~有亿点点难度~~，我们先分析一下。 ## 分析 字母的数量等于进制的大小，判错的时候，可以看一下那个表格右 ......

## T1 在 8 位二进制补码中，10101011 表示的数是十进制下的 - A. 43 - B. -85 - C. -43 - D. -84 答案 **B** 反码 +1 -> 补码 10101011 是补码，第一位是 0 则表示正数，1 表示负数 10101011-1=10101010，得出对 ......

## T1 探险  **【数据范围】** $1\leq n,m,k\leq 10^3,1\leq x_1,x_2 \leq n,1\leq y_1,y_2\leq m$ ## ......

[题目链接](https://ac.nowcoder.com/acm/problem/16610) # 题目 **题目描述** Hanks博士是BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考一个有趣的问题。 今天在课堂上，老师 ......