[雅礼NOIP2018集训] day6

打满暴力好像是一种挑战，已经连续几天考试最后一个小时自闭了，因为自以为打完了暴力，然而，结果往往差强人意

大概是考试的策略有些问题

T1：

我们设$g[x]$为在x时取小于等于m个物品的最大价值，下面要证明的是$g$的单调性

1.若k都小于0，那么$g$是单调减的，这种情况下特判0就好

2.若k都大于0，那么$g$是单调增的，这种情况下显然可以二分

3.有的k大于0，有的k小于0，这种情况下$g$先单调减后单调增。为什么？考虑选择的过程，x确定的时候，我们选当前取值>0的前m个（不够的话就不取）。那么随着x的增大，在已取集合中k<0的会不断减小到0，之后被我们删去;集合外的k>0的会不断增大最终大于0，之后可能被我们加入集合。考虑在某个横坐标之前单位减少量大于增加量，这个横坐标之后单位减少量小于增加量，那么之后单位减少量会恒小于增加量，联系上述的过程理解（已经加入集合的单增的直线只会不断增大，或者被更大代替，而单减的直线不会一直减小，而是会减小到0后被丢出去。也就是单位增加的导函数单增，单位减少的导函数单减（非严格））

那么情况3我们如何处理呢？很简单，我们特判一下0，如果满足条件直接输出即可，否则我们就在单增上二分（在代码中表现的是我们在整个函数上二分，因为单见你呢的那部分显然全部都<S，而<S时我们会把横坐标右移到单增处，实际和上面的情况1和情况2操作完全一样）

$nth_element(val+1,val+n-m+1,val+n)$将$[1,n+1)$第$n-m+1$大的元素放在第$n-m+1$小的位置，满足前面的元素比他小，后面的元素比他大

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

const int N=1e6+;

const ll inf=1e9;

ll n,m,S;

ll k[N],b[N],val[N];

inline ll read()

{

    char ch=getchar();

    ll s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

bool check(ll x)

{

    for (int i=;i<=n;i++) val[i]=k[i]*x+b[i];

    nth_element(val+,val+n-m+,val+n+);

    ll re=;

    for (int i=n;i>=n-m+;i--)

    {

        if (val[i]>) re+=val[i];//不保证前m个是按顺序的，因此<0不能break

        if (re>=S) return ;

    }

    return re>=S;

}

int main()

{

    n=read();m=read();S=read();

    for (int i=;i<=n;i++) k[i]=read(),b[i]=read();

    if (check()) {puts("");return ;}

    ll l=,r=inf;

    while (l<r)

    {

        int mid=l+r>>;

        if (check(mid)) r=mid;

        else l=mid+;

    }

    printf("%lld\n",l);

    return ;

}

T2：

考虑到，一开始的形如$x_i+x_{fa}=w$形成一棵以1为根节点的树，也就是说任意的点都可以用$x_1$表示

设1为偶数点，那么奇数点都可以表示成形如$k-x_1$的形式，偶数点都可以表示为形如$k+x_1$的形式

考虑操作1：我们假设已知$x_u,x_v$用$x_1$的表示和$u,v$是奇数点还是偶数点，分以下情况讨论

1.两个都是奇数点，那么有$k_u-x_1+k_v-x_1=s$，移项得到$2x_1=s+k_u+k_v$，计算答案就好

2.两个都是偶数点，那么有$k_u+x_1+k_v+x_1=s$，移项得到$2x_1=s-k_u-k_v$，计算答案就好

3.一个是奇数点，一个是偶数点，这样的话$x_1$就会消掉，判断得到的结果与给定的s是否相同即可

显然初始化一遍dfs每个点的表示和奇偶都可以轻易得到

考虑操作2如何维护？

我们发现改变一个点与其父亲的$w$值最终改变表达的只是这个点子树里的点，我们把奇数点和偶数点分情况讨论，用树状数组维护区间加就好

如当前点已知表达为$x$，接下来的表达分别为$w_1-x,w_2-w_1+x,w_3-w_2+w_1-x$

总结起来就是奇到奇是+，偶到偶是+，奇到偶和偶到奇都是-（这个主要是方便笔者自己理解...可能有点抽象，感性理解一下）

std用了很神奇的一个树状数组同时解决了奇点和偶点的修改，用的就是上述的性质

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=1e6+;

int n,q,tot,tim;

int head[N],dep[N],dfn[N],edfn[N],t[N],w[N];

struct EDGE

{

    int to,nxt,ww;

}edge[N];

inline int read()

{

    char ch=getchar();

    int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

void ad(int u,int v,int ww)

{

    edge[++tot]=(EDGE){v,head[u],ww};

    head[u]=tot;

}

void dfs(int x)

{

    dfn[x]=++tim;

    for (int i=head[x];i;i=edge[i].nxt)

    {

        int y=edge[i].to;

        dep[y]=dep[x]^;

        dfs(y);

    }

    edfn[x]=tim;

}

void add(int x,int y)

{

    while (x<=n)

    {

        t[x]+=y;

        x+=x&-x;

    }

}

int sum(int x)

{

    int re=;

    while (x)

    {

        re+=t[x];

        x-=x&-x;

    }

    return re;

}

int main()

{

//    freopen("equation.in","r",stdin);

//    freopen("equation.out","w",stdout);

    n=read();q=read();

    for (int i=,u;i<=n;i++)

    {

        u=read();w[i]=read();

        ad(u,i,w[i]);

    }

    dfs();

    for (int i=;i<=n;i++) if (!dep[i]) w[i]=-w[i];

    for (int i=;i<=n;i++) {add(dfn[i],w[i]);add(edfn[i]+,-w[i]);}

    while (q--)

    {

        int opt=read();

        if (opt==)

        {

            int u=read(),v=read(),s=read();

            int x=sum(dfn[u]),y=sum(dfn[v]);

            if (dep[u]&&dep[v])

            {

                ll rt=1ll*x+y-s;

                if (rt%!=) puts("none");

                else printf("%lld\n",rt/);

            }

            else if (!dep[u]&&!dep[v])

            {

                ll rt=1ll*x+y+s;

                if (rt%!=) puts("none");

                else printf("%lld\n",rt/);

            }

            else

            {

                if (!dep[u]) swap(u,v),swap(x,y);

                if (x-y==s) puts("inf");

                else puts("none");

            }

        }

        if (opt==)

        {

            int u=read(),ww=read();

            if (!dep[u]) ww=-ww;

            add(dfn[u],ww-w[u]);add(edfn[u]+,w[u]-ww);

            w[u]=ww;

        }

    }

    return ;

}

T3:

待填

巴特西

[雅礼NOIP2018集训] day6

T1：

T2：

T3:

最新文章

热门文章