题解 | AtCoder Beginner Contest 447
|
10
|
0
|
ABC,Atcoder,题解

1780 字
|
28 分钟

A Seats 2

隔空坐 $n$ 个座位最多坐 $\lceil \frac{n}{2}\rceil$ 个人，比较一下即可。

void solve() {
    int n, m;
    cin >> n >> m;
    cout << ((n + 1) / 2 >= m ? "Yes" : "No") << endl;
}

B mpp

先找出现次数最多的字母出现的次数，在按位比较一下即可。

void solve() {
    string s;
    cin >> s;
    array<int, 26> freq{};
    for (auto v : s) freq[v - 'a']++;
    int mx = *max_element(all(freq));
    for (auto v : s) {
        if (freq[v - 'a'] == mx) continue;
        cout << v;
    }
    cout << endl;
}

C Insert and Erase A

先比较一下两个字符串删去 $\text{A}$ 后是否完全相等，然后用两个指针遍历一下：

  • 如果 $S[ptr1]$ 为 $\text{A}$ ，说明这个位置要删，$ptr1$ 自增。
  • 如果 $T[ptr2]$ 为 $\text{A}$ ，说明这个位置要插入，转换一下就是 $ptr2$​ 自增。

最后计算一下一边跑到末尾之后，另一边还差的数量，也是需要修改的。

void solve() {
    string s, t;
    cin >> s >> t;
    string S = "", T = "";
    for (auto v : s)
        if (v != 'A') S += v;
    for (auto v : t)
        if (v != 'A') T += v;
    if (S != T) {
        cout << -1 << endl;
        return;
    }
    int ans = 0, ptr1 = 0, ptr2 = 0;
    while (ptr1 < s.size() && ptr2 < t.size()) {
        if (s[ptr1] == t[ptr2])
            ptr1++, ptr2++;
        else if (s[ptr1] == 'A')
            ptr1++, ans++;
        else
            ptr2++, ans++;
    }
    ans += s.size() - ptr1 + t.size() - ptr2;
    cout << ans << endl;
}

D Take ABC 2

用三个队列动态维护三个字母的位置，由于 $\text{A}$ 在最左边，所以我们枚举 $\text{A}$ ，然后维护合法的 $\text{B}$ 与 $\text{C}$ 即可。

void solve() {
    string s;
    cin >> s;
    queue<int> a, b, c;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == 'A')
            a.push(i);
        else if (s[i] == 'B')
            b.push(i);
        else if (s[i] == 'C')
            c.push(i);
    }
    int ans = 0;
    while (a.size() && b.size() && c.size()) {
        auto A = a.front();
        a.pop();
        auto B = b.front();
        b.pop();
        while (b.size() && B < A) {
            B = b.front();
            b.pop();
        }
        auto C = c.front();
        c.pop();
        while (c.size() && C < B) {
            C = c.front();
            c.pop();
        }
        if (A < B && B < C) ans++;
    }
    cout << ans << endl;
}

E Divide Graph

因为边的权值是以指数递增的，所以如果一个割的方案中最大边的编号比另一个的最大边小，那么它一定是更优的，也就是说，割的选择会有字典序的特征。

所以我们逆向去枚举每一条边，如果一条边连接了两个不同的连通块，我们就将它们合并，并将连通块的数量 $-1$ 。由于题目保证原图是连通的，随着边的不断加入，连通块的数量一定会逐渐从 $n$ 减少到 1。因此，在某个特定的时刻（即加入某条边 $k$ 之前），图恰好由 $2$ 个连通块构成。因为两个连通块之间的任何不同划分都会至少切断一条编号大于 $k$ 的边，使得总代价直接飙升至少 $2^{k+1}$ 。所以将点集恰好划分为这两个连通块所对应的割必定是唯一的全局最小割。

void solve() {
    int n, m;
    cin >> n >> m;
    vector<PII> E(m + 1);
    DSU dsu(n);
    int cnt = n;
    for (int i = 1; i <= m; ++i) cin >> E[i].fi >> E[i].se;
    for (int i = m; i >= 1; --i) {
        auto [u, v] = E[i];
        if (!dsu.same(u, v)) {
            if (cnt == 2) {
                break;
            }
            dsu.merge(u, v);
            cnt--;
        }
    }
    Z ans = 0, P = 2;
    for (int i = 1; i <= m; ++i) {
        auto [u, v] = E[i];
        if (!dsu.same(u, v)) ans += P;
        P *= 2;
    }
    cout << ans << endl;
}

F Centipede Graph

问题等价于：在树中寻找一条最长的路径，使得路径的所有端点度数 $\geq 3$ ，且所有内部节点度数 $\geq 4$ 。不难想到使用树形 $\text{dp}$ 解决。

对于每个节点 $u$ ，定义 $dp[u]$ 为以 $u$ 为向下的路径的一端，且符合上述度数条件的最大合法长度。

遍历每个节点 $u$ 的所有子节点 $v$ ：

  • 如果 $deg[v]<3$：该子节点甚至不能作为任何有效点使用，其提供给父节点的路径长度 $p:=0$ 。
  • 如果 $deg[v]=3$ ：该子节点只能作为“端点”使用，它不能作为路径的内部节点。因此这条向下的路径必须在 $v$ 这里停下来，所以它能提供的长度固定为 $p:=1$ 。
  • 如果 $deg[v]\geq 4$ ：该子节点既能作为端点，也能作为内部节点。所以我们完全可以接着使用 $v$ 的最长延伸，提供的长度 $p:=dp[v]$。

有了子树的 $p$ 值：

  • 对任何 $deg[u]\geq 3$ 的节点，它自身肯定能作为某个合法路径的端点，即可以往下延伸。因此 $dp[u]=1+\max(pv)$ 。
  • 如果 $deg[u]\geq 4$ ，它不仅能做端点，还有能做一条倒 $V$ 型路径的内部中转点。因此我们可以拼接来自两个不同子树的最长路径，最大长度即为
    $$1+p_{max}+p_{submax}$$
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    vector<int> deg(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
        deg[u]++, deg[v]++;
    }

    vector<int> par(n + 1);
    vector<int> order;
    vector<bool> vis(n + 1);
    queue<int> q;

    q.push(1);
    vis[1] = 1;

    while (q.size()) {
        auto u = q.front();
        q.pop();
        order.pb(u);
        for (auto v : g[u]) {
            if (vis[v]) continue;
            vis[v] = 1;
            par[v] = u;
            q.push(v);
        }
    }
    reverse(all(order));

    int ans = 1;
    vector<int> dp(n + 1);

    for (auto u : order) {
        if (deg[u] < 3) {
            dp[u] = 0;
            continue;
        }

        int mx1 = 0, mx2 = 0;

        for (auto v : g[u]) {
            if (v == par[u]) continue;

            int p = 0;
            if (deg[v] < 3)
                p = 0;
            else if (deg[v] == 3)
                p = 1;
            else
                p = dp[v];

            if (p > mx1)
                mx2 = mx1, mx1 = p;
            else if (p > mx2)
                mx2 = p;
        }

        dp[u] = 1 + mx1;
        ans = max(ans, dp[u]);

        if (deg[u] >= 4) {
            ans = max(ans, 1 + mx1 + mx2);
        }
    }

    cout << ans << endl;
}

G Div. 1 & Div. 2

选取 6 道题，本质上是以 $i_3$ 和 $i_4$​ 为分界点。

  • 对于 $i_3$ ，我们只关心 $i_3$ 左侧的所有元素中，取出前 $2$ 大的不同类型的题目（且不能和 $i_3,i_4$ 题型相同）。
  • 对于 $i_4$ ，我们只关心 $i_4$ 右侧的所有元素中，取出前 $2$ 大的不同类型的题目（且不能和 $i_3,i_4$ 题型相同）。

因为我们要排斥掉 $K_{i_3}$ 和 $K_{i_4}$ 两个类别，为了能保底选出 $2$ 个不同类型的题目，我们在求前缀、后缀最大值时，只需维护当前前 $4$ 大不同类型的最佳分数即可。

对于每种类型 $g$（代表 $i_3$ 可能的类型），真正有竞争力的 $i_3$ 只会是那些左侧能获得的最大分数 $P$ 最大的，或者单体分数最大的。我们对每个题型仅仅抽取出排名前 $3$ 的，将这些收录进数组 $B$ 中并总体按照 $P$ 降序排列。

通过枚举 $i_4$ 并顺次遍历 $B$ 中的 $i_3$ ，如果理论上的最大极值 $P[i] + S[j]$ （ $S[j]$ 为右侧能获得的最大分数）已经 $\leq$ 我们当前的全局最优解 $ans$ ，可以直接 $break$ 终止内层循环，因为后续的 $i$ 再怎么组合也无法超越历史最高了。

constexpr ll INF = 2e18;

struct Top4 {
    ll v[4];
    int c[4];
    int siz;
};

struct TopK {
    ll val[4];
    int col[4], siz;
    vector<ll> mx;

    TopK(int n) {
        siz = 0;
        mx.assign(n + 1, -1);
    }

    void add(int c, ll v) {
        if (v <= mx[c]) return;
        mx[c] = v;

        int pos = -1;
        for (int i = 0; i < siz; ++i) {
            if (col[i] == c) {
                pos = i;
                break;
            }
        }

        if (pos != -1) {
            val[pos] = v;
            while (pos > 0 && val[pos] > val[pos - 1]) {
                swap(val[pos], val[pos - 1]);
                swap(col[pos], col[pos - 1]);
                pos--;
            }
        } else {
            if (siz < 4) {
                val[siz] = v;
                col[siz] = c;
                siz++;
                pos = siz - 1;
            } else if (v > val[3]) {
                val[3] = v;
                col[3] = c;
                pos = 3;
            } else {
                return;
            }
            while (pos > 0 && val[pos] > val[pos - 1]) {
                swap(val[pos], val[pos - 1]);
                swap(col[pos], col[pos - 1]);
                pos--;
            }
        }
    }
};

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    vector<int> k(n + 1);
    vector<vector<int>> group(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> k[i] >> a[i];
        group[k[i]].pb(i);
    }
    vector<Top4> pref(n + 1), suff(n + 1);
    vector<ll> pre(n + 1);

    TopK tkpre(n + 1);
    for (int i = 1; i <= n; ++i) {
        tkpre.add(k[i], a[i]);
        pref[i].siz = tkpre.siz;
        for (int j = 0; j < tkpre.siz; ++j) {
            pref[i].v[j] = tkpre.val[j];
            pref[i].c[j] = tkpre.col[j];
        }
    }

    TopK tksuf(n + 1);
    for (int i = n; i >= 1; --i) {
        tksuf.add(k[i], a[i]);
        suff[i].siz = tksuf.siz;
        for (int j = 0; j < tksuf.siz; ++j) {
            suff[i].v[j] = tksuf.val[j];
            suff[i].c[j] = tksuf.col[j];
        }
    }

    auto get = [&](Top4 t, int e1, int e2) -> ll {
        ll sum = 0;
        int cnt = 0;
        for (int i = 0; i < t.siz; ++i) {
            if (t.c[i] != e1 && t.c[i] != e2) {
                sum += t.v[i];
                cnt++;
                if (cnt == 2) return sum;
            }
        }
        return -INF;
    };

    vector<ll> P(n + 1), S(n + 1);
    for (int i = 1; i <= n; ++i) {
        ll v = get(pref[i - 1], k[i], -1);
        P[i] = (v == -INF) ? -INF : a[i] + v;
    }
    for (int i = 1; i <= n; ++i) {
        ll v = get(suff[i + 1], k[i], -1);
        S[i] = (v == -INF) ? -INF : a[i] + v;
    }

    vector<int> B;
    for (int g = 1; g <= n; ++g) {
        if (group[g].empty()) continue;

        vector<int> cands = group[g], keep;

        sort(all(cands), [&](int a, int b) { return P[a] > P[b]; });
        for (int k = 0; k < min<int>(3, cands.size()); ++k) {
            if (P[cands[k]] != -INF) keep.pb(cands[k]);
        }

        sort(all(cands), [&](int x, int y) { return a[x] > a[y]; });
        for (int k = 0; k < min<int>(3, cands.size()); ++k) {
            if (P[cands[k]] != -INF) keep.pb(cands[k]);
        }

        sort(all(keep));
        keep.erase(unique(all(keep)), keep.end());
        for (auto x : keep) B.pb(x);
    }

    sort(all(B), [&](int a, int b) { return P[a] > P[b]; });

    ll ans = -1;
    for (int j = 1; j <= n; ++j) {
        if (S[j] == -INF) continue;
        for (auto i : B) {
            if (i >= j || k[i] == k[j]) continue;

            if (P[i] + S[j] <= ans) break;

            ll p = get(pref[i - 1], k[i], k[j]);
            ll s = get(suff[j + 1], k[j], k[i]);

            if (p != -INF && s != -INF) {
                ans = max(ans, a[i] + p + a[j] + s);
            }
        }
    }

    cout << ans << endl;
}

自动取模

constexpr int MOD = 998244353;

template <class T>
constexpr T ksm(T a, ll b) {
    T res = 1;
    while (b) {
        if (b & 1) res *= a;
        b >>= 1;
        a *= a;
    }
    return res;
}

template <int P>
struct MInt {
    int x;
    constexpr MInt() : x() {}
    constexpr MInt(ll x) : x{norm(x % getMod())} {}
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) { Mod = Mod_; }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const { return x; }
    explicit constexpr operator int() const { return x; }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return ksm(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr istream &operator>>(istream &is, MInt &a) {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const MInt &a) { return os << a.val(); }
    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
};

template <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

using Z = MInt<MOD>;

并查集

struct DSU {
    vector<int> f, siz;

    DSU() {}
    DSU(int n) { init(n); }

    void init(int n) {
        f.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }

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

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        f[y] = x;
        siz[x] += siz[y];
    }

    bool same(int x, int y) { return find(x) == find(y); }

    int size(int x) { return siz[find(x)]; }
};
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇