Practice.

A. Madoka and Strange Thoughts

题意

给定整数 \(n\)，输出二元组 \((a, b)\) 的个数，满足 \(\frac{\operatorname{lcm}(a, b)}{\operatorname{gcd}(a, b)} \leq 3\)。

思路

我们不妨打个表：

不难发现出现了循环。

更具体地说，令 \(sum = \{0, 1, 4, 7, 10, 11\}\)，那么答案就是 \(16(\frac{n}{6}) + sum[n \% 6]\)。

时间复杂度：\(O(1)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    vector<int> md = {0, 1, 4, 7, 10, 11};
    cout << 16 * (n / 6) + md[n % 6] << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

狠狠地打表

B. Madoka and Underground Competitions

题意

给定一个由 "." 和 "X" 组成的矩阵的大小 \(n \times n\)，矩阵内横向和竖向每 \(k\) 个位置内至少有一个 \(X\)，以及给定的一个坐标 \((r, c)\) 一定为 \(X\)。

输出一个方案，使 \(X\) 的个数最少。

思路

既然要最少，我们直接空 \(k - 1\) 个放一个  \(X\) 即可。

那么我们直接从给定坐标开始一行一行放即可。

时间复杂度：\(O(n ^ 2)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n, k, r, c;
    cin >> n >> k >> r >> c;
    vector<vector<bool>> ans(n + 1, vector<bool>(n + 1));
    for(int x = r, y = c; y >= 1; y --, x ++){
        for(int p = x; p >= 1; p -= k){
            if(p > n) continue;
            ans[p][y] = true;
        }
        for(int p = x; p <= n; p += k){
            if(p < 0) continue;
            ans[p][y] = true;
        }
    }
    for(int x = r, y = c; y <= n; y ++, x --){
        for(int p = x; p >= 1; p -= k){
            if(p > n) continue;
            ans[p][y] = true;
        }
        for(int p = x; p <= n; p += k){
            if(p < 0) continue;
            ans[p][y] = true;
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++) cout << (ans[i][j] ? 'X' : '.');
        cout << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

喜报，RTE!

C. Madoka and Formal Statement

题意

给定两个序列 \(a, b\)，定义一次操作为选定一个数 \(a_i\)，满足 \(a_i \leq a_{(i \% n) + 1}\)，并将 \(a_i\) 加上 \(1\)。

输出是否可以进行若干次操作，将 \(a\) 变为 \(b\)。

思路

观察可得下面两个条件：

1. \(b_i \geq a_i\)；

2. 如果 \(b_i\) 变大了，那么它的后一个数不能比这个数 \(-1\) 小。

满足条件即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> b[i];
    a[n] = a[0], b[n] = b[0];
    for(int i=0;i<n;i++) {
        if(a[i] > b[i] || (b[i] - b[i + 1] > 1 && a[i] != b[i])){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

乱猜即可乱猜即可