AtCoder Beginner Contest 135

AtCoder Beginner Contest 135

这应该是我第一次打Atcoder,写个blog留纪念。


A - Harmony

  • 就是求是否有一个数,在数轴上距离a,b相等,直接代码。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;

    ll a, b;

    int main(){
    scanf("%lld%lld", &a, &b);
    if(abs(a - b) % 2 == 1){
    printf("IMPOSSIBLE\n");
    return 0;
    }
    printf("%lld\n", (a + b) / 2);
    return 0;
    }

B - 0 or 1 Swap

  • 把数列读进来,排个序,和原来的对比一下就行了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #include<bits/stdc++.h>
    using namespace std;

    int a[59], b[59], n;

    int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
    scanf("%d", &a[i]);
    b[i] = a[i];
    }
    int ans = 0;
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
    if(a[i] != b[i]){
    ans++;
    }
    }
    if(ans <= 2) printf("YES\n");
    else printf("NO\n");
    return 0;
    }

C - City Savers

  • 额,这道题一开始我错了一次,但是我也不知道哪错了。。。好像是贪心没考虑清楚?我一开始枚举的下面那个数组,后来改成上面的就A了。貌似是因为得优先把上一个剩下的用完?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;

    int n;
    ll a[100009], b[100009];
    ll ans;

    int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n + 1; i++){
    scanf("%lld", &a[i]);
    }
    for(int i = 1; i <= n; i++){
    scanf("%lld", &b[i]);
    }
    for(int i = 1; i <= n + 1; i++){
    if(b[i - 1] > 0 && a[i] > 0){
    int k = min(a[i], b[i - 1]);
    ans += k;
    a[i] -= k;
    b[i - 1] -= k;
    }
    if(b[i] > 0 && a[i] > 0){
    int k = min(a[i], b[i]);
    ans += k;
    a[i] -= k;
    b[i] -= k;
    }
    }
    printf("%lld\n", ans);
    return 0;
    }

D - Digits Parade

  • 这个是个dp,还是竹神提醒了一下状态,感觉以前做过这样的题,应该是一个类型的。
  • $f(i,j)$表示前i个组成的数模13余j的种类数,然后就可以转移,当第i个是一个确定的数时,可以直接枚举上一个位置的余数,然后因为到这位以后相当于上一位乘了10,所以上一位的余数*10再模13再加这一位再模13就是要转移的对象,同理如果这一位是一个问号,只需要枚举这一位是从0到9的情况即可。具体不太清楚的看代码。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll mod = 1e9 + 7;

    string s;
    int n, a[100009];
    ll f[100009][20];

    int main(){
    cin >> s;
    n = s.length();
    for(int i = 1; i <= n; i++){
    a[i] = (s[i - 1] == '?' ? -1 : s[i - 1] - '0');
    }
    if(a[1] == -1) for(int i = 0; i <= 9; i++) f[1][i] = 1;
    else f[1][a[1]] = 1;
    for(int i = 2; i <= n; i++){
    if(a[i] == -1){
    for(int j = 0; j <= 9; j++){
    for(int k = 0; k <= 12; k++){
    (f[i][(((k*10)%13)+j)%13] += f[i - 1][k] % mod) %= mod;
    }
    }
    }
    else{
    for(int j = 0; j <= 12; j++){
    (f[i][(((j*10)%13)+a[i])%13] += f[i - 1][j] % mod) %= mod;
    }
    }
    }
    printf("%lld\n", f[n][5] % mod);
    return 0;
    }

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×