Codeforces Round 536 (Div. 2) 题解

学长出题orz，不过cf服务器炸了也是。。。

A

题目大意：给定一个字符矩阵，如果某个字符及其左上，左下，右上，右下的临近字符都是X那么就说以该字符为中心构成一个“X”。求中心不同的“X”个数。

遍历找一遍就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
char mat[505][505] = {0};
int main(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        scanf("%s", &mat[i][1]);
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(mat[i][j] == 'X' && mat[i + 1][j + 1] == 'X' && mat[i - 1][j - 1] == 'X' && mat[i + 1][j - 1] == 'X' && mat[i - 1][j + 1] == 'X')
                ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

B

题目链接

按照题目的意思进行模拟即可。
因为不同菜品之间的价格不会变，所以可以直接在开始时对所有菜品排序，然后用一个指针指示当前最便宜的菜品的编号。之后就是按题意模拟了。
本题有一个坑，就是如果菜没了cost就直接置为0了。。。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
int n, m;
int a[100005], c[100005];
ll ans[100005] = {0};
pp p[100005];
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &c[i]), p[i].first = c[i], p[i].second = i;
    sort(p + 1, p + n + 1);
    int cur = 1;
    for(int i = 1; i <= m; ++i){
        int t, d;
        scanf("%d%d", &t, &d);
        if(a[t] >= d) ans[i] += 1ll * d * c[t], a[t] -= d;
        else{
            ans[i] += 1ll * a[t] * c[t], d -= a[t], a[t] = 0;
            while(d){
                while(cur <= n && a[p[cur].second] == 0) cur++;
                if(cur > n) break;
                
                int id = p[cur].second;
                int bb = min(a[id], d);
                ans[i] += 1ll * bb * c[id];
                a[id] -= bb, d -= bb;
            }
            if(cur > n) {
                ans[i] = 0;
                break; 
            }
        }
    }
    for(int i = 1; i <= m; ++i)
        printf("%I64d\n", ans[i]);
    return 0;
}

C

题目大意：给定$n$个数，求一种划分，将所有数分为若干组，每个组至少包含两个数，使得$\Sigma\text{每一个组内数的和的平方}$最小。

贪心。可以证明当每个组里只有2个元素的时候答案可以最小，然后组合方式就是当前最小元素搭配当前最大元素。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[300005];
ll ans = 0;
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= (n >> 1); ++i)
        ans += 1ll * (a[i] + a[n - i + 1]) * (a[i] + a[n - i + 1]);
    printf("%I64d\n", ans);
    return 0;
}

D

题目大意：给定一张无向图，起点在1处，每走过一个之前没有经过的顶点就会将这个顶点的编号写在之前顶点编号的后面，形成一个顶点编号序列。显然序列的开头是1。每一条边和每一个顶点都可以重复经过。求一个序列，使其字典序最小。

一开始以为是强连通分量分解，后来发现也是一个贪心。先把1放入小根堆，然后每次取出堆顶元素，设其为$v$，与$v$相邻的且未经过的点放进堆里，如此反复就可以得到答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge{
    int v, nxt;
};
Edge e[200005];
int at[100005], cnt = 0;
int V, E;
int in[100005] = {0}; 
int st[100005], top = 0;
int ans[100005];
priority_queue<int, vector<int>, greater<int> > pq;
void addEdge(int u, int v){
    e[++cnt].v = v, e[cnt].nxt = at[u], at[u] = cnt;
}
int main(){
    scanf("%d%d", &V, &E);
    for(int i = 1; i <= E; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v), addEdge(v, u);
    }
    in[1] = true, ans[1] = 1;
    for(int i = at[1]; i; i = e[i].nxt){
        if(in[e[i].v]) continue;
        pq.push(e[i].v), in[e[i].v] = true;
    }
    for(int i = 2; i <= V; ++i){
        int dd = pq.top();
        pq.pop();
        ans[i] = dd;
        for(int j = at[dd]; j; j = e[j].nxt){
            if(in[e[j].v]) continue;
            pq.push(e[j].v), in[e[j].v] = true;
        }
    }
    for(int i = 1; i < V; ++i)
        printf("%d ", ans[i]);
    printf("%d\n", ans[V]);
    return 0;
}

E

题目链接

容易看出每一个时间点Bob的动作是唯一确定的，所以可以先用排序和堆处理出每一个时间点的动作。
然后DP，设$f(i, j)$为第$i$天结束时，用了$j$次妨碍机会后，所得到的钱的最小值。那么在一个时间点，如果有红包可抢，如果抢就用$f(i-1, j)+w$更新$f(d, j)$，不抢就用$f(i-1, j-1)$更新$f(i, j)$。没有红包抢就用$f(i-1, j)$更新$f(i, j)$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<pair<int, int>, int> ppp;
int n, m, k;
int l[100005], r[100005], mon[100005], d[100005];
ll f[100005][205] = {0}, ans = 0;
pair<int, int> pp[100005];
priority_queue<ppp> pq;
int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= k; ++i)
        scanf("%d%d%d%d", &l[i], &r[i], &d[i], &mon[i]), pp[i].first = l[i], pp[i].second = i, ans += mon[i];
    sort(pp + 1, pp + k + 1);
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    int cur = 1;
    for(int i = 1; i <= n; ++i){
        while(cur <= k && pp[cur].first == i){
            int id = pp[cur].second;
            pq.push(make_pair(make_pair(mon[id], d[id]), r[id]));
            cur++;
        }
        if(pq.empty()){
            f[i][0] = min(f[i - 1][0], f[i][0]);
            for(int j = 1; j <= m; ++j){
                f[i][j] = min(f[i - 1][j], f[i][j]);
                f[i][j] = min(f[i - 1][j - 1], f[i][j]);
            }
        }else{
            ppp pt = pq.top();
            int curd = pt.first.second;
            ll curm = pt.first.first;

            f[curd][0] = min(f[curd][0], f[i - 1][0] + curm);
            for(int j = 1; j <= m; ++j){
                f[curd][j] = min(f[curd][j], f[i - 1][j] + curm);
                f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            }
        }
        while(!pq.empty() && pq.top().second <= i)
            pq.pop();
    }
    for(int i = 0; i <= m; ++i)
        ans = min(ans, f[n][i]);
    printf("%I64d\n", ans);
    return 0;
}

F

题目大意：给定一个递推数列：

$$f_i = (\prod_{j = 1}^{k} f_{i - j}^{b_j})\mod p$$

其中$i>k, p=998244353$。已知$k, n, f_n, b_1, \cdots, b_k$，且$f_1=\cdots=f_{k-1}=1$，求$f_k$的可能值。

由于$f$的前$k-1$项全部是$1$，所以可以只考察$f_n$中$f_k$的指数。这个可以用快速幂来做。
已知指数和幂求底数，这就是一个经典的k次剩余问题，由于本题没有额外的限制，所以使用原根和BSGS算法解决。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int c[10005] = {0}, bb[10005] = {0}, tmp[20005] = {0};
int k, n, m, b[105];
const int p = 998244353;
void mul(int *a1, int *a2){
    for(int i = 0; i <= (k << 1); ++i)
        tmp[i] = 0;
    for(int i = 0; i <= k; ++i){
        for(int j = 0; j <= k; ++j){
            tmp[i + j] = (tmp[i + j] + 1ll * a1[i] * a2[j]) % (p - 1);
        }
    }
    for(int i = k << 1; i >= k; --i){
        for(int j = 0; j < k; ++j){
            tmp[i - k + j] = (tmp[i - k + j] + 1ll * tmp[i] * b[k - j]) % (p - 1);
        }
        tmp[i] = 0;
    }
    for(int i = 0; i < k; ++i)
        a1[i] = tmp[i];
}
void poww(int *a1, int t, int *a2){
    while(t){
        if(t & 1) mul(a2, a1);
        mul(a1, a1), t >>= 1;
    }
}
int poww_i(int a, int b, int c){
    a %= c;
    int res = 1;
    while(b){
        if(b & 1) res = (1ll * res * a) % c;
        a = (1ll * a * a) % c, b >>= 1; 
    }
    return res;
}
int extgcd(int a, int b, int &x, int &y){
    int d = a;
    if(b)
        d = extgcd(b, a % b, y, x), y = y - (a / b) * x;
    else
        x = 1, y = 0;
    return d;
}
int inv(int x, int m){
    int u, v;
    if(extgcd(x, m, u, v) != 1)
        return -1;
    return u < 0 ? u + m: u;
}
int BSGS(int y, int z, int m){
    map<int, int> rec;
    int s = (int)floor(sqrt(m - 1) + 0.5), cur = 1;
    int v = inv(poww_i(y, s, m), m);
    if(v == -1) return -1;
    for(int i = 0; i < s; ++i)
        rec[cur] = i, cur = 1ll * cur * y % m;
    for(int i = 0; i <= s; ++i){
        if(rec.count(z))
            return i * s + rec[z];
        z = 1ll * z * v % m;
    }
    return -1;
}
int main(){
    scanf("%d", &k);
    for(int i = 1; i <= k; ++i)
        scanf("%d", &b[i]);
    scanf("%d%d", &n, &m);
    bb[1] = 1, c[0] = 1;
    if(k > 1) poww(bb, n - 1, c); //c[k - 1]
    else c[k - 1] = poww_i(b[1], n - 1, p - 1);
    int exp1 = BSGS(3, m, p), u, v;
    int d = extgcd(c[k - 1], p - 1, u, v);
    if(exp1 % d)
        printf("-1\n");
    else{
        u = (u + p - 1) % (p - 1);
        u = 1ll * (exp1 / d) * u % (p - 1);
        printf("%d\n", poww_i(3, u, p));
    }
    return 0;
}

小结

这次比赛相对而言比较看重基本功，并没有什么非常难的题目（然鹅我还是只A了4题orz）。
不过这次比赛的失误比较多，先是在A和B上各贡献了一发WA，又是在F上把k次剩余看成了离散对数。。。导致排名比较难看。
总之：线上比赛要拼手速，更要拼准确度；要巩固好数学基础；掌握更好的DP姿势。