首页 > 其他分享 >Codeforces Round 953(Div.2) 题解(A-E)

Codeforces Round 953(Div.2) 题解(A-E)

时间：2024-07-08 20:52:30浏览次数：18  
标签：ch 题解 953 long sum Div.2 define LL getchar

Codeforces Round 953(Div.2) 题解(A-E)

A

题意

Alice有n本书，第一本书有\(a_1\)页，序号为1，第二本书有\(a_2\)页,序号为2， …… , 第n本书有\(a_n\)页，序号为n。Alice将把所有书分成两堆，并阅读每一堆中序号最大的一本书。Alice喜欢读书，请你告诉她，她最多可以读多少页的书。

Solution

第n本书一定在一堆中，所以第n本书一定会被阅读。要想结果最大，须在其他书中找出页数最多的书。时间复杂度\({O}(\sum n)\)

#include <bits/stdc++.h>
#define LL long long
#define ls (p<<1)
#define rs (p<<1|1)
#define INF INT_MAX
#define lowbit(x) (x&-x)
#define mod 1000000007
#define ULL unsigned long long
void write(LL x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
LL read(){
	LL x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
	return x*f;
}
using namespace std;
const int N=105;
int n,a[N],ans;
void solve(){
	n=read(),ans=0;
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	for(int i=1;i<n;++i){
		ans=max(ans,a[i]);
	}
	printf("%d\n",ans+a[n]);
}
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	freopen("ans.out","w",stdout);
#endif
	int T;
	T=read();
	while(T--) solve();
	return 0;
}

B

题意

有一个长度为 \(n\) 的数列和两个常数 \(a,b\) 以及一个正整数 \(k(1 \leq k \leq n)\)，数列按以下方式构造：

  • 对于前 \(k\) 项，第 \(i\) 项的值为 \(b-i+1\)；
  • 对于剩下的项，每一项的值都为 \(a\)。

整数 \(k\) 的值由你决定，但你需要保证数列中所有的项均为非负整数。在此条件下，你需要求出这个数列的和的最大值。

Solution

考虑贪心。让前k个数大于等于a，当 \(b-i+1\) 小于a时，每一项为a。时间复杂度\({O}(T)\)

#include <bits/stdc++.h>
#define LL long long
#define ls (p<<1)
#define rs (p<<1|1)
#define INF INT_MAX
#define lowbit(x) (x&-x)
#define mod 1000000007
#define ULL unsigned long long
void write(LL x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
LL read(){
	LL x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
	return x*f;
}
using namespace std;
const int N=0;
LL n,a,b,ans,k;
void solve(){
	n=read(),a=read(),b=read();
	k=min(b-a+1,n);
	k=max(k,0ll);
	// printf("A %lld\n",k);
	ans=a*(n-k)+(b+b-k+1)*k/2;
	printf("%lld\n",ans);
}
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	freopen("ans.out","w",stdout);
#endif
	int T;
	T=read();
	while(T--) solve();
	return 0;
}

C

题意

设排列 \(p\) 的曼哈顿值为 $ |p_1 - 1| + |p_2 - 2| + \ldots + |p_n - n| $ 。

例如，对于排列 $ [1, 2, 3] $ , 它的曼哈顿值为 $ |1 - 1| + |2 - 2| + |3 - 3| = 0 $ ；
对于排列 $ [3, 1, 2] $ , 它的曼哈顿值为 $ |3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4 $ 。

给出 $ n $ 和 $ k $ . 询问是否存在一个长度为 $ n $ 的排列 $ p $ 的曼哈顿值为 $ k $ ，若存在，输出排列 $ p $ 。

对于每组数据，如果不存在合法的排列，输出"No"；否则先输出一行"Yes"，然后在第二行输出 $ n $ 个不同的整数 $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ ) 表示一个合法的排列。

如果存在多个合法的排列，你可以输出任意一个。

Solution

首先，k为奇数时一定无解。

证明：

\[\sum_{i=1}^{n}|p_{i}-i|\equiv\sum_{i=1}^{n}(p_i-i)\pmod{2} \\ \sum_{i=1}^{n}(p_i-i)\equiv\sum_{i=1}^np_i-\sum_{i=1}^{n}i\pmod{2}\\ \sum_{i=1}^np_i-\sum_{i=1}^{n}i\equiv0\pmod{2} \]

其次，k若大于一个值一定无解，该最大值当 \(p\) 是从大到小排列时取到。

证明：

考虑一个从小到大的排列 \(p\) ，对于 \(i,j\) ，若 \(i\) 固定不动 ，\(j\) 增大，则交换 \(p_i,p_j\) 一定会使曼哈顿值越来越大，当 \(j=n\) 时结果最大。

最后，若有解，考虑构造出答案。对于一个从小到大的排列 \(p\) ，若交换 \(p_i,p_j\) 则曼哈顿值增大 \(2\times|p_i-p_j|\) 。所以考虑 \(2\times|p_i-p_j|\) 从大到小配出k。（从小到大无法配出k）用两个指针模拟这一过程。

时间复杂度 \({O}(\sum n)\) 。

#include <bits/stdc++.h>
#define LL long long
#define ls (p<<1)
#define rs (p<<1|1)
#define INF INT_MAX
#define lowbit(x) (x&-x)
#define mod 1000000007
#define ULL unsigned long long
void write(LL x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
LL read(){
	LL x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
	return x*f;
}
using namespace std;
const int N=2e5+5;
LL n,k,a[N],sum;
void solve(){
	n=read(),k=read(),sum=0;
	if(k&1){
		puts("No");
		return;
	}
	for(int i=1;i<=n;++i){
		sum+=abs(n-2*i+1);
		a[i]=i;
	}
	if(sum<k){
		puts("No");
		return;
	}
	puts("Yes");
	int L=1,R=n;
	while(k && L<=R){
		while(2ll*(a[R]-a[L])>k) R--;
		k-=2ll*(a[R]-a[L]);
		swap(a[L],a[R]);
		L++,R--;
	}
	for(int i=1;i<=n;++i){
		printf("%lld ",a[i]);
	}
	puts("");
}
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	freopen("ans.out","w",stdout);
#endif
	int T;
	T=read();
	while(T--) solve();
	return 0;
}

D

题意

有 \(n\) 个候选人（编号为 \(1 \sim n\)）参加选举，第 \(i\) 个人现在有 \(a_i\) 票，除此之外还有 \(c\) 票还没有投。你可以执行以下操作任意多次：

  • 让编号为 \(i\) 的候选人无法参加选举。此时，该人所得的所有票视作“还没有投”。

在你执行完操作之后，还没有投的所有票将被投给能参加选举的编号最小的候选人。此时将所有候选人按票数从多到少排序（票数相同时按编号从小到大排序），排在最前面的人赢得选举。

现在，让 \(i\) 分别取 \(1,2,\dots,n\)，请求出你至少要执行多少次上述操作，才能让第 \(i\) 个人赢得选举。

Solution

若 \(a_i\) 是编号最小的最大值，则i直接获胜。

若 \(a_i\) 不是，则需要将在i之前的所有候选人全部去掉。若取出后还不是，则需要将i之后的数中的最大值去掉。

时间复杂度\({O}(\sum n)\) 。

#include <bits/stdc++.h>
#define LL long long
#define ls (p<<1)
#define rs (p<<1|1)
#define INF INT_MAX
#define lowbit(x) (x&-x)
#define mod 1000000007
#define ULL unsigned long long
void write(LL x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
LL read(){
	LL x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
	return x*f;
}
using namespace std;
const int N=2e5+5;
LL n,c,a[N],s[N],maxx[N];
void solve(){
	memset(s,0,sizeof(s));
	memset(maxx,0,sizeof(maxx));
	n=read(),c=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	a[1]+=c;										//默认多余的票先投给1
	for(int i=1;i<=n;++i){
		s[i]=s[i-1]+a[i];
	}
	for(int i=n;i>=1;--i){
		maxx[i]=max(maxx[i+1],a[i]);
	}
	LL m=0;
	for(int i=1;i<=n;++i){
		if(a[i]==maxx[1] && m<a[i]) printf("0 ");	//若a[i]是最大值且编号最小
		else{
			LL cnt=i-1;
			if(s[i-1]+a[i]<maxx[i+1]) cnt++;	//若a[i]并不是最大值，则一定需要将前i-1个全部去除才可能让i获胜
			printf("%lld ",cnt);				//若去除后还不是最大值，则去除后几个数的最大值后一定获胜
		}
		m=max(m,a[i]);
	}
	puts("");
}
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	freopen("ans.out","w",stdout);
#endif
	int T;
	T=read();
	while(T--) solve();
	return 0;
}

E

题意

给定长度为 \(n\) 的二进制字符串 \(s,t\)，串内只包含 \(0\) 和 \(1\)，现有 \(q\) 次询问，每次给出一个区间 \([l,r]\)，分别记 \(s,t\) 在 \([l,r]\) 上的子串为 \(a,b\)，进行任意次如下两种操作：

  • 若 \(\exist i,i+2\in[l,r]\) 使得 \(a_i=a_{i+2}=0\)，则可以使 \(b_{i+1}\) 的值变为 \(1\)。
  • 若 \(\exist i,i+2\in[l,r]\) 使得 \(b_i=b_{i+2}=1\)，则可以使 \(a_{i+1}\) 的值变为 \(1\)。

现求所有操作结束后，串 \(a\) 内最多可以包含多少 \(1\)。

Solution

对于 \([l+2,r-2]\) 的数，预处理用前缀和维护即可。对于边界需要特判。代码细节较多。时间复杂度 \({O}(\sum n +\sum q)\) 。

#include <bits/stdc++.h>
#define LL long long
#define ls (p<<1)
#define rs (p<<1|1)
#define INF INT_MAX
#define lowbit(x) (x&-x)
#define mod 1000000007
#define ULL unsigned long long
void write(LL x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
LL read(){
	LL x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
	return x*f;
}
using namespace std;
const int N=2e5+5;
int n,a[N],b[N],sum[N],q,tmp[N],tmp1[N];
string s;
void solve(){
	memset(sum,0,sizeof(sum));
	n=read();
	cin>>s;
	for(int i=1;i<=n;++i){
		a[i]=s[i-1]-'0';
	}
	cin>>s;
	for(int i=1;i<=n;++i){
		b[i]=s[i-1]-'0';
		tmp[i]=b[i];
		tmp1[i]=b[i];
	}
	for(int i=2;i<n;++i){
		if(a[i-1]==0 && a[i+1]==0) tmp[i]=1;
	}
	sum[1]=(a[1]==1);
	for(int i=2;i<n;++i){
		if(a[i]==1) sum[i]=sum[i-1]+1;
		else if(tmp[i-1]==1 && tmp[i+1]==1) sum[i]=sum[i-1]+1;
		else sum[i]=sum[i-1];
	}
	q=read();
	int l,r;
	while(q--){
		int ans=0;
		l=read(),r=read();
		if(l==r){
			printf("%d\n",(a[l]==1));
			continue;
		}
		if(r-l+1<=4){
			for(int i=l+1;i<r;++i){
				if(a[i-1]==0 && a[i+1]==0) tmp1[i]=1;
			}
			ans=(a[l]==1)+(a[r]==1);
			for(int i=l+1;i<r;++i){
				if(a[i]==1) ans++;
				else if(tmp1[i-1]==1 && tmp1[i+1]==1) ans++;
			}
			for(int i=l+1;i<r;++i){
				tmp1[i]=b[i];
			}
			printf("%d\n",ans);
		}
		else{
			ans=sum[r-2]-sum[l+1];
			if(a[l]==1) ans++;
			if(a[l+1]==1) ans++;
			if(b[l]==1 && tmp[l+2]==1 && a[l+1]!=1) ans++;
			if(a[r-1]==1) ans++;
			if(a[r]==1) ans++;
			if(b[r]==1 && tmp[r-2]==1 && a[r-1]!=1) ans++;
			printf("%d\n",ans);
		}
	}
}
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	freopen("ans.out","w",stdout);
#endif
	int T;
	T=read();
	while(T--) solve();
	return 0;
}

标签：ch,题解,953,long,sum,Div.2,define,LL,getchar
From： https://www.cnblogs.com/mj666/p/18290676

相关文章

  • 题解：洛谷 P1890 gcd区间
    题解：洛谷P1890gcd区间标签：线段树，st表，分块，dp题意给定数列\(a\)，有\(m\)次询问求区间\([l,r]\)的最大公约数。思路这道题有多种写法，如标签所示。线段树线段树可以维护具有结合性的操作，很明显\(\gcd\)满足。这道题线段树跑的慢是因为无修改操作，自然没有其他\(O(1)......
  • 题解：洛谷 P2678 [NOIP2015 提高组] 跳石头
    题解：洛谷P2678[NOIP2015提高组]跳石头标签：二分，贪心题意给定一个数列，\(a_0=0,a_{N+1}=L\)，从其中删除不超过\(M\)个数，使得\(a_i-a_{i-1}\)的最小值最大。思路从最小值最大不难想到二分答案。统计\(a_i-a_j<mid\)的数量\(k\)，如果不满足的话说明不删，\(j\getsi\)。......
  • VSCode中 npm install 安装依赖包太慢了，一直加载不出来问题解决
    1.问题描述采用VSCode打开别人传过来的项目时，需要先加载依赖包，一般是通过终端来加载：终端中输入npminstall. 但是采用npminstall安装依赖包出现问题，一直加载不完，卡到某一地方，如图： 2.尝试解决2.1采用淘宝镜像，依旧慢，最后证书过期2.2采用pnpminstall（做了一部分）npmins......
  • 题解：洛谷 P1843 奶牛晒衣服
    题解：洛谷P1843奶牛晒衣服标签：二分，贪心题意给定一个数列，每秒可以将所有数减\(a\)，也可以选择一个数减\(b\)，二者可同时进行，求让所有数小于等于\(0\)的最小秒数。思路要求最小的秒数，也就是刚好所有数字小于等于\(0\)，且尽量大。这个秒数具有单调性，考虑二分答案。二分的......
  • CodeForces CF1980C Sofia and the Lost Operations 题解 但是最后TLE 仅供思路参考
    CodeForcesCF1980CSofiaandtheLostOperations题解嗨嗨，又来了啊，蒟蒻再来一篇题解SofiaandtheLostOperations题面翻译索菲亚有一个包含$n$个整数的数组$a[1],a[2],…,a[n]$。有一天她对这个数组感到厌倦，于是决定顺序地对其应用$m$个修改操作。每个修改操作由一......
  • 洛谷p1449后缀表达式题解
    #include<stdio.h>#include<stdlib.h>#defineMAXSIZE100typedeflongElemType;typedefstruct{ ElemType*base; ElemType*top; intStackSize;}sqStack;voidInitStack(sqStack*s){ s->base=(ElemType*)malloc (MAXSIZE*sizeof(ElemTyp......
  • 24暑期第三次训练C组题解
    目录A津津的储蓄计划auto遍历:B校门外的树memset()C杨辉三角DSpecialCharacters位运算&三目运算符EStrangeSplittingFStickogonGCardExchange构造结构体和重载运算符HLeastProductI选数JPeter的烟A津津的储蓄计划模拟题,按题意模拟即可.voidfunc(){ intjin......
  • WPF ComboBox数据绑定：初始化动态加载ItemsSource后首次赋值Text不显示问题解决
    原来：<ComboBoxText="{BindingItem}"ItemsSource="{BindingItemLists}"></ComboBox>privatevoidParas_Init(){ItemLists=newObservableCollection<string>();ItemLists.Add("111......
  • [BZOJ4350] 括号序列再战猪猪侠 题解
    我们设\(dp_{i,j}\)表示第\(i\)到第\(j\)个括号合并为序列且最外层不是括号\(i\)的可能性，\(f_{i,j}\)表示最外层是括号\(i\)的可能性。则有：\[\begin{cases}dp_{i,j}=\sumf_{i,k}(dp_{k+1,j}+f_{k+1,j})\\f_{i,j}=dp_{i+1,j}+f_{i+1,j}\end{cases}\]当然，并不是所......
  • [ABC210E] Ring MST 题解
    链接洛谷相应链接atcoder相应链接题意给n(1≤n≤......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99