Contestant. Rank 3437. Unrated.

A. Coins

题意

给定 \(n, k\)，输出是否可以找到一对整数 \(x, y\)，满足 \(2 \cdot x + k \cdot y = n\)。

思路

移项可得，\(x = \frac{n - ky}{2}\)。

那么，只要分母是偶数即可。

也就是说，我们考虑 \(n, k\) 的奇偶性：当 \(n\) 为奇数，\(k\) 为偶数的时候就无法满足。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

void init(){}

void solve() {
    int n, k;
    cin >> n >> k;
    if(n % 2 == 0) cout << "YES\n";
    else{
        if(k % 2 == 0) cout << "NO\n";
        else cout << "YES\n";
    }
}

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

移个项就ok力

B. Long Legs

题意

给定坐标 \((x, y)\)，定义操作如下三选一：

\((x, y) \rightarrow (x + m, y)\)
\((x, y) \rightarrow (x, y + m)\)
\(m = m + 1\)

输出从坐标原点到 \((x, y)\) 需要的最小操作数。

思路

我们先假设最后的 \(m\) 值已知，对于横坐标 \(x\)：

如果 \(x \% m = 0\)，那么走 \(\frac{x}{m}\) 步即可
如果 \(x \% m \neq 0\)，那么我们会多出 \(x - \lfloor \frac{x}{m} \rfloor m\) 步，不难发现多出来的步数小于 \(m\)。那么，我们直接在 \(m\) 递增到 \(x - \lfloor \frac{x}{m} \rfloor m\) 的时候走一步即可。因此，最后需要 \(\lceil \frac{x}{m} \rceil\) 步。

对于 \(m\)，暴力枚举即可。

有趣的是，我们只需枚举到 \(3e5\)，对于枚举到的 \(i\)，我们分别将 \(m\) 赋为 \(i, \frac{\max(a, b)}{i}\) 计算即可。

时间复杂度：\(O(3e5)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

void init(){}

int cal(int a, int b, int& ans, int i) {
    int cur = i - 1;
    if(a % i != 0) cur ++;
    if(b % i != 0) cur ++;
    cur += a / i + b / i;
    ans = min(ans, cur);
    return ans;
}

void solve() {
    int a, b;
    cin >> a >> b;
    if(a > b) swap(a, b);
    int ans = inf;
    for(int i=0;i<=3e5;i++){
        ans = cal(a, b, ans, i + 1);
        if(i != 0) ans = cal(a, b, ans, b / i + 1);
    }
    cout << ans << '\n';
}


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

笑死，卡半天快速算 \(m\) 的方法，结果只要暴力。暴力没写好还 \(fst\) 了（恼

C. Search in Parallel

题意

给定 \(n\) 中颜色，两个机器人可以按照指定序列按照给定的时间间隔 \(s_1, s_2\) 访问颜色。

现在，给定每个颜色需要访问的次数，输出两个机器人的访问序列，使最后需要的总时长最小。

思路

贪心。

我们先按照需要访问的次数排个序，然后依次遍历。

如果这个数放到第一个机器人的序列中，那么循环一次需要 \(s_1(n_a + 1)\) 个单位时间。同理，第二个需要 \(s_2(n_b + 1)\)。

那么，我们一定希望需要的时间更少，所以我们比较上面的值，然后放到较小的那个对应的序列中即可。

如何证明呢？因为之后放入元素后，会导致循环一次的时间变大，所以尽早放入是最佳选择。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

void init(){}

void solve() {
    int n, s1, s2;
    cin >> n >> s1 >> s2;
    vector<pii> r(n);
    for(int i=0;i<n;i++) {
        int cur;
        cin >> cur;
        r[i] = {cur, i + 1};
    }
    sort(r.rbegin(), r.rend());
    vector<int> a, b;
    for(int i=0;i<n;i++){
        if((a.size() + 1) * s1 < (b.size() + 1) * s2) a.emplace_back(r[i].sc);
        else b.emplace_back(r[i].sc);
    }
    cout << a.size() << ' ';
    for(auto e : a) cout << e << ' ';
    cout << '\n';
    cout << b.size() << ' ';
    for(auto e : b) cout << e << ' ';
    cout << '\n';
}


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

无脑乱猜即可（