Codeforces Round #577 (Div. 2)

A. Important Exam

思路：水题
AC代码

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 1010;

struct Student{
    string s;
}stu[N];

int n, m, a, ans;

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        cin >> stu[i].s;
    for (int i = 0; i < m; i ++ ){
        cin >> a;
        int cnt[6] = {0};
        for (int j = 1; j <= n; j ++ ){
            if (stu[j].s[i] == 'A')
                cnt[1] ++ ;
            else if (stu[j].s[i] == 'B')
                cnt[2] ++ ;
            else if (stu[j].s[i] == 'C')
                cnt[3] ++ ;
            else if (stu[j].s[i] == 'D')
                cnt[4] ++ ;
            else if (stu[j].s[i] == 'E')
                cnt[5] ++ ;
        }
        ans += a * max(cnt[1], max(cnt[2], max(cnt[3], max(cnt[4], cnt[5]))));
    }
    cout << ans << "
";
    return 0;
}

B. Zero Array

思路：和为奇数或者和小于最大的数的两倍时都无法满足
AC代码

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 1e5 + 10;

int n;
int a[N];
ll sum;

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
        sum += 1ll * a[i];
    }
    sort(a + 1, a + n + 1);
    if (sum & 1 || sum < 2 * a[n])
        cout << "NO
";
    else
        cout << "YES
";
    return 0;
}

C. Maximum Median

思路：二分以前做过
AC代码

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 2e5 + 10;

int n, k;
ll ans;
ll a[N];

bool judge(ll x){
    ll res = 0;
    for (int i = (n + 1) >> 1; i <= n; i ++ )
        if (a[i] < x)
            res += x - a[i];
    if (res <= k)
        return true;
    return false;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ )
        cin >> a[i];
    sort(a + 1, a + n + 1);
    ll l = a[(n + 1) >> 1], r = 2e9;
    while (l <= r){
        ll mid = (l + r) >> 1;
        if (judge(mid)){
            ans = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    cout << ans << "
";
    return 0;
}

D. Treasure Hunting

思路：二分+dp 状态转移方程还是很好写的主要是求第j层边界到第i层边界水平移动步数
AC代码

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

int n, m, k, q;
ll ans;
ll b[N];
ll a[N][2], dp[N][2];

ll calc(int pos, int u, int i, int v){
    ll res = INF, p = lower_bound(b + 1, b + q + 1, a[pos][u]) - b;
    if (p <= q)
        res = abs(a[pos][u] - b[p]) + abs(a[i][v] - a[i][v ^ 1]) + abs(b[p] - a[i][v ^ 1]);
    p = upper_bound(b + 1, b + q + 1, a[pos][u]) - b - 1;
    if (p)
        res = min(res, abs(a[pos][u] - b[p]) + abs(a[i][v] - a[i][v ^ 1]) + abs(b[p] - a[i][v ^ 1]));
    return res;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 1; i < N; i ++ )
        a[i][0] = INF, a[i][1] = -INF;
    memset(dp, 0x3f, sizeof(dp));
    cin >> n >> m >> k >> q;
    for (int i = 1; i <= k; i ++ ){
        int r, c;
        cin >> r >> c;
        a[r][0] = min(a[r][0], 1ll * c);
        a[r][1] = max(a[r][1], 1ll * c);
    };
    a[1][0] = 1, a[1][1] = max(a[1][1], 1ll);
    dp[1][0] = abs(a[1][1] - 1) + abs(a[1][1] - a[1][0]), dp[1][1] = abs(a[1][1] - 1);
    for (int i = 1; i <= q; i ++ )
        cin >> b[i];
    sort(b + 1, b + q + 1);
    int pos = 1;
    for (int i = 2; i <= n; i ++ ){
        if (a[i][0] == INF)
            continue;
        for (int v = 0; v < 2; v ++ )
            for (int u = 0; u < 2; u ++ )
                dp[i][v] = min(dp[i][v], dp[pos][u] + calc(pos, u, i, v) + i - pos);
        pos = i;
    }
    ans = min(dp[pos][0], dp[pos][1]);
    cout << ans << "
";
    return 0;
}