NOIP模拟测试10「大佬·辣鸡·模板」

大佬

显然假期望

我奇思妙想出了一个式子$f[i]=f[i-1]+\sum\limits_{j=1}^{j<=m} C_{k \times j}^{k}\times w[j]$

然后一想不对得容斥

于是我得到$f[i]=f[i-1]+\sum\limits_{j=1}^{j<=m} C_{j\times(k-1)}^{k-1} \times w[j]$

但还是不对

现在思考第一个式子为什么不对

我们枚举矩阵选数

1 2 3

1 2 3

1 2 3

这样我们C的话概率会很鬼$\frac {4}{12}$$\times$$\frac {3}{11}$$\times$$\frac {2}{10}$

显然应该是$\frac 1 3$$\times $$\frac 1 3$$\times$$\frac 1 3$

我算小了

真的是小了吗？

思考第二个式子为什么不对，显然我们如果这样做应该再乘$C_{k}^{1}$但这么乘起来会重复

1111111会被多贡献很多回

还是要容斥

然后考试时我思维就停止了

我们或许可以换种思路考虑

同样是一个区间，我们这样算区间贡献

$\sum\limits_{j=1}^{j<=m} j^k-(j-1)^k$

理解一下

$j^k$表示$<=j$随便选，然后再容斥掉$(j-1)^k$（所有都比j小，选不到j）

得到贡献

然后再用f转移即可

#include<bits/stdc++.h>

#define ll long long

#define A 700000

using namespace std;

const ll mod=1e9+7;

ll n,m,k,sumday,w[A],ni,ans=0;

inline ll meng(ll x,ll k){

    ll ans=1;

    for(;k;k>>=1,x=x*x%mod)

        if(k&1)

            ans=ans*x%mod;

    return ans;

}

int main(){

    scanf("%lld%lld%lld",&n,&m,&k);

    if(k>n) {

        puts("0");

        return 0;

    }

    ni=1;

    for(ll i=1;i<=m;i++)

        scanf("%lld",&w[i]);

    for(ll i=1;i<=m;i++)

        ((ans=(ans%mod+(meng(i,k)%mod-meng(i-1,k)%mod+mod)*w[i]%mod)%mod))%=mod;

    ans=ans*(n-k+1)%mod;

    ni=meng(meng(m,k),mod-2)%mod;

    cout<<ans%mod*ni%mod<<endl;

}

辣鸡

考试历程：

想到$n^2$过不了应该是$n^log$的，或许是$n^{log^2}$

反正$n^2$能过我吃掉键盘

然后我就思考，我tm应该用什么呢，CDQ？树状数组？线段树？权值线段树？还是像上次光那个题一样的傻逼大模拟？

偶对了，一定是像光那个题一样的傻逼题。

但我的光现在还没有过啊。。

这个题暴力分好少啊

然后我还是打了个普通$n^2$然后发现它炸了。

我发现难以调出来还是改成了xy相关

考完后

这个题还真$n^2$能过

完了我没有立flag

后来得知是优化过的$n^2$

打起来像插头dp

首先矩阵内的贡献我们可以用(x2-x1)*(y2-y1)*2算出来

然后矩阵之间分很多种情况

然而每一种都比较简单,比插头简单的多

方格表示过于,,,容易出现各种错误,格点表示

具体还是看代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define A 1100000

struct node{

    ll x1,x2,y1,y2;

    friend bool operator <(const node a,const node b){

        return ((a.x1==b.x1)?a.y1<b.y1:a.x1<b.x1);

    }

}nd[A];

ll ans=0,n;

int main(){

    scanf("%lld",&n);

    for(ll i=1;i<=n;i++){

        scanf("%lld%lld%lld%lld",&nd[i].x1,&nd[i].y1,&nd[i].x2,&nd[i].y2);

        ans+=(nd[i].x2-nd[i].x1)*(nd[i].y2-nd[i].y1)*2;

    }

    sort(nd+1,nd+n+1);

    for(ll i=1;i<n;i++){

        for(ll j=i+1;j<=n;j++){

            if(nd[j].x1>nd[i].x2+1) break;

            if(nd[i].y2+1<nd[j].y1||nd[i].y1-1>nd[j].y2) continue;

//            printf("ix1=%lld iy1=%lld jx1=%lld jy1=%lld\n",nd[i].x1,nd[i].y1,nd[j].x1,nd[j].y1);

            if(nd[j].x1>nd[i].x2){

                if(nd[i].y2<nd[j].y1||nd[i].y1>nd[j].y2) ans++;

                else if(nd[i].y1==nd[j].y1){

                    if(nd[i].y2==nd[j].y2)

                        ans+=(nd[i].y2-nd[i].y1)*2;

                    else if(nd[i].y2<nd[j].y2)

                        ans+=(nd[i].y2-nd[i].y1)*2+1;

                    else if(nd[i].y2>nd[j].y2)

                        ans+=(nd[j].y2-nd[i].y1)*2+1;

                }

                else if(nd[i].y2==nd[j].y2){

                    if(nd[i].y1==nd[j].y1)

                        ans+=(nd[i].y2-nd[j].y1)*2;

                    else if(nd[i].y1<nd[j].y1)

                        ans+=(nd[i].y2-nd[j].y1)*2+1;

                    else if(nd[i].y1>nd[j].y1)

                        ans+=(nd[i].y2-nd[i].y1)*2+1;

                }

                else if(nd[i].y2>nd[j].y2&&nd[i].y1<nd[j].y1)

                    ans+=(nd[j].y2-nd[j].y1)*2+2;

                else if(nd[i].y2<nd[j].y2&&nd[i].y1<nd[j].y1)

                    ans+=(nd[i].y2-nd[j].y1)*2+2;

                else if(nd[i].y2>nd[j].y2&&nd[i].y1>nd[j].y1)

                    ans+=(nd[j].y2-nd[i].y1)*2+2;

                else if(nd[i].y2<nd[j].y2&&nd[i].y1>nd[j].y1)

                    ans+=(nd[i].y2-nd[i].y1)*2+2;

//                printf("second%lld\n",ans);

            }

            else{

                if(nd[i].x1==nd[j].x1){

                    if(nd[i].x2==nd[j].x2)

                        ans+=(nd[i].x2-nd[i].x1)*2;

                    else if(nd[i].x2<nd[j].x2)

                        ans+=(nd[i].x2-nd[i].x1)*2+1;

                    else if(nd[i].x2>nd[j].x2)

                        ans+=(nd[j].x2-nd[i].x1)*2+1;

                }

                else if(nd[i].x2==nd[j].x2){

                    if(nd[i].x1==nd[j].x1)

                        ans+=(nd[i].x2-nd[j].x1)*2;

                    else if(nd[i].x1<nd[j].x1)

                        ans+=(nd[i].x2-nd[j].x1)*2+1;

                    else if(nd[i].x1>nd[j].x1)

                        ans+=(nd[i].x2-nd[i].x1)*2+1;

                }

                else if(nd[i].x2>nd[j].x2)

                    ans+=(nd[j].x2-nd[j].x1)*2+2;

                else if(nd[i].x1<nd[j].x1&&nd[i].x2<nd[j].x2)

                    ans+=(nd[i].x2-nd[j].x1)*2+2;

//                printf("frist%lld\n",ans);

            }

//            printf("i=%lld j=%lld ans=%lld\n",i,j,ans);

        }

    }

    cout<<ans<<endl;

}

模板

我一开始确实以为是模板

然后就开始打了,树差,线段树,权值线段树,合并往上仍

不就是和雨天的尾巴差不多的一道题目吗 AC预订

然后越想越不对,觉得难以维护桶

看数据范围不维护桶勉强可以70分

那就先得70分吧

然后我就打炸了,看着最后时间将至赶紧删了打暴力

暴力树上差分还有30分,树上差分打对就行

然后树上差分我觉得也不行,也是相当难维护,set,vector,map,multiset往上仍,但无济于事

最小的点是10 10 10,打个纯暴力还有10分呢

我成功奶死了自己

0分!

tqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltqltql

说一下这个怎么做

前置知识：

启发式合并

线段树

注意很多细节，我会在启发式合并中具体讲

NOIP模拟测试10「大佬·辣鸡·模板」的相关教程结束。