Educational Codeforces Round 26

https://codeforces.com/contest/837

E公式推导看明白了，但是因子求解部分的代码还不是很懂，所以还没有补

A. Text Volume

#include <bits/stdc++.h>

using namespace std;

int main () {
    int n;
    string s;
    cin >> n;
    getchar ();
    getline (cin, s);
    int ans = 0, len = 0;
    for (int i = 0; i < s.size (); i++) {
        if (s[i] == ' ')    ans = max (ans, len), len = 0;
        else if (s[i] >= 'A' && s[i] <= 'Z')    len++;
    }
    ans = max (ans, len);
    cout << ans;
}

B. Flag of Berland

#include <bits/stdc++.h>

using namespace std;
const int N = 105;
char a[N][N], idx[] = {'R', 'B', 'G'};
int n, m;

bool check (int model) {
    map<char, vector<int>> mp;
    if (model) { //横
        for (int i = 1; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                if (a[i][j] != a[i][j-1])   return false;
            }
            mp[a[i][1]].push_back (i);
        }
    }
    else {
        for (int j = 1; j <= m; j++) {
            for (int i = 2; i <= n; i++) {
                if (a[i][j] != a[i-1][j])   return false;
            }
            mp[a[1][j]].push_back (j);
        }        
    }
    set<int> s;
    for (int i = 0; i < 3; i++)     s.insert (mp[idx[i]].size ());
    if (s.size () != 1)     return false;
    //检查是否连续
    int nn = *s.begin ();
    for (int i = 0; i < 3; i++) {
        for (int j = 1; j < nn; j++) {
            if (mp[idx[i]][j] - mp[idx[i]][j-1] != 1)   return false;
        }
    }
    return true;
}

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    if (check (0) || check (1))    cout << "YES\n";
    else    cout << "NO\n";
}

C. Two Seals

#include <bits/stdc++.h>

using namespace std;
const int N = 105;
int x[N], y[N], a, b, n, ans;

int main () {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++)   cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            //if (x[i] > a || x[j] > a || y[i] > b || y[j] > b)   break;
            int s = x[i] * y[i] + x[j] * y[j];
            if (x[i] + x[j] <= a && max (y[i], y[j]) <= b)  ans = max (ans, s);
            if (x[i] + x[j] <= b && max (y[i], y[j]) <= a)  ans = max (ans, s);
            if (y[i] + y[j] <= a && max (x[i], x[j]) <= b)  ans = max (ans, s);
            if (y[i] + y[j] <= b && max (x[i], x[j]) <= a)  ans = max (ans, s);
            if (x[i] + y[j] <= a && max (y[i], x[j]) <= b)  ans = max (ans, s);
            if (x[i] + y[j] <= b && max (y[i], x[j]) <= a)  ans = max (ans, s);
            if (y[i] + x[j] <= a && max (x[i], y[j]) <= b)  ans = max (ans, s);
            if (y[i] + x[j] <= b && max (x[i], y[j]) <= a)  ans = max (ans, s);
        }
    }
    cout << ans << endl;
}

//n^2暴力选即可

D. Round Subset

线性dp小题。把一个维度塞进数组，另一个作为值

// LUOGU_RID: 103242598
#include <bits/stdc++.h>
#define ll long long
#define vi vector<ll>

using namespace std;
const int N = 205, M = 30 * N;
ll cnt2[N], cnt5[N];
int n, k;
ll f[N][M][2]; //f[j][k]: 选了j个数,其中有k个5时, 2的数量

int main () {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        while (x % 2 == 0)   x /= 2, cnt2[i] ++;
        while (x % 5 == 0)   x /= 5, cnt5[i] ++;
        //cout << cnt2[i] << ' ' << cnt5[i] << endl;
    }
    //cout << log (1e18) / log (5) << ' ' << log (1e18) / log(2) << endl;
    memset (f, -1, sizeof f);
    f[0][0][0] = f[0][0][1] = 0;
    for (int i = 1; i <= n; i++) {
        int t = (i & 1);
        for (int j = 0; j <= min(k, i); j++) {
            for (int k = 0; k < j * 30; k++) {
                if (!j || k < cnt5[i] || f[j-1][k-cnt5[i]][t] == -1)   continue;
                f[j][k][t^1] = max (f[j][k][t^1], f[j-1][k-cnt5[i]][t] + cnt2[i]);
            }
        }
        //f.swap (tmp);
        for (int j = 0; j <= min(k, i); j++) {
            for (int k = 0; k < j * 30; k++) {
                f[j][k][t] = f[j][k][t^1];
            }
        }
    }
    ll ans = 0;
    for (ll i = 0; i < 30 * n; i++) { //cnt5
        //cout << i << ' ' << f[n][k][i] << endl;
        ans = max (ans, min (i, f[k][i][n&1]));
    }
    cout << ans << endl;
}

//min(cnt2, cnt5)

E. Vasya's Function

F. Prefix Sums

G. Functions On The Segments