Educational Codeforces Round 9 题解

A

比较阅读理解。。读懂了还好

int n, p;
std::vector<std::string> vs;
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> p;
    rep (i, 1, n) {
        std::string s; cin >> s;
        vs.push_back(s);
    }
    std::reverse(ALL(vs));
    lli apples = 0;
    lli ans = 0;
    for (auto s : vs) {
        if (s.size() == 8) {
            // halfplus
            lli last_apples = apples * 2 + 1;
            ans += apples * p + (p / 2);
            apples = last_apples;
        } else {
            // half
            lli last_apples = apples * 2;
            ans += apples * p;
            apples = last_apples;
        }
    }
    printf("%lld
", ans);
    return 0;
}

B

枚举翻转哪个位置的前缀，用前缀和算一算就行了。后缀同理。

const int MAXN = 5e5 + 10;
 
int n;
lli pp[MAXN];
char ss[MAXN];
int seq[MAXN];
lli pref[MAXN][2];
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    rep (i, 1, n) cin >> pp[i];
    cin >> ss;
    rep (i, 0, n - 1) seq[i + 1] = (ss[i] == 'B');
 
    lli ans = 0;
    rep (cas, 0, 1) {
        rep (i, 1, n) rep (j, 0, 1) pref[i][j] = pref[i - 1][j] + (seq[i] == j) * pp[i];
        ans = std::max(ans, pref[n][1]);
        rep (i, 1, n) {
            lli allans = pref[n][1];
            allans -= pref[i][1]; allans += pref[i][0];
            ans = std::max(ans, allans);
        }
        std::reverse(seq + 1, seq + 1 + n);
        std::reverse(pp + 1, pp + 1 + n);
    }
    printf("%lld
", ans);
    return 0;
}

C

经典贪心。

const int MAXN = 5e4 + 10;
 
int n;
std::string ss[MAXN];
 
bool cmp(std::string sa, std::string sb) {
    return sa + sb < sb + sa;
}
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    rep (i, 1, n) cin >> ss[i];
    std::sort(ss + 1, ss + 1 + n, cmp);
    rep (i, 1, n) cout << ss[i];
    cout << endl;
    return 0;
}

D. Longest Subsequence

基础数论题，然而我不会。

首先 (> m) 的数都可以扔了，这样我们可以把数据范围缩到 (10^6)。

接下来考虑算贡献：记录每个数字能对哪些 lcm 产生贡献，也就是对于 (i in [1, m])，如果 (x|i) 那么让 (mathrm{ans}_i) 加 (1)。这个东西可以用一个类似埃氏筛的东西优化，即对于一个 (x)，让所有 (mathrm{ans}_{kx}(kx leq m)) 都加 (1)。重复的数字可以合并计算。

时间复杂度 (O(mlog m))，虽然这个我也不知道咋来的。

最开始没看到输出下标，然后看了好一会也没看出来样例为啥是对的。。。

#易错警示：题目要输出什么一定好好看清。

const int MAXN = 1e6 + 10;
 
int n, m;
std::vector<int> bwl[MAXN];
int occ[MAXN];
std::vector<int> nums;
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    n = read(); m = read();
    rep (i, 1, n) {
        int x = read();
        if (x > m) continue;
        bwl[x].push_back(i);
    }
    rep (i, 1, MAXN - 5) if (bwl[i].size()) nums.push_back(i);
    for (auto v : nums) {
        for (int j = 1; j * v <= m; ++j) {
            occ[j * v] += bwl[v].size();
        }
    }
    int tans = 1;
    for (int i = 1; i <= m; ++i) if (occ[i] > occ[tans]) tans = i;
    cout << tans << ' ' << occ[tans] << endl;
    std::vector<int> inds;
    for (auto v : nums) if (tans % v == 0) for (auto id : bwl[v]) inds.push_back(id);
    std::sort(ALL(inds));
    for (auto id : inds) cout << id << ' ';
    cout << endl;
    return 0;
}

E. Thief in a Shop

一个很 nb 的做法。

正着 DP 不好写考虑交换维度和答案：设 f[i][j] 表示考虑前 i 个物品，凑出价格为 j 最少需要多少个物品，第一维可以滚掉。一个很普通的完全背包。

然而这么写连样例都过不去。

问题在于，题目让我们求的是恰好 (k) 个物品的情况，但是这么 DP 只能算出 (leq k) 个物品的情况。如果有价格为 (0) 的物品的话，不足 (k) 个物品也能通过 (0) 价格物品来补齐，但是这里没有 (0)。

于是考虑造出一个 (0) 来。

取 (v = min a_i)，接下来把所有物品的价格都减掉 (v)，此时我们就成功获得了一个 (0) 价格物品！对修改过价格的物品做背包，我们可以知道每一种（修改后的）价格最少需要多少物品凑出来，如果 (leq k) 就说明这个（修改后的）价格是合法的。

注意到所有物品的价格都被减掉了 (v)，那么选 (k) 个物品时价格就被减掉了 (kv)，所以输出答案的时候还要将价格加上 (kv)。

const int MAXN = 1000 + 10;
 
int n, k;
int aa[MAXN];
int dp[MAXN * MAXN];
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    n = read(); k = read();
    rep (i, 1, n) aa[i] = read();
    std::sort(aa + 1, aa + 1 + n);
    rep (i, 2, n) aa[i] -= aa[1];
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    rep (i, 2, n) {
        rep (j, aa[i], aa[n] * k) {
            dp[j] = std::min(dp[j], dp[j - aa[i]] + 1);
        }
    }
    rep (i, 0, aa[n] * k) {
        if (dp[i] <= k) {
            cout << i + aa[1] * k << ' ';
        }
    }
    cout << endl;
    return 0;
}

F. Magic Matrix

首先可以把题目转化成对于每个点 ((i, j))，求第 (i) 行和第 (j) 行每列元素对应取 max 是否都大于 ((i, j))。

考虑确定当前值后将其他元素变为“大于为 1 小于为 0”这样一个思想，我们对于每一个节点 ((i, j))，将所有大于等于它的数字变成 (0)，小于它的数字变成 (1)，那么题设就转化成了第 (i) 行和第 (j) 行按位与起来是否不为 0.

接下来再用边插入边查询的思想，按权值从小到大依次考虑所有节点，将已经考虑过的节点设置为 1（一起处理所有相同权值的节点），对当前节点查询第 (i) 行和第 (j) 行按位与起来是否不为 0 即可。这个过程可以用 bitset 优化，时间复杂度 (O(n^3/64)).

const int MAXN = 2500 + 10;
 
int n;
int aa[MAXN][MAXN];
 
std::bitset<MAXN> mat[MAXN];
 
bool checksym() {
    for (int i = 1; i <= n; ++i) if (aa[i][i]) return false;
    rep (i, 1, n) rep (j, 1, n) if (aa[i][j] != aa[j][i]) return false;
    return true;
}
 
struct Node {
    int i, j, x;
} nodes[MAXN * MAXN]; int cnt;
 
bool cmp(Node x, Node y) { return x.x < y.x; }
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    n = read();
    rep (i, 1, n) rep (j, 1, n) aa[i][j] = read();
    if (!checksym()) {
        cout << "NOT MAGIC" << endl;
        return 0;
    }
    rep (i, 1, n) rep (j, 1, n) {
        nodes[++cnt] = {i, j, aa[i][j]};
    }
    std::sort(nodes + 1, nodes + 1 + cnt, cmp);
    for (int i = 1; i <= cnt; ++i) {
        int r = i;
        while (r + 1 <= cnt && nodes[i].x == nodes[r + 1].x) ++r;
        for (int x = i; x <= r; ++x) {
            int a = nodes[x].i, b = nodes[x].j;
            if ((mat[a] & mat[b]).any()) {
                // mat[i][j] = 0 if AA[i][j] > AA[a][b]
                cout << "NOT MAGIC" << endl;
                return 0;
            }
        }
        for (int x = i; x <= r; ++x) mat[nodes[x].i][nodes[x].j] = 1;
        i = r;
    }
    cout << "MAGIC" << endl;
    return 0;
}