这次意外考得不错…但是并没有太多厉害的地方，因为我只是打满了暴力【还没去推T3】
第一题折腾了一个小时，看了看时间先去写第二题了。第二题尝试了半天还是只写了三十分的暴力，然后看到第三题是期望，本能排斥，跑回去写第一题了。
手画第一题的样例2，指着图片一点一点调试发现思路中间就错了，然后开了份新代码重写去了，好在原来那份里大部分东西都用得上。按数据点骗分，推出了y=2的性质，最后居然多拿了25分。
只剩下二十分钟了，第三题直奔数据范围。把k=2的分手推出来，然后非常没有梦想地选择搜索过小于8的数据。我觉得自己推不出来，概率和期望我就是学不会，好在也没有去推，不然大概真的就算推出来也想不完…大概是我算错了复杂度，居然多给了我五分。
期望得分120，实际得分75+30+45=150。
想起来设密码，那我就直接贴题面了。
T1：
题目描述
辣鸡ljh NOI之后就退役了，然后就滚去学文化课了。
然而在上化学课的时候，数学和化学都不好的ljh却被一道简单题难住了，受到了大佬的嘲笑。
题目描述是这样的：
在一个二维平面上有一层水分子，请问形成了多少个氢键？
这个二维平面可以看做一个类似棋盘的东西，每个格子可以容纳一个水分子，左下角的格子为(0,0)，这个格子右边的格子为(1,0)，上方格子为(0,1)，以此类推。
辣鸡ljh当然不会做了，所以他来求助JeremyGou，JeremyGou一眼就看穿了真相，并想用这道题来考一考正在做NOIP模拟赛的你。
注：在本题中，我们认为一个水分子能与和它曼哈顿距离为2且直线距离小于2的其他格子形成氢键。
输入格式
一个整数n
接下来n行，每行给出四个整数x1,y1,x2,y2
表示以(x1,y1)为左下角,(x2,y2)为右上角的矩形中每个格子都有一个水分子。
给出的所有矩形没有交集。
输出格式
一个整数，表示氢键的数量。
数据范围与提示
子任务
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
long long sum,maxx;
struct node{
long long x1,y1,x2,y2;
}a[];
bool cmp(node x,node y){
if(x.x1<y.x1)return true;
else if(x.x1==y.x1){
if(x.y1<y.y1)return true;
else return false;
}
else return false;
}
int main()
{
scanf("%d",&n);
if(n==){
long long x1,y1,x2,y2;
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
printf("%lld",(x2-x1)*(y2-y1)*);
return ;
}
for(int i=;i<=n;i++){
scanf("%lld%lld%lld%lld",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
sum+=(a[i].x2-a[i].x1)*(a[i].y2-a[i].y1)*;
}
sort(a+,a+n+,cmp);
for(int i=;i<n;i++){
for(int j=i+;j<=n;j++){
if(a[j].x1>a[i].x2+)break;
if(a[j].y2<a[i].y1-||a[j].y1>a[i].y2+)continue;
if(a[j].x1<=a[i].x2){
if(a[j].x1==a[i].x1){
if(a[j].x2==a[i].x2)sum+=(a[j].x2-a[j].x1)*;
else if(a[j].x2<a[i].x2)sum+=(a[j].x2-a[j].x1)*+;
else sum+=(a[i].x2-a[i].x1)*+;
}
else if(a[j].x2==a[i].x2){
if(a[j].x1>a[i].x1)sum+=(a[j].x2-a[j].x1)*+;
else sum+=(a[i].x2-a[i].x1)*+;
}
else if(a[j].x2<a[i].x2)sum+=(a[j].x2-a[j].x1+)*;
else sum+=(a[i].x2-a[j].x1+)*;
}
else{
if(a[j].y1>a[i].y2||a[j].y2<a[i].y1)sum++;
else if(a[j].y1==a[i].y1){
if(a[j].y2==a[i].y2)sum+=(a[j].y2-a[j].y1)*;
else if(a[j].y2<a[i].y2)sum+=(a[j].y2-a[j].y1)*+;
else sum+=(a[i].y2-a[i].y1)*+;
}
else if(a[j].y2==a[i].y2){
if(a[j].y1>a[i].y1)sum+=(a[j].y2-a[j].y1)*+;
else sum+=(a[i].y2-a[i].y1)*+;;
}
else if(a[j].y1>a[i].y1&&a[j].y2<a[i].y2)sum+=(a[j].y2-a[j].y1+)*;
else if(a[j].y1>a[i].y1&&a[j].y2>a[i].y2)sum+=(a[i].y2-a[j].y1+)*;
else if(a[j].y1<a[i].y1&&a[j].y2>a[i].y2)sum+=(a[i].y2-a[i].y1+)*;
else sum+=(a[j].y2-a[i].y1+)*;
}
}
}
printf("%lld",sum);
return ;
}
说实话，那片博客的代码写得很条理，而我的分类讨论简直是一片混乱…
T2：
题目描述
辣鸡ljh NOI之后就退役了，然后就滚去学文化课了。
他每天都被katarina大神虐，仗着自己学过一些姿势就给katarina大神出了一道题。
有一棵 n 个节点的以 1 号节点为根的树，每个节点上有一个小桶，节点u上的小桶可以容纳个小球，ljh每次可以给一个节点到根路径上的所有节点的小桶内放一个小球，如果这个节点的小桶满了则不能放进这个节点，在放完所有小球之后就企图去刁难katarina大神，让katarina大神回答每个节点的小桶内的小球有多少种颜色。
然而katarina大神一眼就秒掉了，还说这就是一道傻逼模板题。
现在katarina大神想考考即将参加NOIP2019的你能不能回答上辣鸡ljh的问题。
输入格式
第一行，一个整数n，树上节点的数量。
接下来n − 1行，每行两个整数u, v，表示在u, v之间有一条边。
接下来一行n个整数，k1~kn表示每个节点上的小桶数量。
下一行是一个整数m，表示ljh进行的操作数量。
接下来m行，每行两个整数x, c，分别表示进行操作的节点和小球颜色。
下一行是一个整数Q，表示你需要回答的询问数。
接下来Q行，每行一个整数x，表示一个询问。
输出格式
对于每个询问输出一行表示这个询问的答案、
数据范围与提示
子任务
本次考试最大自闭点。
考场上想到了平衡树的启发式合并…不会写。事实上我不会写启发式合并，指所有类型【除了并查集】。
然后想想树剖，又觉得没必要，也不好搞。然后想想树上差分，也pass掉了。
甚至想到bitset传递闭包…后来觉得我大约是傻了。
最后老老实实码了个三十分的暴力，其实是尝试着尝试着越写越像暴力。用set便捷水分。
另一边隔空爆踩我们的学车大佬考场上码了树上启发式合并，考完以后改了一个小时就第一个A了本题。而我到现在还在挣扎动态开点线段树怎么写来着我怎么又忘了。
再留个坑。
好，坑填上了。跟着TKJ大佬写了平衡树:D
试着写了一下各种方法居然还是平衡树【对我来说】最好写…orz
之后去看大家的其他写法
平衡树的话，就是对于每个节点开一棵splay，然后对于放球的操作，在操作位置的splay里插入一个新节点，splay中以tim排序。
每次插入节点的时候要先判断这个颜色有没有出现过，用map存每种颜色在这颗splay内最早出现的时间，如果最早出现的时间能被更新，则要用一个change操作去改变原来有贡献的节点。
所有放球操作结束以后，dfs一遍全树，从叶子往树根合并所有平衡树。记录下每个节点对应的平衡树是哪颗，在每次合并的时候选择父子节点中平衡树size较小的，作为这两个节点对应的平衡树，把另一棵的节点暴力插入进这棵。
每次合并完一个节点的儿子以后，以k数组为限制查询一次答案并记录，询问的时候就可以直接输出答案了。
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int n,m,num,q,flag,ans1;
int ver[],Next[],head[],tot,k[],rec[],now,ans[];
void add(int x,int y){
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
struct node{
int ch[],tim,col,fa,siz,cnt,val;//val=tim 排序，siz=子树和 桶，cnt子树贡献
}t[*];
struct tree{
int root;
map<int,int>mp;
/* int rot(){
return root;
}*/
int size(){
return t[root].siz;
}
void update(int x){
t[x].siz=t[t[x].ch[]].siz+t[t[x].ch[]].siz+;
t[x].cnt=t[t[x].ch[]].cnt+t[t[x].ch[]].cnt+t[x].val;
}
void rotate(int x){
int y=t[x].fa,z=t[y].fa;
int k=(t[y].ch[]==x);
if(z)t[z].ch[t[z].ch[]==y]=x;
t[x].fa=z;
t[y].ch[k]=t[x].ch[k^];
t[t[x].ch[k^]].fa=y;
t[x].ch[k^]=y;
t[y].fa=x;
update(y);
}
void splay(int x){
while(t[x].fa!=){
int y=t[x].fa,z=t[y].fa;
if(t[y].fa!=){
(t[y].ch[]==x)^(t[z].ch[]==y)?rotate(x):rotate(y);
}
rotate(x);
}
update(x);
root=x;
}
void insert(int tim,int col,int val){
int f=,x=root;
while(x&&t[x].tim!=tim){
f=x;
x=t[x].ch[tim>t[x].tim];
}
x=++num;
if(f)t[f].ch[tim>t[f].tim]=x;
t[x].tim=tim,t[x].cnt=t[x].val=val,t[x].siz=;
t[x].fa=f,t[x].col=col;
splay(x);
}
void change(int tim){
int x=root;
while(x&&t[x].tim!=tim){
x=t[x].ch[tim>t[x].tim];
}
if(x)t[x].val=;
splay(x);
}
int find(int tim,int col){
// printf("%d\n",mp[col]);
if(mp[col]==){
mp[col]=tim;
return ;
}
else if(mp[col]>tim){
change(mp[col]);
mp[col]=tim;
return ;
}
else return ;
}
int findx(int x,int limit){
if(!x)return ;
if(t[t[x].ch[]].siz>=limit)findx(t[x].ch[],limit);
else if(t[t[x].ch[]].siz+>=limit)return ans1+t[t[x].ch[]].cnt+t[x].val;
else ans1+=t[t[x].ch[]].cnt+t[x].val,findx(t[x].ch[],limit-t[t[x].ch[]].siz-);
}
int findval(int limit){
ans1=;
if(limit==)return ;
if(limit>=t[root].siz)return t[root].cnt;
int x=findx(root,limit);
// splay(x);
return x;
}
void print(int x){
if(!x)return;
if(t[x].ch[])print(t[x].ch[]);
printf("%d-%d-%d \n",t[x].col,t[x].tim,t[x].val);
if(t[x].ch[])print(t[x].ch[]);
}
}a[];
void make(int x){
if(!x)return;
make(t[x].ch[]);
a[now].insert(t[x].tim,t[x].col,a[now].find(t[x].tim,t[x].col));
make(t[x].ch[]);
}
void dfs(int x,int fa){
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(y==fa)continue;
dfs(y,x);
if(a[rec[x]].size()<a[rec[y]].size()){
now=rec[y];
// printf(" %d %d\n",x,y);
make(a[rec[x]].root);
rec[x]=now;
}
else{
now=rec[x];
// printf(" %d %d\n",x,y);
make(a[rec[y]].root);
}
}
// a[rec[1]].print(a[rec[1]].root);
// printf("\n");
// flag=x;
ans[x]=a[rec[x]].findval(k[x]);
}
int main()
{
scanf("%d",&n);
for(int i=,x,y;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
for(int i=;i<=n;i++)scanf("%d",&k[i]),rec[i]=i;
scanf("%d",&m);
t[].cnt=t[].siz=;
for(int i=,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
a[rec[x]].insert(i,y,a[rec[x]].find(i,y));
// a[rec[x]].print(a[rec[x]].root);
// printf("\n");
}
dfs(,);
scanf("%d",&q);
for(int i=,x;i<=q;i++){
scanf("%d",&x);
printf("%d\n",ans[x]);
}
return ;
}
T3：
题目描述
辣鸡ljh NOI之后就退役了，然后就滚去学文化课了。
他发现katarina大佬真是太强了，于是就学习了一下katarina大佬的做题方法。
比如这是一本有n道题的练习册，katarina大佬每天都会做k道题。
第一天做第1~k题，第二天做第2~k+1题……第n-k+1天做第n-k+1~n道题。
但是辣鸡 ljh 又不想太累，所以他想知道katarina大佬做完这本练习册的劳累度。
每道题有它的难度值，假设今天katarina大佬做的题目中最大难度为t，那么今天katarina大佬的劳累度就是wt୲，做完这本书的劳累值就是每天的劳累值之和。
但是辣鸡ljh一道题都不会，自然也不知道题目有多难，他只知道题目的难度一定在1~m之间随机。
他想让即将参加 NOIP 的你帮他算算katarina大佬做完这本书的劳累值期望
输入格式
第一行，三个整数n,m,k
第二行，m个整数表示wt1……wtm
输出格式
输出劳累值期望对1000000007取模的值。
数据范围与提示
子任务
只剩20分钟了，我又很没梦想。看着数据范围先推k<=2，发现总情况是m^k【m²】，对于每个难度值，它的贡献情况数是i+i-1种。对于两道题里的每一道题，它都可以选择m种难度。而m难度，即最大难度，能产生贡献的是前一道题选择它，后一道题随便选，以及前一道题随便选，后一道题选它。去掉两道题都选它的重复情况，答案一共是m+m-1种。对于m-1难度，去掉选了m的情况，然后类推。
然后根据贡献乘上w再乘上分母的逆元，大概七八分钟写了这个，隐隐约约有点正解思路但没往下想，继续看数据点。
n<=8的情况挺多，来，搜索。【？】
于是又几分钟写了个搜索，提交完还剩三分钟。
正解其实和我k<=2的思路有点像。对于一个难度m，以它为最大值计算情况有m^k种，其中还有（m-1）^k种它其实并不作为最大值产生贡献。所以对于1~m每一个难度i，它产生的贡献是(i^k-(i-1)^k)*w[i]。把每个i的贡献加起来，乘以一个天数【每天都要这么算一次贡献】，再乘上分母总情况的逆元，就是正确结果了。
而题解给出的DP做法我是真的没看懂…【用心出题，用脚写题解】
#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,k;
const long long mod=;
long long w[],ans,ans1;
long long ks(long long x,long long k){
long long num=;
while(k){
if(k&)num=num*x%mod;
x=x*x%mod;
k>>=;
}
return num;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&k);
if(k>n){
printf("");
return ;
}
for(int i=;i<=m;i++)scanf("%lld",&w[i]);
long long ans=ks(ks(m,k),mod-);
for(int i=;i<=m;i++){
long long a1=ks(i,k);
long long a2=ks(i-,k);
ans1=(ans1+((a1-a2+mod)%mod*w[i]%mod))%mod;
}
ans=ans1*ans%mod*(n-k+)%mod;
printf("%lld",ans);
return ;
}
这次考试感觉也是有很多很多问题…比较突出的是想到不会写，以及对数学部分的抵触和不擅长。
纠结要不要继续写T2，还是去训练昨天新讲的DP