2021牛客寒假算法基础集训营6

A 回文括号序列计数

根据题目描述的回文那只能0, 1

int main() {
    IOS;
    for (cin >> _; _; --_) {
        ll n; cin >> n;
        cout << (n ? 0 : 1) << '\n';
    }
    return 0;
}

B 系数

\((x^2+x+1)^n=(x^2-2x+1)^n=(x-1)^{2n} (mod \ 3)\)

然后就是一个二项式定理

int c[3][3];

ll C(int n, int m) { return m > n ? 0 : c[n][m]; }

ll lucas(ll n, ll m) { return m ? C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod : 1; }

int main() {
    IOS; c[0][0] = c[1][0] = c[1][1] = c[2][0] = c[2][2] = 1; c[2][1] = 2;
    for (cin >> _; _; --_) {
        cin >> n >> k; n <<= 1;
        ll ans = (lucas(n, k) * (n - k & 1 ? -1 : 1) % 3 + 3) % 3;
        cout << ans << '\n';
    }
    return 0;
}

C 末三位

快速幂

int qpow(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1, a = a * a % mod) if (b & 1) ans = a * ans % mod;
    return ans;
}

int main() {
    IOS;
    while (cin >> n) {
        ll ans = qpow(5, n);
        if (ans / 10 == 0) cout << "00" << ans << '\n';
        else if (ans / 100 == 0) cout << '0' << ans << '\n';
        else cout << ans << '\n';
    }
    return 0;
}

D 划数

特判 n == 2

int main() {
    IOS;
    while (cin >> n >> m) {
        int ans = 0;
        rep (i, 1, n) {
            cin >> k;
            if (k == m) { m = -1; continue; }
            ans = (ans + k) % 11;
        }
        cout << ans << '\n';
    }
    return 0;
}

E 网格

对每行/列dp一次, 算出每行/列最大值

f[i][0/1] 表示第i个的方向是 0/1 的最大价值

int a[N][N], f[N][2];

int get(int x) { return x + __builtin_popcount(x); }

int main() {
    IOS; cin >> n >> m;
    rep (i, 1, n) rep (j, 1, m) cin >> a[i][j];
    ll ans = 0;
    rep (i, 1, n) {
        memset(f, 0, sizeof f);
        rep (j, 2, m)
            f[j][0] = max(f[j - 1][1] + get(a[i][j] ^ a[i][j - 1]), f[j - 1][0]),
            f[j][1] = max(f[j - 1][0], f[j - 1][1]); 
        ans += max(f[m][0], f[m][1]);
    }
    rep (i, 1, m) {
        memset(f, 0, sizeof f);
        rep (j, 2, n)
            f[j][0] = max(f[j - 1][1] + get(a[j][i] ^ a[j - 1][i]), f[j - 1][0]),
            f[j][1] = max(f[j - 1][0], f[j - 1][1]); 
        ans += max(f[n][0], f[n][1]);
    }
    cout << ans;
    return 0;
}

F 组合数问题

打表之后用这个

ll qpow(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1, a = a * a % mod) if (b & 1) ans = ans * a % mod;
    return ans;
}

int main() {
    IOS;  cin >> n; n /= 4;
    ll ans = 0;
    if (n % 2 == 0) ans = qpow(2, 2 * n - 1) % mod;
    else ans = (mod - qpow(2, 2 * n - 1) % mod) % mod;
    ans = (ans + qpow(2, 4 * n - 2) % mod) % mod;
    cout << ans % mod;
    return 0;
}

G 机器人

跟国王硬币一个套路, 贪心排序就行了

PII a[N];
 
int main() {
    read(n, m);
    rep (i, 1, n) read(a[i].fi, a[i].se);
    sort(a + 1, a + 1 + n, [](PII& a, PII& b) { return a.se * (b.fi - 1) > b.se * (a.fi - 1); });
    __int128 ans = m;
    rep (i, 1, n)  ans = ans * a[i].fi + a[i].se;
    write(ans);
    return 0;
}

H 动态最小生成树

暴力过百万, 标算还卡常

标算线段树维护MST, 牛客神机暴力即可

struct node { int x, y, c; } a[N], b[N];
 
int n, m, _, k, cas;
int f[N];
 
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
 
void work(int l, int r) {
    int ans = 0;
    rep (i, l, r) b[i] = a[i];
    rep (i, 1, n) f[i] = i;
    sort(b + l, b + r + 1, [](node& a, node& b) { return a.c < b.c; });
    rep (i, l, r) {
        int x = find(b[i].x), y = find(b[i].y);
        if (x == y) continue;
        f[y] = x; ans += b[i].c;
    }
    int cnt = 0;
    rep (i, 1, n) if (i == f[i]) ++cnt;
    if (cnt == 1) cout << ans << '\n';
    else cout << "Impossible\n";
}
 
int main() {
    IOS; cin >> n >> m >> k;
    rep (i, 1, m) cin >> a[i].x >> a[i].y >> a[i].c;
    rep (i, 1, k) {
        int op; cin >> op;
        if (op == 1) {
            int x, y, z, t; cin >> x >> y >> z >> t;
            a[x] = { y, z, t };
        } else {
            int l, r; cin >> l >> r; work(l, r);
        }
    }
    return 0;
}

I 贪吃蛇

爆搜

int n, m, _, k, cas;
char c[N][N];
int d[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
int dist[N][N];
 
int main() {
    IOS; memset(dist, -1, sizeof(dist));
    int n, m, sx, sy, ex, ey;
    cin >> n >> m >> sx >> sy >> ex >> ey;
    rep (i, 1, n) rep (j, 1, m) cin >> c[i][j];
    queue<PII> q; dist[sx][sy] = 0; q.push({ sx, sy });
    while (q.size()) {
        int x = q.front().fi, y = q.front().se; q.pop();
        rep (i, 0, 3) {
            int X = x + d[i][0], Y = y + d[i][1];
            if (X < 1 || X > n || Y < 1 || Y > m || c[X][Y] == '#' || dist[X][Y] >= 0) continue;
            dist[X][Y] = dist[x][y] + 1;  q.push({X, Y});
        }
    }
    if (dist[ex][ey] == -1) return cout << "-1", 0;
    cout << dist[ex][ey] * 100;
    return 0;
}

J 天空之城

最小生成树

const int N = 2e5 + 5, p = 131;

struct node { int x, y; ll c; } e[N];

int n, m, _, k, cas;
int f[5005];
ll ans = 0;
unordered_map<ull, int> st;
char s[15];

ull get(char *s) {
    ull cur = 0; int sz = st.size() + 1;
    for (int i = 0; s[i]; ++i) cur = cur * p + s[i];
    if (st.count(cur)) return st[cur];
    return st[cur] = sz, sz;
}

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

bool work() {
    sort(e + 1, e + m + 1, [](node& a, node& b) { return a.c < b.c; });
    rep (i, 1, m) {
        int u = find(e[i].x), v = find(e[i].y);
        if (u == v) continue;
        f[v] = u; ans += e[i].c;
    }
    int cnt = 0;
    rep (i, 1, n) if (i == f[i]) ++cnt;
    return cnt == 1; 
}

int main() {
    IOS;
    while (cin >> n >> m) {
        rep (i, 1, n) f[i] = i; cin >> s; ans = 0;
        unordered_map<ull, int>().swap(st); get(s);
        rep (i, 1, m) { cin >> s; e[i].x = get(s); cin >> s; e[i].y = get(s); cin >> e[i].c; }
        if (!work()) { cout << "No!\n"; continue; }
        cout << ans << '\n';
    }
    return 0;
}