AtCoder Beginner Contest 129

https://atcoder.jp/contests/abc129
4/6: ABCD

A - Airplane

水题：

#include <bits/stdc++.h>

using namespace std;

int main () {
    int a, b, c;
    cin >> a >> b >> c;
    cout << a + b + c - max ({a, b, c});
}

B - Balance

前缀和水题

#include <bits/stdc++.h>

using namespace std;
const int N = 105;
int a[N], pre[N], suf[N], n, ans = 1e9;

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i], pre[i] = pre[i-1] + a[i];
    for (int i = n; i >= 1; i--)    suf[i] = suf[i+1] + a[i];
    for (int i = 1; i <= n; i++) {
        ans = min (ans, abs (pre[i] - suf[i+1]));
    }
    cout << ans;
}

C - Typical Stairs

dp水题

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5, mod = 1000000007;
int x, n, m, f[N];

int main () {
    cin >> n >> m;
    map<int, int> mp;
    for (int i = 1; i <= m; i++)    cin >> x, mp[x] ++;
    if (n == 1) {
        if (mp[1])  cout << 0;
        else    cout << 1;
        return 0;
    }
    f[0] = 1;
    if (!mp[1])     f[1] = 1;

    for (int i = 2; i <= n; i++) {
        if (mp[i])  continue;
        if (!mp[i-1])   f[i] = (f[i] + f[i-1]) % mod;
        if (!mp[i-2])   f[i] = (f[i] + f[i-2]) % mod;;
    }
    cout << f[n];
}

D - Lamp

二分
因为把n写成m而WA了两发，太sb了

#include <bits/stdc++.h>

using namespace std;
const int N = 2005;
int n, m, hang[N][N], lie[N][N], ans;
char a[N][N];
vector <int> v1[N], v2[N];

void print () {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << hang[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << lie[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
}

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] == '#')     v1[i].push_back (j), v2[j].push_back (i);
        }
        v1[i].push_back (m + 1);
    }
    for (int j = 1; j <= m; j++)    v2[j].push_back (n + 1);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '#') continue;
            int pos = *upper_bound (v1[i].begin (), v1[i].end (), j);
            //cout << pos - j << ' ';
            for (int k = j; k < pos; k++)   hang[i][k] = pos - j;
            j = pos;
        }
        //cout << endl;
    }

    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (a[i][j] == '#') continue;
            int pos = *upper_bound (v2[j].begin (), v2[j].end (), i);
            //cout << pos - i << ' ';
            for (int k = i; k < pos; k++)   lie[k][j] = pos - i;
            i = pos;
        }
        //cout << endl;
    }

    //print ();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '#') continue;
            ans = max (ans, hang[i][j] + lie[i][j] - 1);
        }
    }
    cout << ans;
}

E - Sum Equals Xor

锻炼dp思想的好题。
前提：异或是不进位加法
转移过程详见代码注释。

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int mod = 1e9 + 7;
ll f1 = 1, f0; //f1表示相等,f0表示小于

int main () {
    string s;
    cin >> s;
    for (int i = 0; i < s.size (); i++) {
        if (s[i] == '0') { 
            f0 = (f0 * 3) % mod; //放(0,1)或(1,0)或(0,0),只要不进位就行
            f1 = f1; // 只能放(0,0)
        }
        else { //s[i] == '1'
            f0 = (f0 * 3 + f1) % mod; //不进位的三种 + 因为当前为小于所以剩下的放什么都行
            f1 = (f1 * 2) % mod; //放(0,1)或(1,0)
            
        }
    }
    cout << (f0 + f1) % mod;
}

//异或就是不进位加法

F - Takahashi's Basics in Education and Learning

明天补