AtCoder Beginner Contest 166

传送门

A - A?C

AtCoder Beginner Contest 166
#include <bits/stdc++.h>
#define ll long long
using namespace std;
char s[5];
int main() {
    scanf("%s",s);
    if(s[1] == 'B') s[1] = 'R';
    else s[1] = 'B';
    printf("%s\n", s);
    return 0;
}
A.cpp

B - Trick or Treat

AtCoder Beginner Contest 166
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105;
bool vis[N];
int main() {
    int n ,k;
    scanf("%d%d", &n, &k);
    for(int i = 0, x, y; i < k; i++) {
        scanf("%d", &x);
        for(int j = 0; j < x; j++) {
            scanf("%d", &y);
            vis[y] = true;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) ans++;
    }
    printf("%d\n", ans);
    return 0;
}
B.cpp

C - Peaks

题意:有N个人,M条边,每个人有一个高度H,输出有多少个节点满足它比所有它相邻的人高。

数据范围:$ 2 \leq N \leq 10^{5}, 1 \leq M \leq 10^{5}, 1 \leq H_{i} \leq 10^{9} $

题解:开一个数组表示是否有它相邻的人比它高,每输入一条边更新即可。

AtCoder Beginner Contest 166
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
bool vis[N];
int h[N];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &h[i]);
    }
    for(int i = 0, u, v; i < m; i++) {
        scanf("%d%d", &u, &v);
        if(h[u] <= h[v]) vis[u] = true;
        if(h[v] <= h[u]) vis[v] = true;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) ans++;
    }
    printf("%d\n", ans);
    return 0;
}
C.cpp

D - I hate Factorization

题意:给定X,输出一组(A,B),满足A5-B5=X。

数据范围:$ 1 \leq X \leq 10^{9} $

题解:枚举A,判断A5-X是否能正好开5次方即可。

AtCoder Beginner Contest 166
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll cal(ll x) {
    return x * x * x * x * x;
}
int main() {
    ll x;
    scanf("%lld", &x);
    for(ll a = 1;; a++) {
        ll det = cal(a) - x, bb = -1;
        for(ll b = 0;; b++) {
            ll t = cal(b);
            if(t == abs(det)) {
                bb = b;
                break;
            }
            if(t > abs(det)) {
                break;
            }
        }
        if(bb != -1) {
            printf("%lld %lld\n", a, bb * (det < 0 ? -1 : 1));
            break;
        }
    }
    return 0;
}
D.cpp

E - This Message Will Self-Destruct in 5s

题意:给一个长度为N的序列A,求有多少数字对(i,j)满足Ai+Aj=|i - j|。

数据范围:$ 2 \leq N \leq 2 \times 10^{5} , 1 \leq A_{i} \leq 10^{9}$

题解:对于每个位置,每次找在它之前满足要求的数,即求有多少数字对(i,j)满足Ai+Aj=i - j(i > j)。

原式等价于:A+ j = i - Ai,那么只需要每次查询 i - Ai的个数,然后更新Ai + i即可。

AtCoder Beginner Contest 166
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int a[N];
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    ll ans = 0;
    unordered_map<int, int> ma;
    for(int i = 1; i <= n; i++) {
        if(ma.count(i - a[i])) {
            ans += ma[i - a[i]];
        }
        ma[i + a[i]]++;
    }
    printf("%lld\n", ans);
    return 0;
}
E.cpp

F - Three Variables Game

题意:给N个字符串("AB","AC","BC")和A,B,C三个值,按顺序执行每个字符串的操作,如果这个字符串是"AB",那么将执行A--,B++或A++,B--,其它字符串类似,并且每一个操作之后A,B,C三个值不能小于0,判断是否按顺序执行下来,如是,并要求具体操作序列。

数据范围:$ 1 \leq N \leq 10^{5}, 0 \leq A,B,C \leq 10^{9} $

题解:对于操作"AB":

1.A>B,那么就执行A--,B++。

2.A<B,那么就执行A++,B--。

3.A=B,看下一个字符串是否包含A,如果包含A,那就执行A++,B--,反之执行A--,B++。

其它操作类似(虽然没有证明这个做法的正确性,但是感觉很对。

AtCoder Beginner Contest 166
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
char s[N][3];
int a[3], n;
int main() {
    scanf("%d%d%d%d", &n, &a[0], &a[1], &a[2]);
    for(int i = 0; i < n; i++) {
        scanf("%s", s[i]);
    }
    vector<char> ans;
    bool flag = true;
    for(int i = 0; i < n; i++) {
        int ta = s[i][0] - 'A', tb = s[i][1] - 'A';
        if(a[ta] > a[tb]) {
            ans.push_back(s[i][1]);
            a[tb]++, a[ta]--;
        }else if(a[tb] > a[ta]){
            ans.push_back(s[i][0]);
            a[ta]++, a[tb]--;
        }else {
            if(a[ta] == 0) {
                flag = false;
                break;
            }
            if(i + 1 >= n || s[i][0] == s[i + 1][0] || s[i][0] == s[i + 1][1]) {
                ans.push_back(s[i][0]);
                a[ta]++, a[tb]--;
            }else {
                ans.push_back(s[i][1]);
                a[tb]++, a[ta]--;
            }
        }
    }
    if(flag) {
        printf("Yes\n");
        for(int i = 0; i < n; i++) {
            printf("%c\n", ans[i]);
        }
    }else {
        printf("No\n");
    }
    return 0;
}
F.cpp

 

上一篇:分享166个最常用的 “Linux命令” 总有一个是你需要用到的!赶快点亮到你的收藏夹


下一篇:分享166个最常用的 “Linux命令” 总有一个是你需要用到的!赶快点亮到你的收藏夹