NOIP提高组模拟赛23(Noip improvement group simulation 23)

本场比赛是暴力的胜利!!!!

A. d

怎么说呢,考场想到正解方式,但是错误使用双指针,而且完全没想平衡树。。。。

做法就是分别按照\(a,b\)排序,然后枚举按照升序删掉多少\(a\)小的,剩下的按照\(b\)删,使用平衡树很好的解决,可惜考场完全忘了有这个东西。。

好在这样的暴力有\(81pts\)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;

typedef long long ll;
const int maxn=100005;
const int inf=2147483647;
int n,m;
struct node{ll a,b;}a[maxn];
struct FHQ_Treap{
	struct node{
		int l,r,val,size,key;
	}t[maxn];
	int root,tot;
	int New(int val){t[++tot].val=val;t[tot].size=1;t[tot].key=rand();return tot;}
	void push_up(int x){t[x].size=t[t[x].l].size+t[t[x].r].size+1;}
	void split(int x,int &l,int &r,int val){
		if(x==0){l=r=0;return;}
		if(t[x].val>val){split(t[x].l,l,t[x].l,val);r=x;push_up(r);return;}
		else{split(t[x].r,t[x].r,r,val);l=x;push_up(l);return;}
	}
	int merge(int l,int r){
		if(!l||!r)return l|r;
		if(t[l].key<t[r].key){t[l].r=merge(t[l].r,r);push_up(l);return l;}
		else{t[r].l=merge(l,t[r].l);push_up(r);return r;}
	}
	void insert(int val){
		int l=0,r=0;split(root,l,r,val);
		root=merge(merge(l,New(val)),r);
	}
	void erase(int val){
		int l=0,r=0,m=0;split(root,l,r,val);split(l,l,m,val-1);
		m=merge(t[m].l,t[m].r);
		root=merge(merge(l,m),r);
	}
	int kth(int x,int k){
		if(k==t[t[x].l].size+1)return t[x].val;
		if(k<=t[t[x].l].size)return kth(t[x].l,k);
		else return kth(t[x].r,k-t[t[x].l].size-1);
	}
	void pre(int x){
        x+=10;
        for(int i=1;i<=x;++i)t[i].val=t[i].l=t[i].r=t[i].size=0;
        root=0;tot=0;
    }
}T;
int pa[maxn];
bool cma(int x,int y){
    if(a[x].a!=a[y].a)return a[x].a<a[y].a;
    return a[x].b<a[y].b;
}

void work(){
    T.pre(n);
    for(int i=1;i<=n;++i)pa[i]=i;
    sort(pa+1,pa+n+1,cma);
    for(int i=1;i<=n;++i)T.insert(a[i].b);
    ll ans=T.kth(T.root,m+1)*1ll*a[pa[1]].a;
    for(int i=1;i<=m;++i){
        T.erase(a[pa[i]].b);
        ans=max(ans,T.kth(T.root,m-i+1)*a[pa[i+1]].a*1ll);
    }
    printf("%lld\n",ans);
}

int main(){
    int T;scanf("%d",&T);
    for(int ask=1;ask<=T;++ask){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)scanf("%lld%lld",&a[i].a,&a[i].b);
        work();       
    }
    return 0;
}

B. e

这是暴力的高光时刻!!!!

每次询问按照\(dfs\)序排一下,然后对相邻的两个点不停的暴力跳父亲取\(min\)

没错,暴力跳!

这样有\(89pts\)!!!

\(pyt\)学长在博客里说暴力的上界是\(89\)

然而,只需要加上快读+快输+特判(\(val-r==0\)),你就能轻松愉快的\(A\)掉,什么主席树?树套树?暴力\(yyds\)!!!!

暴力没有上界!!

其实应该可以卡掉,但是数据有点水,可以证明这种暴力的复杂度在最坏情况下是询问次数*节点数

假设树退化成一条链,每次都询问两个端点…….那这个暴力就萎了


#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=100005;
int n,a[maxn],head[maxn],tot,lastans,ls[maxn];
bool flag;
int read(){
    int x=0;char c;c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}

void print(int x){
    if(x==0)putchar('0');
    char c[105];int w=0;
    while(x)c[++w]=x%10+'0',x/=10;
    for(int i=w;i>=1;--i)putchar(c[i]);
    putchar('\n');
}
struct edge{
    int to,net;
}e[maxn<<1|1];
void add(int u,int v){
    e[++tot].net=head[u];
    head[u]=tot;
    e[tot].to=v;
}
struct node{
    int dep,fa,son,top,size,id;
}d[maxn];
int dfn[maxn],dn;

void dfs1(int x){
    dfn[x]=++dn;
    for(int i=head[x];i;i=e[i].net){
        int v=e[i].to;
        if(v==d[x].fa)continue;
        d[v].dep=d[x].dep+1;
        d[v].fa=x;
        dfs1(v);
    }
}

bool cmp(int x,int y){
    return dfn[x]<dfn[y];
}

int work(int u,int v,int r){
    int ans=2147483647;
    if(d[u].dep<d[v].dep)swap(u,v);
    while(d[u].dep>d[v].dep){
        ans=min(ans,abs(a[u]-r));
        if(ans==0)return ans;
        u=d[u].fa;
    }
    while(u!=v){
        ans=min(ans,abs(a[u]-r));
        ans=min(ans,abs(a[v]-r));
        if(ans==0)return ans;
        u=d[u].fa;v=d[v].fa;
    }
    ans=min(ans,abs(a[u]-r));
    return ans;
}

void DO(int k,int r){
    if(k<=1||flag){
        lastans=abs(a[ls[1]]-r);
        return;
    }
    sort(ls+1,ls+k+1,cmp);
    lastans=2147483647;
    for(int i=1;i<k;++i)lastans=min(lastans,work(ls[i],ls[i+1],r));
}
int main(){
    
    int q,type;flag=1;
    n=read();q=read();type=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)if(a[i]!=a[1]){flag=0;break;}
    for(int i=1;i<n;++i){
        int u,v;u=read();v=read();
        add(u,v);add(v,u);
    }
    if(!flag){
        d[1].dep=1;
        dfs1(1);
    }
    
    for(int i=1;i<=q;++i){
        int r,k;r=read();k=read();
        for(int j=1;j<=k;++j)ls[j]=read();
        for(int j=1;j<=k;++j)ls[j]=(ls[j]-1+lastans*type)%n+1;
        DO(k,r);
        print(lastans);
    }
    return 0;
}

不过这题还是再次证明了那个真理:暴力出奇迹!

C. f

两个数是否对逆序对有贡献,取决于两个数二进制不同的最高位

用\(Tire\)树预处理出来从某位开始与该数不同的数的个数,然后二分答案,二分逆序对个数,查询有多少小于的

直接搞会\(TLE\),需要\(meet in middle\),因为每一位的贡献是固定且互不影响的,所以将二进制拆成两半考虑,每次组合一下即可

查询时用到了一点双指针思想,利用前一半数量单增,对应后一半单减进行优化。

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=500005;
int a[maxn],a2[maxn],p2;
ll gt[33][2];
int n,k,p,k1,k2,s2,s1,root;
struct tire{
    struct node{
        int son[2],cnt;
    }t[maxn<<6|1];
    int cnt=1;
    void ins(int v){
        int x=1;
        for(int i=30;i>=-1;--i){
            ++t[x].cnt;
            if(i==-1)break;
            int now=v>>i&1;
            if(!t[x].son[now])t[x].son[now]=++cnt;
            gt[i][now]+=t[t[x].son[now^1]].cnt;
            x=t[x].son[now];
        }
    }
}T;
struct node{
    ll num;int i;
}fr[maxn],se[maxn];
bool cmp(node x,node y){return x.num<y.num;}
int check(ll x){
    ll ans=0,j=s2;
    for(int i=1;i<=s1;++i){
        while(se[j].num+fr[i].num>x&&j>0)--j;
        ans+=j;
    }
    return ans;
}

int main(){
    scanf("%d%d%d",&n,&k,&p);   
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    if(k==0){printf("0 0\n");return 0;}
    for(int i=1;i<=n;++i)T.ins(a[i]);
    k1=k>>1;k2=k-k1;
    s1=1<<k1,s2=1<<k2;
    for(int i=0;i<s1;++i){
        for(int j=0;j<k1;++j)fr[i+1].num+=gt[j][i>>j&1];
        fr[i+1].i=i;
    }
    sort(fr+1,fr+s1+1,cmp);
    for(int i=0;i<s2;++i){
        for(int j=0;j<k2;++j)se[i+1].num+=gt[j+k1][i>>j&1];
        se[i+1].i=i;
    }
    sort(se+1,se+s2+1,cmp);
    ll l=0,r=1ll*n*(n-1)/2;
    while(l<r){
        ll mid=(l+r)>>1;
        if(check(mid)<p)l=mid+1;
        else r=mid;
    }
    ll ans1=l;
    ll pr=check(ans1-1),j=s2;
    for(int i=1;i<=s1;++i){
        while(se[j].num+fr[i].num>ans1)--j;
        int ls=j;
        while(se[j].num+fr[i].num==ans1&&j>0)a2[++p2]=fr[i].i+(se[j].i<<k1),--j;
        j=ls;
    }
    sort(a2+1,a2+p2+1);
    ll ans2=a2[p-pr];
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}
————————

This game is a violent victory!!!!

A. d

How to say, the examination room thought of the positive solution, but mistakenly used double pointers, and didn’t think about the balance tree at all….

The method is to sort according to \ (a, B \), and then enumerate how many \ (a \) small ones are deleted according to ascending order, and the rest are deleted according to \ (B \), which is well solved by using the balanced tree. Unfortunately, the examination room completely forgot this thing..

Fortunately, such violence has \ (81pts \)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;

typedef long long ll;
const int maxn=100005;
const int inf=2147483647;
int n,m;
struct node{ll a,b;}a[maxn];
struct FHQ_Treap{
	struct node{
		int l,r,val,size,key;
	}t[maxn];
	int root,tot;
	int New(int val){t[++tot].val=val;t[tot].size=1;t[tot].key=rand();return tot;}
	void push_up(int x){t[x].size=t[t[x].l].size+t[t[x].r].size+1;}
	void split(int x,int &l,int &r,int val){
		if(x==0){l=r=0;return;}
		if(t[x].val>val){split(t[x].l,l,t[x].l,val);r=x;push_up(r);return;}
		else{split(t[x].r,t[x].r,r,val);l=x;push_up(l);return;}
	}
	int merge(int l,int r){
		if(!l||!r)return l|r;
		if(t[l].key<t[r].key){t[l].r=merge(t[l].r,r);push_up(l);return l;}
		else{t[r].l=merge(l,t[r].l);push_up(r);return r;}
	}
	void insert(int val){
		int l=0,r=0;split(root,l,r,val);
		root=merge(merge(l,New(val)),r);
	}
	void erase(int val){
		int l=0,r=0,m=0;split(root,l,r,val);split(l,l,m,val-1);
		m=merge(t[m].l,t[m].r);
		root=merge(merge(l,m),r);
	}
	int kth(int x,int k){
		if(k==t[t[x].l].size+1)return t[x].val;
		if(k<=t[t[x].l].size)return kth(t[x].l,k);
		else return kth(t[x].r,k-t[t[x].l].size-1);
	}
	void pre(int x){
        x+=10;
        for(int i=1;i<=x;++i)t[i].val=t[i].l=t[i].r=t[i].size=0;
        root=0;tot=0;
    }
}T;
int pa[maxn];
bool cma(int x,int y){
    if(a[x].a!=a[y].a)return a[x].a<a[y].a;
    return a[x].b<a[y].b;
}

void work(){
    T.pre(n);
    for(int i=1;i<=n;++i)pa[i]=i;
    sort(pa+1,pa+n+1,cma);
    for(int i=1;i<=n;++i)T.insert(a[i].b);
    ll ans=T.kth(T.root,m+1)*1ll*a[pa[1]].a;
    for(int i=1;i<=m;++i){
        T.erase(a[pa[i]].b);
        ans=max(ans,T.kth(T.root,m-i+1)*a[pa[i+1]].a*1ll);
    }
    printf("%lld\n",ans);
}

int main(){
    int T;scanf("%d",&T);
    for(int ask=1;ask<=T;++ask){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)scanf("%lld%lld",&a[i].a,&a[i].b);
        work();       
    }
    return 0;
}

B. e

This is the highlight of violence!!!!

Each inquiry is arranged in the order of \ (DFS \), and then \ (min \) is taken for the two adjacent points

Yes, violent jump!

There are \ (89pts \)!!!

\(PYT \) the senior said in his blog that the upper bound of violence is \ (89 \)

However, just add fast reading + fast losing + special judgment (\ (val-r = = 0 \), and you can easily and happily \ (a \). What is the chairman tree? Tree over tree? Violence \ (yyds \)!!!!

Violence has no upper bound!!

In fact, it should be possible to get stuck, but the data is a little watery, which can prove that the complexity of this violence is the number of queries * the number of nodes in the worst case

Suppose the tree degenerates into a chain, asking two endpoints at a time Then the violence will wither


#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=100005;
int n,a[maxn],head[maxn],tot,lastans,ls[maxn];
bool flag;
int read(){
    int x=0;char c;c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}

void print(int x){
    if(x==0)putchar('0');
    char c[105];int w=0;
    while(x)c[++w]=x%10+'0',x/=10;
    for(int i=w;i>=1;--i)putchar(c[i]);
    putchar('\n');
}
struct edge{
    int to,net;
}e[maxn<<1|1];
void add(int u,int v){
    e[++tot].net=head[u];
    head[u]=tot;
    e[tot].to=v;
}
struct node{
    int dep,fa,son,top,size,id;
}d[maxn];
int dfn[maxn],dn;

void dfs1(int x){
    dfn[x]=++dn;
    for(int i=head[x];i;i=e[i].net){
        int v=e[i].to;
        if(v==d[x].fa)continue;
        d[v].dep=d[x].dep+1;
        d[v].fa=x;
        dfs1(v);
    }
}

bool cmp(int x,int y){
    return dfn[x]<dfn[y];
}

int work(int u,int v,int r){
    int ans=2147483647;
    if(d[u].dep<d[v].dep)swap(u,v);
    while(d[u].dep>d[v].dep){
        ans=min(ans,abs(a[u]-r));
        if(ans==0)return ans;
        u=d[u].fa;
    }
    while(u!=v){
        ans=min(ans,abs(a[u]-r));
        ans=min(ans,abs(a[v]-r));
        if(ans==0)return ans;
        u=d[u].fa;v=d[v].fa;
    }
    ans=min(ans,abs(a[u]-r));
    return ans;
}

void DO(int k,int r){
    if(k<=1||flag){
        lastans=abs(a[ls[1]]-r);
        return;
    }
    sort(ls+1,ls+k+1,cmp);
    lastans=2147483647;
    for(int i=1;i<k;++i)lastans=min(lastans,work(ls[i],ls[i+1],r));
}
int main(){
    
    int q,type;flag=1;
    n=read();q=read();type=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)if(a[i]!=a[1]){flag=0;break;}
    for(int i=1;i<n;++i){
        int u,v;u=read();v=read();
        add(u,v);add(v,u);
    }
    if(!flag){
        d[1].dep=1;
        dfs1(1);
    }
    
    for(int i=1;i<=q;++i){
        int r,k;r=read();k=read();
        for(int j=1;j<=k;++j)ls[j]=read();
        for(int j=1;j<=k;++j)ls[j]=(ls[j]-1+lastans*type)%n+1;
        DO(k,r);
        print(lastans);
    }
    return 0;
}

However, this question proves the truth again: violence produces miracles!

C. f

Whether two numbers contribute to the reverse order pair depends on the highest bit of the two binary numbers

Use the \ (tire \) tree to preprocess the number of numbers that are different from the number from a certain bit, and then divide the answer into two parts, divide the number of pairs in reverse order, and query how many are less than

For a direct meeting of \ (TLE \), you need \ (meet in middle \). Because the contribution of each bit is fixed and does not affect each other, you can split the binary into two parts and combine it each time

A little double pointer idea is used in the query, which is optimized by using the single increase of the first half of the quantity and the single decrease of the second half.

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=500005;
int a[maxn],a2[maxn],p2;
ll gt[33][2];
int n,k,p,k1,k2,s2,s1,root;
struct tire{
    struct node{
        int son[2],cnt;
    }t[maxn<<6|1];
    int cnt=1;
    void ins(int v){
        int x=1;
        for(int i=30;i>=-1;--i){
            ++t[x].cnt;
            if(i==-1)break;
            int now=v>>i&1;
            if(!t[x].son[now])t[x].son[now]=++cnt;
            gt[i][now]+=t[t[x].son[now^1]].cnt;
            x=t[x].son[now];
        }
    }
}T;
struct node{
    ll num;int i;
}fr[maxn],se[maxn];
bool cmp(node x,node y){return x.num<y.num;}
int check(ll x){
    ll ans=0,j=s2;
    for(int i=1;i<=s1;++i){
        while(se[j].num+fr[i].num>x&&j>0)--j;
        ans+=j;
    }
    return ans;
}

int main(){
    scanf("%d%d%d",&n,&k,&p);   
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    if(k==0){printf("0 0\n");return 0;}
    for(int i=1;i<=n;++i)T.ins(a[i]);
    k1=k>>1;k2=k-k1;
    s1=1<<k1,s2=1<<k2;
    for(int i=0;i<s1;++i){
        for(int j=0;j<k1;++j)fr[i+1].num+=gt[j][i>>j&1];
        fr[i+1].i=i;
    }
    sort(fr+1,fr+s1+1,cmp);
    for(int i=0;i<s2;++i){
        for(int j=0;j<k2;++j)se[i+1].num+=gt[j+k1][i>>j&1];
        se[i+1].i=i;
    }
    sort(se+1,se+s2+1,cmp);
    ll l=0,r=1ll*n*(n-1)/2;
    while(l<r){
        ll mid=(l+r)>>1;
        if(check(mid)<p)l=mid+1;
        else r=mid;
    }
    ll ans1=l;
    ll pr=check(ans1-1),j=s2;
    for(int i=1;i<=s1;++i){
        while(se[j].num+fr[i].num>ans1)--j;
        int ls=j;
        while(se[j].num+fr[i].num==ans1&&j>0)a2[++p2]=fr[i].i+(se[j].i<<k1),--j;
        j=ls;
    }
    sort(a2+1,a2+p2+1);
    ll ans2=a2[p-pr];
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}