第 18 场 小白入门赛

6 武功秘籍

考察进制理解。

对于第 i i i 位,设 b i t i = x bit_i=x biti=x ,每一位的最大值是 b j b_j bj ,也就是说每一位是 b j + 1 b_j+1 bj+1 进制 ,那么第 i i i 位的大小就是 x × ∑ j = i + 1 l a s ( b j + 1 ) x\times \sum_{j=i+1}^{las} (b_j+1) x×j=i+1las(bj+1)

据此推导。

#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
    int n, k;
    cin >> n >> k;
    if(k == 1){
        cout << "0\n";
        return ;
    }
    -- k;
    vector<int> bit;
    while(n){
        bit.push_back(n % 10);
        n /= 10;
    }
    vector<int> t(bit.size() + 1);
    // for(auto &x : bit) cout << x << ' '; cout << '\n';
    int l, r = 0, lasBit = 0;
    t[0] = 1;
    for(int i = 0; i < bit.size(); i ++){
        l = r + 1;
        r += t[i] * bit[i];
        if(r >= k){
            lasBit = i;
            break;
        }
        // cout << i << ' ' << l << ' ' << r << '\n';
        t[i + 1] = t[i] * (bit[i] + 1);
    }
    // cout << lasBit << '\n';
    for(int i = lasBit; i >= 0; i --){
        cout << (k / t[i]);
        k %= t[i];
    }
}

signed main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T --){
        solve();
    }

    return 0;
}

2 + 4 情报传递

思维题,技巧在于具有大量相同的区间,实际上只有左右两个特殊区间,以及中间大量相同的区间。

首先,如果不存在点不能走,那么从 x x x 走到 y y y ,贪心走 ⌈ y − x 2 ⌉ \lceil \frac {y-x}{2} \rceil 2yx 即可。

假设在 a → b a\rightarrow b ab 区间内,存在 x x x c c c 的倍数,设 d d d 是这些点的最小值, e e e 是最大值。

那么从 a → d − 1 a\rightarrow d-1 ad1 e + 1 → b e+1\rightarrow b e+1b 贪心走即可。

剩下的全是相同的走法。

O ( 1 ) O(1) O(1)

dp 思路很简答,爬楼梯问题, O ( n ) O(n) O(n)

Trick :

第一个 ≥ x \geq x x c c c 的倍数 : ⌈ x c ⌉ × c \lceil \frac x c \rceil \times c cx×c

第一个 ≤ x \leq x x c c c 的倍数 : ⌊ x c ⌋ × c \lfloor \frac x c \rfloor \times c cx×c

#include<bits/stdc++.h>
using namespace std;
#define int long long

int dis(int a, int b){
    return (b - a) / 2 + (b - a) % 2;
}

void solve(){
    int a, b, c, x = 0;
    cin >> a >> b >> c;
    int d = (a + c - 1) / c * c; // 第一个 >= a 的 c 的倍数
    int e = b / c * c; // 第一个 <= b 的 c 的倍数
    if(d > b){ 
        cout << dis(a, b) << '\n';
    }
    else{
        cout << dis(a, d - 1) + dis(e + 1, b) + 1 + dis(1, c + 1) * ((e - d) / c) << '\n';
    } 
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T --){
        solve();
    }

    return 0;
}

3 村长分钱

已知 a , b a,b a,b , 求满足 a   m o d   y = b a \bmod y=b amody=b ,多少 y y y 满足要求

a = b + x y a=b+xy a=b+xy

x y = b − a xy=b-a xy=ba ,计算一下 b − a b-a ba 有多少因子即可。

注意只统计 > b >b >b 的因子。

#include <iostream>
#include <cmath>
using namespace std;

int count_solutions(int a, int b) {
    if (a < b) return 0; // 无解的情况
    int d = a - b;
    int count = 0;

    // 枚举 d 的因数
    for (int x = 1; x * x <= d; ++x) {
        if (d % x == 0) {
            if (x > b) count++;         // x 是 d 的因数,且 x > b
            if (d / x != x && d / x > b) count++; // d/x 也是因数,且 d/x > b
        }
    }

    return count;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << count_solutions(a, b) << endl;
    return 0;
}

5 好汉身份

假设先手的回合,发现选择 a + b a+b a+b 小的更优。

发现后手同样如此。

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct node{
    int a, b;
    bool operator < (const node & T) const {
        return a + b < T.a + T.b;
    }
}v[2100];

int n;

void solve(){
    cin >> n;
    n <<= 1;
    for(int i = 1; i <= n; i ++){
        cin >> v[i].a;
    }
    for(int i = 1; i <= n; i ++){
        cin >> v[i].b;
    }
    sort(v + 1, v + n + 1);
    int res = 0; 
    for(int i = 1; i <= n; i ++){
        if(i & 1) res += v[i].a;
        else res -= v[i].b;
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T --){
        solve();
    }

    return 0;
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部