2019.7.29 NOIP模拟测试10 反思总结【T2补全】

这次意外考得不错…但是并没有太多厉害的地方，因为我只是打满了暴力【还没去推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[200010];
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==1){
        long long x1,y1,x2,y2;
        scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
        printf("%lld",(x2-x1)*(y2-y1)*2);
        return 0;
    }
    for(int i=1;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)*2;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[j].x1>a[i].x2+1)break;
            if(a[j].y2<a[i].y1-1||a[j].y1>a[i].y2+1)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)*2;
                    else if(a[j].x2<a[i].x2)sum+=(a[j].x2-a[j].x1)*2+1;
                    else sum+=(a[i].x2-a[i].x1)*2+1;
                }
                else if(a[j].x2==a[i].x2){
                    if(a[j].x1>a[i].x1)sum+=(a[j].x2-a[j].x1)*2+1;
                    else sum+=(a[i].x2-a[i].x1)*2+1;
                }
                else if(a[j].x2<a[i].x2)sum+=(a[j].x2-a[j].x1+1)*2;
                else sum+=(a[i].x2-a[j].x1+1)*2;
            }
            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)*2;
                    else if(a[j].y2<a[i].y2)sum+=(a[j].y2-a[j].y1)*2+1;
                    else sum+=(a[i].y2-a[i].y1)*2+1;
                }
                else if(a[j].y2==a[i].y2){
                    if(a[j].y1>a[i].y1)sum+=(a[j].y2-a[j].y1)*2+1;
                    else sum+=(a[i].y2-a[i].y1)*2+1;;
                }
                else if(a[j].y1>a[i].y1&&a[j].y2<a[i].y2)sum+=(a[j].y2-a[j].y1+1)*2;
                else if(a[j].y1>a[i].y1&&a[j].y2>a[i].y2)sum+=(a[i].y2-a[j].y1+1)*2;
                else if(a[j].y1<a[i].y1&&a[j].y2>a[i].y2)sum+=(a[i].y2-a[i].y1+1)*2;
                else sum+=(a[j].y2-a[i].y1+1)*2;
            }
        }
    }
    printf("%lld",sum);
    return 0;
}

View Code

说实话，那片博客的代码写得很条理，而我的分类讨论简直是一片混乱…

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[200010],Next[200010],head[100010],tot,k[100010],rec[100010],now,ans[1000010];
void add(int x,int y){
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
struct node{
    int ch[2],tim,col,fa,siz,cnt,val;//val=tim 排序，siz=子树和 桶，cnt子树贡献 
}t[100010*40];
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[0]].siz+t[t[x].ch[1]].siz+1;
        t[x].cnt=t[t[x].ch[0]].cnt+t[t[x].ch[1]].cnt+t[x].val;
    }
    void rotate(int x){
        int y=t[x].fa,z=t[y].fa;
        int k=(t[y].ch[1]==x);
        if(z)t[z].ch[t[z].ch[1]==y]=x;
        t[x].fa=z;
        t[y].ch[k]=t[x].ch[k^1];
        t[t[x].ch[k^1]].fa=y;
        t[x].ch[k^1]=y;
        t[y].fa=x;
        update(y);
    }
    void splay(int x){
        while(t[x].fa!=0){
            int y=t[x].fa,z=t[y].fa;
            if(t[y].fa!=0){
                (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
            }
            rotate(x);
        }
        update(x);
        root=x;
    }
    void insert(int tim,int col,int val){
        int f=0,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=1;
        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=0;
        splay(x);
    }
    int find(int tim,int col){
//        printf("%d
",mp[col]);
        if(mp[col]==0){
            mp[col]=tim;
            return 1;
        }
        else if(mp[col]>tim){
            change(mp[col]);
            mp[col]=tim;
            return 1;
        }
        else return 0;
    }
    int findx(int x,int limit){
        if(!x)return 0;
        if(t[t[x].ch[0]].siz>=limit)findx(t[x].ch[0],limit);
        else if(t[t[x].ch[0]].siz+1>=limit)return ans1+t[t[x].ch[0]].cnt+t[x].val;
        else ans1+=t[t[x].ch[0]].cnt+t[x].val,findx(t[x].ch[1],limit-t[t[x].ch[0]].siz-1);
    }
    int findval(int limit){
        ans1=0;
        if(limit==0)return 0;
        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[0])print(t[x].ch[0]);
        printf("%d-%d-%d 
",t[x].col,t[x].tim,t[x].val);
        if(t[x].ch[1])print(t[x].ch[1]);
    }
}a[100010];
void make(int x){
    if(!x)return;
    make(t[x].ch[0]);
    a[now].insert(t[x].tim,t[x].col,a[now].find(t[x].tim,t[x].col));
    make(t[x].ch[1]);
}
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
",x,y);
            make(a[rec[x]].root);
            rec[x]=now;
        }
        else{
            now=rec[x];
//            printf(" %d %d
",x,y);
            make(a[rec[y]].root);
        }
    }
//    a[rec[1]].print(a[rec[1]].root);
//    printf("
");
//    flag=x;
    ans[x]=a[rec[x]].findval(k[x]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    for(int i=1;i<=n;i++)scanf("%d",&k[i]),rec[i]=i;
    scanf("%d",&m);
    t[0].cnt=t[0].siz=0;
    for(int i=1,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("
");
    }
    dfs(1,0);
    scanf("%d",&q);
    for(int i=1,x;i<=q;i++){
        scanf("%d",&x);
        printf("%d
",ans[x]);
    }
    return 0;
}

View Code

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=1000000007;
long long w[510],ans,ans1;
long long ks(long long x,long long k){
    long long num=1;
    while(k){
        if(k&1)num=num*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return num;
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    if(k>n){
        printf("0");
        return 0;
    }
    for(int i=1;i<=m;i++)scanf("%lld",&w[i]);
    long long ans=ks(ks(m,k),mod-2);
    for(int i=1;i<=m;i++){
        long long a1=ks(i,k);
        long long a2=ks(i-1,k);
        ans1=(ans1+((a1-a2+mod)%mod*w[i]%mod))%mod;
    }
    ans=ans1*ans%mod*(n-k+1)%mod;
    printf("%lld",ans);
    return 0;
}

View Code

这次考试感觉也是有很多很多问题…比较突出的是想到不会写，以及对数学部分的抵触和不擅长。

纠结要不要继续写T2，还是去训练昨天新讲的DP

2019.7.29 NOIP模拟测试10 反思总结【T2补全】

题目描述

输入格式

输出格式

数据范围与提示

子任务

题目描述

输入格式

输出格式

数据范围与提示

子任务

题目描述

输入格式

输出格式

数据范围与提示

子任务