梭在前面：
1.这是一个类似题解的博客而不是游记，所以就不花大篇幅来说考场外的事了。
2.WH这次集训感触挺大，题的质量参差不齐但总体不错，题的描述都传到个人题库了，但秉承良心终究没有放样例_(:з」∠)_
3.如果没有参加只是过来看个热闹的大佬（我觉得没有），我也会将NOIP相似的题型搞一个整理，这样也能顺便理一下考试思路。
4.每道题的标题“第K题”“丑陋的代码”都可点击进入。
$DAY1^A_M:$
早上六点起床八点考试的经历总算领会到了，到了考场还是困得一批。
打开第一题：
emm？这题啥玩意啊，D1T1不应该是个暴力或膜你吗，这个长得像DP是啥玩意？
于是完美地避开了正解，看到暴力分有不少于是打了暴力就滚粗了。。。
就算再难既然是D1T1那一定有很巧妙的做法啊！一上来就打个暴力是啥意思！？总是要动动脑吧。
正解也很简单：既然字符串长度<50，于是对于每一个字符暴力搜一遍就没了，就没了。。。
_第一题丑陋的代码_
代码都是异常的短啊_(:з」∠)，感觉自己完蛋了。
看了下第二题：
第一眼就知道是个分治加组合数，把桃子两两距离走法算出来，乘法原理带一下就OK了，为此激动地一批！
然后就直接滚去打求逆元板子了_(:з」∠)，结果发现模数不是质数用不了。
想起之前好像做过一个类似的一道省选题，它是用$CRT$加上$LUCAS$解的，而且那道题还没有出现$pi^k$的形式，我不相信NOIP有那么难于是就没打，然后就暴力分滚粗了_(:з」∠)_
最后正解说只要求个分解质因数然后算一下就行了，高二巨佬考场AC，我考后怎么打都超时，然后就没管了。
_T2丑陋的代码_
第三题：
一道图论而且还是棵树，最近$NOIPtg$好像十分喜欢考的样子。。
智障的我只敲了部分分就去肝第二题了。。。明明可以乱搞拿更多分的。
30%数据就是一棵最小生成树，如果包含了村民就是一个完全图，但看到女巫找到深度为2的点就不好搞了。。
正解说的是一个星形图：
如果1号点是女巫，那他一定可以通过星形点到任意点去，且距离为2.
证明最优性如下：
1.由于已经讨论过村民的情况，所以此图只包含膜法师和女巫。
2.由于任何一个人种要么没有要么有两个，不妨设1号点与2号点间直接连起来距离更优，则将2与*号点断开后，另一个女巫到2号点距离会从2变为3，不成立。
大概就是这样吧，NOIP好像没考过啥分类讨论的题，但做一做总是好的。
T3丑陋的代码
$DAY1^P_M:$
第一天睡了7天来唯一一次午觉。
第一题：
模拟水题，终于跟$NOIPtg$接轨了（滑稽）
是个人都A了，不讲。
第二题：
一瞬间产生了会A了此题的念头。
数据是N<=200，如果小一点的话可以暴力枚举$O(N^5)$过掉，于是我们想想能不能手动减少数据。
先把前两个序列处理一下，将sum存到一个map里，在将后三个序列处理一下，查询对应的map值有没有标记，标记了就输出YES，期望时间复杂度$O(T*N^3*logN^2)$，大概在$10^7$左右，按道理是能过的。
于是就像意料之中的一样，炸了。。
事实上分成2组还不是很优，将5个序列分成（1,2,2）三组，先处理2个2个序列的和分别存到一个新数组里排好序。然后再枚举最后一个序列，用双指针逼近正确答案。
T2丑陋代码
说不定也可以先unique一下两个新数组，然后用个二分在最后一个序列找答案，但是此题照样原地爆炸（后面有道题我这样过了QAQ）。
第三题：
做到这题的第一反应：哇这题不水吗！求子串直接贪心+二分找到第一个大于2048的点，把后面全部计算上不就好了吗？
于是开开心心地打完这道题然后一辈子没有再理他，然后考试结束，听到了求子序列的消息。。
子序列可以不连续啊！有一个爆炸我全部玩完，但幸好最后还是捞到点分。。
先谈谈贪心的性质：
- 由于是合并成2048，所以只要$log_2(a_i)$不是整数那一定就没用了，记录一下没用元素的个数k，到最后由于这些选不选都无所谓，所以直接乘$2^k$即可。
- 分析剩下2的幂的元素，我们可以贪心地得出结论：只要任意数量相加大于2048，那一定是一组解，因为如果没有合并成2048的话，最大值即是$1024+512+256..+2+1=2047$。
- 问题就变成了在一个数组里任意挑选几个数，想了想线段树发现是错的，于是只好按正解打了一个类似背包的东西了。
设$f[i]$为和为i时的个数，超过2048就按2048算，于是得到
$f[(i+a[i]>=2048)?2048:i+a[i].]+=fi$
初始的时候$f[a[i]]++$记录一下即可，其实之前做过类似的序列求和题目就挺好想了。。
T3代码：点我
D1就是说了一下比较基本的操作，感觉没啥难的但考的就是不好，还需要多多总结。。
$DAY2^A_M:$
第一题
过水，就直接说意思了：给你一个序列(n<=10^7),求前m(m<=100)大的数的和。
没啥讲头，直接上一个优先队列保留前10000~50000个数，每次循环多少次更新一下就好了，做法有点暴力但还是过了。。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#include <iostream>
#include <queue>
#define ll long long
#define mo 1000000000
using namespace std;
int n,m;
ll x,y,maxx,size,sum;
priority_queue<int ,vector<int> ,greater<int> > q,q1;
void check()
{
size=maxx=0;
while (!q.empty()) {
ll k=q.top(); q.pop();
if (size<=m)
{
size++; q1.push(k); maxx=max(maxx,k);
}
}
while (!q1.empty()) {
int k=q1.top(); q1.pop(); q.push(k);
}
}
int main()
{
cin>>n>>m;
cin>>x>>y; ll a=x;
for (int i=1;i<=n;i++){
if (i%10000==0) check();
if (size>m&&x>maxx) { x=(y*x+a)%mo; continue;}
size++,q.push(x),maxx=max(maxx,x); x=(y*x+a)%mo;
}
int t=0;
while (t<m)
{
int k=q.top(); q.pop();
sum+=k; t++;
}
cout<<sum<<endl;
}
第二题：
看到期望本能地躲避了。。。事实上只是一个简单的位运算模拟，是个人都A了。。
NOIP靠这种题目放在D1T2的可能性还是有的，毕竟期望不是不考而且模拟还是重头。
对于位运算的一个基本事实：
每一位的位运算答案都是独立的，不会影响其他位置。
我们可以通过算出各个数位上的答案，最后通过乱搞以2的幂的形式再加回去，就可以得到最终答案了。
那么如何计算每一个数位上的期望呢？
回归最简单的期望题，可以用DP求解。
设$f[i]$为到第i位的期望答案，发现只需考虑当前位置和运算符即可，就分类讨论下。。
但是不知道为啥，不论位数多大都要从数据范围2^20计算，不然就爆炸（貌似是因为xor会影响前面的原因）。。
第二题丑陋的代码
第三题（划横线以示注意）：
题目并无特殊，但是想分享一下考试时的一些经历警醒自己。
考试到最后只剩40分钟左右，打完正解估计是不可能了（LZ除外），于是本蒟蒻开始狂敲暴力：对于每一次询问都把他那条链截取下来方便求解，按照此做法可得60分。
但是我之前狂刷二分题，考试时候就脑抽，认为如果二分答案他的最大天数，就可以再次贪心地求出当前情况每天可走最大路程，但明明可以直接在链上贪心走最大的路程，就直接算出天数了。。
相当于强行将算法翻转了一下，不仅没有减少时间复杂度（$O(n)–>O(nlogn)$），而且贪心最大天数完全没有贪心路程编程复杂度简单，导致最后二分还是打炸了。。一位初三巨佬思路和我一样，但他直接贪心路程求解，于是暴力得60，我只有20。
不要因为满足什么算法的性质就直接往上面套，可能会有更加简单且思维性更低的算法可以更好求解。
我贪心的程序
$DAY2^P_M:$
第一题
二维前缀和裸题，是个人都A了，再次不赘述。（WH某位巨佬居然写二维树状数组！虽然最后炸了。。）
第二题
一个通常的思路就是：如果一个题目里面让你维护两组数据且均对答案有影响，正常思路就是先使一个序列有序，再通过另一个序列进行求解，数学上叫控制变量法，几个月前做过类似的题，又忘了。。
看到题的第一眼就有种隐隐约约的感觉：桃子越容易烂的应该先摘。贪心还可以进一步证明：
- 如果di>dj在k和k+1天分别摘了j和i桃
- 两种不同摘法的代价是$ai+aj-(k-1)*di-k*dj>ai+aj-(k-1)*dj-k*di$
- 等价于$-k*di-k*dj+di>-k*dj-k*di+dj$
- 等价于$di>dj$
- 所以先摘i再摘j更优。
于是就给di排个序吧，拍完序就可以用DP求解了，DP式子就是很基础的那种，f[i][j]表示前i棵树摘了j棵，由于确定了di从大到小，所以求出来一定是最优的，考试时没排序疯狂证明他的后效性于是又暴力滚粗。。
详细式子见程序，注意的是如果苹果烂成负数的话要注意标0。
T2丑陋程序
第三题鸽了，DP是人写出来的啊
我校大佬贪心80
$DAY3^A_M:$
第一题：
很经典（？）的问题，NOIP初赛考过，但我以前不知道。。。
求一个区间的第K大值不需要排完整个序列，只需要模拟快排中的一部分，找到任意一个元素在序列里的位置，然后分治答案就行了。
说是这样说，但是细节实现很难受，以前没写过考场上真的写不出来（除了某些大佬厚颜无耻机智的调用STL的kth函数20号秒A），所以在程序里打了详细的注释，有空就看看。
丑陋的代码：
1 | #include <bits/stdc++.h> |
第二题：
我连暴力都不会打了。。
一个看似背包的问题，但容量10^8，DP还是记忆化搜索都要依赖容量的，所以直接gg。
但是一个最简单的算法— — 暴力搜索只需要知道n个物品选不选的情况即可，所以考虑如何优化暴力。
看到n很小，只有40，但$2^n$的暴力还是爆炸，于是想到折半搜索（没想到）
先将序列分为两半，直接记录每种情况的答案，大概也就$2^20$左右的情况，然后在两个序列中找两个元素相加，使得小于m时最大— —二分喽（双指针好像更快，但是本蒟蒻觉得打个二分编程复杂度简单）
甚至可以unique减少重复的元素，详细地看程序。
T2丑陋的程序
第三题
依旧是CRT加卢卡斯，之后有空再写。
$DAY3^P_M:$
第一题
NOIP膜你赛考省选题，还是蓝的。
虽然标的是蓝题，但只要掌握了一些依赖背包的食用方法，此题还是很简单的。但依赖背包被老师劝退了
不妨看一下NOIP的原题，依赖背包的实质就是原本每次转移一个物品的价值变为转移一个物品及其附加物品的价值。
对于本题，我们按斜率k存储物品，那么同k时后来挖到的金子就是附加的物品，由于转移同斜率物品的先决条件是把在他之前此斜率出现的金子全挖走，我们可以在每一个K上做一个前缀和，转移的时候找其中最优的一个存在f[j]里即可。
具体代码
第二题：
3天来唯一的数据结构就打爆了（好像博客里面就没说过什么题对过）。
题目规定颜色不超过30组，疯狂暗示$2^{30}$不爆，考试十分迷糊的我理解成了数组范围所以觉得不可做就打了一个维护30大小桶的线段树，于是炸到暴力分。。
其实直接int存储，表达成二进制后每一位表示当前颜色有没有被覆盖，用按位或正常转移即可。
不知道还能怎么讲了。。上代码
于是前3天题目除了一些T3大部分都总结完了，这三套卷子涉及了一些玄学的题目以及玄学的解法：
- n个数求任取数大于k的方案，
- 折半搜索，
- O(N)求序列第K大，
- 控制变量等。
有几题考的是位运算，位运算NOIP好像没怎么考过，但数位DP还是有的，没准今年就考裸的位运算操作了呢$QwQ$？？
数据结构考的线段树，根据去年的尿性来看数据结构再考的可能性挺大，就是不出也能数据结构骗分。
数论就是CRT和组合数基本运用，NOIP喜欢第一题搞一个简单的数学题让你推，而且本蒟蒻就数学不好。。可以多找些题练练。
DP的话是NOIP重头戏，依赖背包虽是原题但出的吼，其他的话用DP骗个部分分也是可以的。
图论就考了一个树，可见他的重要性，虽说考DIJ堆优化的几率更大但是后面的题还是有谈到的。