Codeforces Round #701 (Div. 2) 题解 (A-C)

最近练车+过年,补题时间不太多。

A. Add and Divide

题意

给出两个整数a和b,在一次操作中,你可以选择让a=a/b或b++,问使得a=0的最小操作次数。

题解

直接枚举即可,最坏情况下时间复杂度O(nlog(n)),不过因为每次只能+1,所以大部分情况下还是很快的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
ll max(ll a, ll b) {
    if (a > b) return a;
    return b;
}
ll min(ll a, ll b) {
    if (a < b) return a;
    return b;
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll a,b;
        cin>>a>>b;
        ll a2=a,b2=b;
        int re=imax,num=0,i=0;
        for(int j=b;j<max(a,b)+3;j++){
            if(j==1) {
                i++;
                continue;
            }
            num=i;
            a2=a,b2=b+i;
            while(a2/b2!=0){
                a2=a2/b2;
                num++;
            }
            if(re<num) {
                break;
            }
            //cout<<num<<" "<<j<<endl;
            re=num;
            i++;
        }
        cout<<re+1<<endl;

    } 
    return 0; 
}

B. Replace and Keep Sorted

题意

给出一个递增数组和一个区间,输出对应区间“相似数组”的个数。
相似数组也需要递增,长度相同,每个元素均为1-k,只有一个地方不同。

题解

因为相似数组只能有一个元素不同,所以除了num[l]和num[r]可以取的个数分别是num[l+1]-2和k-num[r-1]-1,剩下的都是num[i+1]-num[i-1]-2,然后将可以取的个数累加起来。普通的累加一定不行,需要用到线段树等快速求区间和的东西。
这题用线段树可能小题大作,也能用前缀和的方式得出结果。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
ll n, a[100005], d[270000], b[270000];
void build(ll s, ll t, ll p) {
    if (s == t) {
        d[p] = a[s];
        return;
    }
    ll m = (s + t) / 2;
    build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
    d[p] = d[p * 2] + d[(p * 2) + 1];
}
ll getsum(ll l, ll r, ll s, ll t, ll p) {
    // [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
    if (l <= s && t <= r)
        return d[p];
    ll m = (s + t) / 2, sum = 0;
    //throw 100;
    if (b[p]) {

        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m),
            b[p * 2] += b[p], b[p * 2 + 1] += b[p];
        b[p] = 0;
    }
    if (l <= m) sum = getsum(l, r, s, m, p * 2);
   // cout << sum << " " << s << " " << t << endl;
    if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
    //cout << sum <<" "<<s<<" "<< t<< endl;
    return sum;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,q,k,l,r;
    cin>>n>>q>>k;
    int num[n+2];
    for(int i=1;i<=n;i++){
        cin>>num[i];
        if(i==1) continue;
        else if(i==2){
            a[i-1]=num[i]-2;
        }
        else if(i==n){
            a[i-1]=num[i]-num[i-2]-2;
            a[i]=k-num[i-1]-1;
        }
        else a[i-1]=num[i]-num[i-2]-2;

    }
    build(1, n, 1);
    //for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    //cout<<endl;
    for(int i=0;i<q;i++){
        cin>>l>>r;
        if(l==r){
            cout<<k-1<<endl;
            continue;
        }
        ll sum=0;
        sum+=num[l+1]-2;
        sum+=k-num[r-1]-1;
        //cout<<" "<<sum<<endl;
        if(r-l>1) sum+=getsum(l+1,r-1,1,n,1);
        cout<<sum<<endl;

    }


    return 0;

}

C. Floor and Mod

题意

题解

题目来源于https://codeforces.com/contest/1485

知识共享许可协议
Text is available under CC BY-NC-SA 4.0 unless otherwise stated.

除非特殊声明,本站所有内容均以 CC BY-NC-SA 4.0协议授权。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇