Educational Codeforces Round 38 C - F

https://codeforces.com/contest/938
今天写出了三题ovo

C. Constructing Tests

多画几个图就能发现，对于 \(n\times n\) 的正方形来说，要使得 \(m\times m\) 的子正方形至少有一个 \(0\)，则最少的 \(0\) 个数为 \(\lfloor \frac{n}{m} \rfloor ^ 2\)

即最大的 \(1\) 的个数 \(x=n^2-\lfloor \frac{n}{m} \rfloor ^ 2=(n+\lfloor \frac{n}{m} \rfloor)(n-\lfloor \frac{n}{m} \rfloor)\)，即化为 \(x\) 的两因子相乘的形式。令 \(a=n+\lfloor \frac{n}{m} \rfloor, b = n-\lfloor \frac{n}{m} \rfloor\)，解得 \(n=\frac{a+b}2, \lfloor \frac nm \rfloor =\frac{a-b}2\)

因此只需分解 \(x\)，然后判断解出来的 \(n, m\) 是否合法即可。

复杂度为 \(O(t\sqrt x)\)

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

using namespace std;

void solve () {
    ll x;
    cin >> x;    
    if (x == 0) {
        cout << "1 1\n";
        return ;
    }
    for (ll i = 1; i * i <= x; i++) {
        if (x % i)  continue;
        ll a = i, b = x / i;
        if (a == b || ((a + b) & 1))    continue;
        ll n = (a + b) / 2;
        if (n < 1 || n > 1e9)   continue;
        if (b - a < 2 || b - a > 2 * n || ((b - a) & 1))    continue;
        ll t = (b - a) / 2, m = n / t;
        if (n / m != t)  continue;
        cout << n << ' ' << m << endl;
        return ;
    }
    cout << "-1\n";
}

int main () {
    int t;
    cin >> t;
    while (t--)     solve ();
    // cout << sqrt (1e9);
}

//n^2 - (n / m)^2 = x

D. Buy a Ticket

又是图论小技巧（把点权转化为边权）！！
建立虚拟源点连向 \(n\) 个城市，边权为 \(a_i\)，然后因为是往返，所以就把边乘2倍再加进去
建立虚拟源点: 把点权化为源点到点的边权

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

using namespace std;
typedef pair<ll, int> pii;
const int N = 2e5 + 5, M = N * 4;
int n, m;
int h[N], e[M], ne[M], idx;
ll w[M], d[N], p[N];
bool vis[N];

void add (int a, int b, ll c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void bfs (int st) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push ({0, st});
    d[st] = 0;

    while (!q.empty ()) {
        auto t = q.top ();
        q.pop ();
        int ver = t.second;
        ll dist = t.first;
        if (vis[ver])   continue;
        vis[ver] = true;

        for (int i = h[ver]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] > dist + w[i]) {
                d[j] = dist + w[i];
                q.push ({d[j], j});
            }
            //else    return ;
        }
    }
}

int main () {
    memset (h, -1, sizeof h);
    memset (d, 0x3f, sizeof d);
    scanf ("%d%d", &n, &m);
    while (m--) {
        int a, b;
        ll c;
        scanf ("%d%d%lld", &a, &b, &c);
        add (a, b, c * 2), add (b, a, c * 2);
    }
    for (int i = 1; i <= n; i++)    scanf ("%lld", &p[i]), add (0, i, p[i]), add (i, 0, p[i]);
    bfs (0);
    for (int i = 1; i <= n; i++)    printf ("%lld ", d[i]);
}

//建立虚拟源点: 把点权化为源点到点的边权

E. Max History

组合数学！又是推柿子qaq

如果发现某几步看不懂的话可能是忘记了这些重要的基础公式！！！！

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

using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int a[N], n, maxn;
ll fz = 1, ans, tt;

ll qmi(ll a, ll k, ll p){
    ll res = 1;
    while(k){
        if(k & 1)    res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i], (fz *= i) %= mod;
    sort (a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i] == a[n])   break;··
        if (a[i] != a[i-1]) tt = qmi (n - i + 1, mod - 2, mod); //有n-i-1个数比ai小
        (ans += a[i] * fz % mod * tt % mod) %= mod;
    }
    cout << ans << endl;
}

//n!/(n-k)

F. Erasing Substrings

妙妙dp题。
我想到了朴素的状压： \(dp_{i, j}\) 表示考虑到第 \(i\) 位，\(j\) 代表删除的集合（二进制表示）的最小字符串。
然后就不会做了，因为不会用字符串来表示 \(dp\) 数组呜呜。
看了眼题解，说是有个优化：

（link: https://zyd.blog.luogu.org/solution-cf938f）

学到了，这个优化真的很妙。

然后就是滚动数组优化了一下：

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

using namespace std;
const int N = 5005;
bool f[N]; //f[i][S]; 考虑前i位,S为被删除的集合, 能否等于ans[1...x-len]的bool值
string s;

int main () {
    cin >> s;
    int n = s.size (), k = log2 (n), S = (1 << k);
    memset (f, true, sizeof f);
    for (int i = 0; i < n - S + 1; i++) {
        char ch = 'z';
        for (int j = 0; j < S; j++) {
            for (int x = 0; x < k; x++) {
                f[j | (1 << x)] |= f[j]; //下一步删 2^x
            }
        }
        for (int j = 0; j < S; j++) {
            if (f[j])   ch = min (ch, s[i + j]); //删完这一段之后下一个最小字符
        }
        for (int j = 0; j < S; j++) { //滚动数组
            if (s[i + j] != ch)     f[j] = false; //删去后没法保证前缀相等(为最小)
        }
        cout << ch;
    }
    // cout << log2 (5000);   
}

//O(n^2logn)

G. Shortest Path Queries

complex ds qaq