AtCoder Beginner Contest 149

D - Prediction and Restriction

读题的锅！！没说输了要扣分！！！
两种做法。

贪心

对于相同格子 \(i,i+k,i+2k,...\) 采取赢，平，赢，平,...策略

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

using namespace std;
const int N = 1e5 + 5;
string t;
int n, k, r, s, p; //012:rsp
ll sum; 
int a[N];//相同,1被标记

int main () {
    cin >> n >> k >> r >> s >> p >> t;

    //贪心? 对于相同格子i,i+k,i+2k,...采取赢，平，赢，平,...策略
    for (int i = 0; i < k; i++) {
        a[i] = 1;
        if (t[i] == 'r')         sum += p;
        else if (t[i] == 's')    sum += r;
        else if (t[i] == 'p')    sum += s;
    }
    for (int i = k; i < n; i++) {
        if (t[i-k] == t[i] && a[i-k])    continue;
        a[i] = 1;
        if (t[i] == 'r')         sum += p;
        else if (t[i] == 's')    sum += r;
        else if (t[i] == 'p')    sum += s;
    }
    cout << sum;
}

// r > s, s > p, p > r
//线性递推,某些格子被ban

dp

\(f_{i,0/1/2}\) 表示 \(i\) 选择 \(r/s/p\) 时，\(i,i-k,i-2k,...\) 的和的最大值。
所以最后答案即为：

\[\sum_{i=n-k}^{n-1} \max(f_{i,0}, f_{i,1}, f_{i,2}) \]

分开(隔 \(k\))转移再合并！

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

using namespace std;
const int N = 1e5 + 5;
int f[N][3]; //第i个选的是0/1/2的最大值
string t, ans;
int n, k, r, s, p; //012:rsp
ll sum;

int main () {
    cin >> n >> k >> r >> s >> p >> t;
    
    for (int i = 0; i < k; i++) {
        if (t[i] == 'r')         f[i][2] = p;
        else if (t[i] == 's')    f[i][0] = r;
        else if (t[i] == 'p')    f[i][1] = s;
    }
    for (int i = k; i < n; i++) {
        if (t[i] == 'r') {
            f[i][0] += max (f[i-k][1], f[i-k][2]);
            f[i][1] += max (f[i-k][0], f[i-k][2]);
            f[i][2] += max (f[i-k][0], f[i-k][1]) + p;
        }
        else if (t[i] == 's') {
            f[i][0] += max (f[i-k][1], f[i-k][2]) + r;
            f[i][1] += max (f[i-k][0], f[i-k][2]);
            f[i][2] += max (f[i-k][0], f[i-k][1]);
        }
        else if (t[i] == 'p') {
            f[i][0] += max (f[i-k][1], f[i-k][2]);
            f[i][1] += max (f[i-k][0], f[i-k][2]) + s;
            f[i][2] += max (f[i-k][0], f[i-k][1]);
        }
    }
    for (int i = n - k; i < n; i++) {
        sum += max ({f[i][0], f[i][1], f[i][2]});
    }
    cout << sum;
}

// r > s, s > p, p > r
// 先分开转移再合并

E - Handshake

二分能取到的最小值

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

using namespace std;
const int N = 1e5 + 5;
ll n, m, a[N], s[N], sum, cnt;

bool check (ll x) { //最小取x
    sum = cnt = 0;
    for (int i = 1; i <= n; i++) {
        int pos = upper_bound (a + 1, a + n + 1, x - a[i]) - a;
        cnt += n - pos + 1;
        sum += s[n] - s[pos - 1] + a[i] * (n - pos + 1);
    }
    return cnt <= m;
}

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    sort (a + 1, a + n + 1);
    // for (int i = 1; i <= n; i++)    cout << a[i] << ' ';cout << endl;
    for (int i = 1; i <= n; i++)    s[i] = s[i-1] + a[i];

    ll l = 1, r = 2 * a[n];
    while (l < r) {
        ll mid = l + r >> 1;
        if (check (mid))    r = mid;
        else    l = mid + 1;
    }
    cout << sum - (cnt - m) * r;
}

//二分能娶到的最小的数
//O(nlogn)

F - Surrounded Nodes

正难则反。
分母为 \(2^n\)。
对于当前点 \(u\) 的贡献：
\(u\) 黑,无贡献，略。u白: \(2^{n-1}\) 种
\(u\) 白的前提下, 无贡献的两种可能:

\(u\) 的子树全白: \(1\) 种
\(u\) 只有的所有相邻点 \(v\) 的子树中（注：此时把 \(u\) 暂时视为根，即原 \(u\) 的父亲往上的点集也视为 \(u\) 的子树）只有一棵子树有黑点: 共 \(\sum 2^{size_v}-1\) 种。
即所求为：

\[\sum_{u=1}{n}(2^{n-1}-1-\sum_{u,v相邻}(2^{size_v}-1)) \]

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

using namespace std;
const int N = 2e5 + 5, M = N * 2, mod = 1e9 + 7;
int h[N], e[M], ne[M], idx, n;
ll sz[N], ans[N], pw[N]; //字数大小, 当前贡献

void add (int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs (int u, int fa) {
    sz[u] = 1;
    ll sum = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa)    continue;
        dfs (j, u);
        sz[u] += sz[j];
        (sum += pw[sz[j]] - 1) %= mod;
    }
    (sum += pw[n-sz[u]] - 1) %= mod; //u往上的别忘了算(也算在相邻点)
    (ans[u] += pw[n-1] - 1 - sum + mod) %= mod;
}

ll qmi(ll a, ll k, ll p) {
    ll ans = 1;
    while (k) {
        if (k & 1)  ans = ans * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return ans;
}

int main () {
    memset (h, -1, sizeof h);
    cin >> n;
    pw[0] = 1;
    for (int i = 1; i <= n; i++)    pw[i] = (pw[i-1] * 2) % mod;// cout << pw[i] << ' ';
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        add (a, b), add (b, a);
    }
    dfs (1, -1);
    // for (int i = 1; i <= n; i++)    cout << sz[i] << ' ';cout << endl;
    ll sum = 0;
    for (int i = 1; i <= n; i++)    (sum += ans[i]) %= mod;
    cout << (sum * qmi (pw[n], mod - 2, mod)) % mod << endl;
}

//妙妙思考:正难则反
//从下往上计数: 对于当前点u的贡献
//u黑,无贡献，略。u白: 2^{n-1}种
//u白的前提下, 无贡献的两种可能:
//1. u的子树全白: 1种
//2. u只有的所有相邻点v的子树中只有一黑: 2^{size_v}-1, (对u的所有子树v求和)
//最后除分母2^n