atcoder_abc388_abcdeg

比赛链接

abc388

A - ?UPC

题目描述

You are given a string $S$. Here, the first character of $S$ is an uppercase English letter, and the second and subsequent characters are lowercase English letters.
Print the string formed by concatenating the first character of $S$ and UPC in this order.

• $S$ is a string of length between $1$ and $100$, inclusive.
• The first character of $S$ is an uppercase English letter.
• The second and subsequent characters of $S$ are lowercase English letters.

解法

根据题意直接输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define int long long
#define endl '\n'

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin>>s;
	cout<<s[0]<<"UPC"<<endl;
} 

s=input()
print(s[0]+"UPC")

B - Heavy Snake

题目描述

There are $N$ snakes.

Initially, the thickness of the $i$-th snake is $T_i$, and its length is $L_i$.

The weight of a snake is defined as the product of its thickness and length.

For each integer $k$ satisfying $1\le k\le D$, find the weight of the heaviest snake when every snake’s length has increased by $k$.

• $1\le N,D\le 100$
• $1\le T_i,L_i\le 100$
• All input values are integers.

解法

由于$n，d$都非常小，直接暴力即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define int long long
#define endl '\n'
const int N=110;
int l[N],t[N];

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,d;
	cin>>n>>d;
	for(int i=1;i<=n;i++){
   
		cin>>t[i]>>l[i];
	}
	for(int i=1;i<=d;i++){
   
		int maxx=0;
		for(int j=1;j<=n;j++){
   
			maxx=max(maxx,(l[j]+i)*t[j]);
		}
		//cout<<"#:";
		cout<<maxx<<endl;
	}
} 

N=110
l=[0]*N
t=[0]*N
n,d=map(int,input().split())
for i in range(1,n+1):
    t[i],l[i]=map(int,input().split())
for i in range(1,d+1):
    maxx=0
    for j in range(1,n+1):
        maxx=max(maxx,(l[j]+i)*t[j])
    print(maxx)

C - Various Kagamimochi

题目描述

There are $N$ mochi (rice cakes) arranged in ascending order of size. The size of the $i$-th mochi $(1\le i\le N)$ is $A_i$.
Given two mochi $A$ and $B$, with sizes $a$ and $b$ respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi $A$ on top of mochi $B$ if and only if $a$ is at most half of $b$.
You choose two mochi out of the $N$ mochi, and place one on top of the other to form one kagamimochi.
Find how many different kinds of kagamimochi can be made.
Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.

• $2\le N\le 5\times 10^5$
• $1\le A_i\le 10^9(1\le i\le N)$
• $A_i\le A_{i+1}(1\le i<N)$
• All input values are integers.

解法

二分查找，遍历每个麻糬时，每次找到大于等于他的二倍的麻薯的下标$j$，给答案加上$n-j+1$。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define int long long
#define endl '\n'
const int N=5e5+10;
int a[N];

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int ans=0;
	for(int i=1;i<=n;i++){
   
		int w=lower_bound(a+i+1,a+1+n,2*a[i])-a;
		ans+=n-w+1;
	}
	cout<<ans<<endl;
} 

import bisect
n=int(input())
a=[0]+list(map(int,input().split()))
ans=0
for i in range(1,n+1):
    w=bisect.bisect_left(a,i+1,n+1,2*a[i])
    ans+=n-w+1
print(ans)

D - Coming of Age Celebration

题目描述

On a certain planet, there are $N$ aliens, all of whom are minors.
The $i$-th alien currently has $A_i$ stones, and will become an adult exactly $i$ years later.
When someone becomes an adult on this planet, every adult who has at least one stone gives exactly one stone as a congratulatory gift to the alien who has just become an adult.
Find how many stones each alien will have after $N$ years.
Assume that no new aliens will be born in the future.

• $1\le N\le 5\times 10^5$
• $0\le A_i\le 5\times 10^5$
• All input values are integers.

题解

对于每个外星人$i$，最后所剩余的宝石数为$max(0,a_i-(n-i))$,能给后面$a_i$个外星人送出宝石，用支持快速区间加值，单点查询的数据结构即可（树状数组，线段树），由于本题只会给后面的区间进行加值，所以用差分，前缀和也可以处理。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define int long long
#define endl '\n'
const int N=5e5+10;
int a[N];

struct st{
   
	int l,r;
	int v,add;
}t[N<<2];

void build(int p,int l,int r)
{
   
	t[p].l=l,t[p].r=r;
	if(l==r){
   
		t[p].v=a[l];
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	t[p].v=t[p<<1].v+t[p<<1|1].v;
}

void spread(int p)
{
   
	if(t[p].add){
   
		t[p<<1].v+=t[p].add*(t[p<<1].r-t[p<<1].l+1);
		t[p<<1|1].v+=t[p].add*(t[p<<1|1].r-t[p<<1|1].l+1);
		t[p<<1].add+=t[p].add;
		t[p<<1|1].add+=t[p].add;
		t[p].add=0;
	}
}

void change(int p,int x,int y,int z)
{
   
	if(x<=t[p].l && t[p].r<=y){
   
		t[p].v+=z*(t[p].r-t[p].l+1);
		t[p].add+=z;
		return;
	}
	spread(p);
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid) change(p<<1,x,y,z);
	if(y>mid) change(p<<1|1,x,y,z);
	t[p].v=t[p<<1].v+t[p<<1|1].v;
}

int ask(int p,int x,int y)
{
   
	if(x<=t[p].l && t[p].r<=y){
   
		return t[p].v;
	}
	spread(p);
	int mid=t[p].l+t[p].r>>1;
	int ans=0;
	if(x<=mid) ans+=ask(p<<1,x,y);
	if(y>mid) ans+=ask(p<<1|1,x,y);
	return ans;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=n;i++){
   
		int x=ask(1,i,i);
		//cout<<" x=:"<<x<<" ";
		cout<<max(0LL,x-(n-i))<<" ";
		change(1,i+1,min(n,i+x),1);
	}
} 

import sys
sys.setrecursionlimit(10**6)
N=5*10**5+10
a=[0]*N
t=[{
   'l':0,'r':0,'v':0,'add':0}for _ in range(4*N)]
def build(p,l,r):
    t[p]['l'],t[p]['r']=l,r
    if l==r:
        t[p]['v']=a[l]
        return
    mid=(l+r)>>1
    build(p<<1,l,mid)
    build(p<<1|1,mid+1,r)
    t[p]['v']=t[p<<1]['v']+t[p<<1|1]['v']
def spread(p):
    if t[p]['add']:
        t[p<<1]['v']+=t[p]['add']*(t[p<<1]['r']-t[p<<1]['l']+1)
        t[p<<1|1]['v']+=t[p]['add']*(t[p<<1|1]['r']-t[p<<1|1]['l']+1)
        t[p<<1]['add']+=t[p]['add']
        t[p<<1|1]['add']+=t[p]['add']
        t[p]['add']=0
def change(p,x,y,z):
    if x<=t[p]['l']and t[p]['r']<=y:
        t[p]['v']+=z*(t[p]['r']-t[p]['l']+1)
        t[p]['add']+=z
        return
    spread(p)
    mid=(t[p]['l']+t[p]['r'])>>1
    if x<=mid:
        change(p<<1,x,y,z)
    if y>mid:
        change(p<<1|1,x,y,z)
    t[p]['v']=t[p<<1]['v']+t[p<<1|1]['v']
def ask(p,x,y):
    if x<=t[p]['l']and t[p]['r']<=y:
        return t[p]['v']
    spread(p)
    mid=(t[p]['l']+t[p]['r'])>>1
    ans=0
    if x<=mid:
        ans+=ask(p<<1,x,y)
    if y>mid:
        ans+=ask(p<<1|1,x,y)
    return ans
n=int(input())
a=[0]+list(map(int,input().split()))
build(1,1,n)
for i in range(1,n+1):
    x=ask(1,i,i)
    print(max(0,x-(n-i)),end=" ")
    change(1,i+1,min(n,i+x),1)

E - Simultaneous Kagamimochi

题目描述

There are $N$ mochi (rice cakes), arranged in ascending order of size. The size of the $i$-th mochi $(1\le i\le N)$ is $A_i$.
Given two mochi $A$ and $B$, with sizes $a$ and $b$ respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi $A$ on top of mochi $B$ if and only if $a$ is at most half of $b$.
Find how many kagamimochi can be made simultaneously.
More precisely, find the maximum non-negative integer $K$ for which the following is possible:

• From the $N$ mochi, choose $2K$ of them to form $K$ pairs. For each pair, place one mochi on top of the other, to make $K$ kagamimochi.
• $2\le N\le 5\times 10^5$
• $1\le A_i\le 10^9(1\le i\le N)$
• $A_i\le A_{i+1}(1\le i<N)$
• All input values are integers.

题解

可以贪心的想，如果有$k$对满足，那么一定可以用前$k$个麻薯和后$k$个麻薯进行匹配。用二分答案找出满足题意的最大的$k$即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define int long long
#define endl '\n'
const int N=5e5+10;
int a[N];
int n;

int check(int x)
{
   
	for(int i=1;i<=x;i++){
   
		if(a[i]*2>a[n-x+i]) return 0;
	}
	return 1;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n); 
	int l=0,r=n/2;
	while(l<r){
   
		int mid=l+r+1>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<endl;
} 

n=int(input())
a=[0]+list(map(int,input().split()))
a.sort()
def check(x):
    for i in range(1,x+1):
        if a[i]*2>a[n-x+i]:
            return 0
    return 1
l=0
r=n//2
while l<r:
    mid=(l+r+1)//2
    if check(mid):l=mid
    else:r=mid-1
print(l)

本题还有另外一种解法
因为 $2a_i\le a_{n-k+i}$，设 $p_i$ 为满足大于等于 $a_{p_i}\le 2a_i$的最小下标。
则可以得到 $p_i\le n-k-i$ ,也就是 $p_i-i\le n-k$。
可以用这一性质来进行二分。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define int long long
#define endl '\n'
const int N=5e5+10;
int a[N],p[N],pre[N];
int n;

bool check(int x)
{
   
	return pre[x]<=n-x;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	pre[0]=-2e9;
	for(int i=1;i<=n;i++){
   
		p[i]=lower_bound(a+1+i,a+1+n,2*a[i])-a;
		if(p[i]==n+1) p[i]=2e9;
		p[i]-=i;
		pre[i]=max(pre[i-1],p[i]);
	}
	int l=0,r=n/2;
	while(l<r){
   
		int mid=l+r+1>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<endl;
} 

n=int(input())
a=[0]+list(map(int,input().split()))
p=[0]*(n+1)
pre=[-2*(10**9)]*(n+1)
def check(x):
    return pre[x]<=n-x
for i in range(1,n+1):
    p[i]=next((j for j in range(i+1,n+1) if a[j]>=2*a[i]),n+1)
    if p[i]==n+1:p[i]=2*(10**9)
    p[i]-=i
    pre[i]=max(pre[i-1],p[i])
l,r=0,n//2
while l<r:
    mid=(l+r+1)//2
    if check(mid):l=mid
    else:r=mid-1
print(l)

G - Simultaneous Kagamimochi 2

题目描述

There are $N$ mochi (rice cakes), arranged in ascending order of size. The size of the $i$-th mochi $(1\le i\le N)$ is $A_i$.

Given two mochi $A$ and $B$, with sizes $a$ and $b$ respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi $A$ on top of mochi $B$ if and only if $a$ is at most half of $b$.

You are given $Q$ integer pairs. Let $(L_i,R_i)$ be the $i$-th pair $(1\le i\le Q)$, and solve the following problem for each $i$:

Using only the $R_i-L_i+1$ mochi from the $L_i$-th to the $R_i$-th, how many kagamimochi can you make simultaneously?

More precisely, find the maximum non-negative integer $K$ such that:

• Out of the $R_i-L_i+1$ mochi from the $L_i$-th to the $R_i$-th, choose $2K$ mochi and form $K$ pairs. For each pair, place one mochi on top of the other, to make $K$ kagamimochi.

• $2\le N\le 2\times 10^5$
• $1\le A_i\le 10^9(1\le i\le N)$
• $A_i\le A_{i+1}(1\le i<N)$
• $1\le Q\le 2\times 10^5$
• $1\le L_i<R_i\le N(1\le i\le Q)$
• All input values are integers.

题解

和 $e$ 题的第二种思路类似，可以得到 $p_i-i\le r-l+1-k$,区间最值可以用st表进行处理和查询。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define int long long
#define endl '\n'
const int N=5e5+10;
int a[N],p[N],st[N][20];
int n;

int query(int l,int r){
   
	int k=log2(r-l+1);
	return max(st[l][k],st[r-(1<<k)+1][k]);
}

bool check(int l,int r,int x)
{
   
	return query(l,l+x-1)<=r-l+1-x;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
   
		p[i]=lower_bound(a+1+i,a+1+n,2*a[i])-a;
		if(p[i]==n+1) p[i]=2e9;
		p[i]-=i;
		st[i][0]=p[i];
	}
	for(int j=1;j<=20;j++){
   
		for(int i=1;i+(1<<j-1)<=n;i++){
   
			st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
		}
	}
	int q;
	cin>>q;
	while(q--){
   
		int l,r;
		cin>>l>>r;
		int l0=0,r0=(r-l+1)/2;
		while(l0<r0){
   
			int mid=l0+r0+1>>1;
			if(check(l,r,mid)) l0=mid;
			else r0=mid-1;
		}
		cout<<l0<<endl;
	}
} 

import math
n=int(input())
a=[0]+list(map(int,input().split()))
p=[0]*(n+1)
st=[[0]*20 for _ in range(n+1)]

def query(l,r):
    k=math.floor(math.log2(r-l+1))
    return max(st[l][k],st[r-(1<<k)+1][k])

def check(l,r,x):
    return query(l,l+x-1)<=r-l+1-x

for i in range(1,n+1):
    p[i]=next((j for j in range(i+1,n+1) if a[j]>=2*a[i]),n+1)
    if p[i]==n+1:p[i]=2*(10**9)
    p[i]-=i
    st[i][0]=p[i]

for j in range(1,20):
    for i in range(1,n-(1<<j)+2):
        st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1])

q=int(input())
for _ in range(q):
    l,r=map(int,input().split())
    l0,r0=0,(r-l+1)//2
    while l0<r0:
        mid=(l0+r0+1)//2
        if check(l,r,mid):l0=mid
        else:r0=mid-1
    print(l0)