T1 [Daimayuan] Collision（C++，多源最短路）

題目描述

\(siyisss\) 的王國是由 \(n\) 個村鎮(zhèn)和 \(n?1\) 條雙向道路構(gòu)成的，村鎮(zhèn)從 \(1\) 到 \(n\) 依次編號，每條雙向道路連接兩個不同的村鎮(zhèn)，使得從任意一個村鎮(zhèn)出發(fā)都可以到達任意一個村鎮(zhèn)。接下來請你回答 \(q\) 個問題，每次給出兩個整數(shù) \(c\), \(d\)，表示現(xiàn)在分別有一個人在村鎮(zhèn) \(c\),一個人在村鎮(zhèn) \(d\)，現(xiàn)在在 \(c\) 的人要用最短的時間到達村鎮(zhèn)\(d\)，在村鎮(zhèn) \(d\) 的人要以最短的時間到達村鎮(zhèn)$ c$，假設(shè)兩人同時出發(fā)，兩人的速度也是一樣的，每條雙向道路的長度也是一樣的，請問兩人相遇的時候是在某一個村鎮(zhèn)，還是在某條雙向道路上？

輸入描述

第一行輸入兩個整數(shù) \(n\), \(q\) 代表村鎮(zhèn)的數(shù)量和詢問的數(shù)量

接下來 \(n?1\) 行，每行兩個整數(shù)用來描述一條雙向道路

最后 \(q\)，每行兩個整數(shù)代表 \(c\), \(d\)

輸出描述

對于每個詢問，如果他們在某個村鎮(zhèn)相遇，請示出Town，否則輸出Road

樣例輸入1

5 2
1 2
2 3
3 4
4 5
1 3
1 5

樣例輸出1

Town
Town

樣例輸入2

9 9
2 3
5 6
4 8
8 9
4 5
3 4
1 9
3 7
7 9
2 5
2 6
4 6
2 4
5 8
7 8
3 6
5 6

樣例輸處2

Town
Road
Town
Town
Town
Town
Road
Road
Road

數(shù)據(jù)范圍

\(2≤n≤100000\)

\(1≤q≤100000\)

對于每一個詢問 \(1≤c_i<d_i≤n\)

解題思路

題意是給出一張無向連通圖，然后詢問\(q\)次，每次要求判斷\(c\),\(d\)兩人相遇的位置。

根據(jù)數(shù)據(jù)范圍，我們需要將每次詢問的時間復(fù)雜度降至\(O(1)\)或者\(O(log\ q)\)。

理解題意之后，第一個問題就是如何判斷兩人相遇的位置：

（1）如果最短路的長度為奇數(shù)，那么兩人在Road相遇；

（2）如果最短路的長度為偶數(shù)，那么兩人在Town相遇。

關(guān)于最短路的算法，我們最容易想到的是Floyd。但是\(n\in [2,100000]\)，直接\(T\)飛掉。

回顧題意：\(n\)個節(jié)點、\(n-1\)條邊、全連通。

這不就是一棵樹嘛。

那么我們要知道樹的特點：任意兩個節(jié)點之間只有一條通路。

我們只需要找出最近公共父節(jié)點（LCA），就可以得出兩個節(jié)點之間的通路長度。

采用倍增尋訪算法，時間復(fù)雜度為\(O(qlog\ q)\)，可以接受。

AC代碼如下：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string.h>
using namespace std;
const int max_n = 1e5;
const int max_expo = 32;

struct edge { int v, next; }edges[max_n * 2];
int tot = -1, heads[max_n + 1];
int dp[max_n + 1][max_expo];
int lg[max_n + 1];
int depth[max_n + 1];


void add_edge(int u, int v) {
	edges[++tot] = { v,heads[u] }; heads[u] = tot;
	edges[++tot] = { u,heads[v] }; heads[v] = tot;
}

void init(int s, int fa) {
	for (int i = 1; i < lg[depth[s]]; i++) {
		dp[s][i] = dp[dp[s][i - 1]][i - 1];
	}

	for (int i = heads[s]; i != -1; i = edges[i].next) {
		int v = edges[i].v;
		if (v != fa) {
			dp[v][0] = s;
			depth[v] = depth[s] + 1;
			init(v, s);
		}
	}
}

int lca(int x, int y) {
	if (depth[x] < depth[y]) swap(x, y);
	while (depth[x] != depth[y]) x = dp[x][lg[depth[x] - depth[y]] - 1];
	if (x == y) return x;
	for (int i = lg[depth[x]]; i >= 0; i--) {
		if (dp[x][i] != dp[y][i]) {
			x = dp[x][i];
			y = dp[y][i];
		}
	}
	return dp[x][0];
}

int main() {
	int n, q, u, v;
	//cin >> n >> q;
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= max_n; i++) {
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
	}
	memset(heads + 1, -1, sizeof(int) * n);
	for (int i = 0; i < n - 1; i++) {
		//cin >> u >> v;
		scanf("%d%d", &u, &v);
		add_edge(u, v);
	}

	dp[1][0] = 1;
	depth[1] = 1;
	init(1, 1);

	for (int i = 0; i < q; i++) {
		//cin >> u >> v;
		scanf("%d%d", &u, &v);
		int ret = lca(u, v);
		//if ((depth[ret] * 2 - depth[u] - depth[v]) % 2 == 0) cout << "Town" << endl;
		//else cout << "Road" << endl;
		if ((depth[ret] * 2 - depth[u] - depth[v]) % 2 == 0) printf("Town\n");
		else printf("Road\n");
	}
	return 0;
}

T2 [Daimayuan] 農(nóng)田劃分（C++，數(shù)學(xué)，BFS）

題目描述

約翰是一個農(nóng)場主，他的農(nóng)場有n塊田，編號從 \(1\)到 \(n\)，這 \(n\)塊田通過 \(m\)條雙向道路相連(數(shù)據(jù)保證這\(n\)塊田都是聯(lián)通的)，我們假設(shè)第\(i\)塊田會產(chǎn)生 \(2^ikg\) 的收益，現(xiàn)在約翰想把農(nóng)田的工作全部交給自己的兩個孩子，劃分方式必須滿足以下規(guī)則:

1.每一塊田都需要恰好被分給一個孩子.

2.分給兩個孩子的農(nóng)田必須是聯(lián)通的.就是說對于任意一個孩子在劃分給自己的任意一塊田，都可以不經(jīng)過另外一個孩子的田，到達自己的任意一塊田.

3.劃分給兩個孩子的收益必須盡可能的相等，如果無法相等，年長的孩子會得到大的那一份.

對于第 \(i\)塊田，如果你要把它分給年長的孩子，請輸出A,否則輸出B.

題目輸入

第一行輸入兩個整數(shù)分別代表 \(n,m\) 接下來 \(m\)行，每個兩個整數(shù)\(u,v\)，代表這兩塊農(nóng)田通過一條雙向道路直接相連，數(shù)據(jù)保證沒有重邊和自環(huán)

題目輸出

輸出一個字符串，代表答案

樣例輸入1

3 2
1 3
3 2

樣例輸出1

ABA

樣例輸入2

6 6
3 5
2 6
1 3
3 6
5 1
4 6

樣例輸出2

BABABA

數(shù)據(jù)范圍

\(2≤n≤3e5,1≤m≤3e5\)

解題思路

首先，我們要知道：

對于數(shù)列\([1,2,2^2,...,2^{n-1},2^n]\)，\(2^n\)是大于之前所有的數(shù)加和的。

利用這個性質(zhì)，因為我們要保證年長的孩子分得的土地更多，所以\(n\)號田地一定會被分給年長的孩子。

繼續(xù)利用這個性質(zhì)，因為我們又要保證劃分盡可能的相等，所以\(n-1\)號田地一定會被劃分給另外一個孩子。

這有什么用呢？

我們的具體算法是這樣的：

刪除\(n\)號田地及與其相連的所有通路，然后從\(n-1\)號田地開始\(BFS\)，所有被搜索到的田地均分給另外一個孩子，剩下的田地歸年長的孩子。

算法時間復(fù)雜度為\(O(n)\)。

最后，AC代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-477245.html

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
const int max_n = 3e5;
const int max_m = 3e5;

struct edge { int v, next; }edges[max_m * 2];
int tot = -1, heads[max_n + 1];
queue<int>q;
bool book[max_n + 1];

void add_edge(int u, int v) {
	edges[++tot] = { v,heads[u] }; heads[u] = tot;
	edges[++tot] = { u,heads[v] }; heads[v] = tot;
}

void bfs(int s) {
	q.push(s);//初始化

	//bfs主體
	while (!q.empty()) {
		int head = q.front();
		q.pop();//取出首節(jié)點

		if (book[head]) continue;
		book[head] = true;//訪問判斷

		for (int i = heads[head]; i != -1; i = edges[i].next) {//進行嘗試
			int v = edges[i].v;
			if (book[v]) continue;//重復(fù)訪問
			q.push(v);
		}
	}
}

int main() {
	int n, m, u, v;
	cin >> n >> m;
	memset(heads + 1, -1, sizeof(int) * n);
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		if (u == n || v == n) continue;//邏輯刪除
		add_edge(u, v);
	}
	bfs(n - 1);
	for (int i = 1; i <= n; i++) {
		if (book[i]) cout << 'B';
		else cout << 'A';
	}
	return 0;
}

T3 [Daimayuan] 三段式（C++，數(shù)組前綴和）

有一個長度為\(n\)的序列，現(xiàn)在我們想把它切割成三段(每一段都是連續(xù)的），使得每一段的元素總和都相同，請問有多少種不同的切割方法

輸入描述

第一行給出一個數(shù)\(n\)，(\(1≤n≤10^5\))

第二行給出序列\(a_1\)，\(a_2\)，\(a_3\)，...，\(a_n\)，(\(|a_i|≤10^5\))

輸出描述

輸出一個數(shù)表示有多少種不同的切割方法

樣例輸入

4
1 2 3 3

樣例輸出

1

樣例解釋

可以將它分成第一組\(1\)，\(2\)，第二組\(3\)，第三組\(3\)

解題思路

根據(jù)題意，很容易得到下面的公式：

要滿足題意有兩個前提條件（特殊判定）：

（1）\(sum\ \%\ 3==0\)；

（2）\(n\ge3\)。

if (n < 3 || sum % 3 != 0) {
    cout << 0 << endl;
    return 0;
}

然后我們來尋找可能的分割方式。

如果有多于\(1\)種的分割方法，那么一定存在子段和為\(0\)。

與其去找子段和為\(0\)的部分，不如轉(zhuǎn)化思維，使用前綴和的概念（經(jīng)常用于連續(xù)區(qū)間和問題）。

這樣我們就只需要尋找前綴和同為\(\frac13sum\)的部分了。

然后具體問題具體分析，因為題目中只要求分割為三段，所以我們直接找出前后兩段\(\frac13sum\)即可。

注意，至少要為中間的\(\frac13sum\)預(yù)留一個元素的位置。

long long ans = 0;
for (int i = 1; i <= n - 1; i++) {
	if (pre[i] == subsum) {
		ans += tail_counter[i + 2];
	}
}

其中tail_counter中的元素意義為：\(i\)位置及其之后有多少個后綴和為\(\frac13sum\)。

最后，AC代碼如下：

#include <iostream>
using namespace std;
const int max_n = 1e5;

long long arr[max_n + 1], pre[max_n + 1], tail[max_n + 2];
long long tail_counter[max_n + 1];

int main() {
	int n;
	long long sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		sum += arr[i];
	}

	if (n < 3 || sum % 3 != 0) {
		cout << 0 << endl;
		return 0;
	}
	long long subsum = sum / 3;
	for (int i = 1; i <= n; i++) {
		pre[i] = arr[i] + pre[i - 1];
	}
	for (int i = n; i >= 1; i--) {
		tail[i] = arr[i] + tail[i + 1];
		tail_counter[i] = tail_counter[i + 1];
		if (tail[i] == subsum) tail_counter[i]++;
	}
	long long ans = 0;
	for (int i = 1; i <= n - 1; i++) {
		if (pre[i] == subsum) {
			ans += tail_counter[i + 2];
		}
	}
	cout << ans << endl;
	return 0;
}

T4 [Daimayuan] 模擬輸出受限制的雙端隊列（C++，模擬）

給你一個輸出受限的雙端隊列，限制輸出的雙端隊列即可以從一端插入元素，彈出元素，但是另一端只可以插入不可以刪除元素。即每次你可以執(zhí)行以下三種操作的其中一種：

1. 在左邊壓入一個字符
2. 在右邊壓入一個字符
3. 彈出最左邊的字符

現(xiàn)在給你 \(n\) 個字符作為隊列的輸入，請問最多有多少可能的出隊次序，并按字典序打印這些出隊次序。

輸入格式

第一行一個數(shù) \(n\)，表示輸入的長度

第二行一個長度為 \(n\) 的字符串

輸出格式

第一行一個整數(shù) \(k\)，表示可能的出隊方案數(shù)

下面 \(k\) 行，按字典序輸出每種出隊方案

樣例輸入

3
123

樣例輸出

6
123
132
213
231
312
321

數(shù)據(jù)規(guī)模

對于全部數(shù)據(jù)保證 \(1≤n≤7\)。

解題思路

雖然題目說是模擬，但是我們不嘗試一下別的方法肯定不會甘心的，所以嘗試理解序列滿足的規(guī)則。

以樣例輸入為例子，我們留出三個位置\(□□□\)。

考慮一種簡單的情況，我們在所有元素入隊之后再進行出隊操作，那么一下邏輯成立：

首先對于\(a_1\)，我們可以任意指定它的位置；

然后對于\(a_2\)，因為\(a_1\)的位置已經(jīng)確定了，\(a_2\)必須在\(a_1\)的前方或者\(a_1\)的后方，其位置選擇受限；

同理可知\(a_3\)位置選擇同樣受限。

似乎并沒有可以用來優(yōu)化代碼的規(guī)律存在，所以我們還是老老實實回去模擬。

模擬雙端隊列采用STL提供的deque容器，由于搜索的結(jié)果存在重復(fù)，采用set存儲結(jié)果去重（同時set會自動將結(jié)果按字典序排序）。

#include <iostream>
#include <deque>
#include <set>
using namespace std;
const int max_n = 7;

string in_str;
int n;
set<string>ans;

采用dfs搜索可能的出隊方案：

void dfs(int step, deque<char>d, string str) {//dfs狀態(tài)
	//終止條件
	
	//dfs主體
	//返回后操作
}

接下來我們對dfs代碼功能進行實現(xiàn)。

實現(xiàn)具體的代碼之前我們需要知道每一步有幾種可能的操作：

1）在首部插入一個元素；

d.push_front(in_str[step]);
dfs(step + 1, d, str);
d.pop_front();

2）在尾部插入一個元素；

d.push_back(in_str[step]);
dfs(step + 1, d, str);
d.pop_back();

3）出隊一個元素；

while (!d.empty()) {
	str += d.front(); d.pop_front();
	//在首部插入一個元素
	d.push_front(in_str[step]);
	dfs(step + 1, d, str);
	d.pop_front();
	//在尾部插入一個元素
	d.push_back(in_str[step]);
	dfs(step + 1, d, str);
	d.pop_back();
}

以上步驟實現(xiàn)完后，終止條件顯而易見：

if (step == n) {
	while (!str.empty()) {
		str += d.front(); d.pop_front();
		ans.insert(str);
	}
	return;
}

dfs完整代碼如下：

void dfs(int step, deque<char>d, string str) {//dfs狀態(tài)
	//終止條件
	if (step == n) {
		while (!str.empty()) {
			str += d.front(); d.pop_front();
			ans.insert(str);
		}
		return;
	}
	//dfs主體
	//在首部插入一個元素
	d.push_front(in_str[step]);
    dfs(step + 1, d, str);
    d.pop_front();//返回后操作
    //在尾部插入一個元素
    d.push_back(in_str[step]);
    dfs(step + 1, d, str);
    d.pop_back();//返回后操作
    //出隊一個元素
    while (!d.empty()) {
        str += d.front(); d.pop_front();
        //在首部插入一個元素
        d.push_front(in_str[step]);
        dfs(step + 1, d, str);
        d.pop_front();//返回后操作
        //在尾部插入一個元素
        d.push_back(in_str[step]);
        dfs(step + 1, d, str);
        d.pop_back();//返回后操作
    }
}

最后，AC代碼如下：

#include<iostream>
#include <set>
#include <deque>
using namespace std;
const int max_n = 7;

int n;
string in_str;
set<string>ans;

void dfs(int step, deque<char>d, string str) {//dfs狀態(tài)
	//終止條件
	if (step == n) {
		while (!d.empty()) {
			str += d.front(); d.pop_front();
		}
		ans.insert(str);
		return;
	}
	//dfs主體
	//在首部插入一個元素
	d.push_front(in_str[step]);
	dfs(step + 1, d, str);
	d.pop_front();//返回后操作
	//在尾部插入一個元素
	d.push_back(in_str[step]);
	dfs(step + 1, d, str);
	d.pop_back();//返回后操作
	//出隊一個元素
	while (!d.empty()) {
		str += d.front(); d.pop_front();
		//在首部插入一個元素
		d.push_front(in_str[step]);
		dfs(step + 1, d, str);
		d.pop_front();//返回后操作
		//在尾部插入一個元素
		d.push_back(in_str[step]);
		dfs(step + 1, d, str);
		d.pop_back();//返回后操作
	}
}

int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	deque<char>d;
	cin >> n;
	cin >> in_str;
	dfs(0, d, "");
	cout << ans.size() << endl;
	for (auto iter : ans) cout << iter << endl;
	return 0;
}

T5 [Daimayuan] 簡單差分（C++，線段樹）

給定一個長度為 \(n\) 數(shù)組 \(A\)，執(zhí)行以下操作 \(m\) 次：

選擇一段區(qū)間 \([l,r]\)，將區(qū)間中所有的數(shù)加上整數(shù) \(x\)。

操作完成后回答 \(k\) 個問題：

每個問題給定一段區(qū)間 \([l,r]\)，輸出區(qū)間中所有數(shù)的和。

輸入格式

第一行三個正整數(shù) \(n,m,k\)。

接下來一行 \(n\) 個數(shù)，表示數(shù)組 \(A\)。

接下來 \(m\) 行，每行輸入三個整數(shù) \(l,r,x\)。

接下來 \(k\) 行，每行輸入兩個整數(shù) \(l,r\)。

輸出格式

輸出 \(k\) 行，每行一個數(shù)表示對應(yīng)問題的和。

樣例輸入

10 1 1
1 2 3 4 5 6 7 8 9 10
5 8 1
8 9

樣例輸出

18

數(shù)據(jù)規(guī)模

對于全部數(shù)據(jù)，保證 \(1≤n≤2×10^5\)，\(1≤m,k≤10^5\)，\(|x|≤10^5\)。

解題思路

線段樹模板題，不做過多解釋。

不了解線段樹的可以看一下這個dalao的博客：線段樹詳解 - Xenny - 博客園。

AC代碼如下：

#include <iostream>
using namespace std;
const int max_n = 2e5;
const int max_m = 1e5;
const int max_k = 1e5;
const int max_x = 1e5;

long long tree[max_n * 4 + 1], arr[max_n + 1];
long long lazy_tags[max_n * 4 + 1];

void build_tree(int idx, int l, int r) {
	if (l == r) {
		tree[idx] = arr[l];
		return;
	}

	int m = l + r >> 1;
	build_tree(idx << 1, l, m);
	build_tree((idx << 1) + 1, m + 1, r);
	tree[idx] = tree[idx << 1] + tree[(idx << 1) + 1];
}

void push_down(int idx, int l, int r) {
	if (lazy_tags[idx]) {
		int m = l + r >> 1;
		lazy_tags[idx << 1] += lazy_tags[idx];
		tree[idx << 1] += lazy_tags[idx] * (long long)(m - l + 1);
		lazy_tags[(idx << 1) + 1] += lazy_tags[idx];
		tree[(idx << 1) + 1] += lazy_tags[idx] * (long long)(r - m);
		lazy_tags[idx] = 0;
	}
}

void update(int idx, int l, int r, int L, int R, long long val) {
	if (L <= l && r <= R) {
		tree[idx] += (long long)(r - l + 1) * val;
		lazy_tags[idx] += val;
		return;
	}
	push_down(idx, l, r);
	int m = l + r >> 1;
	if (L <= m) update(idx << 1, l, m, L, R, val);
	if (R >= m + 1) update((idx << 1) + 1, m + 1, r, L, R, val);
	tree[idx] = tree[idx << 1] + tree[(idx << 1) + 1];
}

long long query(int idx, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		return tree[idx];
	}
	push_down(idx, l, r);
	int m = l + r >> 1;
	long long sum = 0;
	if (L <= m) sum += query(idx << 1, l, m, L, R);
	if (R >= m + 1) sum += query((idx << 1) + 1, m + 1, r, L, R);
	return sum;
}

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	build_tree(1, 1, n);
	int l, r, x;
	for (int i = 0; i < m; i++) {
		cin >> l >> r >> x;
		update(1, 1, n, l, r, x);
	}
	for (int i = 0; i < k; i++) {
		cin >> l >> r;
		cout << query(1, 1, n, l, r) << endl;
	}
	return 0;
}

T6 [Daimayuan] 非遞減的01序列（C++，前綴和）

題面

\(huaji\)有一個 01 序列，每次可以對其中的某一位取反（\(0\)變\(1\)，\(1\)變\(0\)）

求最少翻轉(zhuǎn)其中的幾位可以使得該序列變?yōu)?strong>非遞減序列

輸入格式

第一行輸入一個整數(shù) \(n\) (\(1≤n≤10^6\))

第二行輸入一個長度為 \(n\) 的且僅包含 0 和 1 的字符串

輸出格式

輸出一個整數(shù)，為該序列變?yōu)榉沁f減序列的最少操作次數(shù)

輸入樣例

6
010110

輸出樣例

2

解題思路

其實題意描述有一點問題，求的應(yīng)該是將該序列變?yōu)閱握{(diào)不減的01序列（因為沒有單調(diào)性其實也是非遞減）。

我們的目標具體來說就是選定某個位置，之前的均為0，之后的均為1，同時保證與原序列相似性最高。

根據(jù)這個目標，我們只需要遍歷每一個可能的位置，選出其中需要操作次數(shù)最少的就可以了。

問題在于如何快速獲取操作次數(shù)。

因為只有兩種元素：0和1。所以我們只需要知道其中一種的數(shù)量，剩下的都是另外一種。

那么采用前綴和的概念，累計指定位置前\(0\)的數(shù)量。

//首元素特殊處理
if (str[0] == '0') zero_counter[0] = 1;
else one_counter[0] = 1;

for (int i = 1; i < len; i++) {
	zero_counter[i] = zero_counter[i - 1];
	if (str[i] == '0') zero_counter[i]++;
}

然后遍歷每一個位置即可：

int ans = zero_counter[len - 1];//目標序列沒有0
for (int i = 0; i < len; i++) {
	ans = min(ans, (i + 1 - zero_counter[i]) + (zero_counter[len - 1] - zero_counter[i]));
}

最后，AC代碼如下：

#include <iostream>
using namespace std;
const int max_len = 1e6;

int zero_counter[max_len];

int main() {
	int n;
	cin >> n;
	string str;
	cin >> str;
	int len = str.size();
	if (str[0] == '0') zero_counter[0] = 1;
	for (int i = 1; i < len; i++) {
		zero_counter[i] = zero_counter[i - 1];
		if (str[i] == '0') zero_counter[i]++;
	}
	int ans = zero_counter[len - 1];//目標序列沒有0
	for (int i = 0; i < len; i++) {
		ans = min(ans, (i + 1 - zero_counter[i]) + (zero_counter[len - 1] - zero_counter[i]));
	}
	cout << ans << endl;
	return 0;
}

T7 [Daimayuan] 數(shù)學(xué)（C++，最大公約數(shù)）

給定整數(shù) \(n\)，胖教授想將\(1～n\)這\(n\)個數(shù)字分成兩組，每一組至少有一個數(shù)，并且使得兩組數(shù)字的和的最大公約數(shù)最大，請輸出最大的最大公約數(shù)。

輸入格式

一行一個整數(shù)\(n\)。

輸出格式

輸出一行一個整數(shù)表示答案。

樣例輸入

6

樣例輸出

7

數(shù)據(jù)規(guī)模

對于\(20\%\)的數(shù)據(jù)，保證\(n≤100\)。

對于\(100\%\)的數(shù)據(jù)，保證\(n≤10^9\)。

解題思路

我們從最大公約數(shù)的概念入手：

若\(x\)和\(y\)的最大公約數(shù)是\(z\)，那么\(x\)和\(y\)都是\(z\)的倍數(shù)。

那么我們所要尋找的最大公約數(shù)一定能夠整除\(sum=(1+n)*n/2\)。

要找到最大的最大公約數(shù)，我們就只需要找到一個最小的數(shù)，使其能整除\(sum\)即可。

AC代碼如下：

#include<iostream>
using namespace std;

int main() {
	long long n;
	cin >> n;
	long long sum = (n + 1) * n / 2;
	for (long long i = 2; i * i <= sum; i++)
		if (sum % i == 0) {
			printf("%lld", sum / i);
			break;
		}
	return 0;
}

T8 [Daimayuan] pSort（C++，強連通分量）

題目描述

有一個由 \(n\) 個元素組成的序列 \(a_1,a_2,…,a_n\)；最初，序列中的每個元素滿足 \(a_i=i\)。

對于每次操作，你可以交換序列中第 \(i\) 個元素和第 \(j\) 個元素當(dāng)且僅當(dāng)滿足 \(|i?j|=d_i\)。

題目給出序列 \(b_1,b_2,…,b_n\) 和 \(d_1,d_2,…,d_n\)，詢問是否可以通過若干次交換，使得序列 \(a\) 和序列 \(b\) 完全相同。

輸入格式

第 \(1\) 行一個正整數(shù) \(n\)，含義如上。

第 \(2\) 行 \(n\) 個正整數(shù)表示 \(b_1,b_2,…,b_n\)。

第 \(3\) 行 \(n\) 個正整數(shù)表示 \(d_1,d_2,…,d_n\)。

輸出格式

若能，輸出 YES；否則輸出 NO。

輸入 #1

7
4 2 5 1 3 7 6
4 6 6 1 6 6 1

輸出 #1

YES

輸入 #2

7
4 3 5 1 2 7 6
4 6 6 1 6 6 1

輸出 #2

NO

數(shù)據(jù)范圍

\(1≤n,d_i≤100\)。保證序列 \(b\) 中元素不重復(fù)。

補充說明

原題：CF28B pSort | 洛谷

解題思路

對于題意的理解如下：

if (abs(i - j) == d[i] || abs(i - j) == d[j]) {
	/* i,j是可交換的 */
}

那么我們可以把\(a\)序列抽象為一張無向圖，可交換關(guān)系為無向邊。

則強連通分量之內(nèi)的節(jié)點可以隨意交換。

也就是說，如果需要交換所有節(jié)點都在同一個強連通分量之中，就輸出YES；

反之，如果需要交換的任意一對節(jié)點不在一個強連通分量中，就輸出NO。

接下來實現(xiàn)代碼：

我們采用染色法標記不同的強連通分量，用廣度優(yōu)先搜索對整張圖進行染色，時間復(fù)雜度為\(O(n^2)\)。

void bfs(int bg) {
	color++;
	q.push(bg);

	int head, next, i;
	while (!q.empty()) {
		head = q.front();
		q.pop();

		if (book[head]) continue;
		book[head] = true;
		colors[head] = color;

		for (i = 1; i <= n; i++) {
			if (i == head) continue;
			next = abs(head - i);
			if (next == ds[head] || next == ds[i]) q.push(i);
		}
	}
}

我們需要遍歷每一個節(jié)點進行嘗試，所以算法總時間復(fù)雜度為\(O(n^3)\)，可以接受。

for (i = 1; i <= n; i++) {
	if (!colors[i]) bfs(i);
}

最后，AC代碼如下：

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
const int max_n = 100;

int bs[max_n], ds[max_n];
int colors[max_n], color = 0;
queue<int>q;
int book[max_n];
int n;

void bfs(int bg) {
	color++;
	q.push(bg);

	int head, next, i;
	while (!q.empty()) {
		head = q.front();
		q.pop();

		if (book[head]) continue;
		book[head] = true;
		colors[head] = color;

		for (i = 1; i <= n; i++) {
			if (i == head) continue;
			next = abs(head - i);
			if (next == ds[head] || next == ds[i]) q.push(i);
		}
	}
}

int main() {
	cin >> n;
	int i;
	for (i = 1; i <= n; i++) cin >> bs[i];
	for (i = 1; i <= n; i++) cin >> ds[i];
	for (i = 1; i <= n; i++) {
		if (!colors[i]) bfs(i);
	}

	for (i = 1; i <= n; i++) {
		if (colors[bs[i]] != colors[i]) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}

T9 [Daimayuan] Owwwwwwwwwww...f（C++，強連通分量）

小\(A\)地盤上的所有人被從 \(1\) 到 \(n\) 編號，每個人都有自己傳話的對象，第 \(i\) 個人對第 \(a_i\)個人傳話。 有一天，小\(A\)在宮殿的頂部大聲喊著\(Owf\)，于是一個有趣的游戲在小\(A\)的地盤上開始了。

規(guī)則如下：

該游戲有許多輪，每個人都會開始一輪游戲。如果編號為 \(x\) 的人想要開始一輪游戲，他會對第 \(a_x\)個人說"\(Oww...wwf\)"（有 \(t\) 個\(w\)）。如果 \(t>1\)，第 \(a_x\)個人就會對第 \(a_{ax}\)個人說"\(Oww...wwf\)"（有 \(t?1\) 個\(w\)）。直到有人聽到"\(Owf\)"（\(t=1\)），這個人就是這一輪的\(Joon\)。不存在同時進行兩輪游戲的情況。 為了使游戲更有意思，小\(A\)有一個邪惡的計劃。他想找到最小的 \(t\)（\(t≥1\)）使得對于每個人 \(x\) 當(dāng)?shù)?\(x\) 個人開始的一局游戲使 \(y\) 成為了 \(Joon\) ，也使得由 \(y\) 開始的一局游戲 \(x\) 成為 \(Joon\) 。請為小\(A\)找這個最小的 \(t\)。 注意：可能有的人傳話對象是自己。

輸入格式：

第一行輸入一個 \(n\) (\(1≤n≤150\))，表示小A地盤上的人數(shù)。

第二行輸入\(a_1\)，\(a_2\)，\(a_3\)，...\(a_n\)，第 \(i\) 個數(shù)表示第 \(i\) 個人傳話的對象 \(a_i\)。

輸出格式：

輸出最小的 \(t\)，如果沒有請輸出 \(?1\)。

樣例輸入:

4
2 3 1 4

樣例輸出：

3

解題思路：

把題中序列抽象為一張有向圖，有\(n\)個節(jié)點、\(n\)條有向邊\(<i,a_i>\)。

如果能夠達成題中所述的雙向傳話，兩個人必須在一個環(huán)中。

如果環(huán)的長度為偶數(shù)，那么這個環(huán)的傳話次數(shù)為其長度一半；

如果環(huán)的長度為奇數(shù)，那么這個環(huán)的傳話次數(shù)為其長度。

我們需要做的就是統(tǒng)計每一個環(huán)的傳話次數(shù)，然后計算最小公倍數(shù)即可。

很簡單對吧qwq？

那么現(xiàn)在來實現(xiàn)代碼。

首先是搜索環(huán)的長度：

void dfs(int bg) {
	int next = as[bg], sum = 1;
	book[bg] = true;
	while (next != bg) {
		if (book[next]) {
			fail = true;
			return;
		}
		sum++;
		book[next] = true;
		next = as[next];
	}
	if (sum % 2 == 0) ans.push_back(sum / 2);
	else ans.push_back(sum);
}

然后計算所有ans的最小公倍數(shù)：

long long ret = 1;
for (auto iter : ans) {
	ret = lcm((long long)(iter), ret);
}
cout << ret << endl;

后排提醒：/* 十年OI一場空，不開long long見祖宗 */。

最后，AC代碼如下：

#include <iostream>
#include <vector>
using namespace std;
const int max_n = 150;

int as[max_n + 1];
bool book[max_n], fail = false;
vector<int>ans;

void dfs(int bg) {
	int next = as[bg], sum = 1;
	book[bg] = true;
	while (next != bg) {
		if (book[next]) {
			fail = true;
			return;
		}
		sum++;
		book[next] = true;
		next = as[next];
	}
	if (sum % 2 == 0) ans.push_back(sum / 2);
	else ans.push_back(sum);
}

long long gcd(long long x, long long y) {
	long long t;
	while (y != 0) {
		t = x % y;
		x = y;
		y = t;
	}
	return x;
}

long long lcm(long long x, long long y) {
	long long ret = gcd(x, y);
	return x * y / ret;
}

int main() {
	int n, u, v;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> as[i];
	}
	for (int i = 1; !fail && i <= n; i++) {
		if (!book[i]) {
			dfs(i);
		}
	}
	if (fail) {
		cout << -1 << endl;
		return 0;
	}
	long long ret = 1;
	for (auto iter : ans) {
		ret = lcm((long long)(iter), ret);
	}
	cout << ret << endl;
	return 0;
}

T10 [Daimayuan] 樹（C++，動態(tài)規(guī)劃，01背包方案數(shù)）

有一棵 \(n\) 個節(jié)點的以 \(1\) 號點為根的有根樹?，F(xiàn)在可以對這棵樹進行若干次操作，每一次操作可以選擇樹上的一個點然后刪掉連接這個點和它的兒子的所有邊。

現(xiàn)在我們想知道對于每一個 \(k\) (\(1≤k≤n\))，最少需要多少次操作能讓圖中恰好存在 \(k\) 個聯(lián)通塊。

輸入格式

第一行輸入一個正整數(shù) \(n\)。

第二行輸入 \(n?1\) 個整數(shù) \(f_1,f_2,...,f_{n?1}\)，\(f_i\) 表示 \(i+1\) 號點的父親，保證 \(1≤f_i≤i\)。

輸出格式

輸出 \(n\) 個整數(shù)，第 \(i\) 個數(shù)表示 \(k=i\) 時的答案，如果無法讓圖中恰好存在 \(i\) 個聯(lián)通塊，則輸出 -1。

樣例輸入1

6
1 2 1 1 2

樣例輸出1

0 -1 1 1 -1 2

數(shù)據(jù)規(guī)模

共 \(10\) 個測試點。

測試點 \(1,2,3\) 滿足 \(n≤20\)。

測試點 \(4,5,6\) 滿足 \(n≤100\)。

對于所有數(shù)據(jù)，滿足 \(1≤n≤3000\)。

解題思路

對于一棵樹來說，刪去任意一條邊都會使連通塊數(shù)目\(+1\)。

那么要判斷能否得到\(k\)個連通塊，我們只需要判斷能否恰好刪去\(k-1\)條邊。

題目要求操作為：刪除一個節(jié)點與子節(jié)點之間的所有邊。

那么統(tǒng)計每個節(jié)點的子節(jié)點數(shù)目，然后就變?yōu)榱?strong>01背包可行性問題：

每一個節(jié)點都是一個物品，問能否恰好裝滿容量為\(k-1\)的背包？

for (int i = 1; i <= n; i++) {//嘗試每一個物品
	for (int j = 0; j < n; j++) {//嘗試新的重量組合
		if (j - items[i] >= 0)
        	ans[i][j] = ans[i - 1][j] || ans[i - 1][j - items[i]];
    	else
            ans[i][j] = ans[i - 1][j];
    }
}

以上我們只是檢驗了可行性問題，但是題目中還有另外一個要求：操作次數(shù)最少。

因為在物品組合中沒有先后順序，所以我們可以通過物品組合中的物品數(shù)量來確定操作次數(shù)。

只有新的操作次數(shù)小于舊的操作次數(shù)的時候，我們才進行更新。

for (int i = 1; i <= n; i++) {//嘗試每一個物品
	for (int j = 0; j < n; j++) {//嘗試新的重量組合
        if (j - items[i] >= 0 && ans[i - 1][j] && ans[i - 1][j - items[i]])
        	ans[i][j] = min(ans[i - 1][j], ans[i - 1][j - items[i]] + 1);
    	else if (ans[i - 1][j])
            ans[i][j] = ans[i - 1][j];
        else if (j - items[i] >= 0 && ans[i - 1][j - items[i]])
            ans[i][j] = ans[i - 1][j - items[i]];
    }
}

注：1）以上代碼段中，ans中元素的含義發(fā)生了變化：可行/不可行 -> 物品數(shù)量；

2）為了與不存在的組合（ans[i][j] = 0）相區(qū)分，我們?yōu)樗写嬖诘慕M合物品數(shù)量添加偏置bias，也就是說，物品數(shù)量 = ans[i][j] - bias。

以上代碼的空間復(fù)雜度、時間復(fù)雜度均可以接受，可以AC，接下來是優(yōu)化部分qwq。

因為嫌棄這個算法的空間復(fù)雜度，所以我們對其進行優(yōu)化，壓縮到二維數(shù)組：

for (int i = 1; i <= n; i++) {//嘗試每一個物品
	for (int j = 0; j < n; j++) {//嘗試新的重量組合
        if (j - items[i] >= 0 && ans[(i - 1) % 2][j] && ans[(i - 1) % 2][j - items[i]])
        	ans[i % 2][j] = min(ans[(i - 1) % 2][j], ans[(i - 1) % 2][j - items[i]] + 1);
    	else if (ans[(i - 1) % 2][j])
            ans[i % 2][j] = ans[(i - 1) % 2][j];
        else if (j - items[i] >= 0 && ans[(i - 1) % 2][j - items[i]])
            ans[i % 2][j] = ans[(i - 1) % 2][j - items[i]];
    }
}

還是嫌棄？繼續(xù)壓，壓縮到一維數(shù)組：

for (int i = 1; i <= n; i++) {//嘗試每一個物品
	for (int j = n; j >= items[i]; j--) {//嘗試新的重量組合
		if (j - items[i] >= 0 && ans[j] && ans[j - items[i]])
            ans[j] = min(ans[j], ans[j - items[i]] + 1);
		else if (ans[j]) ans[j] = ans[j];
        else if (j - items[i] >= 0 && ans[j - items[i]])
            ans[j] = ans[j - items[i]] + 1;
	}
}

然后我們刪除一些無用的部分：

for (int i = 1; i <= n; i++) {//嘗試每一個物品
	for (int j = n; j >= items[i]; j--) {//嘗試新的重量組合
		if (ans[j] && ans[j - items[i]]) ans[j] = min(ans[j], ans[j - items[i]] + 1);
		else if (ans[j - items[i]]) ans[j] = ans[j - items[i]] + 1;
	}
}

嗯，好看多了qwq。

最后，AC代碼如下：

#include <iostream>
using namespace std;
const int max_n = 3000;

int ans[max_n + 1], n;
int items[max_n + 1];


int main() {
	cin >> n;
	int fa;
	for (int i = 1; i < n; i++) {
		cin >> fa;
		items[fa]++;
	}

	int bias = 1;
	ans[0] = bias;
	for (int i = 1; i <= n; i++) {//嘗試每一個物品
		for (int j = n; j >= items[i]; j--) {//嘗試新的重量組合
			if (ans[j] && ans[j - items[i]]) ans[j] = min(ans[j], ans[j - items[i]] + 1);
			else if (ans[j - items[i]]) ans[j] = ans[j - items[i]] + 1;
		}
	}

	cout << 0;
	for (int i = 2; i <= n; i++) {
		cout << ' ' << ans[i - 1] - bias;
	}
	return 0;
}

到了這里，關(guān)于[Week 20]每日一題（C++，圖論，數(shù)學(xué)，搜索）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！