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