AtCoder Beginner Contest 165

传送门

A - We Love Golf

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    int k, a, b;
    scanf("%d%d%d", &k, &a, &b);
    bool flag = false;
    for(int i = a; i <= b; i++) {
        if(i % k == 0) flag = true;
    }
    printf("%s
", flag ? "OK" : "NG");
    return 0;
}

B - 1%

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    ll n, now = 100;
    scanf("%lld", &n);
    int ans = 0;
    while(now < n) {
        now += now / 100;
        ans++;
    }
    printf("%d
", ans);
    return 0;
}

C - Many Requirements

题意：给Q个四元组{a_i,b_i,c_i,d_i}，要求生成一个长度为N且值在[1,M]之间的不下降序列A，令$S=sum_{A_{b_{i}}-A_{a_{i}}=c_{i}} d_{i}$，最大化S。

数据范围：$ 2 leq N leq 10, 1 leq M leq 10,1 leq Q leq 50, 1 leq a_{i} < b_{i} leq N, 0 leq c_{i} < M, 1 leq d_{i} leq 10^{5} $

题解：暴力求出每个满足要求的序列，然后依次求出S，每次取大即可。暴力求出每个序列的复杂度是$C(n + m - 1, n)$，隔板法。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 55;
int a[N], b[N], c[N], d[N];
int n, m, q, ans;
void dfs(int x, vector<int>& t) {
    if(t.size() == n) {
        int sum = 0;
        for(int i = 0; i < q; i++) {
            if(t[b[i]] - t[a[i]] == c[i]) sum += d[i];
        }
        ans = max(ans, sum);
        return;
    }
    for(int i = x; i <= m; i++) {
        t.push_back(i);
        dfs(i, t);
        t.pop_back();
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 0; i < q; i++) {
        scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
        a[i]--, b[i]--;
    }
    vector<int> t;
    t.push_back(1);
    dfs(1, t);
    printf("%d
", ans);
    return 0;
}

 D - Floor Function

题意：在[1,N]之间取一个整数x，最大化$ left lfloor frac{Ax}{B} ight floor - Aleft lfloor frac{x}{B} ight floor $。

数据范围：$ 1 leq A leq 10^{6}, 1 leq B,N leq 10^{12} $

题解：可以发现这个值是有一个长度为B的循环节，且在[0,B-1]上是递增的，所以答案就是A*min(B - 1, N) / B。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    ll a, b, n;
    scanf("%lld%lld%lld", &a, &b, &n);
    printf("%lld
", a * min(b - 1, n) / b);
    return 0;
}

E - Rotation Matching

题意：输出M对不同数字（a_i,b_i）[1,N]，每一轮编号为a_i和b_i去第i个地方比赛，比完一轮以后，每个人的编号加1，如果当前这个人编号为N，则变为1，满足N轮以后没有一对人重复比过。

数据范围：$ 1 leq M , M imes 2 + 1 leq N leq 100000 $

题解：题意比较绕，简化了就是输出M对不同的数字（a_i,b_i），定义dis(x,y)为(x-y+(x - y < 0 ? n : 0))，满足任意i，j，dis(a_i,b_i) != dis(a_j,b_j)，dis(a_i,b_i) != dis(b_j,a_j)，dis(b_i,a_i) != dis(a_j,b_j)，dis(b_i,a_i) != dis(b_j,a_j)。

具体构造见代码。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    if(n & 1) {
        for(int i = 0; i < m; i++) {
            printf("%d %d
", i + 1, n - i - 1);
        }
    }else {
        for(int i = 0; i < m; i++) {
            if(i < n / 4) printf("%d %d
", i + 1, n - i);
            else printf("%d %d
", i + 1, n - i - 1);
        }
    }
    return 0;
}

F - LIS on Tree

题意：给一颗N个节点的树，每个节点有个值a_i，求1到其它节点的最短路径中a构造的最长上升子序列。

数据范围：$ 2 leq N leq 2 imes 10^{5} , 1 leq a_{i} leq 10^{9} $

题解：一般的最长上升子序列可以用二分一个升序序列更新可求得，这题以1为根节点dfs，二分更新序列，递归下去，然后回溯即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
vector<int> G[N];
int a[N], ans[N];
void dfs(int u, int fa, vector<int>& t) {
    ans[u] = t.size();
    for(auto v : G[u]) {
        if(v == fa) continue;
        int L = 0, R = t.size() - 1, x = -1;
        while(L <= R) {
            int mid = (L + R) >> 1;
            if(t[mid] >= a[v]) x = mid, R = mid - 1;
            else L = mid + 1;
        }
        int tmp;
        if(x == -1) t.push_back(a[v]);
        else tmp = t[x], t[x] = a[v];
        dfs(v, u, t);
        if(x == -1) t.pop_back();
        else t[x] = tmp;
    }
}
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vector<int> t;
    t.push_back(a[1]);
    dfs(1, -1, t);
    for(int i = 1; i <= n; i++) {
        printf("%d
", ans[i]);
    }
    return 0;
}