「解题报告」AtCoder Beginner Contest 178

人生 AK 第一场，不过我还是这么的菜……

比赛链接

A. Not

考察输入输出。

#include<iostream>
using namespace std;
int main() {int x; cin >> x; x ^= 1; cout << x;}

B. Product Max

对四个值取个 $\max$ 即可。

#include<iostream>
using namespace std;
#define LL long long
LL a, b, c, d, x, y;
int main()
{
    cin >> a >> b >> c >> d;
    x = max(a * c, a * d), y = max(b * c, b * d);
    cout << max(x, y);
}

C. Ubiquity

简单容斥一下即可。

#include<iostream>
using namespace std;
const int P = 1e9 + 7;
int qp(int a,int b) {int r = 1; while(b) {if(b & 1) r = 1ll * r * a % P; a = 1ll * a * a % P; b >>= 1;} return r;}
int n;
int main()
{
    cin >> n;
    int ans = qp(10, n), k = 2ll * qp(9, n) % P;
    ans = (ans - k + P) % P, k = qp(8, n), ans = (ans + k) % P;
    cout << ans;
}

D. Redistribution

枚举数列的长度，然后简单插板即可。

#include<cstdio>
#include<cstring>
#include<iostream>
const int P = 1e9 + 7;
using namespace std;
const int CN = 2e3 + 100;
int C[CN][CN];
void pcal(int n){
    C[0][0] = 1;
    for(int i = 1; i <= n; i++){
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) C[i][j] = ( C[i - 1][j] +0ll+ C[i - 1][j - 1] ) % P;
    }
}
int n, ans = 0; 
int main()
{
    ios :: sync_with_stdio(false);
    cin >> n, pcal(n);
    int ans = 0;
    for(int l = 1; l * 3 <= n; l++) ans = (ans + C[n - l * 2 - 1][l - 1]) % P;
    cout << ans << endl;
}

E. Dist Max

求平面曼哈顿距离的最大值，有一个经典的技巧是把曼哈顿距离的绝对值拆成四个值的 $\max$，即有：
$$|x-x’|+|y-y’|=\max x-x’+y-y’, x-x’+y’-y, x’-x+y-y’, x’-x+y’-y$$ 于是维护一下 $x+y$ 和 $x-y$ 的最大最小值更新答案即可。

#include<iostream>
using namespace std;
#define int long long
const int CN = 2e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, x[CN], y[CN], mx = -INF, mn = INF, ans = -INF;
signed main()
{
    ios :: sync_with_stdio(false);
    freopen("_in.in", "r", stdin);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    for(int i = 1; i <= n; i++) mx = max(mx, x[i] + y[i]), mn = min(mn, x[i] + y[i]);
    ans = max(ans, mx - mn);
    mx = -INF, mn = INF;
    for(int i = 1; i <= n; i++) mx = max(mx, x[i] - y[i]), mn = min(mn, x[i] - y[i]);
    ans = max(ans, mx - mn);
    cout << ans;
}

F. Contrast

大概拿set维护一下就好，但是我的做法好像假了，不过考场上瞎搞过去了……
做法先咕着吧。

先贴一份假代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<set>
using namespace std;
const int CN = 2e5 + 5;
int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}
int n, a[CN], b[CN]; int cnt[CN]; set<int, greater<int> > S;
int main()
{
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= n; i++) b[i] = read(), S.insert(b[i]), cnt[ b[i] ]++;
    memset(b, 0, sizeof(b));

    bool flag = true;
    for(int i = 1; i <= n && flag; i++){
        bool has = false;
        for(set<int> :: iterator it = S.begin(); it != S.end(); it++){
            int val = *it;
            if(val ^ a[i]){
                b[i] = val, has = true, cnt[val]--; 
                if(!cnt[val]) S.erase(it); break;
            }
        }
        flag &= has;
    }

    if(!flag) puts("No");
    else{
        puts("Yes");
        for(int i = 1; i <= n; i++) printf("%d ", b[i]);
    }
}