Educational Codeforces Round 9

https://codeforces.com/contest/632
3/6: ABC

A. Grandma Laura and Apples

模拟

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

using namespace std;
const int N = 45;
int n, m, a[N], ans, money;

signed main () {
    cin >> n >> m;
    string s;
    m /= 2;
    for (int i = 0; i < n; i++) {
        cin >> s;
        if (s.size () == 8)     a[i] = 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        money *= 2;
        if (a[i])   money ++;
        ans += money;
    }
    cout << m * ans;

}

//x = 2^{n-1} + 2^{cnt-1} - 1
//

B. Alice, Bob, Two Teams

前缀和

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

using namespace std;
const int N = 5e5 + 5;
int n, a[N], ans;
int preA[N], preB[N], sufA[N], sufB[N];

signed main () {
    string s;
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    cin >> s;
    s = ' ' + s;
    for (int i = 1; i <= n; i++) {
        preA[i] = preA[i-1], preB[i] = preB[i-1];
        if (s[i] == 'A')    preA[i] += a[i];
        else    preB[i] += a[i], ans += a[i];
    }
    for (int i = n; i >= 1; i--) {
        sufA[i] = sufA[i+1], sufB[i] = sufB[i+1];
        if (s[i] == 'A')    sufA[i] += a[i];
        else    sufB[i] += a[i];
    }
    for (int i = 1; i <= n; i++) {
        //假设在i翻转前缀
        ans = max (ans, preA[i] + sufB[i+1]);
    }
    for (int i = n; i >= 1; i--) {
        //假设在i翻转后缀
        ans = max (ans, sufA[i] + preB[i-1]);
    }
    cout << ans;
}

C. The Smallest String Concatenation

排序水题

#include <bits/stdc++.h>

using namespace std;
const int N = 5e4 + 5;
int n;
string s[N];

bool cmp (string a, string b) {
    return a + b < b + a;
}

int main () {
    cin >> n;
    for (int i = 0; i < n; i++)     cin >> s[i];
    sort (s, s + n, cmp);
    for (int i = 0; i < n; i++)     cout << s[i];
}

D. Longest Subsequence

离散化 + 筛因数
这题其实非常简单，但是当时没思考qaq

// LUOGU_RID: 98487907
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e6 + 5;
int n, m, a[N], cnt[N], b[N], ans[N];
int lcm = 1, tot, k;

signed main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > m)   continue;
        b[k++] = a[i], cnt[a[i]] ++;
    }
    sort (b, b + k);
    k = unique (b, b + k) - b;
    for (int i = 0; i < k; i++) {
        for (int j = b[i]; j <= m; j += b[i])     ans[j] += cnt[b[i]];
    }
    for (int i = 1; i <= m; i++) {
        if (ans[i] > tot)   tot = ans[i], lcm = i;
    }
    
    cout << lcm << ' ' << tot << endl;
    for (int i = 1; i <= n; i++) {
        if (lcm % a[i] == 0)    cout << i << ' ';
    }    
}

剩下眼睛不舒服，明天补

E. Thief in a Shop

F. Magic Matrix