Educational Codeforces Round 17

https://codeforces.com/contest/762

A. k-th divisor

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

using namespace std;
ll n, k;

void get_div (ll x) {
    vector<ll> v;
    v.push_back (1);
    if (x != 1)     v.push_back (x);
    for (ll i = 2; i*i <= x; i++) {
        if (x % i == 0) {
            v.push_back (i);
            if (i !=  x / i) {
                v.push_back (x / i);
            }
        }
    }
    sort (v.begin (), v.end ());
    //cout << v.size () << endl;
    //for (auto i : v)    cout << i << ' ';  cout << endl;
    if (v.size () < k)      cout << -1;
    else    cout << v[k-1];
}

int main () {
    cin >> n >> k;
    get_div (n);
}

B. USB vs. PS/2

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

using namespace std;
int a, b, c, n, cnt;
ll ans;
multiset<int> s1, s2;

int main () {
    cin >> a >> b >> c >> n;
    for (int i = 0; i < n; i++) {
        int x;
        string s;
        cin >> x >> s;
        if (s[0] == 'U')    s1.insert (x);
        else    s2.insert (x);
    }

    while (s1.size () && a > 0) {
        cnt ++, ans += *s1.begin ();
        s1.erase (s1.begin ()), a --;
    }
    while (s2.size () && b > 0) {
        cnt ++, ans += *s2.begin ();
        s2.erase (s2.begin ()), b --;
    }
    multiset<int> s;
    for (auto i : s1)   s.insert (i);
    for (auto i : s2)   s.insert (i);
    while (s.size () && c > 0) {
        cnt ++, c --;
        ans += *s.begin ();
        s.erase (s.begin ());
    }
    cout << cnt << ' ' << ans << endl;
}

C. Two strings

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int posl[N], posr[N], ansr, ansl, n, m;

bool check (int l, int r) { //删掉[l,r]
    if (posl[l-1] < posr[r+1])    return true;
    return false;
}

int main () {
    string a, b;
    cin >> a >> b;
    n = a.size (), m = b.size ();
    a = ' ' + a, b = ' ' + b;
    ansl = 0, ansr = m + 1;
    for (int i = 0; i <= m + 1; i++)    posl[i] = n + 1;
    
    //预处理匹配
    for (int i = 1, j = 1; i <= m && j <= n; j++) {
        if (a[j] == b[i])   posl[i] = j, i ++;
    }
    for (int i = m, j = n; i >= 1 && j >= 1; j--) {
        if (a[j] == b[i])   posr[i] = j, i --;
    }

    //for (int i = 1; i <= m; i++)    cout << posl[i] << ' '; cout << endl;
    //for (int i = 1; i <= m; i++)    cout << posr[i] << ' '; cout << endl;

    if (posl[1] == n + 1 && posr[m] == 0) {
        cout << '-';
        return 0;
    }

    //if (posl[1] == n + 1) { //删前缀
        for (int i = 1; i <= m; i++) {
            if (posr[i] != 0) {
                ansl = 1, ansr = i - 1;
                break;
            }
        }
    //}
    //else if (posr[m] == 0) { //删后缀
        for (int i = m; i >= 1; i--) {
            if (posl[i] != n + 1) {
                if (m - i - 1 < ansr - ansl)    ansl = i + 1, ansr = m;
                break;
            }
        }
    //}
    //else {
        //二分枚举
        for (int l = 1; l <= m; l++) {
            int tl = l, tr = m;
            while (tl < tr) {
                int mid = tl + tr >> 1;
                if (check (l, mid))    tr = mid;
                else    tl = mid + 1;
                //cout << l << ' ' << tr << endl;
            }
            //cout << endl;
            if (check (l, tr)) {
                int r = tr;
                if (ansr - ansl > r - l)    ansl = l, ansr = r;
            }
        }
    //}

    if (!ansl)    cout << '-';
    else {
        //cout << ansl << ' ' << ansr << endl;
        for (int i = 1; i < ansl; i++)  cout << b[i];
        for (int i = ansr + 1; i <= m; i++) cout << b[i];
    }
}

//题意: 把b删掉一段连续的后,使其成为a的子序列,输出删去后满足条件的最长b
//优化枚举: 找到合法方案后, 删除更多依旧合法, 故枚举左端点, 二分右端点
//优化匹配: (核心: 每个b都有在a中对应的位置, 因为a不变所以可以记录位置)
//posl[i]: b中[1,i]的字符匹配到a里, 第i个元素在a中对应的位置(前缀匹配)
//posr[i]: b中[i,lenb]的字符匹配到a里, 第i个元素在a中对应的位置(后缀匹配)
//则匹配等价于check是否满足posl[l-1] < posr[r+1]即可

D. Maximum path

wa了但是明天再改好了

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

using namespace std;
const int N = 1e5 + 5, inf = -1e18;
int ans = -1e18;
int f[5][N][2]; //f[i][j][0]: 从下面走过来, f[i][j][1]: 从上面走过来
int a[5][N], s[5][N], n, m;

bool Range (int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m)   return false;
    return true;
}

int dfs (int x, int y, int dir) {
    if (!Range (x, y))      return inf;
    if (f[x][y][dir] != inf)       return f[x][y][dir];
    f[x][y][dir] = max (dfs (x, y + 1, 0), dfs (x, y + 1, 1)) + a[x][y];
    if (dir)    f[x][y][dir] = max (f[x][y][dir], dfs (x - 1, y, 1) + a[x][y]);
    else        f[x][y][dir] = max (f[x][y][dir], dfs (x + 1, y, 0) + a[x][y]);
    return f[x][y][dir];
}

int query (int sx, int sy, int fx, int fy) { //求二位前缀和
    return s[fx][fy] - s[sx-1][fy] - s[fx][sy-1] + s[sx-1][sy-1];
}

signed main () {
    cin >> m;
    n = 3;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            f[i][j][0] = f[i][j][1] = inf;
        }
    }
    //逆向做
    f[n][m][0] = f[n][m][1] = a[n][m];
    ans = dfs (1, 1, 0);

    if (m & 1) { //考虑往左拐一格的情况
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
            }
        }

        for (int i = 2; i <= m; i++) { //枚举在哪个点拐的
            //(1,i-1)到(n,i)的和 + (1,1)到(1,i-2)
            int sum = query (1, i - 1, n, i);
            if (i > 2)  sum += query (1, 1, 1, i - 2);
            if (i < m)  sum += f[n][i+1][1];
            ans = max (ans, sum);
        }
    }
    cout << ans << endl;
}

//偶数的时候可以被不返回的路径代替
//奇数的时候可以至多返回一次,且只往回走一格,可以枚举返回的位置,转化为子问题

E. Radio stations

F. Tree nesting