July 25, 2019 (Thinking)

Some people say I am not happy!

Time is running out, even if it's still a lot of water, I don't have time to complain, topic!

prob1: A

A tree with n nodes contributes a little to its ancestors if and only if the distance between a node and one of its ancestors is less than the point weight.

Finally a human nature \\\\\\\\\ Running every day Similarly, a point (i) can be contributed once by a point (j) on its subtree if and only if (dep[j]-dep[i] <=w[j]\), the term is transferred to \\(dep[j] <=dep[i]\. Using the same idea, we first discretize the weights and use the tree array (cnt[i]) to maintain the number less than or equal to (i). Each visit to a point\(i\), first use\\\\ to store the then\\\\\\\\\\\\\\\\\ Finally, output the answer.

Range algorithm for differential doubling jump to reach ancestors, also very strong

In short, the water problem, because the array opened small and not open well \\\\\\\\\

Look at the code:

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define in read()
#define fur(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define pl pair<ll,ll>
#define xx 220000
#define nm make_pair
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    for(;!isalnum(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
struct point{ll fa,w,dis;}dot[xx];
vector<pl> e[xx];
ll cnt[xx<<1],ans[xx],n;
ll all=0,res=0,v1[xx<<1],v2[xx<<1];
inline int lowbit(int i){return i&-i;}
inline void add(int i,ll x)
{
    if(!i) return;
    while(i<=n)
    {
        cnt[i]+=x;
        i+=lowbit(i);
    }
}
inline int ask(int i)
{
    int now=0;
    while(i>0)
    {
        now+=cnt[i];
        i-=lowbit(i);
    }
    return now;
}
inline void dfs1(int g)
{
    fur(i,0,(int)e[g].size()-1)
    {
        dot[e[g][i].first].dis=dot[g].dis+e[g][i].second;
        dfs1(e[g][i].first);
    }
}
inline void dfs2(int g)
{
    ll before=ask(dot[g].dis);
    fur(i,0,(int)e[g].size()-1) dfs2(e[g][i].first);
    ll then=ask(dot[g].dis);
    add(dot[g].w,1ll);
    ans[g]=then-before;
}
inline int look(ll k)
{
    int h=1,t=all;
    while(h<=t)
    {
        int mid=(h+t)>>1;
        if(k<v2[mid]) t=mid-1;
        else if(k>v2[mid]) h=mid+1;
        else return mid;
    }
}
int main()
{
    n=in;
    fur(i,1,n) dot[i].w=in;
    fur(i,2,n)
    {
        dot[i].fa=in;
        ll x=in;
        e[dot[i].fa].push_back(nm(i,x));
    }
    dfs1(1);
    fur(i,1,n)
    {
        v1[i]=dot[i].dis-dot[i].w;
        v1[n+i]=dot[i].dis;
    }
    sort(v1+1,v1+n*2+1);
    fur(i,1,2*n)
    {
        while(v1[i]==v1[i+1]) i++;
        v2[++all]=v1[i];
    }
    fur(i,1,n)
    {
        dot[i].w=look(dot[i].dis-dot[i].w);
        dot[i].dis=look(dot[i].dis);
    }
    n*=2;
    dfs2(1);
    fur(i,1,n/2) printf("%lld ",ans[i]);
    printf("\n");
    return 0;
}

prob2: B

Main idea of the title: Seek the number of pairs of points ((i,j)) in three groups of permutations such that \(a_i < a_j, b_i < b_j, c_i < c_j)

At first glance, I thought it was \\\\\ cdq \\\\\\\\\\

The correct solution should be reprimanded.

\ (kuai) Let's look at (lst) Sister Xue's problem-solving:

Let(S(i,j)=[A_i>A_j]+[B_i>B_j]+[C_i>C_j]

Let(M(i,j)=max(S(i,j),S(j,i))

It can be found that M(i,j) is either (2) or (3). Let the number of (M(i,j)=2) be \\\\\\\\\\\\
\(a+b=C_n^2\)

By calculating the numbers of (A_i>A_j) & \(B_i>B_j), \(A_i>A_j)& \\\\\\\\\\\\\\\\

To sum up, one minus two is the answer.

Procedures:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define in read()
#define fur(i,a,b) for(int i=a;i<=b;++i)
#define ll int
#define xx 2000010
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    for(;!isalnum(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
long long ans,seed,n;
ll cnt1[xx],cnt2[xx],cnt3[xx],a[xx],b[xx],c[xx];
#define fuck 19260817
#define cow 233333
#define xie (1<<24)-1
inline ll Ran()
{
    return seed=((fuck*seed)^cow)&xie;
}
inline void gen(ll *A)
{
    fur(i,1,n) A[i] = i;
    fur(i,1,n) swap(A[i],A[Ran()%i+1]);
}
inline int lowbit(int i){return i&-i;}
inline void add(int i,ll x,ll *cnt){while(i<=n){cnt[i]+=x;i+=lowbit(i);}}
inline int ask(int i,ll *cnt){ll res=0;while(i>0){res+=cnt[i];i-=lowbit(i);}return res;}
struct man{ll x,y;}g1[xx],g2[xx],g3[xx];
inline bool cmp(man f,man s){return f.x<s.x;}
int main()
{
    n=in;
    seed=in;gen(a);
    seed=in;gen(b);
    seed=in;gen(c);
    ans=-(n*(n-1)>>1);
    fur(i,1,n)
    {
        g1[i]=(man){a[i],b[i]};
        g2[i]=(man){b[i],c[i]};
        g3[i]=(man){a[i],c[i]};
    }
    sort(g1+1,g1+n+1,cmp);
    sort(g2+1,g2+n+1,cmp);
    sort(g3+1,g3+n+1,cmp);
    fur(i,1,n)
    {
        add(g1[i].y,1,cnt1);
        ans+=ask(g1[i].y-1,cnt1);
    }
    fur(i,1,n)
    {
        add(g2[i].y,1,cnt2);
        ans+=ask(g2[i].y-1,cnt2);
    }
    fur(i,1,n)
    {
        add(g3[i].y,1,cnt3);
        ans+=ask(g3[i].y-1,cnt3);
    }
    printf("%lld\n",ans>>1);
    return 0;
}

prob3: C

Topic: Luogu P4823 \\\\\\\\ Save the Dwarfs

\ (sb greedy practices: test data (90), luogu data\\\\\\\\\\

Look for someone who can do things at the present height and arm length, press into a small pile, find the shortest one, let him do things, and then abandon him until he can't do things.

Code:

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define in read()
#define fur(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define pl pair<ll,ll>
#define nm make_pair
#define xx 4001
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    for(;!isalnum(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
struct heep
{
    priority_queue<pl,vector<pl>,greater<pl> >q;
    inline void ad(ll x,int i)
        {
            q.push(nm(x,i));
        }
    inline int top()
        {
            return q.top().second;
        }
    inline void clear()
        {
            while(!q.empty()) q.pop();
        }
}p;
ll a[xx],b[xx],ans=0;
bool choose[xx];
int main()
{
    ll n=in,sum=0,c=0;
    fur(i,1,n)
    {
        a[i]=in,b[i]=in;
        sum+=a[i];
    }
    ll h=in;
    fur(i,1,n)
    {
        if(b[i]+sum>=h)
        {
            p.ad(a[i],i);
            c=max(c,b[i]);
        }
    }
    while(sum+c>=h)
    {
        ++ans;
        sum-=a[p.top()];
        choose[p.top()]=true;
        p.clear();
        c=0;
        fur(i,1,n)
        {
            if(!choose[i])
            {
                if(b[i]+sum>=h)
                {
                    p.ad(a[i],i);
                    c=max(c,b[i]);
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

It's OK to open (O 2) but it's going to be inexplicable (WA\)

Positive Solution: Sort by height and arm length, the sum and the smallest will be discarded first, because it is useless, and then use (f[i]) to store the highest ladder height formed when (i) individuals are gone, to make state transition.

Look at the code specifically:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define in read()
#define fur(i,a,b) for(int i=a;i<=b;++i)
#define fdr(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
#define xx 4001
inline int read()
{
    int x=0,f=1;char ch=getchar();
    for(;!isalnum(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
struct link{ll a,b;}x[xx];
ll f[xx];
inline bool cmp(link q1,link q2){return q1.a+q1.b<q2.a+q2.b;}
int main()
{
    int n=in;
    fur(i,1,n)
    {
        x[i].a=in;
        x[i].b=in;
        f[i]=-1;
        f[0]+=x[i].a;
    }
    int h=in;
    sort(x+1,x+n+1,cmp);
    fur(i,1,n) fdr(j,i,1) if(f[j-1]+x[i].b>=h) f[j]=max(f[j],f[j-1]-x[i].a);
    fdr(i,n,0)
    {
        if(f[i]>=0)
        {
            printf("%d\n",i);
            return 0;
        }
    }
    return 0;
}

prob4:D

Topic: The target point falls on the leaf node of a tree with equal probability. Some nodes have hints to indicate whether there is a target point in the sub-tree of the node, so as to find the optimal expectation of reaching the target point.

Expectations(DP)Recommendations This question Introduction

Let(F[i] find the expected steps of the target point in the (i) node subtree for starting from the (i) node, and let\(G[i] return the expected steps of(i) node for not finding, \(cnt[i]\ be the number of leaf nodes in the \(i\) node subtree. Then(F[i]=Sigma(F[son[i][j]]*cnt[son[i][j]]/cnt[i]+G[son[i][j]*(cnt[i]-\Sigma_q^{j-1} cnt[son[i]]]]]/cnt[i]
\(G[i]=\Sigma{G[son[i][j]]/cnt[i]}\)
For the convenience of storage and transfer, only the molecules in the formula are retained.
See the code for details:

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
#define in read()
#define fur(i,a,b) for(int i=a;i<=b;i+=1)
#define ll long long
#define xx 1100
inline int read()
{
    int x=0,f=1;char ch=getchar();
    for(;!isalnum(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
vector<int>e[xx];
bool snail[xx];
double g[xx],f[xx],cnt[xx];
inline void init(int n)
{
    fur(i,1,n) e[i].clear(),snail[i]=false;
    fur(i,1,n) g[i]=f[i]=0;
}
inline bool cmp(int x,int y){return g[x]/cnt[x]<g[y]/cnt[y];}
inline void dfs(int j)
{
    if((int)e[j].size()==0)
    {
        g[j]=f[j]=0;
        cnt[j]=1;
        return;
    }
    int son[xx],len=0;
    cnt[j]=0;
    fur(i,0,(int)e[j].size()-1)
    {
        dfs(e[j][i]);
        son[++len]=e[j][i];
        f[e[j][i]]+=1;
        g[e[j][i]]+=2;
        cnt[j]+=cnt[e[j][i]];
    }
    sort(son+1,son+len+1,cmp);
    double sum=0;
    fur(i,1,len)
    {
        sum+=cnt[son[i]];
        f[j]+=f[son[i]]*cnt[son[i]]+g[son[i]]*(cnt[j]-sum);
        g[j]+=g[son[i]];
    }
    f[j]/=cnt[j];
    if(snail[j]) g[j]=0;
}
int main()
{
    int t=in;
    while(t--)
    {
        int n=in;
        fur(i,1,n)
        {
            int x=in;
            if(x>0) e[x].push_back(i);
            char op[2];
            scanf("%s",op);
            if(op[0]=='Y') snail[i]=true;
        }
        dfs(1);
        printf("%.4lf\n",f[1]);
        init(n);
    }
    return 0;
}

Tags: PHP less

Posted on Tue, 06 Aug 2019 17:57:50 -0700 by rachae1