codeforces#913

CF913A Modular Exponentiation

题面：给出正整数n和m，求m % 2^n，其中1 <= n,m <= 1e8。

分析：注意到如果a < b，那么a % b = a。

n, m = input(), input()
print m if n > 32 else m % pow(2, n)

CF913B Christmas Spruce

题面：给定一棵有根树，根节点编号固定为1，满该树是否满足所有非叶子节点至少有3个叶子节点。

分析：通过dfs自下而上统计即可。

#include <bits/stdc++.h>
using namespace std;
int n, ok = 1;
vector<int> g[1005];
int dfs(int x, int f) {
    if (g[x].size() == 1) return 1;
    int cnt = 0;
    for (auto i : g[x]) {
        if (i == f) continue;
        cnt += dfs(i, x);
    }
    if (cnt < 3) ok = 0;
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        int p;
        scanf("%d", &p);
        g[p].push_back(i);
        g[i].push_back(p);
    }
    dfs(1, -1);
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
}

CF913C Party Lemonade

题面：有n种规格不同的柠檬，第i种规格的容量为2^(i-1)，花费为ci，每种规格件数不限，求购买不低于L容量柠檬的最少花费。

分析：将规格按性价比排序，依次考虑，对于某种规格，如果购买量不小于其容量，那最优做法肯定是购买该种规格；反之购买量大于其容量，则有两种选择：一种是直接买一个该规格，另一种是不买，用性价比更低但容量和花费可能更小的来满足，取较小者即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, L;
struct ST {
    LL c, v, k;
    bool operator<(const ST &o) const {
        if (k != o.k) return k < o.k;
        return v < o.v;
    }
}f[35];
LL dfs(int x, LL left) {
    if (left == 0) return 0;
    if (x > n) return LLONG_MAX;
    if (f[x].v <= left) {
        LL cnt = left / f[x].v;
        return f[x].c * cnt + min(f[x].c, dfs(x + 1, left - f[x].v * cnt));
    }
    return min(f[x].c, dfs(x + 1, left));
}
int main() {
    cin >> n >> L;
    for (int i = 1; i <= n; i++)
        cin >> f[i].c;
    for (int i = 1, j = 1; i <= n; i++, j *= 2)
        f[i].v = j;
    for (int i = 1, j = n; i <= n; i++, j--)
        f[i].k = f[i].c * f[j].v;
    sort(f + 1, f + 1 + n);
    cout << dfs(1, L) << endl;
    return 0;
}

CF913D Too Easy Problems

题面：一场时长为T的考试中共有n道题，解决第i道题要花ti的时间，总得分为解出问题题数之和，考虑到题目难度有差异，对第i道题定了个权值ai，在解出总题数不超过ai时，解出的第i题才计分，求可能得到的最高分数。

分析：二分答案。因为分数按解出题数来算，将题目按t排序，优先做花时少的题目，在固定分数s后，还需要知道解出题数k，才能判断分数s是否可达到，因此需要再二分k。

#include <bits/stdc++.h>
using namespace std;
int n, T, maxs;
struct ST {
    int a, t, x;
    bool operator<(const ST &o) const {
        if (t != o.t) return t < o.t;
        return a > o.a;
    }
}f[200005];
vector<ST> ans;
bool chk1(int s, int k) {
    int s1 = 0, t1 = 0;
    vector<ST> ans1;
    for (int i = 0; i < n; i++) {
        if (f[i].a >= k) {
            t1 += f[i].t;
            s1 += 1;
            ans1.push_back(f[i]);
            if (s1 == k) break;
        }
    }
    if (t1 <= T && s1 >= s) {
        maxs = s;
        ans1.swap(ans);
        return true;
    }
    return false;
}
bool chk(int s) {
    int lo = s, hi = n, mid;
    while (lo < hi) {
        mid = lo + (hi - lo + 1) / 2;
        if (chk1(s, mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    return lo >= s && chk1(s, lo);
}
int main() {
    scanf("%d%d", &n, &T);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &f[i].a, &f[i].t);
        f[i].x = i + 1;
    }
    sort(f, f + n);
    int lo = 0, hi = n, mid;
    while (lo < hi) {
        mid = lo + (hi - lo + 1) / 2;
        if (chk(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    printf("%d\n", maxs);
    if (maxs == 0) {
        puts("0");
    } else {
        printf("%d\n", ans.size());
        for (auto i : ans)
            printf("%d ", i.x);
        puts("");
    }
    return 0;
}