前言
中考完第二天就开始了集训，说实话，是既兴奋又紧张。一切似乎都是新的，让第二次来的我充满新鲜感（第一天不知道机房位置，还是跟着同学去的）。
集训中的感想
身边都是很优秀的同龄人，在一起刷题感到很有斗志，果然在学校刷题和在家里刷题是完全不同的。
部分题目总结
真题练习（2020.7.22）
-
这五道题是第一天的练手题，也是历年的真题，难度在接受范围以内，我之前除第五题都做过。
第五题还没有做，先 gugugu
单调队列（2020.7.22）
-
这六题是第一天所讲的单调队列题目，其中有版子题，也有根据单调队列优化 dp 的内容。我还不大会优化 dp，先放出模板题的代码。
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
using namespace std;
const int N = 2*1e6+5;
int n,m;
struct Node {
int val,pos;
}e[N];
deque<Node> q;
int ans[N];
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%d",&e[i].val);
e[i].pos=i-1;
}
ans[0]=0;
for(int i=1;i<=n;i++) {
//保证是个队列 且保证单调性
while(!q.empty()&&q.back().val>e[i].val)
q.pop_back();
//新元素入队
q.push_back(e[i]);
while(!q.empty()&&q.front().pos<i-m)
q.pop_front();
ans[i]=q.front().val;
}
for(int i=0;i<n;i++) printf("%d\n",ans[i]);
return 0;
}
字符串问题（2020.7.23）
-
大都不会做，可以说是找到软肋了。
树状数组
-
除了三元上升子序列全部都做完了，三元上升子序列只打了暴力。
给出树状数组知道的使用方法
单点查询 区间查询 单点修改 区间修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21inline int lowbit(int x) {return x&-x;}
void add(int x,int k) {
for(;x<=n;x+=lowbit(x))
t[x]+=k;
}
//单点加上 k
int ask(int x){
int ans=0;
for(;x;x-=x&-x)
ans+=t[x];
return ans;
}
//单点查询
//对于区间修改，我们可以使用差分来完成
//add(x,a[i]-a[i-1])
//此时将 l~r 全部加上 k 只需
//add(x,k) add(y-1,-k)
//对于区间查询，我们可以使用前缀和来完成
//ask(r)-ask(l-1)
Nauuo 的模拟赛（2020.7.24）
这就是要补的题了