义乌集训7.15 contest 8题解

2021.7.15 Contest 题解

T1:

Description:

​ 平面直角坐标系上有 (n) 个点，白云想用一条直线来近似他们。

​ 白兔告诉白云，使得方差最小的直线是回归直线，若 (n) 个点为 ((x_i,y_i), i in [1, n])，则回归直线的斜率为

​ (k=frac{sum^n_{i=1}ig((x_i-x')*(y_i-y')ig)}{sum^n_{i=1}ig((x_i-x')^2ig)})

​ 其中 (x') 表示 (x_i) 的平均数，(y') 表示 (y_i) 的平均数。

​ 我们还知道，回归直线满足 (y'=kx'+b) ，由此也能够得到 (b) 的值。

​ 现在白云的任务是，向平面内依次插入 (n) 个点，每插入一个点，就需要求出所有点的回归直线的 (k) 和 (b)。

Input:

​ 第一行一个正整数 (n)

​ 接下来 (n) 行，每行两个实数 (x,y) 表示插入一个点 ((x, y))

Output:

​ 共 (n−1) 行，每行两个实数，第 (i) 行的两个实数表示插入前 ((i + 1)) 个点的回归直线的斜率和截距。保留四位小数。

Sample1 Input:

3
7.1 9.99
10.2 30.18
6.2 1.89

Sample1 Output:

6.5129 -36.2516
6.9280 -40.2497

Hint:

对于 (60\%) 的数据, (n leq 10^3)
对于 (100\%) 的数据, (n leq 10^5,;x,y leq 100)

给出的实数的小数位数不超过 (6) 位

题目分析：

​ 稍微推一下柿子即可。

代码如下(马蜂很丑，不喜勿喷)——

#include<bits/stdc++.h>
#define N 5005
#define inf 100000000
#define LL long long
#define DB double
using namespace std;
int n;DB sx1,sx2,sy,sxy,x,y,k,b;
inline int read(){int ret=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}while(isdigit(ch)) ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();return ret*f;}
int main(){
//	freopen("line.in","r",stdin);freopen("line.out","w",stdout);
	n=read();for(register int i=1;i<=n;i++) scanf("%lf%lf",&x,&y),sx1+=x,sx2+=x*x,sy+=y,sxy+=x*y,(i^1)&&(k=(sxy-sx1*sy/(DB)i)/(sx2-sx1*sx1/(DB)i),b=sy/(DB)i-k*sx1/(DB)i,printf("%0.4lf %0.4lf
",k,b),0);return 0;
}

T2:

Description:

​ 白云建立了 (n) 个商店，白兔打算按照编号 (1 ∼ n) 的顺序访问这些商店。商店 (i) 有一个价格 (a_i) 表示交易商品所需的代价。

​ 白兔在按顺序走时，每到达一个商店，可以花费代价购买一件商品，并放入自己手中。也可以出售手上的商品，并获得利润。

​ 白兔的力量有限，同一时刻只能携带一个商品。问它遍历完所有商店后能够获得的利润最大是多少？

​ 白兔的精力也有限，所以，在最大化利润的前提下，它想让交易次数尽可能地少。

​ 当然，白云不想让白兔轻松获利，它有时会命令一段区间内的商店把价格同时加上一个数。

Input:

​ 第一行一个整数 (T) 表示数据组数
​ 对于每一组数据
​ 第一行两个整数 (n,Q)
​ 第二行 (n) 个整数描述序列 (a_1 ∼ a_n)
​ 接下来 (Q) 行，每行第一个数表示操作类型。
​ 如果为 (1) 表示你需要帮助白兔求出，如果它立即出发，它能获得的最大利润，以及在最大利润的前提下，最小交易次数。
​ 如果为 (0) 后面接三个整数 (l,r,c) 表示在区间 ([l, r]) 内的商品价格都加上 (c)。

Output:

​ 对于每一个询问操作，输出一行两个数表示最大利润和最小交易次数。

Sample1 Input:

2
5 9
9 10 7 6 8
1
0 4 5 2
0 3 5 4
1
0 2 5 -2
0 3 5 -3
0 4 5 -2
0 5 5 -4
1
4 3
2 4 3 5
1
0 3 3 3
1

Sample1 Output:

3 4
5 2
0 0
4 4
4 2

Hint:

对于 (100\%) 的数据，(T le 5,1 le n,Q le 10^5,|c| le 10^5)，任意时刻 (0 < a_i <2^{31})。

题目分析：

​ 第一问很简单，我们贪心地考虑，对于 (forall i in [1,n-1]) 如果 (a_i<a_{i+1})，则在 (i) 买入，在 (i+1) 卖出，这样答案一定是最优的。

​ 第二问我们考虑用线段树。在贪心的基础上，我们发现第二问实际上就是让我们求所有的极长非负整数区间且区间和大于 (0) 的区间个数。用线段树维护即可。

代码如下(马蜂很丑，不喜勿喷)——

#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int n,Q,a[N],R[N<<2],L[N<<2],s[N<<2];LL S[N<<2];
inline void PU(int x){S[x]=S[x<<1]+S[x<<1|1],s[x]=s[x<<1]+s[x<<1|1];if(L[x<<1|1]>0&&R[x<<1]>0) s[x]--;if(!L[x<<1]) L[x]=L[x<<1|1];else L[x]=L[x<<1];if(!R[x<<1|1]) R[x]=R[x<<1];else R[x]=R[x<<1|1];}
inline void U(int x,int l,int r,int pos,int v){if(l==r){L[x]+=v,R[x]+=v;if(L[x]>0) S[x]=L[x],s[x]=1;else S[x]=s[x]=0;return;}int mid=l+r>>1;if(mid>=pos) U(x<<1,l,mid,pos,v);else U(x<<1|1,mid+1,r,pos,v);PU(x);}
inline void B(int x,int l,int r){if(l==r){L[x]=R[x]=a[l+1]-a[l];if(L[x]>0) S[x]=L[x],s[x]=1;else S[x]=s[x]=0;return;}int mid=l+r>>1;B(x<<1,l,mid),B(x<<1|1,mid+1,r),PU(x);}
struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
	FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
	template<typename T>FastIO& operator >> (T&ret){
		ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
	}
	FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
	template<typename T>FastIO& operator << (T x){
		if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
//	freopen("seq.in","r",stdin);freopen("seq.out","w",stdout);
	int T;fin>>T;while(T--){fin>>n>>Q;for(register int i=1;i<=n;i++) fin>>a[i];B(1,1,n-1);while(Q--){int op,l,r,v;fin>>op;if(op==1) fout<<S[1]<<' '<<s[1]*2<<'
';else fin>>l>>r>>v,(l^1)&&(U(1,1,n-1,l-1,v),0),(r^n)&&(U(1,1,n-1,r,-v),0);}}return 0;
}

T3:

Description:

​ 白云有一颗 (n) 个节点的树，每个点有一个点权

​ 白兔需要找到两条点不相交的路径，要求最大化这两条路径覆盖点的点权和

Input:

​ 第一行包含一个数 (n) 表示树的结点数
​ 接下来一行 (n) 个数表示每个点的点权
​ 接下来 (n − 1) 行每行两个数描述一条树边。

Output:

​ 输出最大点权和。

Sample1 Input:

8
1 2 99 4 5 3 2 1
1 2
1 4
1 6
1 3
4 5
6 7
6 8

Sample1 Output:

115

Sample2 Input:

9
1 2 3 4 5 6 7 8 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9

Sample2 Output:

25

Hint:

对于全部数据，(1 leq n leq 10^5,1leq a_i leq 10^9.)

题目分析：

​ 两种做法，一种是找出树的直径，分类讨论即可；另一种也是我写的方法，换根DP。

​ 考虑到两条路径的形态只会有三种情况：

​ 1.两个毫无干系的子树里各选出一条链；

​ 2.在一棵子树里选出一条经过子树的根的链，然后在剩余的儿子子树里找一条链；

​ 3.在一棵子树里选出一条子树内的链，然后再选一条经过子树的父亲的链。

​ 直接维护每个节点到叶子结点的最长链、次长链，子树内的最长链以及经过子树的父亲的最长链即可。

代码如下(马蜂很丑，不喜勿喷)——

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int n,tot,fir[N],nxt[N<<1],son[N<<1];LL f[N],g[N],a[N],ans;inline void add(int x,int y){son[++tot]=y,nxt[tot]=fir[x],fir[x]=tot;} inline void dfs(int x,int fa){
	int son1=0,son2=0,size=0;LL dis1=-1,dis2=-1,S1=-1,S2=-1;for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa)
	{int to=son[i];size++,dfs(to,x),g[x]=max(g[x],g[to]);if(g[to]>S1) S2=S1,S1=g[to];else if(g[to]>S2) S2=g[to];if(f[to]>dis1) dis2=dis1,son2=son1,dis1=f[to],son1=to;else if(f[to]>dis2) dis2=f[to],son2=to;}
	ans=max(ans,S1+S2),f[x]=a[x]+f[son1],g[x]=max(g[x],f[x]+f[son2]),ans=max(ans,g[x]);for(register int i=fir[x];i;i=nxt[i]) if((son[i]^fa)&&(son[i]^son1)&&(son[i]^son2)) ans=max(ans,f[x]+f[son2]+g[son[i]]),ans=max(ans,a[x]+f[son[i]]+f[son2]+g[son1]),ans=max(ans,a[x]+f[son[i]]+f[son1]+g[son2]);
}
inline void dfs2(int x,int fa,LL dis){
	int son1=0,son2=0;LL dis1=-1,dis2=-1;for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa) if(f[son[i]]>dis1) dis2=dis1,son2=son1,dis1=f[son[i]],son1=son[i];else if(f[son[i]]>dis2) dis2=f[son[i]],son2=son[i];
	for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa){int to=son[i];if(to^son1) ans=max(ans,dis+f[son1]+g[to]),dfs2(to,x,max(dis,f[x])+a[to]);else ans=max(ans,dis+f[son2]+g[to]),dfs2(to,x,max(dis,f[son2]+a[x])+a[to]);}
}
struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
	FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
	template<typename T>FastIO& operator >> (T&ret){
		ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
	}
	FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
	template<typename T>FastIO& operator << (T x){
		if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
//	freopen("attack.in","r",stdin);freopen("attack.out","w",stdout);
	fin>>n;for(register int i=1;i<=n;i++) fin>>a[i];for(register int i=1,x,y;i<n;i++) fin>>x>>y,add(x,y),add(y,x);dfs(1,0),dfs2(1,0,a[1]);cout<<ans<<'
';return 0;
}

T4:

Description:

白云在白兔的城市，打算在这里住 (n) 天，这 (n) 天，白云计划找白兔订购水。

白云给出了接下来的 (n) 天，每天的需水量，第 (i) 天为 (D_i) 升。

白兔给出了接下来的 (n) 天，每天水的价格，第 (i) 天为 (P_i) 元每升。

白云的小区有一个共用水壶，最大容量为 (V) 升，初始为空。 接下来每天，白云可以进行如下操作：

  1. 使用水壶中的部分水
  2. 向白兔购买若干水，并放入水壶中
  3. 向白兔购买若干水，并使用

任何时候水壶中的水不能超过 (V) 升，而且每升水每在水壶中存放一天，需要付出 (m)元

白兔为了难为白云，决定在某些天进行破坏操作，即选择一个子序列 (b_1,...,b_t)，在这序列中的每一天，它会在当天早上把前一天储存的水放掉。第 (i) 天有一个破坏难度 (val_i)，白兔为了挑战自己，决定让自己进行破坏操作的 (val) 是严格单调递增。它会找一个破坏天数最多的方案，在保证破坏次数最多的前提下，使得破坏序列的字典序最小。

白云已经知道了白兔的想法，并且获取了这个破坏难度，所以它已经能计算出白兔会在哪些日子进行破坏。

那么白云想知道，在此基础上，白云要度过接下来 (n) 天的最小总花费。

Input:

​ 第一行三个整数 (n, m, V)
​ 第二行 (n) 个整数描述 (val) 数组
​ 第三行 (n) 个整数描述 (D) 数组
​ 第四行 (n) 个整数描述 (P) 数组

Output:

​ 输出最小花费。

Sample1 Input:

5 10 10
5 1 2 0 3
2 2 2 2 2
1 10 20 50 10

Sample1 Output:

142

Hint:

对于 (100\%) 的数据，满足 (nle 10^6)，(m,p_ile 10^3)，答案 (leq 2^{63}-1).

​

题目分析：

​ 考场上理解错题意了，写了一个CDQ分治+斜率优化DP，QAQ。

​ 正解贪心（据说是由一道费用流的题目改编过来的

​ 我们首先先求出最长上升子序列，用单调栈+二分维护出来即可。接着就可以搞事情了。

​ 显然，对于一组最优解，如果白云在第 (i) 天买了若干水存到水壶里，那么 (p_i) 一定是单调递增的，因为越早买的水，如果不仅费用高，占容量，而且还要额外付 (m) 元，显然是不优的。于是我们可以维护一个单调队列，如果队首比当天直接买更优，就用队首去更新答案，模拟这个过程，由于有容量限制，还需要维护一个全局标记。

代码如下(马蜂很丑，不喜勿喷)——

#include<bits/stdc++.h>
#define N 1000005
#define inf 2147483647
#define LL long long
#define DB double
using namespace std;
int n,H,T,q[N],val[N],st[N],top,fa[N],Min[N];LL m,tag,a[N],W[N],P[N],D[N],ans,V;bool vis[N];vector<int> G[N];
//int n,top,tot,H,T,q[N],fa[N],Min[N],st[N],rk[N],rk2[N],K2[N],K[N];LL m,V,s[N],f[N],val[N],D[N],P[N];bool vis[N];
//inline LL calcy(int x){return f[x]-s[x];} inline LL calcx(int x){return m*(LL)x-P[x];} inline LL Calcy(int x,int y){return calcy(x)-calcy(y);} inline LL Calcx(int x,int y){return calcx(x)-calcx(y);}
//inline LL calc(int x,int y){return calcy(y)-min(D[x],V)*calcx(y)+s[x-1]+m*(LL)x*min(D[x],V)+P[x]*max(D[x]-V,0ll);} inline bool cmp(int x,int y){return D[x]<D[y];} 
//inline void solve(int L,int R){
//	if(L==R){f[L]=min(f[L],f[L-1]+P[L]*D[L]);return;}int mid=L+R>>1,k1=L,k2=mid+1;
//	for(register int i=L;i<=R;i++) if(rk[i]<=mid) K[k1]=rk[i],k1++;else K2[k2]=rk[i],k2++;for(register int i=L;i<=mid;i++) rk[i]=K[i];for(register int i=mid+1;i<=R;i++) rk[i]=K2[i];solve(L,mid);
//	int l=L,r=R;for(register int i=mid;i>=L;i--) if(vis[i]){l=i;break;} for(register int i=mid+1;i<=R;i++) if(vis[i]){r=i-1;break;} 
//	H=1,T=0;for(register int i=L;i<=mid;i++) if(rk2[i]>=l){int x=rk2[i];while(H<T&&(DB)Calcy(q[T],x)/(DB)Calcx(q[T],x)<=(DB)Calcy(q[T-1],q[T])/(DB)Calcx(q[T-1],q[T])) T--;q[++T]=x;}
//	for(register int i=mid+1;i<=R;i++) if(rk[i]<=r){int x=rk[i];while(H<T&&(DB)Calcy(q[H],q[H+1])/(DB)Calcx(q[H],q[H+1])<=min(V,D[x])) H++;if(H<=T) f[x]=min(f[x],calc(x,q[H]));}solve(mid+1,R);
//	int i=L,j=mid+1,k=L;while(i<=mid&&j<=R) if(m*(LL)rk2[i]-P[rk2[i]]<=m*(LL)rk2[j]-P[rk2[j]]) K2[k]=rk2[i],k++,i++;else K2[k]=rk2[j],k++,j++;while(i<=mid) K2[k]=rk2[i],k++,i++;while(j<=R) K2[k]=rk2[j],k++,j++;for(i=L;i<=R;i++) rk2[i]=K2[i];
//}
//387590581
//1250938123
inline void ins(int x,int y){vector<int>::iterator it=G[x].end();it--;if(val[*it]>val[y]) G[x].push_back(y);}
inline int get(int x,int y){int l=0,r=G[y].size()-1,num;while(l<=r){int mid=l+r>>1;if(val[G[y][mid]]<x) num=G[y][mid],r=mid-1;else l=mid+1;}return num;} struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
	FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
	template<typename T>FastIO& operator >> (T&ret){
		ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
	}
	FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
	template<typename T>FastIO& operator << (T x){
		if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
//	freopen("new.in","r",stdin);//freopen("new.out","w",stdout);
//	fin>>n>>m>>V;for(register int i=1;i<=n;i++) fin>>val[i];for(register int i=1;i<=n;i++) fin>>D[i];for(register int i=1;i<=n;i++) fin>>P[i],s[i]=s[i-1]+D[i]*P[i],f[i]=s[i],rk[i]=rk2[i]=i;
//	if(n==2){LL ans=D[1]*P[1]+D[2]*P[2];if(val[2]<=val[1]) if(D[2]<=V) ans=min(ans,D[1]*P[1]+D[2]*(m+P[1]));else ans=min(ans,D[1]*P[1]+(D[2]-V)*P[2]+V*(m+P[1]));cout<<ans<<'
';return 0;}
//	st[++top]=0,val[0]=-inf;for(register int i=1;i<=n;i++){
//		int l=1,r=top,pos=1;while(l<=r){int mid=l+r>>1;if(val[st[mid]]<val[i]) l=mid+1,pos=mid;else r=mid-1;}
//		fa[i]=st[pos];if(pos==top) st[++top]=i,Min[top]=i;else if(val[i]<val[st[pos+1]]) st[pos+1]=i;
//	}
//	int x=Min[top];while(x) vis[x]=1,x=fa[x];sort(rk+1,rk+n+1,cmp),solve(1,n);cout<<f[n]<<'
';
	fin>>n>>m>>V;for(register int i=1;i<=n;i++) fin>>val[i];for(register int i=1;i<=n;i++) fin>>D[i];for(register int i=1;i<=n;i++) fin>>P[i],W[i]=P[i]-m*(LL)i;
	st[++top]=0,val[0]=-inf,G[1].push_back(0);for(register int i=1;i<=n;i++){
		int l=1,r=top,pos=1;while(l<=r){int mid=l+r>>1;if(val[st[mid]]<val[i]) l=mid+1,pos=mid;else r=mid-1;}
		fa[i]=get(val[i],pos);if(pos==top) st[++top]=i,Min[top]=i,G[top].push_back(i);else if(val[i]<val[st[pos+1]]) st[pos+1]=i,ins(pos+1,i);
	}
	int x=Min[top];while(x) vis[x]=1,x=fa[x];H=1,T=0;for(register int i=1;i<=n;i++){
		if(vis[i]) H=T+1,tag=0;LL tt=tag;while(H<=T&&W[q[H]]<=W[i]&&a[q[H]]-tt<=D[i]) if(a[q[H]]-tt<0) H++;else tag+=(a[q[H]]-tt),D[i]-=(a[q[H]]-tt),ans+=(a[q[H]]-tt)*(W[q[H]]+m*(LL)i),H++,tt=tag;
		if(H<=T&&W[q[H]]<=W[i]) ans+=D[i]*(W[q[H]]+m*(LL)i),tag+=D[i],D[i]=0;ans+=D[i]*P[i];while(H<=T&&W[i]<W[q[T]]) T--;q[++T]=i,a[i]=V+tag;
	}
	cout<<ans<<'
';return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/jiangxuancheng/p/15046818.html