526互联

10 月 16 日模拟赛总结

发布时间 2023-10-16 23:01:36作者: PikachuQAQ

Before

本文章在洛谷博客同步发布

Contest-Link

预期 \(30 + 0 + 0 + 20 = 50\)。

实际 \(30 + 0 +100+ 60 = 190\)。

挂分 \(-140\)。

rk2/totrk7，行。

看 T1，单调栈，不会，写暴力溜。看 T2，挺线段树的，但好像维护不了，写暴力溜。看 T3，不会怎么还不会啊，挺 K 的一个树形 DP，没拿暴力 30 分是最大的失误。然后就只有 1h 了，感觉今天要爆零啊。然后开 T4，啊啊这不板子题吗，怎么最简单啊，这么牛。你直接坐坐坐坐坐坐坐下！结果被坐下了，剩下 15min 还没调出来，我恼恼恼恼恼恼恼。然后本来想输出样例的，但不能放弃，然后我调调调调调调，然后是并查集写错了，看了半小时，哈哈。只剩 5min 了大样例还是错的，我急急急急急急急。哈哈。我当场感觉今天寄了啊，垫底了啊。哈哈哈哈哈哈哈。

结果非常炸裂，我 T4 过了。经典西西弗数据啊。而且初一组就我一人 AC 了。原来是我样例复制少了，最后 3min 惊险调出来了，哈哈哈哈哈哈哈。

然后就寄了。

T1

Description

给定一个排列，每一轮对于每个数，如果它左边相邻的数比它大则删除，求几轮后不会再删除数。

\(1 \le n\le 10^6\)。

Solution

这不显然的单调栈吗我考试时怎么没想出来啊。

只要不是逆序对塞进去然后答案计数即可。

考场想法：暴力。

考场寄因：暴力。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。

Code

\(\text{100pts:}\)

// 2023/10/16 PikachuQAQ

#include <iostream>

using namespace std;

const int kMaxN = 1e6 + 7;

int n, a[kMaxN], ans;
int stk[kMaxN], top;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = n, cnt; i; i--) {
        for (cnt = 0; top && stk[top] < a[i]; ) {
            top--, cnt++;
        }
        stk[++top] = a[i], ans = max(ans, cnt);
    }
    cout << ans;

    return 0;
}

T2

Description

给定 \(1\) 到 \(n\) 的数轴上每个点最多能够被覆盖的次数 \(a_i\)，以及 \(m\) 个区间，求最多可以选择几个区间。

\(1 \le n,m,a_i \le 10^5\)，\(1 \le l_i, r_i \le n\)。

Solution

可以证明，按右端点排序来覆盖是最优的。

于是我们使用线段树贪心的覆盖，能塞就塞。

时间复杂度 \(O(n\log n)\)，空间复杂度 \(O(n)\)。

Code

\(\text{100pts:}\)

// 2023/10/16 PikachuQAQ

#include <iostream>
#include <algorithm>

using namespace std;

const int kMaxN = 1e6 + 7, kMaxM = 4e6 + 7, INF = 1e9;

struct E {
    int l, r;
} a[kMaxN];

bool cmp(E x, E y) {
    return x.r < y.r;
}

int n, m, ans;
int seg[kMaxM], add[kMaxM];

int M(int l, int r) { return l + r >> 1; } 
int L(int p) { return p << 1; } 
int R(int p) { return p << 1 | 1; } 
void tag(int p, int d) { seg[p] += d, add[p] += d; } 
void pushup(int p) { seg[p] = min(seg[L(p)], seg[R(p)]); }
void pushdown(int p) { 
    tag(L(p), add[p]), tag(R(p), add[p]);
    add[p] = 0;
}

void Update(int s, int t, int l, int r, int p, int d) {
    if (s <= l && r <= t) {
        tag(p, d);
    } else {
        pushdown(p);
        if (s <= M(l, r)) {
            Update(s, t, l, M(l, r), L(p), d);
        }
        if (t >= M(l, r) + 1) {
            Update(s, t, M(l, r) + 1, r, R(p), d);
        }
        pushup(p);        
    }
}


int Query(int s, int t, int l, int r, int p) {
    int res = INF;
    if (s <= l && r <= t) {
        return seg[p];
    }
    pushdown(p);
    if (s <= M(l, r)) {
        res = min(Query(s, t, l, M(l, r), L(p)), res);
    } 
    if (t >= M(l, r) + 1) {
        res = min(res, Query(s, t, M(l, r) + 1, r, R(p)));
    }
    return res;
}


int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        Update(i, i, 1, n, 1, x);
    }
    for (int i = 1; i <= m; i++) {
        cin >> a[i].l >> a[i].r;
    }
    sort(a + 1, a + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        if (Query(a[i].l, a[i].r, 1, n, 1)) {
            ans++;
            Update(a[i].l, a[i].r, 1, n, 1, -1);
        }
    }
    cout << ans;

    return 0;
}

T3

Description

给定一棵树，对边进行黑白染色，不能有两条黑边相邻，求最多黑边数量以及对应的方案数。

\(1 \le n \le 1000\)。

Solution

有 \(f_{i,0/1}\) 表示 \(i\) 不选择或选择时的能匹配的最多点，\(g_{i,0/1}\) 表示 \(f_i\) 匹配点的方案数，\(p_i\) 表示 \(i\) 不匹配的状况下，\(j\) 匹配的方案数。

当这个点不连接时，能匹配的点自然是它儿子最多能选雨最多不选中的最大值，也就是：

\[f_{u,0}=\sum^m_{v=1} \max(f_{v,0},f_{v,1}) \]

然后我们考虑选择。对于当前的能匹配的点，我们减去重复的 \(\max(f_{v,0},f_{v,1})\)，也有可能下面的儿子直接不匹配了，所以点加上 \(f_{v,0}+1\)。也就是：

\[f_{u,1}=\max^m_{i=1}(f_{u,0} - \max(f_{v,0}, f_{v,1})+f_{v,0}+1) \]

然后我们统计方案数。我们只考虑转移合法的，从下往上转移即可。

令 \(x=[f_{v,0}\ge f_{v,1}],y=[f_{v,0}\le f_{v,1}]\)，有 \(g_{u,0}\) 转移：

\[g_{u,0}=\prod^m_{j=1}(g_{v,0} \times x + g_{v,1}) \]

然后就有了选择的 \(g_{u,1}\) 转移：

\[g_{u,1}=\dfrac{g_{u,0}}{h_j}\times g_{v,0} \]

然后 DP 数组会炸，高精度一下，就做完了。

时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。

Code

\(\text{100pts:}\)

// 2023/10/16 PikachuQAQ

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

const int kMaxN = 1007, INF = 1e9;

typedef long long ll;

struct BigInt {
    static const int BASE = 100000000, WIDTH = 8; 
    vector<ll> s;

    BigInt() {
        *this = 0;
    }

    BigInt(const int& num) {
        *this = num;
    }

    BigInt operator = (int num) {
        s.clear();
        do {
            s.push_back(num % BASE);
            num /= BASE;
        } while (num > 0);
        return *this;
    }

    BigInt operator = (const string& str) {
        s.clear();
        int x, len = (str.length() - 1) / WIDTH + 1;
        for (int i = 0; i < len; i++) {
            int end = str.length() - i * WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start, end - start).c_str(), "%lld", &x);
            s.push_back(x);
        }
        return *this;
    }
    bool operator<(const BigInt& b) {
        if (s.size() < b.s.size()) return true;
        if (s.size() > b.s.size()) return false;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] < b.s[i]) return true;
            if (s[i] > b.s[i]) return false;
        }
        return false;
    }

    bool operator >= (const BigInt& b) {
        return !(*this < b);
    }

    bool operator == (const BigInt& b) {
        if (s.size() != b.s.size()) return 0;
        for (int i = 0; i < s.size(); i++)
            if (s[i] != b.s[i]) return 0;
        return 1;
    }

    BigInt operator + (const BigInt& b) {
        BigInt c;
        c.s.clear();
        for (int i = 0, g = 0;; i++) {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = g;
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x += b.s[i];
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c;
    }

    BigInt operator - (const BigInt& b) {
        BigInt c;
        c = *this;
        for (int i = 0; i < c.s.size(); i++) {
            int tmp;
            if (i >= b.s.size())
                tmp = 0;
            else
                tmp = b.s[i];
            if (c.s[i] < tmp) {
                c.s[i + 1] -= 1;
                c.s[i] += BASE;
            }
            c.s[i] -= tmp;
        }
        while (c.s.back() == 0 && c.s.size() > 1) c.s.pop_back();
        return c;
    }

    void operator -= (const BigInt& b) {
        *this = *this - b;
    }

    BigInt operator * (const BigInt& b) {
        BigInt c;
        c.s.resize(s.size() + b.s.size());
        for (int i = 0; i < s.size(); i++)
        for (int j = 0; j < b.s.size(); j++) c.s[i + j] += s[i] * b.s[j];
        for (int i = 0; i < c.s.size() - 1; i++) {
            c.s[i + 1] += c.s[i] / BASE;
            c.s[i] %= BASE;
        }
        while (c.s.back() == 0 && c.s.size() > 1) c.s.pop_back();
        return c;
    }

    void operator *= (const BigInt& b) {
        *this = *this * b;
    }

    friend istream& operator >> (istream& input, BigInt& x) {
        string s;
        if (!(input >> s)) return input;
        x = s;
        return input;
    }

    friend ostream& operator << (ostream& output, const BigInt& x) {
        output << x.s.back();
        for (int i = x.s.size() - 2; i >= 0; i--) {
            char buf[20];
            sprintf(buf, "%08d", x.s[i]);
            for (int j = 0; j < strlen(buf); j++) output << buf[j];
        }
        return output;
    }
} mod = 2, ans;

BigInt Copy(const BigInt& b, int x) {
    BigInt t;
    t.s.resize(b.s.size() + x);
    for (int i = 0; i < b.s.size(); i++) t.s[i + x] = b.s[i];
    return t;
}

BigInt Divide(const BigInt& a, const BigInt& b, BigInt& mod) {
    BigInt c;
    c.s.resize(a.s.size() - b.s.size() + 1);
    mod = a;
    int Pow[(int)log2(BigInt::BASE) + 5];
    Pow[0] = 1;
    for (int i = 1; i <= log2(BigInt::BASE); i++) Pow[i] = Pow[i - 1] * 2;
    for (int i = c.s.size() - 1; i >= 0; i--) {
        BigInt t;
        t = Copy(b, i);
        for (int j = log2(BigInt::BASE); j >= 0; j--)
        if (mod >= t * Pow[j]) {
            c.s[i] += Pow[j];
            mod -= t * Pow[j];
        }
    }
    while (c.s.back() == 0 && c.s.size() > 1) c.s.pop_back();
    return c;
}

int n;
vector<int> a[kMaxN];
BigInt g[kMaxN][2], h[kMaxN];
ll f[kMaxN][2];

void DFS(int u, int fa) {
    BigInt res = 1;
    f[u][0] = 0, f[u][1] = -INF;
    g[u][0] = 1;
    for (int v : a[u]) {
        if (v ^ fa) {
            DFS(v, u);
            h[v] = g[v][0] * (f[v][0] >= f[v][1]) + g[v][1] * (f[v][0] <= f[v][1]);
            res *= h[v];
            f[u][0] += f[v][1] * (f[v][0] < f[v][1]) + f[v][0] * (f[v][0] < f[v][1] == 0);
        }
    }
    g[u][0] = res, f[u][1] = -INF;
    for (int v : a[u]) {
        if (v ^ fa) {
            int val = f[u][0] - max(f[v][1] - f[v][0], 0ll) + 1;
            if (f[u][1] < val) {
                f[u][1] = val;
                g[u][1] = Divide(res, h[v], mod) * g[v][0];
            } else if (f[u][1] == val) {
                g[u][1] = Divide(res, h[v], mod) * g[v][0] + g[u][1];
            }
        }
    }
}

int main() {
    for (int i = 1; i <= 1005; i++) {
        mod *= 2;
    }
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1, u, m; i <= n; i++) {
        cin >> u >> m;
        for (int j = 1, v; j <= m; j++) {
            cin >> v;
            a[u].push_back(v);
        }
    }
    DFS(1, 0);
    ans = g[1][0] * (f[1][0] >= f[1][1]) + g[1][1] * (f[1][0] <= f[1][1]);
    cout << max(f[1][0], f[1][1]) << '\n' << ans << '\n';

    return 0;
}

T4

Description

给定 \(n\) 个数之间的一些大于、小于、等于关系，关系数为 \(m\)，按照数值第一编号第二排序，求是否唯一。

多组数据。

\(0 \le n \le 10000, 0 \le m \le 20000, T \le 30\)。

Solution

很显然，当 \(a\) 比 \(b\) 大时，我们建一条从 \(a\) 到 \(b\) 的变，\(a\) 比 \(b\) 小同理。

然后这个等于处理比较麻烦，我们想到一个点数值一样，那么大小关系也是一样的，我们可以把这些互相等于的连通块缩到一个点在和其他点连边，然后进行操作。这一部分可以用并查集处理。

首先想想 no enough 怎么处理。

我们知道，当一个点的入度为零时，我们不知道还有哪些数比他更大，那么当入度为零的点数大于一时，这几个点因为没有比他们互相关系更大的了，我们判断不了他们之间的互相关系，所以这种情况就是条件缺失，并且当出度为零的点数大于一时，我们也互相判断不了这些点的大小关系，同样条件不足。这一部分可以统计缩点后的图的点入出度。

然后想想 contradiction，冲突怎么处理。

很显然，一个合法的大小关系一定是一个 DAG，不可能出现以下情况：

A > B and B > A

A > B and B > C and C > A

也就是说，不可能图中会有环。一旦有环就会冲突。这一部分可以拓扑排序处理。注意是对缩点后的图进行。

最后，以上两种情况都不是，那么就是 yes 了。

考场想法：并查集拓扑排序。

考场寄因：没寄。

时间复杂度 \(O(n+m)\)，空间复杂度 \(O(n+m)\)。

Code

\(\text{100pts:}\)

// 2023/10/16 PikachuQAQ

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int kMaxN = 10007;

int n, m, cnt1, cnt2, tot;
vector<int> g[kMaxN], a[kMaxN];
int in[kMaxN], out[kMaxN];
int fa[kMaxN], siz[kMaxN];
char laugh_my_axx_off;
bool ne, co;
queue<int> q;

int findfa(int x) {
    return (fa[x] == x) ? x : (fa[x] = findfa(fa[x]));
}

void uni(int x, int y) {
    int u = findfa(x), v = findfa(y);
    if (siz[u] > siz[v]) {
        swap(u, v);
    }
    fa[u] = v, siz[v] += siz[u];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    while (cin >> n >> m) {
        for (int i = 0; i <= n; i++) {
            fa[i] = i, siz[i] = 1;
        }
        for (int i = 0, u, v; i < m; i++) {
            cin >> u >> laugh_my_axx_off >> v;
            if (laugh_my_axx_off == '<') {
                g[v].push_back(u);
            }
            if (laugh_my_axx_off == '>') {
                g[u].push_back(v);
            }
            if (laugh_my_axx_off == '=') {
                uni(u, v);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j : g[i]) {
                a[findfa(i)].push_back(findfa(j));
                in[findfa(j)]++, out[findfa(i)]++;  
            }
        }
        for (int i = 0; i < n; i++) {
            cnt1 += (in[i] == 0 && fa[i] == i);
            cnt2 += (out[i] == 0 && fa[i] == i);
        }
        ne = (cnt1 > 1 || cnt2 > 1);
        for (int i = 0; i < n; i++) {
            if (in[i] == 0 && fa[i] == i) {
                q.push(i);
            }
        }
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int v : a[u]) {
                --in[v];
                if (in[v] == 0) {
                    q.push(v);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (in[i] > 0 && fa[i] == i) {
                co = 1;
            }
        }
        if (co) {
            cout << "contradiction\n";
        } else if (ne) {
            cout << "not enough\n";
        } else {
            cout << "yes\n";
        }
        co = ne = cnt1 = cnt2 = 0;
        for (int i = 0; i < n; i++) {
            in[i] = out[i] = 0;
            g[i].clear(), a[i].clear();
        }
    }

    return 0;
}

Summary

需要掌握的：规划时间。