A. Drinks Choosing 2s/256MB

题意

给定a[i],每次选出一个x,在集合中删去两个和x相等的数,最多做n/2上取整次,问最多划掉多少个。

#include <iostream>
 
const int N = 1001;
 
int cnt[N];
 
int main () {
    register int i, j;
    int n, m, x;
 
    std::cin >> n >> m;
    for (i = 1; i <= n; ++ i) {
        std::cin >> x;
        ++ cnt[x];
    }
 
    int ans = 0;
    for (i = 1; i <= m; ++ i) {
        ans += (cnt[i] % 2);
    }
 
    std::cout << n - ans / 2;
 
    return 0;
}

B. Sport Mafia 2s/256MB

题意

有一个盒子,每次操作可以放入或吃掉盒子里若干个糖果(第一次操作必须放入一个糖果)。给定操作数和盒子里最终剩余的糖果,求吃掉了多少个糖果。

解法

推一元二次方程的求根公式

#include <iostream>
#include <cmath>
 
typedef long long ll;
 
int main () {
    ll n, k, m, d;
 
    std::cin >> n >> k;
    m = (n + k) * 2;
    d = std::round(std::sqrt(9 + 4 * m));
    std::cout << n - (d  - 3) / 2 << "\n";
 
    return false; 
}

C. Basketball Exercise

题意

给2*n个数组,选取若干上下左右不相邻的数,使得和最大,求这个和

解法

简单DP,令fi分别为第i列中,不取,取第一个数,取第二个数三种情况的累加和

#include <iostream>
 
typedef long long ll;
const int N = 1e5+1;
 
ll a[N][3], f[N][3];
 
inline ll max(ll x, ll y) {
    return x > y ? x : y;
}
 
int main () {
    register int i, j;
    ll n;
 
    std::cin >> n;
    for (i = 1; i <= n; ++ i) std::cin >> a[i][0];
    for (i = 1; i <= n; ++ i) std::cin >> a[i][1];
 
    for (i = 1; i <= n; ++ i) {
        f[i][0] = max(f[i - 1][1], f[i - 1][2]) + a[i][0];
        f[i][1] = max(f[i - 1][0], f[i - 1][2]) + a[i][1];
        f[i][2] = max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2]));
    }
 
    std::cout << max(f[n][0], max(f[n][1], f[n][2]));
 
    return 0;
}

D1. Submarine in the Rybinsk Sea (easy edition) &

D2. Submarine in the Rybinsk Sea (hard edition)