• 周五. 12月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

义乌集训7.16 contest 9题解

admin

11月 28, 2021

2021.7.16 Contest 题解

T1:

Description:

​ 白云为了提高 coke 的销售量,进行了一次促销活动。活动的内容如下:

• coke 的价格降为 (2) 元每瓶。

• 每 (3) 个空瓶可兑换 (1) 元钱。

• 不能向他人借钱和空瓶。

现在,白兔有 (n) 元钱,请你帮他算出他最多可以买多少瓶 coke。

Input:

​ 仅一行,一个数 (n)

Output:

​ 仅一行,表示他最多可以买的 coke 的瓶数。

Sample1 Input:

12

Sample1 Output:

7

Hint:

对于 (50\%) 的数据, (n leq 100)
对于 (100\%) 的数据, (n leq 10^9)

题目分析:

​ 已经被做烂的题目。。。

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

#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int n,ans,res,tmp;
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(){
	cin>>n;while(n>=2) tmp=n/2,ans+=tmp,n-=tmp*2,res+=tmp,n+=res/3,res%=3;cout<<ans<<'
';return 0;
}

T2:

Description:

​ 一个有 (n) 个整数的数字序列,白云和白兔都想从中选出一个区间,但是要求他们选出的区间不能相交。 求白云和白兔所选区间数字之和的最大值。

Input:

​ 第一行,一个数 (n),表示整数的个数。

​ 第二行 (n) 个数,描述这个序列。

Output:

​ 仅一行,表示最大的数字和。

Sample1 Input:

10
1 2 -3 2 1 4 -3 2 1 2

Sample1 Output:

12

Hint:

data range:

序列所有数绝对值在 (10^5) 以内

对于 (50\%) 的数据,(n leq 100)

对于 (70\%) 的数据,(n leq 1000)

对于 (100\%) 的数据,(n leq 100000)

sample explaination:

​ 取两个区间分别为 (2,1,4)(2,1,2),得到最大的和

题目分析:

​ 简单题。维护一个前缀最大子段和,一个后缀最大子段和,枚举分段点,直接取max就行了。

​ 但是我在写这道题的时候想到了一个有趣的结论——

​ 答案一定是一个全局最大子段和+除去这一子段后的最大子段和或者是全局最大子段和-这一最大子段中的最小子段,证明显然。

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

#include<bits/stdc++.h>
#define N 100005
#define inf 100000000
#define LL long long
using namespace std;
int n;LL ans,res,l[N],r[N],Max,a[N]; 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(){
	fin>>n,Max=0;for(register int i=1;i<=n;i++){fin>>a[i];if(res+a[i]<0) res=0;else res+=a[i];if(res>Max) Max=res;l[i]=Max;}
	Max=0,res=0;for(register int i=n;i;i--){if(res+a[i]<0) res=0;else res+=a[i];if(res>Max) Max=res;r[i]=Max;} for(register int i=0;i<=n;i++) ans=max(ans,l[i]+r[i+1]);cout<<ans;return 0;
}

T3:

Description:

​ 白云有一个 (1,2,…,n) 的排列。 白兔想从中选出一个大小为三的子序列。

​ 白云给了一个要求:这个子序列的第一个数必须是三个数中的最小值,第二个数必须是三个数中的最大值。

​ 白兔想知道它有多少种选子序列的方案。

Input:

​ 一行两个数 (n,seed) 本题的排列采用随机数生成器生成,生成方法为:

int n;
unsigned long long seed;
unsigned long long rd() {
	seed ^= seed << 13;
	seed ^= seed >> 7;
	seed ^= seed << 17;
	return seed;
}
cin >> n >> seed;
p[1] = 1;
for (int i = 2 ; i <= n ; i++) {
	p[i] = i;
	swap(p[i], p[rd() % i + 1]);
}

Output:

​ 输出满足要求的子序列方案数。

Sample1 Input:

5 10

Sample1 Output:

3

Hint:

data range:

​ 对于 (30\%) 的数据,(n leq 100)

​ 对于 (50\%) 的数据,(n leq 1000)

​ 对于 (80\%) 的数据,(n leq 10^5)

​ 对于 (100\%) 的数据,(n leq 3 imes 10^6)

sample explaination:

​ 排列为 5 1 4 3 2,满足要求的子序列为 (1, 4, 3),(1, 4, 2),(1, 3, 2)

题目分析:

​ 看到数据范围的时候,我们可以发现用线段树由于常数很大一定是艹不过去的。

​ 最简单的解法就是直接树状数组维护逆序对容斥一下,但是我这里讲一种我自己的比较复杂的一种解法——

​ 首先题目的意思就是求满足 $a_i < a_k < a_j $三元组 ((i,j,k)) 的数量。

​ 我们从大到小枚举 (k),那么问题就是快速如何求出 (1leq i < j<k)(a_i<a_k<a_j) 的二元组个数。(以下的 (i) 默认小于 (k) )

​ 我们可以快速求出 (a_i<a_k)(i) 的个数 (tmp),也可以快速求出 (a_i<a_k)(i) 之和 (res)

​ 那么根据容斥原理,我们可以得到,(1leq i < j<k)(a_i<a_k<a_j) 的二元组个数=(tmp*(k-1)-res-tmp*(tmp-1)/2)

​ 这个柿子可能需要一定时间理解一下。

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

#include<bits/stdc++.h>
#define N 3000005
#define inf 2147483647
#define LL long long
using namespace std;
int n,a[N],s[N];LL ans,sum[N],S[N];unsigned long long seed;inline unsigned long long rd(){seed^=seed<<13;seed^=seed>>7;seed^=seed<<17;return seed;}
inline void A(int x,int y,int z){for(register int i=x;i<=n;i+=i&-i) S[i]+=y,s[i]+=z;} inline void Q(int x,int &y,LL &z){for(register int i=x;i;i-=i&-i) y+=s[i],z+=S[i];}
inline void solve(int x){int y=a[x];A(y,-x,-1);int tmp=y-1;LL res=sum[y-1];Q(y-1,tmp,res);ans+=1ll*tmp*(x-1)-res-1ll*tmp*(tmp-1)/2ll;}
 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(){
	cin>>n>>seed,a[1]=1,sum[1]=1;for(register int i=2,x;i<=n;i++) a[i]=i,x=rd()%i+1,swap(a[i],a[x]),sum[a[i]]=i,sum[a[x]]=x;for(register int i=2;i<=n;i++) sum[i]+=sum[i-1];for(register int i=n;i;i--) solve(i);cout<<ans<<'
';return 0;
}

T4:

Description:

​ 有一天 Mifafa 回到家,发现有 (n) 只老鼠在她公寓的走廊上,她大声呼叫,所以老鼠们都跑进了走廊的洞中。

​ 这个走廊可以用一个数轴来表示,上面有 (n) 只老鼠和 (m) 个老鼠洞。第 (i) 只老鼠有一个坐标 (x_i),第 (j) 个洞有一个坐标 (p_j) 和容量 (c_j)。容量表示最多能容纳的老鼠数量。

​ 找到让老鼠们全部都进洞的方式,使得所有老鼠运动距离总和最小。

​ 老鼠 (i) 进入洞 (j) 的运动距离为 (|x_i−p_j|)

无解输出-1

Input:

​ 第一行包含两个整数 (n,m),表示老鼠和洞的数量。

​ 第二行包含 (n) 个整数 (x_1 … x_n),表示老鼠坐标。

​ 接下来 (m) 行每行两个整数 (p, c),表示每个洞的坐标和容量。

Output:

​ 输出最小运动距离或者-1。

Sample1 Input:

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

Sample1 Output:

11

Hint:

对于 (100\%) 的数据,满足 (1leq c,n,mle 10^6)(1leq |p|,|x|le 10^9).

题目分析:

​ 正解反悔贪心。我们将老鼠和洞按照横坐标一起排序。考虑对于一只老鼠 (i),假设它一开始进入了在它左侧离它最近的且没使用完的洞 (j)(如果没有符合条件的洞将距离设为+∞),那么如果要用另一个洞 (k) 去替换 (j),贡献为 ((p_k-x_i)-(x_i-p_j)=p_k+(-2*x_i+p_j)).

​ 同理,对于一个洞 (i),那么如果要用另一个老鼠 (k) 去替换洞里原有的老鼠 (j),贡献为 ((x_k-p_i)-(p_i-x_j)=x_k+(-2*p_i+x_j)).

​ 那么我们用堆来存下每一个枚举过的老鼠,不断地用当前枚举到的洞 (k) 去更新贡献直到 (c_k=0) 或者老鼠已经全部更新过或者用 (k) 去更新不会更优,同时再开一个堆存下洞 (k) 替换老鼠 (i) 的贡献 – (p_k) 。如果更新之后 (c_k) 有剩余,用刚开的堆把 (k) 给存起来。

​ 于是两个堆交替地进行反悔贪心,复杂度 (O(nlogn))

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

#include<bits/stdc++.h>
#define N 1000005
#define LL long long
#define inf 2147483647
#define INF 2147483647114
using namespace std;
struct node{LL x;int id;bool operator <(const node&a)const{return x>a.x;}};
int n,m,rk[N],x[N],p[N],c[N];LL f[105][105],s,V[N];bool flg=1;LL ans;priority_queue<LL,vector<LL>,greater<LL> > H1;priority_queue<node> H2;
inline bool cmp(int x,int y){return p[x]<p[y];} 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(){
	fin>>n>>m;for(register int i=1;i<=n;i++) fin>>x[i];for(register int i=1;i<=m;i++) fin>>p[i]>>c[i],s+=c[i],(c[i]^n)&&(flg=0,0),rk[i]=i;if(s<n){puts("-1");return 0;}sort(x+1,x+n+1),sort(rk+1,rk+m+1,cmp);int now=1;for(register int i=1;i<=n;i++){
		while(now<=m&&p[rk[now]]<=x[i]){
			while(c[rk[now]]&&!H1.empty()&&p[rk[now]]+H1.top()<0){LL tmp=p[rk[now]]+H1.top();c[rk[now]]--,H1.pop(),H2.push(node{-p[rk[now]]-tmp,rk[now]}),ans+=tmp;}
			if(c[rk[now]]) c[rk[now]]--,H2.push(node{-p[rk[now]],rk[now]});now++;
		}
		LL tmp=inf;if(!H2.empty()){tmp=x[i]+H2.top().x;int id=H2.top().id;H2.pop();if(c[id]) c[id]--,H2.push(node{-p[id],id});}ans+=tmp;H1.push(-x[i]-tmp);
	}
	while(now<=m){while(c[rk[now]]&&!H1.empty()&&p[rk[now]]+H1.top()<0){LL tmp=p[rk[now]]+H1.top();c[rk[now]]--,H1.pop(),H2.push(node{-p[rk[now]]-tmp,rk[now]}),ans+=tmp;}if(c[rk[now]]) c[rk[now]]--,H2.push(node{-p[rk[now]],rk[now]});now++;}return cout<<ans,0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注