Codeforces Round #681 (Div. 2, based on VK Cup 2019-2020 - Final)
傳送門（點擊傳送）
A. Kids Seating
題意：
有 4n 個小孩，標號從 1 到 4n ，任意兩個孩子(設兩個孩子的標號為 a 和 b) ，若 gcd(a,b)=1 則兩個孩子會吵架，若 a 是 b 的倍數或 b 是 a 的倍數則孩子會吵架，現在要選出 n 個孩子且兩兩不吵架，請輸出選擇的孩子的標號，
思路：
4n 個孩子選 n 個，標號足夠多，從4n開始往小選且選標號為偶數的孩子，選 n 個即可，這樣選出來的最小標號的孩子的編號也為
4
n
?
(
n
?
1
)
×
2
=
2
n
+
2
4n-(n-1) \times 2 = 2n+2
4n?(n?1)×2=2n+2，選出的標號均符合題意，
代碼：
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t,n;
cin>>t;
while(t--){
cin>>n;
for(int i=4*n,j=0;j<n;j++){
cout<<i-2*j<<" ";
}
cout<<endl;
}
return 0;
}
B. Saving the City
題意：
t 組資料，每組資料給出一個01串，第 i 位置為 0 則表示該位置沒有炸彈，為 1 則表示該位置有炸彈，若第 i 位置炸彈爆炸則 i-1 ，i+1 位置的炸彈也會爆炸，現在引爆一次需要花費 a ，在任意位置 x 放置炸彈需要花費 b ，現在需要你引爆所有給出的炸彈，最少花費是多少，
思路：
先搜索出炸彈帶，定義炸彈帶為連續緊湊的炸彈，把炸彈帶的起始位置和結束位置記錄下來，如果沒有炸彈，我們答案為0，如果有炸彈，那我們至少需要引爆一次，假設引爆第一組，然后判斷相鄰的炸彈帶是單獨引爆劃算還是將兩個炸彈帶之間的空隙都放置炸彈劃算，取花費小的方案，依次類推，算完所有炸彈帶即可，
代碼：
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t,a,b,ans=0,fr,se;
string s;
cin>>t;
while(t--){
cin>>a>>b;
cin>>s;
vector<pair<int,int> >vec;
for(int i=0;i<s.size();i++){
if(s[i]=='1'){
fr=i;
while(i+1<s.size() && s[i+1]=='1'){
i++;
}
se=i;
vec.push_back(make_pair(fr,se));
}
}
if(vec.size()>0) ans=a;
else ans=0;
for(int i=1;i<vec.size();i++){
if((vec[i].first-vec[i-1].second-1)*b<a){
ans+=(vec[i].first-vec[i-1].second-1)*b;
}else{
ans+=a;
}
}
cout<<ans<<endl;
}
return 0;
}
C. The Delivery Dilemma
題意：
t 組資料，每組資料有 n 個菜，對于每個菜都有兩個值，對于第 i 個菜，
a
i
a_{i}
ai?表示訂餐后
a
i
a_{i}
ai?分鐘能送到，
b
i
b_{i}
bi?表示我自己去購買這個菜則需要花費
b
i
b_{i}
bi?分鐘，現在問最少需要多少分鐘我們能準備好所有菜（最一開始已訂完所有我們需要訂的菜，等待到來即可，剩下的就是去購買我們準備自己買的菜），
思路：
二分搜索，最小為
1
1
1，最大為
1
e
9
1e^{9}
1e9，判斷當前時間是否能夠完成，判斷的時候可以先對資料進行預處理，按照
a
[
i
]
a[i]
a[i]從小到大的順序排序，對于我們當前時間 x ，所有
a
[
i
]
≤
x
a[i]≤x
a[i]≤x 的菜可以直接從餐廳訂購，然后求剩下所有
a
[
i
]
>
x
a[i] > x
a[i]>x的菜對應的
b
[
i
]
b[i]
b[i]之和，如果和小于等于 x，則當前時間能夠準備所有菜，求
b
[
i
]
b[i]
b[i]和可以通過預處理前綴和來完成O(1)查詢，
代碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int a,b;
}num[200005];
ll sum[200005];
int pre[200005];
int t,n;
bool judge(int x){
int loc=upper_bound(pre+1,pre+1+n,x)-pre;
if(sum[n]-sum[loc-1]<=1LL*x){
return true;
}else{
return false;
}
}
int main()
{
scanf("%d",&t);
while(t--){
sum[0]=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&num[i].a);
pre[i]=num[i].a;
}
for(int i=1;i<=n;i++){
scanf("%d",&num[i].b);
}
sort(pre+1,pre+1+n);
sort(num+1,num+1+n,[](const node &x,const node &y){return x.a<y.a;});
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+1LL*num[i].b;
}
int l=1,r=1e9;
while(l<r){
int mid=(l+r)>>1;
if(judge(mid)){
r=mid;
}else{
l=mid+1;
}
}
cout<<l<<endl;
}
return 0;
}
D. Extreme Subtraction
題意：
有一個序列，你可以進行任意次操作，每次操作有如下兩種選擇：①前 k 個元素每個元素減一，②后 k 個元素每個元素減一，k 自選，問能否通過操作使序列全部變為0，
思路：
從第二個位置開始，對于每個位置 i ，比較
n
u
m
[
i
]
num[i]
num[i]和
n
u
m
[
i
?
1
]
num[i-1]
num[i?1]的大小，設
c
h
a
=
a
b
s
(
n
u
m
[
i
]
?
n
u
m
[
i
?
1
]
)
cha=abs(num[i]-num[i-1])
cha=abs(num[i]?num[i?1])，如果
n
u
m
[
i
]
num[i]
num[i]大，說明
n
u
m
[
i
]
num[i]
num[i]需要比
n
u
m
[
i
?
1
]
num[i-1]
num[i?1]從后面多進行
c
h
a
cha
cha次操作②，如果
n
u
m
[
i
?
1
]
num[i-1]
num[i?1]大，說明
n
u
m
[
i
?
1
]
num[i-1]
num[i?1]需要比
n
u
m
[
i
]
num[i]
num[i]從前面多進行
c
h
a
cha
cha次操作①，用線段樹進行維護，最后進行完如上操作每個位置的元素一定相等，那么只需要檢查任意位置上的元素是否大于等于0即可，
代碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=30005;
ll num[MAXN];
struct Tree {
ll l,r;
ll sum;
ll lazy;
} tree[MAXN<<2];
void push_up(ll node) {
tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;
}
void push_down(ll node, ll length) {
if(tree[node].lazy) {
tree[node<<1].lazy+=tree[node].lazy;
tree[node<<1|1].lazy+=tree[node].lazy;
tree[node<<1].sum+=(length-(length>>1))*tree[node].lazy;
tree[node<<1|1].sum+=(length>>1)*tree[node].lazy;
tree[node].lazy = 0;
}
}
void build(ll l,ll r, ll node) {
tree[node].lazy = 0;
tree[node].l=l;
tree[node].r=r;
if(l==r) {
tree[node].sum=num[l];
return;
}
ll mid=(l+r)>>1;
build(l,mid,node<<1);
build(mid+1,r,node<<1|1);
push_up(node);
}
void update(ll left,ll right,ll key, ll node) {
if(tree[node].l>=left && tree[node].r<=right) {
tree[node].sum+=(tree[node].r-tree[node].l+1)*key;
tree[node].lazy+=key;
return;
}
push_down(node,tree[node].r-tree[node].l+1);
ll mid=(tree[node].r+tree[node].l)>>1;
if(left<=mid) update(left,right,key,node<<1);
if(right>mid) update(left,right,key,node<<1|1);
push_up(node);
}
ll query(ll left,ll right,ll node) {
if(tree[node].l>=left && tree[node].r<=right) {
return tree[node].sum;
}
push_down(node,tree[node].r-tree[node].l+1);
ll mid=(tree[node].r+tree[node].l)>>1;
ll ans=0;
if(left<=mid) ans+=query(left,right,node<<1);
if(right>mid) ans+=query(left,right,node<<1|1);
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t,n;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>num[i];
}
build(1,n,1);
for(int i=2;i<=n;i++){
ll cha=query(i,i,1)-query(i-1,i-1,1);
if(cha>0){
update(i,n,-1*cha,1);
}else if(cha<0){
update(1,i-1,cha,1);
}
}
ll check=query(1,1,1);
if(check>=0) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/204028.html
標籤：其他
上一篇：Android知識點2