YACS-2022.4-銀組

語言: CN / TW / HK

https://www.iai.sh.cn/contest 2022.04 銀組,理論上 \(100+100+30+100\)

T1 上鎖的抽屜

題目描述

有一個抽屜櫃裡豎排了 \(n\) 只抽屜。每個抽屜有一把鎖。若要把一隻抽屜『鎖死』,就必須鎖上它自己,而且要把它的上一層抽屜也鎖上。請問有多少種上鎖的方法,可以恰好『鎖死』 \(m\) 只抽屜?

由於答案可能很大,輸出方案數模 \(10^9+7\) 的餘數。

大體思路

計數類問題顯然想到動態規劃。

一般地,設 \(f[i,j]\) 表示前 \(i\) 個抽屜『鎖死』 \(j\) 個的方案數。這樣,我們只需要對第 \(i\) 個抽屜上鎖是否影響『鎖死』的個數即可。

此時我們發現,這還取決於第 \(i-1\) 個抽屜是否上鎖。因此,我們規定 \(f[i,j,0]\) 表示前 \(i\) 個抽屜『鎖死』 \(j\) 個,且第 \(i\) 個抽屜不上鎖的方案數, \(f[i,j,1]\) 表示前 \(i\) 個抽屜『鎖死』 \(j\) 個,且第 \(i\) 個抽屜上鎖的方案數。

當第 \(i\) 個抽屜上鎖時,我們可以藉助第 \(i-1\) 個抽屜上鎖,則之前『鎖死』的個數為 \(j-1\) 個;也可能第 \(i-1\) 個抽屜不上鎖,則前 \(i-1\) 個需要『鎖死』 \(j\) 個。第 \(i\) 個抽屜不上鎖時,必然完全依靠前 \(i-1\) 個抽屜『鎖死』 \(j\) 個,由此可得狀態轉移方程:

\[f[i,j,0]=f[i-1,j,1]+f[i-1,j,0]\\ f[i,j,1]=f[i-1,j-1,1]+f[i-1,j,0]\]

其邊界條件為 \(f[1,1,1]=f[1,0,0]=1\) ,答案為 \(f[n,m,1]+f[n,m,0]\) ,注意取模。

這樣,時空複雜度為 \(O(nm)\) 。注意到 \(i\) 的決策只與 \(i-1\) 相關,可以使用滾動陣列使得空間複雜度降至 \(O(m)\)

ll n, m, f[2][maxn][2];
/*
f[i, j, 0] 表示前i個抽屜鎖死j個,i不鎖死
f[i, j, 1] ......................i鎖死

f[1,0,0]=f[1,1,1]=1
f[i,j,0]=f[i-1,j,1]+f[i-1,j,0]
f[i,j,1]=f[i-1,j-1,1]+f[i-1,j,0]
(j > 0)
*/
int main () {
	read(n); read(m);
	f[1][0][0] = f[1][1][1] = 1;
	rep(i, 2, n) {
		rep(j, 0, i) {
			f[i&1][j][0] = (f[(i-1)&1][j][1] + f[(i-1)&1][j][0]) % mod;
			f[i&1][j][1] = f[(i-1)&1][j][0];
			if(j > 0) (f[i&1][j][1] += f[(i-1)&1][j - 1][1]) %= mod;
		}
	}
	writeln((f[n&1][m][0] + f[n&1][m][1]) % mod);
	return 0;
}

T2 匹配括號(二)

題目描述

給定一個僅由 ()[] 構成的字串,若它不是匹配的,請求出最少刪去多少括號可以使它變成匹配的。匹配定義如下:

  • 空字串是匹配的;
  • 如果字串 \(s\) 是匹配的,那麼 \((s)\)\([s]\) 也是匹配的;
  • 如果字串 \(s\)\(t\) 都是匹配的,那麼 \(st\) 也是匹配的。

大體思路

原題連結 https://loj.ac/p/10150

由於匹配的括號串每一個子串都匹配,考慮區間 DP。設 \(f[i,j]\) 表示區間 \([i,j]\) 最少刪去的括號個數。邊界 \(f[i,i]=1\)

括號匹配是經典的討論邊界的區間 DP。如果 \(s_i,s_j\) 互相匹配,則有初始值 \(f[i,j]=f[i+1,j-1]\) ,否則初始為 \(\infty\) 。然後列舉分割點 \(k\in [i,j)\)\(f[i,j]=\min\{f[i,k]+f[k+1,j]\}\) 。最終答案即為 \(f[1,n]\) ,時間複雜度 \(O(n^3)\)

T3 末日生存

題目描述

小愛正在參加一個末日生存比賽,每過一天要消耗一個單位的物資,最後一天到來之前,如果她沒有物資,就輸了。遊戲一共要持續 \(d\) 天,出發前,小愛有 \(c\) 個單位的物資。

遊戲過程中有 \(n\) 次補給機會,第 \(i\) 次補給機會在第 \(x_i\) 天 ,當天可以補給 \(a_i\) 個單位的物資。

請設計一個方案,使得小愛能夠堅持到最後一天,且補給的次數最小。如果無論如何都到不了終點,輸出 Impossible

大體思路

考場上沒有思路,感覺和之前某個旅行商問題很像,但顯然不一樣。於是直接使用 \(dfs\) ,記 \(dfs(N,C)\) 表示到達第 \(N\) 個補給站時還有 \(C\) 的物資的次數,然後對第 \(N\) 個補給站是否補充物資進行討論,時間複雜度 \(O(2^n)\) ,期望得分 \(30\)

T4 狼人遊戲

題目描述

\(n\) 個人在一起玩狼人遊戲,遊戲中有一些玩家的身份是狼人,剩下玩家的身份是平民。狼人知道彼此之間的身份,而平民對其他人的身份資訊一無所知。

天亮時,每名玩家要指證另一名玩家是狼人。狼人一定會做偽證,指證某個平民為狼人,而平民可能指證某個狼人,也可能指證另一個平民。

給定每名玩家的指證物件,請分析場面上最多可能有多少名狼人?注意遊戲規定至少需要有一名平民。

大體思路

原題 [COCI2014-2015#1] MAFIJA,正好做到過。

將指認關係進行連邊, \(n\) 個節點 \(n\) 條邊形成基環樹(基環森林)。

用並查集維護環,對於每一個環,將其斷開後變為一棵樹,然後將這兩個節點 \(u,v\) 分別作為根跑樹形 DP 即可,答案累加 \(\max(f[u,0],f[v,0])\) 。動態規劃的複雜度為 \(O(n)\) ,總複雜度為 \(O(n\log n)\) ,瓶頸在於並查集。

此題由於所有點權均為 \(1\) ,還有 \(O(n)\) 的貪心做法,但由於推廣性不強,在此不介紹。

/*
f[u][0]+=max(f[v][0], f[v][1])
f[u][1] = 1 + f[v][0]
max f[u][0], f[v][0]
*/
int n, id[maxn], f[maxn][2], ans;
int tot = 1, hd[maxn], ver[maxn * 2], nxt[maxn * 2];
inline void add(int u, int v) {
	ver[++tot] = v; nxt[tot] = hd[u]; hd[u] = tot;
	ver[++tot] = u; nxt[tot] = hd[v]; hd[v] = tot;
}
PII p[maxn]; // cir
bool vis[maxn * 2];
inline void dfs(int u, int fa) {
	f[u][0] = 0, f[u][1] = 1;
	for(int i = hd[u]; i; i = nxt[i]) {
		int v = ver[i];
		if(vis[i] || vis[i ^ 1] || v == fa) continue;
		dfs(v, u);
		f[u][0] += max(f[v][0], f[v][1]);
		f[u][1] += f[v][0];
	}
}
int fa[maxn];
inline int find(int k) {
	return (k == fa[k] ? k : fa[k] = find(fa[k]));
}
int main () {
	read(n);
	rep(i, 1, n) fa[i] = i;
	rep(u, 1, n) {
		int v; read(v);
		add(u, v);
		int f1 = find(u), f2 = find(v);
		if(f1 != f2) fa[f1] = f2;
		else {
			id[++id[0]] = tot;
			p[id[0]] = {u, v};
		}
	}
	rep(i, 1, id[0]) {
		int u = p[i].first, v = p[i].second;
		vis[id[i]] = vis[id[i] ^ 1] = 1;
		dfs(u, 0);
		int tmp = f[u][0];
		dfs(v, 0);
		ans += max(tmp, f[v][0]);
		vis[id[i]] = vis[id[i] ^ 1] = 0;
	}
	writeln(ans);
	return 0;
}