比赛地址：https://codeforces.com/contest/2093

Codeforces Round 1016 (Div. 3)

A. Ideal Generator

https://codeforces.com/contest/2093/problem/A

题意

思路

只有奇数长度的 k 能满足条件

  • k=1: [1], [2], …, [n]
  • k=2: [1, 1], x, [2, 2]
  • k=3: [1, 1, 1], [1, 2, 1], [2, 1, 2]
  • ……

AC代码

点击查看代码 
#define _USE_MATH_DEFINES // To use the definition of cmath

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

// mp.reserve(1024), mp.max_load_factor(0.75);
// Used only for basic types, pair and tuple.
template<typename T>
struct custom_hash_base {
    size_t operator()(const T& x) const {
        static const size_t seed = chrono::steady_clock::now().time_since_epoch().count();
        return _Hash_bytes(&x, sizeof(x), seed);
    }
};

static const auto _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("../in.txt", "r", stdin);
#endif
    return nullptr;
}();

inline void solve() {
    int k;
    cin >> k;
    if (k & 1) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

int main() {
    int T;
    for (cin >> T; T > 0; --T) {
        solve();
    }
    return 0;
}

B. Expensive Number

https://codeforces.com/contest/2093/problem/B

题意

思路

只保留从右往左，第一个非零的数位和它前面的 0，其它的数位都移除

AC代码

点击查看代码 
#define _USE_MATH_DEFINES // To use the definition of cmath

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

// mp.reserve(1024), mp.max_load_factor(0.75);
// Used only for basic types, pair and tuple.
template<typename T>
struct custom_hash_base {
    size_t operator()(const T& x) const {
        static const size_t seed = chrono::steady_clock::now().time_since_epoch().count();
        return _Hash_bytes(&x, sizeof(x), seed);
    }
};

static const auto _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("../in.txt", "r", stdin);
#endif
    return nullptr;
}();

int cnt[110];

inline void solve() {
    memset(cnt, 0, sizeof(cnt));
    string num;
    cin >> num;
    const int len = num.size();
    for (int i = 1; i < len; ++i) {
        if (num[i] == '0')
            cnt[i] += cnt[i - 1] + 1;
        else
            cnt[i] = cnt[i - 1];
    }
    int idx = len - 1;
    for (; idx >= 0; --idx) {
        if (num[idx] != '0') break;
    }
    cout << len - 1 - cnt[idx] << '\n';
}

int main() {
    int T;
    for (cin >> T; T > 0; --T) {
        solve();
    }
    return 0;
}

C. Simple Repetition

https://codeforces.com/contest/2093/problem/C

题意

思路

当 k 大于 1，除了 x = 1 时，都是 NO

x = 1，需要特判。这里直接将 y 构造出来，然后 k 变成 1

k 为 1 时，直接判断是否为质数

AC代码

点击查看代码 
#define _USE_MATH_DEFINES // To use the definition of cmath

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

// mp.reserve(1024), mp.max_load_factor(0.75);
// Used only for basic types, pair and tuple.
template<typename T>
struct custom_hash_base {
    size_t operator()(const T& x) const {
        static const size_t seed = chrono::steady_clock::now().time_since_epoch().count();
        return _Hash_bytes(&x, sizeof(x), seed);
    }
};

static const auto _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("../in.txt", "r", stdin);
#endif
    return nullptr;
}();

ll x, k;

bool isPrime(const ll n) {
    if (n == 1)
        return false;
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (ll i = 5; i <= n / i; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

inline void solve() {
    cin >> x >> k;
    if (x == 1) {
        ll a = 0;
        while (k--) {
            a *= 10;
            a += x;
        }
        x = a, k = 1;
    }
    if (k > 1) {
        cout << "NO\n";
        return;
    }
    cout << (isPrime(x) ? "YES\n" : "NO\n");
}

int main() {
    int T;
    for (cin >> T; T > 0; --T) {
        solve();
    }
    return 0;
}

D. Skibidi Table

https://codeforces.com/contest/2093/problem/D

题意

Vadim loves filling square tables with integers. But today he came up with a way to do it for fun! Let’s take, for example, a table of size , with rows numbered from top to bottom and columns numbered from left to right. We place in the top left cell, in the bottom right, in the bottom left, and in the top right. That’s all he needs for fun!

Fortunately for Vadim, he has a table of size . He plans to fill it with integers from to in ascending order. To fill such a large table, Vadim will divide it into equal square tables, filling the top left one first, then the bottom right one, followed by the bottom left one, and finally the top right one. Each smaller table will be divided into even smaller ones as he fills them until he reaches tables of size , which he will fill in the order described above.

Now Vadim is eager to start filling the table, but he has questions of two types:

  • what number will be in the cell at the -th row and -th column;
  • in which cell coordinates will the number be located.

Help answer Vadim’s questions.

思路

递归，不断缩小边界

AC代码

点击查看代码 
#define _USE_MATH_DEFINES // To use the definition of cmath

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

// mp.reserve(1024), mp.max_load_factor(0.75);
// Used only for basic types, pair and tuple.
template<typename T>
struct custom_hash_base {
    size_t operator()(const T& x) const {
        static const size_t seed = chrono::steady_clock::now().time_since_epoch().count();
        return _Hash_bytes(&x, sizeof(x), seed);
    }
};

static const auto _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("../in.txt", "r", stdin);
#endif
    return nullptr;
}();

int n, q;
ll d, x, y;
int mpx[5] = {0, 1, 2, 2, 1};
int mpy[5] = {0, 1, 2, 1, 2};
int blocks[2][2] = {
    {1, 4},
    {3, 2}
};

void find_num(const ll m, ll i = 1, ll j = 1LL << n, const ll mi = 1LL, const ll mx = 1LL << (n << 1)) {
    if (mi == mx) {
        x = i;
        y = j;
        return;
    }
    const ll del = (mx - mi + 1) / 4;
    const ll pos = m % del;
    const ll block = m / del + (pos != 0);
    const ll del2 = sqrt(del);
    i += mpx[block] == 2 ? del2 : 0;
    j -= mpy[block] == 1 ? del2 : 0;
    find_num(pos, i, j, mi + (block - 1) * del, mx - (4 - block) * del);
}

ll get_num(ll i, ll j, const ll mi = 1LL, const ll mx = 1LL << (n << 1)) {
    if (mi == mx)
        return mi;
    const ll del = (mx - mi + 1) / 4;
    const ll del2 = sqrt(del);
    const ll block = blocks[i > del2][j > del2];
    i = i > del2 ? i - del2 : i;
    j = j > del2 ? j - del2 : j;
    return get_num(i, j, mi + (block - 1) * del, mx - (4 - block) * del);
}

inline void solve() {
    //  1  4 13 16
    //  3  2 15 14
    //  9 12  5  8
    // 11 10  7  6
    cin >> n >> q;
    string spt;
    while (q--) {
        cin >> spt;
        if (spt[0] == '-') {
            // q1
            cin >> x >> y;
            cout << get_num(x, y) << '\n';
        } else {
            // q2
            cin >> d;
            find_num(d);
            cout << x << ' ' << y << '\n';
        }
    }
}

int main() {
    int T;
    for (cin >> T; T > 0; --T) {
        solve();
    }
    return 0;
}

赏

愿此行，终抵群星！