2021 高階競程 Contest #5 - 題解

forbid patrn

• Task Provider: GY
• Task Setter: ys

首殺 team21_32 (00:06)

解法說明

觀察到

$n=3$ 的情況

• 100
• 110
• 111
• 000

這幾種字串不管向右 shift 幾次，都會是合法的字串
前

$2$ 種都能靠 shift 得到

$3$ 個不重複的字串，所以共有

$2\times 3+2=8$ 個字串

其中向右 shift 一次表示最右邊的字元移到最左邊

再觀察到

$n=4$ 的情況

• 1000
• 1100
• 1110
• 1111
• 0000

這幾種字串不管向右 shift 幾次，都會是合法的字串
前

$3$ 種都能靠 shift 得到

$4$ 個不重複的字串，所以共有

$3\times 4+2=14$ 個字串

依此類推不管

$n$ 為多少，總共會有

$(n-1)\cdot n+2$ 個字串

標準程式

#include<cstdio>
using namespace std;

long long n;

int main()
{
  scanf("%lld", &n);
  printf("%lld\n", n*(n-1)+2);

  return 0;
}

交友遊戲

• Task Provider: D4nnyLee
• Task Setter: D4nnyLee

首殺 team21_21 (00:41)

解法說明

因為每送一封信，寄件人跟收件人都會收到

$1$ 塊錢，因此每個人收到的錢的總數一定是偶數。
所以如果每個人的目標金額加起來是奇數的話就可以直接輸出

$-1$。

要注意到題目中沒有限制寄件人跟收件人一定要是不同人，
因此可以自己寄給自己，並且得到

$2$ 塊錢。
所以只要總和為偶數，我們就可以依序用以下的步驟達成目標：

1. 找出所有目標金額為奇數的人，將他們兩兩配成一對，並且讓其中一人寄信給另一人
2. 所有人都自己寄信給自己，直到達到目標金額

在步驟

$1$ 中，因為總和為偶數，所以目標金額為奇數的人一定有偶數個，也就代表奇數的人一定可以找到其他人跟他配。

標準程式

#include <iostream>
#include <vector>
#include <array>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> c(n);
    for (auto &ci : c)
        cin >> ci;

    array<vector<int>, 2> arr{};
    for (int i = 0; i < n; ++i)
        arr[c[i] & 1].push_back(i);

    if (arr[1].size() % 2) {
        cout << "-1\n";
        return 0;
    }

    vector<pair<int, int>> ans;
    for (int i{1}, len = arr[1].size(); i < len; i += 2)
        ans.emplace_back(arr[1][i - 1], arr[1][i]);

    for (int i{0}; i < n; ++i) {
        while (c[i] > 1) {
            ans.emplace_back(i, i);
            c[i] -= 2;
        }
    }

    cout << ans.size() << '\n';
    for (auto [u, v] : ans)
        cout << u + 1 << ' ' << v + 1 << '\n';

    return 0;
}

超時空回歸

• Task Provider: arashi87
• Task Setter: arashi87

首殺 team21_12 (01:28)

解法說明

這題是很裸的拓墣排序，唯一變化的只有需要套上優先隊列來獲取最小的編號 (不過因為

$N$ 很小，也有人暴搜 AC)。每筆輸入都會給定

$D1$ 和

$D2$，所以可以知道

$D2$ 前面至少還有一個編號，因此

$D2$ 入度加一，接者把

$M$ 筆操作都這樣做一遍就可以得到一個所有點的入度陣列。

有了入度陣列後就可以很容易地知道入度為

$0$ 的點可以隨意排列，唯一需要遵循的只有按照大小排序而已，接著排序完所有入度為

$0$ 的點後需要將所有與之相連的點的入度也都減一 (相當於

$D1$ 已經確定位置了，所以

$D2$ 可以少顧慮一個點)，所以前面輸入時也需要維護一個陣列用來確認哪些點相連，接著只需要重複上述步驟直到所有點排序完畢。

需要注意的是有很多人想試著用權重加 sort 通過，不過這是行不通的，在兩個點入度相等的時候他們還是會有先後順序，一定會有其中一個點的入度先拔完，所以行不通。

標準程式

#include <queue>
#include <stdio.h>
#include <string.h>
#define maxN 507
using namespace std;

int n, m;
int mp[maxN][maxN], in[maxN];
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
    while (~scanf("%d%d", &n, &m)) {
        memset(mp, 0, sizeof mp);
        memset(in, 0, sizeof in);
        for (int i = 1, x, y; i <= m; i++)
            scanf("%d%d", &x, &y), mp[x][y] = 1, in[y]++;
        for (int i = 1; i <= n; i++)
            if (!in[i])
                pq.push(i);
        while (!pq.empty()) {
            int tp = pq.top();
            pq.pop();
            printf("%d ", tp);
            for (int i = 1; i <= n; i++) {
                if (mp[tp][i]) {
                    in[i]--;
                    if (!in[i])
                        pq.push(i);
                }
            }
        }
        puts("");
    }
}

眼神殺 - 羔羊

• Task Provider: HDU 5115
• Task Setter: raiso

首殺 – (-:-)

解法說明

本題目的為尋找最佳決策，使用的策略為「枚舉最後一次決策」。
在區間

$[0,n-1]$ 的口試委員中，誰最後走傷害最小？在區間 的口試委員中，誰最後走傷害最小？
這就是一種 Top-Down 的思路，這樣我們需要做的就是「記憶化搜索」，避免重複計算。

在一個區間中，走的人可能有三種「最左、中間與最右」，轉移式：
將dfs(L, R) 定義成：當區間

$[L,R]$ 都離開後，受到的最小傷害值。
枚舉這個區間中最後一個走的人是誰就好了。

ans = min(ans, dfs(L+1, R)+A[L]);
ans = min(ans, dfs(L, R-1)+A[R]);
for(int i = L+1; i < R; i++) //"i" is the last one leaving.
    ans = min(ans, dfs(L, i-1)+dfs(i+1, R)+A[i]);

標準程式

#include <bits/stdc++.h>
#define Int long long
using namespace std;

vector<Int> A, B;
int n;
vector< vector< Int > > his;
vector< vector< bool > > vis;

Int dfs(int L, int R) { //[L, R] leaving
        if(vis[L][R] == 1) return his[L][R];
        vis[L][R] = 1;
        Int ans = LLONG_MAX;
        //w=1
        if(L == R) ans = A[L];

        //w>1
        if(L+1 <= R) ans = min(ans, dfs(L+1, R)+A[L]);
        if(L <= R-1) ans = min(ans, dfs(L, R-1)+A[R]);
        for(int i = L+1; i < R; i++) //"i" is the last one leaving.
                ans = min(ans, dfs(L, i-1)+dfs(i+1, R)+A[i]);

        //eye-damage
        if(L-1 >= 0) ans += B[L-1];
        if(R+1 < n) ans += B[R+1];
        return his[L][R] = ans;
}

int main() {
        cin >> n;
        A.resize(n);
        B.resize(n);
        his.assign(n, vector<Int>(n));
        vis.assign(n, vector<bool>(n, 0));
        for(auto& it: A) cin >> it;
        for(auto& it: B) cin >> it;
        Int ans = dfs(0, n-1);
        cout << ans << endl;
        return 0;
}

壞掉的電腦

• Task Provider: baluteshih
• Task Setter: leo

首殺 team21_34 (02:22)

解法說明

你可以透過對所有電腦查詢某台電腦是否為壞掉的，
例如標準程式中詢問所有人

$1$ 號是否為壞掉的，
如果是壞掉的話就可以直接輸出答案，
否則就可以對所有電腦二分搜，
並利用該電腦（即上面的

$1$ 號）來驗證區間是否存在壞掉的電腦，
因為題目保證會有壞掉的電腦，所以如果

$[l,m]$ 不存在壞掉的電腦，
則

$[m+1,r]$ 一定有壞掉的電腦，即可找出答案

標準程式

#include "lib0113.h"

int main() {
    int n, l, r, m, cnt = 0;
    n = Init();
    for(int i = 1; i <= n; i++)
        cnt += (Query(i, 1, 1) ? 1 : -1);
    if(cnt > 0)
        Fix(1);
    for(l = 1, r = n; l < r;){
        m = l + r >> 1;
        if(Query(1, l, m))
            r = m;
        else
            l = m + 1;
    }
    Fix(l);
}

推甄季

• Task Provider: XDEv11
• Task Setter: ys

首殺 – (-:-)

解法說明

我們可以把每個研究所的面試開始與結束時間當成二個事件，並用時間軸的方式儲存。

之後在每天的開始前，我們就將那天會開始開放面試的研究所加入；
在每天結束後，將那天結束開放面試的研究所移除；
並在每天的開放時段，去尋找可以面試並擁有前

$K$ 大炫耀資本的研究所。

而研究所若是以炫耀資本為觀點儲存，
在每次加入時，只要找到目前炫耀資本第

$K$ 大的研究所，並檢查是否需要替換；
而在每次移除時，則要找到目前炫耀資本第

$K+1$ 大的研究所，檢查是否補上；
這部分就是在 Range Query 時講過的 K-th one。

若移除的研究所炫耀資本為前

$K$ 大，它的炫耀資本應當比第

$K+1$ 大的研究所還大，
在移除後則由第

$K+1$ 大的研究所補上。

標準程式

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class SGT {
	int n;
	vector<long long> t;
	int left(int tv) { return tv + 1; }
	int right(int tv, int tl, int tm) { return tv + 2 * (tm - tl); }
	void modify(int p, long long x, int tv, int tl, int tr) {
		if (tl == tr - 1) t[tv] += x;
		else {
			int tm{(tl + tr) / 2};
			if (p < tm) modify(p, x, left(tv), tl, tm);
			else modify(p, x, right(tv, tl, tm), tm, tr);
			t[tv] = t[left(tv)] + t[right(tv, tl, tm)];
		}
	}
	long long query(int l, int r, int tv, int tl, int tr) {
		if (l == tl && r == tr) return t[tv];
		int tm{(tl + tr) / 2};
		if (r <= tm) return query(l, r, left(tv), tl, tm);
		else if (l >= tm) return query(l, r, right(tv, tl, tm), tm, tr);
		else return query(l, tm, left(tv), tl, tm) + query(tm, r, right(tv, tl, tm), tm, tr);
	}
public:
	explicit SGT(int _n) : n{_n}, t(2 * n - 1) {}
	void modify(int p, long long x) { modify(p, x, 0, 0, n); };
	long long query(int l, int r) { return query(l, r, 0, 0, n); }
	int ps_lower_bound(long long ps) { /* binary search on tree */
		if (ps > t[0]) return -1;

		int tv{0}, tl{0}, tr{n};
		while (tr - tl > 1) {
			int tm{(tl + tr) / 2};
			if (t[right(tv, tl, tm)] >= ps) tv = right(tv, tl, tm), tl = tm;
			else ps -= t[right(tv, tl, tm)], tv = left(tv), tr = tm;
		}
		return tl;
	}
};

void solve() {
	int D, N, K;
	cin >> D >> N >> K;
	vector<vector<int>> vb(D), ve(D);
	for (int i{0}; i < N; ++i) {
		int c, b, e;
		cin >> c >> b >> e, --b, --e;
		vb[b].push_back(c);
		ve[e].push_back(c);
	}

	SGT sgt{300001};
	long long ans{0}, cnt{0};
	for (int i{0}; i < D; ++i) {
		for (auto& x : vb[i]) {
			int kth{sgt.ps_lower_bound(K)};
			if (x > kth) {
				if (kth != -1) cnt -= kth;
				cnt += x;
			}
			sgt.modify(x, 1);
		}

		ans = max(ans, cnt);

		for (auto& x : ve[i]) {
			int kth{sgt.ps_lower_bound(K + 1)};
			if (x > kth) {
				cnt -= x;
				if (kth != -1) cnt += kth;
			}
			sgt.modify(x, -1);
		}
	}

	cout << ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t{1};
	//cin >> t;
	while (t--) solve();

	return 0;
}

國軍弟兄們，上戰場囉！Easy, Hard

• Task Provider: ICPC Taipei 2020 E
• Task Setter: raiso

Easy 首殺 audit21_05 (02:55)

Hard 首殺 – (-:-)

解法說明

我們先從最後兩步驟看這個問題，如：AAABBBA，我們可以將這些弟兄看成三段

$L(1,2,3),M(4,5,6),R(7)$，在這次的案例中，若要可以成功派出這些弟兄，

$M$為可派出，

$L$與

$R$合併後可派出。

在一般化問題後，我們可以將問題換成，若區段

$S$可派出，可能可以全派出，或是其中一段派出後，剩餘可派出，此段可能在

$S$靠左、靠右或是都不靠。
xxxxxxxxx
xxxx.....
...xxx...
.....xxxx

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
string S;
int X;

bool sand(string S) {
	for(auto it: S) if(it != S.back()) return 0;
	if(S.size() < X) return 0;
	return 1;
}

bool dfs(string S) {
	//1 part
	if(sand(S)) return 1;

	bool isok = 0;
	int n = S.size();
	//2 part
	for(int i = 1; !isok && i < n; i++) {
		//LL->[0, i-1], RR->[i, n-1]
		string LL = S.substr(0, i);
		string RR = S.substr(i, n-i);
		if(!isok && sand(LL) && dfs(RR)) isok = 1;
		if(!isok && dfs(LL) && sand(RR)) isok = 1;
	}

	//3 part
	for(int i = 1; !isok && i < n; i++) for(int j = i+1; !isok && j < n; j++) {
		//LL->[0, i-1], MM->[i, j-1], RR->[j, n-1]
		string LL = S.substr(0, i);
		string MM = S.substr(i, j-i);
		string RR = S.substr(j, n-j);
		if(!isok && sand(MM) && dfs(string(LL+RR))) isok = 1;
	}
	return isok;
}

int main() {
	cin >> S >> X;
	bool isok = dfs(S);
	cout << (isok? "Yes": "No") << endl;
}

(未完待續，之後再詳細的解釋)

標準程式

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;

string S;
int X, n;

int main() {
    cin >> S >> X, n = S.size();
    vector< pair<char, int> > A{mp(S[0], 0)};
    for(auto it: S) {
        if(it == A.back().x) A.back().y++;
        else A.pb(mp(it, 1));
    }

    n = A.size();
    vector< vector<int> > dp(n, vector<int>(n, INT_MIN)); 
    //w=1
    for(int i = 0; i < n; i++) dp[i][i] = A[i].y;
    //w=2
    for(int i = 0; i < n-1; i++) {
        if(A[i].x == A[i+1].x) dp[i][i+1] = dp[i][i] + dp[i+1][i+1];
        else if(dp[i+1][i+1] >= X) dp[i][i+1] = dp[i][i];
    }
    //w>2
    for(int w = 3; w <= n; w++) for(int L = 0; L < n-w+1; L++) {
        int R = L+w-1;
        auto& now = dp[L][R];
        //2 part
        for(int i = L+1; i <= R; i++) if(dp[L][i-1] > 0 && dp[i][R] > 0){ 
            //[L, i-1], [i, R]
            if(A[L].x == A[i].x) now = max(now, dp[L][i-1] + dp[i][R]);
            else if(dp[i][R] >= X) now = max(now, dp[L][i-1]);
        }

        //3 part
        for(int i = L+2; i <= R; i++) if(A[L].x == A[i].x && dp[L+1][i-1] >= X && dp[i][R] > 0) {
            //[L, L], [L+1, i-1], [i, R]
            now = max(now, dp[L][L]+dp[i][R]);

        }
    }
    cout << (dp[0][n-1] >= X? "Yes": "No") << endl;
    return 0;
}