csp-s模拟测试56Merchant， Equation，Rectangle题解

概述题面：https://www.cnblogs.com/Juve/articles/11619002.html merchant： 二分答案，贪心选前m大的 但是用sort复杂度不优，会T掉 我们只是找前m大的，至于前m大的如何排序我们并不关心 所以用nth_element()函数找出前m大的，然后贪心check #include<iostream>#include<cstdio>#incl @H_404_0@ @H_404_0@

题面：https://www.cnblogs.com/Juve/articles/11619002.html

merchant：

二分答案，贪心选前m大的

但是用sort复杂度不优，会T掉

我们只是找前m大的，至于前m大的如何排序我们并不关心

所以用nth_element()函数找出前m大的，然后贪心check

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define int long long#define re registerusing namespace std;const int MAXN=1e6+5;int n,m,s,l=0,r=1e9,mID,d[MAXN];struct node{	int k,b;}c[MAXN];int max(int a,int b){	return a>b?a:b;}inline bool check(re int x){	re int res=0;	for(int i=1;i<=n;++i) d[i]=c[i].k*x+c[i].b;	nth_element(d+1,d+n-m+1,d+n+1);	for(re int i=n-m+1;i<=n;++i){		res+=max(0,d[i]);		if(res>=s) return 1;	}	return res>=s;}signed main(){	scanf("%lld%lld%lld",&n,&m,&s);	for(re int i=1;i<=n;++i) scanf("%lld%lld",&c[i].k,&c[i].b);	while(l<r){		mID=(l+r)>>1;		if(check(mID)) r=mID;		else l=mID+1;	}	printf("%lld\n",l);	return 0;}

equation:

我们化减一下就能得出每个$x_i$关于$x_1$的关系：

若设$deep[1]=1$，则：${x_1}\pm{x_i}=t_i$，每个节点i都能表示成这个式子，

$deep[x_i]$是偶数就是加，奇数就是减

把边权放到点权，那么：

$t_i=\sum k*w[j]$，其中j是i到根节点路径上的点，$k=\pm1$，$deep[x_i]$是偶数就是1，奇数就是-1，

对于$t_i$，我们可以用树状数组查询，修改用差分思想，注意deep[i]的正负

询问就是三个未知数三个方程

 

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define int long long#define re registerusing namespace std;const int MAXN=1e6+5;int n,q,vall,fa[MAXN],w[MAXN];int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=0,val[MAXN<<1];voID add(int u,int v,int ww){	++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt,val[cnt]=ww;}int c[MAXN];int lowbit(int x){    return x&(-x);}voID update(int pos,int val){    for(int i=pos;i<=n;i+=lowbit(i)){        c[i]+=val;    }}int query(int pos){    int res=0;    for(int i=pos;i>0;i-=lowbit(i)){        res+=c[i];    }    return res;}int deep[MAXN],dfn=0,rk[MAXN],ID[MAXN],IDd[MAXN];voID dfs(int x,int f,int dep){    deep[x]=dep;    rk[++dfn]=x;    ID[x]=dfn;    for(int i=pre[x];i;i=nxt[i]){        int y=to[i];        if(y==f) continue;        dfs(y,x,dep+1);    }    IDd[x]=dfn;}signed main(){    //freopen("test.in","r",stdin);	scanf("%lld%lld",&q);	if(q==0) return 0;	for(int i=2;i<=n;++i){		scanf("%lld%lld",&fa[i],&w[i]);		add(i,fa[i],w[i]),add(fa[i],i,w[i]);	}    dfs(1,1);    for(int i=1;i<=n;++i){        if((deep[i]&1)==0) update(ID[i],update(IDd[i]+1,-w[i]);        else update(ID[i],-w[i]),w[i]);    }	while(q--){	    int opt;        scanf("%lld",&opt);        if(opt==1){            int u,v,s;            scanf("%lld%lld%lld",&u,&v,&s);            int p=query(ID[u]),q=query(ID[v]);            if((deep[u]&1)==0&&(deep[v]&1)==0){//x1+xu=p,x1+xv=q;                int t=p+q-s;                if(t&1==1) puts("none");                else printf("%lld\n",t/2);            }            else if((deep[u]&1)==0&&(deep[v]&1)==1){//x1+xu=p,x1-xv=q;                int t=p-q;                if(t==s) puts("inf");                else puts("none");            }            else if((deep[u]&1)==1&&(deep[v]&1)==0){                int t=q-p;                if(t==s) puts("inf");                else puts("none");            }            else{//x1-xu=p,x1-xv=q;                int t=p+q+s;                if((t&1)==1) puts("none");                else printf("%lld\n",t/2);            }        }else{            int u,ww;            scanf("%lld%lld",&ww);            if((deep[u]&1)==0){                update(ID[u],ww-w[u]),update(IDd[u]+1,w[u]-ww);            }else{                update(ID[u],w[u]-ww),ww-w[u]);            }            w[u]=ww;        }	}	return 0;}

 

rectangle：

不会了，只有n⁴暴力

先考虑横坐标互不相同的情况。枚举矩形的右边界R和左边界L,假设左边界上的点的坐标为(L,y 1 ),右边界上的点的坐标为(R,y 2 ),不妨设y 1 ≤ y 2,考虑怎么一次计算所有左边界为L右边界为R的矩形的面积和。由于这些矩形的面积可以表示为(R − L) × (y max − y min ),可以发现我们只需要知道在所有L ≤ x ≤ R的点中,满足y ≤ y 1 的不同的y有多少个,以及它们的和;相应地还有满足y ≥ y 2 的信息。枚举右边界后,从大到小地枚举左边界,在移动左边界时用树状数组维护信息即可。现在考虑一般情况,以相同的方式枚举左右边界,此时横坐标为L或R的点可能有很多,这些点的纵坐标会划分出若干个区间,此时再枚举上边界的纵坐标所在的区间,即可得到对应的可行的下边界的区间,仍然可以用树状数组维护和查询。复杂度为O(nm log m),其中m为坐标范围。树状数组常数非常优秀,因此可以快速通过。bonus: 找到一个复杂度为O(nm)的做法。

@H_404_0@ 总结

以上是内存溢出为你收集整理的csp-s模拟测试56Merchant， Equation，Rectangle题解全部内容，希望文章能够帮你解决csp-s模拟测试56Merchant， Equation，Rectangle题解所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。