AtCoder Beginner Contest 135

YorkWu

July 27, 2019

1068 views

No comments

657 words

OI 比赛

[AtCoder Beginner Contest 135](https://atcoder.jp/contests/abc135)

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

---

## A - Harmony

- 就是求是否有一个数，在数轴上距离a，b相等，直接代码。
```cpp
#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

- 把数列读进来，排个序，和原来的对比一下就行了。
```cpp
#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了。貌似是因为得优先把上一个剩下的用完？
```cpp
#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的情况即可。具体不太清楚的看代码。
```cpp
#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;
}
```

Last modification：March 8, 2020