- [Daimayuan] T1 最長公共子序列（C++，DP，二分）
  - - 輸入格式
    - 輸出格式
    - 資料范圍
    - 輸入樣例
    - 輸出樣例
    - 解題思路
- [Daimayuan] T2 喵喵序列（C++，序偶）
  - - 題目描述
    - 輸入格式
    - 輸出格式
    - 樣例輸入
    - 樣例輸出
    - 樣例說明
    - 資料范圍
    - 雙倍經驗
    - 解題思路：
- [Daimayuan] T3 漂亮數（C++，字串）
  - - 輸入描述
    - 輸出描述
    - 輸入樣例
    - 輸出樣例
    - 解題思路
- [Daimayuan] T4 真偽字串（C++，邏輯推理）
  - - 輸入格式
    - 輸出格式
    - 樣例輸入
    - 樣例輸出
    - 樣例解釋
    - 解題思路
- [Daimayuan] T5 走不出的迷宮（C++，圖論，DP）
  - - 輸入格式
    - 輸出格式
    - 樣例輸入1
    - 樣例輸出1
    - 樣例輸入2
    - 樣例輸出2
  - 樣例輸入3
    - 樣例輸出3
    - 資料規模
    - 解題思路
- [Daimayuan] T6 最長同余子陣列（C++，gcd，線段樹）
  - - 資料規模
    - 輸入格式
    - 輸出格式
    - 樣例輸入
    - 樣例輸出
    - 解題思路
- [Daimayuan] T7 互質（C++，數學）
  - - 題目描述
    - 輸入描述
    - 輸出描述
    - 樣例輸入
    - 樣例輸出
    - 資料范圍
    - 解題思路
- [Daimayuan] T9 最短路計數（C++，DP）
  - - 題目描述
    - 輸入格式
    - 輸出格式
    - 樣例輸入
    - 樣例輸出
    - 資料范圍
    - 提示
    - 解題思路
[Daimayuan] T10 最后的舞會（C++，DFS）
- - - 輸入描述
    - 輸出描述
    - 樣例輸入
    - 樣例輸出
    - 樣例解釋
    - 解題思路

[Daimayuan] T1 最長公共子序列（C++，DP，二分）

給出從 $1$ 到 $n$ 的兩個排列 $P_1$ 和 $P_2$，求它們的最長公共子序列，

輸入格式

第一行是一個正整數 $n$，

接下來兩行，每行為 $n$ 個數，為自然數 $1,2,…,n$ 的一個排列，

輸出格式

一個數，即最長公共子序列的長度，

資料范圍

$1≤n≤10^5$

輸入樣例

5 
3 2 1 4 5
2 1 3 4 5

輸出樣例

解題思路

根據資料范圍，我們需要一個$O(N)$或者$O(NlogN)$的演算法，自然會想到動態規劃，

與本題相似的題型有最長公共子序列（$LCS$，復雜度$O(N^2)$），最長上升子序列（復雜度$O(N(N-1)/2$)

表面上看一眼好像最長公共子序列和最長上升子序列并沒有什么聯系（~~不是有公共和子序列嘛~~）

但實際上是有的，我們來重新審視一下最長上升子序列問題：

給定一個序列，我們需要找出一個最長的單調上升的子序列，但實際上我們找出來的并不只是一個序列，而是兩個：索引單調遞增、值也單調遞增，

然后反觀本題的題意，可以發現$n$個數對應$1,...,n$的全排列這個條件，這個條件允許我們反轉值和索引的關系（與索引和值的關系一致，值和索引也都是一一對應的，并無重復），

到這里，我們可以實作以下的代碼，將本題轉換為找出最長上升子序列的問題：

int n, temp;
cin >> n;
for (int i = 0; i < n; i++) {
	cin >> temp;
	indices[temp] = i;//a序列值到索引的映射
}
for (int i = 0; i < n; i++) {
	cin >> temp;
	arr[i] = indices[temp];//arr[i]為b_i在a序列中的位置
}

但是我們之前說過了，常規的最長上升子序列的演算法時間復雜度為$O(N(N-1)/2$，不可接受，

可以優化的地方就是常規動態規劃演算法中，搜索最長前綴的那部分（這里不再贅述），

優化搜索的常用方法就是二分搜索，但是要求是問題具有單調性，接下來我們看看這個問題為什么具有單調性：

直接開始模擬我們的演算法，通過模擬來理解，

維護一個前綴和陣列tails與當前最長上升子序列長度len，起初，len=0, tails[0]=-NaN（-NaN即為負無窮），

然后與常規演算法思路相一致，我們首先搜索以a[0]結尾的最長上升子序列，搜索思路是找到當前有效長度tails陣列中，比a[0]大的最小元素，

顯然，（1）這個元素并不存在（因為有效長度len=0），所以我們擴增長度len=1，

然后繼續嘗試搜索以a[1]結尾的最長上升子序列，思路是一致的，但是可能會出現（2）另一種情況——a[1]<a[0]，

當出現這種情況時，我們把$a[1]$用$a[0]$覆寫，因為當上升序列長度相同的時候，我們希望結尾元素盡可能地小，

依次類推，直到所有元素都遍歷完成，

接下來給出規范化的思路：

（1）搜索當前tails陣列，尋找比a[i]大的元素；

（2）不存在該元素，擴增有效長度len；

（3）存在該元素，覆寫它，

實作代碼如下

tails[0] = -NaN;
for (int i = 0; i < n; i++) {
	int l = 0, r = len + 1, m;
	while (l + 1 != r) {
		m = l + r >> 1;
		if (arr[i] > tails[m]) l = m;
		else r = m;
	}
	tails[r] = arr[i];
	len = max(len, r);
}

最后，AC代碼如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int max_n = 1e5;
const int NaN = 0x3F3F3F3F;

int arr[max_n], indices[max_n];
int tails[max_n], len = 0;

int main() {
	int n, temp;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		indices[temp] = i;
	}
	for (int i = 0; i < n; i++) {
		cin >> temp;
		arr[i] = indices[temp];
	}

	tails[0] = -NaN;
	for (int i = 0; i < n; i++) {
		int l = 0, r = len + 1, m;
		while (l + 1 != r) {
			m = l + r >> 1;
			if (arr[i] > tails[m]) l = m;
			else r = m;
		}
		tails[r] = arr[i];
		len = max(len, r);
	}
	printf("%d", len);
	return 0;
}

[Daimayuan] T2 喵喵序列（C++，序偶）

題目描述

給定一個含有 $n$ 個整數的序列 $a_1,a_2,…a_n$，三個數 $i,j,k$ 是可愛的當且僅當 $i<j<k$ 且 $a_i<a_j<a_k$，

請你求出有多少組 $i,j,k$ 是可愛的，

輸入格式

第 $1$ 行一個整數 $n$ 表示序列元素個數，

第 $2$ 行 $n$ 個整數分別表示 $a_1,a_2,…a_n$，

輸出格式

一行一個整數，表示所求數量，

樣例輸入

5
1 2 2 3 4

樣例輸出

樣例說明

滿足條件的有：$(1,2,3)$，$(1,2,4)$，$(1,2,3)$，$(1,2,4)$，$(1,3,4)$，$(2,3,4)$，$(2,3,4)$，共 $7$ 個，

資料范圍

對于全部資料，有 $1≤n≤3×10^4$，$0≤a_i<2^{63}$，

雙倍經驗

解題思路：

如果沒有重復元素的話，倒是有個快速的演算法（復雜度$O(NlogN)$)，這里簡單說一下，不感興趣可以跳過：

首先利用二分優化過的最長上升子序列演算法找出長度$len$，然后答案就是$C_{len-1}^{3}$，

（利用組合數求和公式$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$，可得$C_2^2+C_3^2+...+C_{n-1}^2=C_{n-1}^3$）

但是本題存在重復元素，所以我們只能老老實實找出所有三元組，

與本題相似的問題是找出所有序偶（有序對），本題是以此為基礎的，所以先說一下序偶問題，

對于序偶問題，采用樹狀陣列（線段樹）來實作，

我們通過模擬來理解大致的思路：

開一個大小為$4*n$的陣列，維護每一個位置上的元素數量（采用離散化，忽略元素值，保存元素的順序），初始化所有區間元素均為$0$，線段樹動態更新，

然后我們遍歷陣列，查詢第一個元素，若其順序位置為$i$，則查看線段樹$1$~$i-1$區間內的元素和（也就是比它小的元素的數量），此即為二元有序對的數量，

在查詢結束之后，我們將這個元素添加到線段樹之中，

為什么要動態更新而不直接建樹？

因為直接建樹，很難維護一個區間（$1$_{$i-1$）中小于指定元素（$i$）的元素數目（因為缺少資訊，我們無法查詢$1$}$i-1$區間中小于指定元素（$i$）的元素數目，能查詢的只是整個區間中的數目），

但是動態更新就不同了，因為當前樹中只有$1$~$i-1$的元素，問題就順利解決了，

三元組就是在二元組的基礎上，再建一棵線段樹（更多元也可以依次類推），第二棵線段樹與前一棵不同就在于它維護的是每一個位置上的二元組數量，

最后，AC代碼如下：

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int max_n = 3e4;
const long long max_a = 1LL << 63LL - 1LL;

long long arr[max_n + 1], sorted_arr[max_n + 1], n, ans;
int tree1[max_n * 4], tree2[max_n * 4];
map<long long, int>value2idx;

int query(int idx, int l, int r, int L, int R, int tree[]) {
	if (L <= l && r <= R) return tree[idx];

	int m = l + r >> 1;
	int sum = 0;
	if (L <= m) sum += query(idx << 1, l, m, L, R, tree);
	if (m + 1 <= R) sum += query((idx << 1) + 1, m + 1, r, L, R, tree);
	return sum;
}

void update(int idx, int l, int r, int x, int val, int tree[]) {
	if (l == r) {
		tree[idx] += val;
		return;
	}
	
	int m = l + r >> 1;
	if (x <= m) update(idx << 1, l, m, x, val, tree);
	if (x >= m + 1) update((idx << 1) + 1, m + 1, r, x, val, tree);
	tree[idx] = tree[idx << 1] + tree[(idx << 1) + 1];
}

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

	//離散化
	sort(sorted_arr + 1, sorted_arr + n + 1, [](long long x1, long long x2) {
		return x1 < x2;
		});
	int new_id = 2;
	value2idx[sorted_arr[1]] = 1;
	for (int i = 2; i <= n; i++)
		if (sorted_arr[i] != sorted_arr[i - 1]) value2idx[sorted_arr[i]] = new_id++;
	new_id--;

	//動態維護
	long long ans = 0, ret = 0;
	for (int i = 1; i <= n; i++) {
		int idx = value2idx[arr[i]];
		if (idx != 1) ans += query(1, 1, new_id, 1, idx - 1, tree2);
		update(1, 1, new_id, idx, 1, tree1);
		if (idx != 1) {
			ret = query(1, 1, new_id, 1, idx - 1, tree1);
			update(1, 1, new_id, idx, ret, tree2);
		}
	}
	cout << ans << endl;
	return 0;
}

[Daimayuan] T3 漂亮數（C++，字串）

有一個長度為 $n$ 的數字 $X$，由 $n$ 位數字組成，即 $a_1,a_2,...a_n$，它們按從左到右的順序組成一個十進制的數，

并且，你將得到一個數 $k$，需要你構造出一個最小的數 $Y$，對于每一位 $i$($1≤i≤m?k$)，滿足 $b_i=b_{i+k}$，并且$X≤Y$，

輸入描述

第一行給出兩個數 $n,k$ 其中 ($2≤n≤200000,1≤k<n$)，

第二行給出 $X:a_1,a_2,...a_n$，

輸出描述

第一行給出$Y$的長度 $m$，

輸出最小的滿足條件的數 $Y:b_1,b_2,...b_m$，

輸入樣例

3 2
353

輸出樣例

3
353

解題思路

根據題意，我們需要找出一個長度為$k$的子串，使得用它回圈形成的字串$Y>X$，

采用模擬來理解思路：

（1）首先取$X$的前$k$個數字形成子串；

for (int i = 0; i < k; i++) {
	arr[i] = X[i];
}

（2）將子串在$X$上滑動比較，如果小于，將子串的最低位自增$1$，

bool flag = true;
for (int i = k; flag && i < n; i += k) {//滑動視窗（視窗長度k）
    for (int j = 0; flag && j < k && i + j < n; j++) {//比較
        if (arr[j] < X[i + j]) {//小于，自增1
            arr[k - 1]++;
            int idx = k - 1;
            while (arr[idx] > 9) {
                arr[idx--] = 0;
                arr[idx]++;
            }
            flag = false;
        }
        else if (arr[j] > X[i + j]) {//特判
            flag = false;
            break;
        }
    }
}

需要注意的是，當高位已經大于，我們就不需要繼續匹配低位了，所以需要增加特判操作，

最后，AC代碼如下：

#include <iostream>
using namespace std;
const int max_len = 200000;
const int max_k = max_len - 1;

int X[max_len], arr[max_k];

int main() {
	int n, k;
	string str;
	cin >> n >> k;
	cin >> str;


	for (int i = 0; i < n; i++) {
		X[i] = str[i] - '0';
		if (i < k) arr[i] = X[i];
	}

	bool flag = true;
	for (int i = k; flag && i < n; i += k) {//滑動視窗（視窗長度k）
		for (int j = 0; flag && j < k && i + j < n; j++) {//比較
			if (arr[j] < X[i + j]) {//小于，自增1
				arr[k - 1]++;
				int idx = k - 1;
				while (arr[idx] > 9) {
					arr[idx--] = 0;
					arr[idx]++;
				}
				flag = false;
			}
			else if (arr[j] > X[i + j]) {
				flag = false;
				break;
			}
		}
	}

	printf("%d\n", n);
	for (int i = 0; i < n; i += k) {
		for (int j = 0; j < k && i + j < n; j++) {
			printf("%d", arr[j]);
		}
	}
	return 0;
}

[Daimayuan] T4 真偽字串（C++，邏輯推理）

給定兩個長度相等的字串 $S_1,S_2$, 問能否找出一個字串 $S$, 使得 $S$ 只洗掉一個字符可以得到 $S_1$, 并且 $S$ 只洗掉一個字符也可以得到 $S_2$ (可以是不同位置的字符)，

輸入格式

輸入第一行給出字串 $S_1$, 第二行給出字串 $S_2$, 兩個字串的長度 $1≤len≤300000$，

輸出格式

如果能找到滿足條件的字串 $S$, 輸出 $1$, 否則輸出 $0$，

樣例輸入

abacaa
aacaba

樣例輸出

樣例解釋

$abacaba$ 洗掉第二個字符 $b$ 可以得到字串 $S_1$, 并且洗掉第一個字符 $b$ 可以得到字串 $S_2$，

解題思路

共有兩種輸出$1$的情況：

（1）$S_1,S_2$完全相同（視為洗掉字符位置一致）；

（2）$S_1,S_2$各自洗掉一個字符之后完全相同，

其余情況均輸出$0$，

接下來進行代碼實作：

當且僅當同時到達末尾的時候，輸出$1$，字符匹配一共有三種情況：

（1）匹配兩個字符，如果相同，則繼續匹配；

（2）如果不同，先嘗試洗掉$S_1$中的字符；如果再次遇到不同，嘗試洗掉$S_2$中字符；若兩個字串仍不匹配，進行（3）；

（3）如果不同，先嘗試洗掉$S_2$中的字符；如果再次遇到不同，嘗試洗掉$S_1$中字符；若兩個字串仍不匹配，輸出$0$，

最后，AC代碼如下：

#include <iostream>
using namespace std;

string s1, s2;

bool judge(int i, int j) {//判斷是否能夠相等
	int len = s1.size();
	bool flag = true;//嘗試洗掉的機會
	while (i < len && j < len) {
		if (s1[i] != s2[j]) {
			if (flag) {
				if (i < j) i++;
				else j++;

				flag = false;
			}
			else return false;
		}
		i++, j++;
	}
	if (i != j && !flag) return false;
	return true;
}

int main() {
	cin >> s1 >> s2;
	int len = s1.size(), ans = -1;
	for (int i = 0; i < len; i++) {//找出第一個不匹配
		if (s1[i] != s2[i]) {
			ans = i;
			break;
		}
	}

	if (ans == -1) cout << 1 << endl;//兩個字串相等
	else {//分情況討論
		if (judge(ans, ans + 1) || judge(ans + 1, ans)) cout << 1 << endl;
		else cout << 0 << endl;
	}
	return 0;
}

[Daimayuan] T5 走不出的迷宮（C++，圖論，DP）

有一個 $H$ 行 $W$ 列的迷宮（行號從上到下是 $1?H$，列號從左到右是 $1?W$），現在有一個由 . 和 # 組成的 H 行 W 列的矩陣表示這個迷宮的構造，. 代表可以通過的空地，# 代表不能通過的墻，

現在有個人從起點 $(1,1)$ 開始走，他每一步只能往右走一格或者往下走一格，并且他不能跨越迷宮的邊界，他會一直走，直到沒有可以走的路時停下來，

請問這個人最多可以經過多少個格子？

輸入格式

第一行兩個整數 $H$，$W$，表示迷宮有 $H$ 行 $W$ 列，

接下來一個 $H$ 行 $W$ 列的由 . 和 # 組成的矩陣，表示迷宮的構造，

注意：保證 $(1,1)$ 的位置一定是 .，

輸出格式

一個整數，表示最多步數，

樣例輸入1

3 4
.#..
..#.
..##

樣例輸出1

樣例輸入2

1 1
.

樣例輸出2

樣例輸入3

5 5
.....
.....
.....
.....
.....

樣例輸出3

資料規模

對于全部資料保證 $1≤H,W≤100$

解題思路

主體思路為動態規劃，時間復雜度為$O(H*W)$，

由題意可知，我們到達一個格子的方式只有從左邊和上邊到達兩種情況，那么我們就繼承這兩種情況中步數更多的一種$+1$來更新：

sum[i][j] = max(sum[i - 1][j], sum[i][j - 1]) + 1;

采用二重回圈遍歷整張圖，由回圈順序，顯而易見：在我們到達(i, j)之前，已經到達了(i - 1, j)和(i, j - 1)，

for (int i = 1; i <= h; i++) {
	for (int j = 1; j <= w; j++) {
		sum[i][j] = max(sum[i - 1][j], sum[i][j - 1]) + 1;
	}
}

但是需要注意兩點：

（1）注意障礙物的存在，以下代碼采用的方式是掩碼把墻的sum置為$0$；

（2）注意尋找最大步數時還需要進行一次$BFS$，因為我們可能到達不了某些格子，從而導致我們得到的答案并不是sum陣列中的最大值，

AC代碼如下：

#include <iostream>
#include <queue>
using namespace std;
const int max_h = 100;
const int max_w = 100;

bool map[max_h + 1][max_w + 1], book[max_h][max_w];
long long sum[max_h + 1][max_w + 1];
long long h, w, ans = 1;
struct node { int x, y; };
queue<node>q;

inline void read() {
	string str;
	cin >> h >> w;
	for (int i = 1; i <= h; i++) {
		cin >> str;
		for (int j = 1; j <= w; j++) {
			if (str[j - 1] == '.') map[i][j] = true;
			else map[i][j] = false;
		}
	}
}

void bfs() {
	q.push(node{ 1,1 });
	book[1][1] = true;
	int step[2][2] = { {1,0}, {0,1} }, temp_x, temp_y;

	while (!q.empty()) {
		node temp = q.front(); q.pop();
		for (int i = 0; i < 2; i++) {
			temp_x = step[i][0] + temp.x;
			temp_y = step[i][1] + temp.y;
			if (temp_x > h || temp_y > w) continue;
			if (!map[temp_x][temp_y]) continue;
			if (book[temp_x][temp_y]) continue;
			q.push(node{ temp_x,temp_y });
			book[temp_x][temp_y] = true;
			ans = max(ans, sum[temp_x][temp_y]);
		}
	}
}

inline void solve() {
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= h; j++) {
			sum[i][j] = max(sum[i - 1][j] * map[i - 1][j],
				sum[i][j - 1] * map[i][j - 1]) + 1;
		}
	}

	bfs();
	cout << ans << endl;
}

int main() {
	read();
	solve();
	return 0;
}

[Daimayuan] T6 最長同余子陣列（C++，gcd，線段樹）

給定一個 $N$ 長陣列 $\{A\}$, 元素之間 兩兩不同.

現在要求你找出最長的 連續子序列, 使得這些元素 $mod\ M$ 意義下同余, 其中 $M≥2$.

形式化的說, 在陣列中找到最長的 $A[L..R],?M≥2$, 使得:

$A_L≡A_{L+1}≡A_{L+2}≡?≡A_R(mod\ M)$

其中, a≡b(mod M) 即是說 a%M=b%M

輸出此長度即可.

資料規模

$1≤n≤2×10^3$
$1≤a_i≤10^{18}$

輸入格式

第一行一個數字 $N$，

接下來一行 $N$ 個整數 $A_1,A_2,…,A_N$，

輸出格式

一個數，表示最長連續同余子序列的長度，

樣例輸入

4
8 2 10 5

樣例輸出

注意到 $8,2,10$ 均為偶數.

進階：

bonus 1: consider what if $N$ is greater (even $1≤N≤2×10^5$)?

bonus 2: consider how to solve the 'subsequence' version.

解題思路

首先來理解一下同余：同余即是元素之間的差值可以被同一個數整除（類似于等引數列），

整個程序分為三步：

（1）我們把輸入處理成兩個相鄰元素之間的差值：

cin >> buffer1;
for (int i = 1; i < n; i++) {
    cin >> buffer2;
    arr[i] = abs(buffer2 - buffer1);
    buffer1 = buffer2;
}

（2）然后建一棵維護區間$gcd$的線段樹：

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] = gcd(tree[idx << 1], tree[(idx << 1) + 1]);
}

（3）最后跑一個滑動視窗，求得最大長度：

long long ans = 0, l = 1, r = 1;
while (r <= n - 1) {
    if (query(1, 1, n - 1, l, r) != 1) {
        ans = max(ans, r - l + 1);
        r++;
    }
    else l++;

    while (r - l + 1 <= ans) r++;//小于ans的嘗試沒有意義
}
cout << ans + 1 << endl;

需要注意的就是當相鄰兩個數相等時的處理：

題意要求模數$M\ge2$，所以我們應該當query回傳值大于$1$的時候增加視窗長度，

根據gcd的演算法，當其中一個輸入資料為$0$時，會回傳另外一個數，所以$0$對于最大公約數的計算沒有影響，

但是當查詢范圍內的所有差值均為$0$的時候，query會回傳$0$，需要注意這時是可以增加視窗長度的，

所以更改判斷條件為query != 1而不是query > 1，

最后，AC代碼如下：

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

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

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

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] = gcd(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];

	int m = l + r >> 1;
	if (R <= m) return query(idx << 1, l, m, L, R);
	else if (L >= m + 1) return query((idx << 1) + 1, m + 1, r, L, R);
	else return gcd(query(idx << 1, l, m, L, R), query((idx << 1) + 1, m + 1, r, L, R));
}

int main() {
	long long n, buffer1, buffer2;
	cin >> n;
	cin >> buffer1;
	for (int i = 1; i < n; i++) {
		cin >> buffer2;
		arr[i] = abs(buffer2 - buffer1);
		buffer1 = buffer2;
	}

	build_tree(1, 1, n - 1);

	long long ans = 0, l = 1, r = 1;
	while (r <= n - 1) {
		if (query(1, 1, n - 1, l, r) != 1) {
			ans = max(ans, r - l + 1);
			r++;
		}
		else l++;

		while (r - l + 1 <= ans) r++;
	}
	cout << ans + 1 << endl;
	return 0;
}

[Daimayuan] T7 互質（C++，數學）

題目描述

給你一個包含n個正整數的序列 $A=(A1,A2,...,An)$,找到 $[1,m]$中每一個滿足下列條件的 $k$：

$gcd(A_i,k)=1$, $1≤i≤n$

輸入描述

第一行輸入兩個整數 $n$, $m$ 第二行輸入$n$個整數代表序列$A$

輸出描述

第一行輸出一個整數代表滿足條件的k的數量接下里每一行輸出一個整數，代表一個滿足條件的$k$

樣例輸入

3 12
6 1 5

樣例輸出

資料范圍

$1≤n,m≤100000$

$1≤a_i≤100000$

解題思路

本來這道題是想用歐拉篩做的（只考慮部分數情況下的“質數”），但是并不是質數就符合條件，因為互質要求是最大公約數為$1$，而質數只是不能分解而已，

對于互質的數$a,b$，$gcd(a,b)=1$，也就是說互質的數不能有公因數，

我們將這個問題優化一下，互質的數不能有公共質因數（因為任何合數都可以分解為質數的乘積），

那么現在我們的思路就是將所有輸入分解為質因數，然后利用分解得到的質因數篩選符合條件的$k$，

接下來是代碼實作部分：

首先，我們需要知道如何將輸入分解為質因數

int num;
for (int i = 0; i < n; i++) {
	cin >> num;
	while (num != 1) {
		fliter[maxPrime[num]] = true;
		num /= maxPrime[num];
	}	
}

其實，就是將$num$不斷除以其最大質因數，

那么問題出現了，如何求任意數的最大質因數？這里采用埃氏篩的演算法（簡而言之就是用質數的倍數篩去非質數）的變形：

memset(isPrime + 1, true, sizeof(bool) * max_n);//初始化，默認所有數均為質數
maxPrime[1] = 1;//對1進行特殊處理
isPrime[1] = false;
for (int i = 2; i <= max_n; i++) {
	if (!isPrime[i]) continue;//非質數
	maxPrime[i] = i;
	for (int j = 2 * i; j <= max_n; j += i) {
		isPrime[j] = false;
		maxPrime[j] = i;
	}
}

篩子做好了，接下來就是篩選$1$~$M$的所有數了：

vector<int>v;
v.push_back(1);//對1進行特殊處理
for (int i = 2; i <= m; i++) {
    bool flag = true;
    int temp = i;
    while (temp != 1) {
        if (fliter[maxPrime[temp]]) {
            flag = false;
            break;
        }
        temp /= maxPrime[temp];
    }
    if (flag) v.push_back(i);
}

在題目之初提到的問題就是篩選一個$k$，既需要考慮$k$能否分解為小于$k$的數，又要考慮$k$之后的數是否為$k$的倍數，

但是現在我們將序列$A$中的元素分解了，就沒有這個問題了，只需要考慮$k$能否分解即可，

最后，AC代碼如下：

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
const int max_n = 100000;

bool isPrime[max_n + 1], fliter[max_n + 1];     //質數陣列, 篩子
int maxPrime[max_n + 1];                        //最大質因數

int main() {
    //prepare
    memset(isPrime + 1, true, sizeof(bool) * max_n);//初始化，默認所有數均為質數
    maxPrime[1] = 1;//對1進行特殊處理
    isPrime[1] = false;
    for (int i = 2; i <= max_n; i++) {
        if (!isPrime[i]) continue;//非質數
        maxPrime[i] = i;
        for (int j = 2 * i; j <= max_n; j += i) {
            isPrime[j] = false;
            maxPrime[j] = i;
        }
    }

    //input
    int n, m, num;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> num;
        while (num != 1) {
            fliter[maxPrime[num]] = true;
            num /= maxPrime[num];
        }
    }

    //fliter
    vector<int>v;
    v.push_back(1);//對1進行特殊處理
    for (int i = 2; i <= m; i++) {
        bool flag = true;
        int temp = i;
        while (temp != 1) {
            if (fliter[maxPrime[temp]]) {
                flag = false;
                break;
            }
            temp /= maxPrime[temp];
        }
        if (flag) v.push_back(i);
    }

    //output
    cout << v.size() << endl;
    for (auto iter : v) {
        cout << iter << endl;
    }
    return 0;
}

[Daimayuan] T9 最短路計數（C++，DP）

題目描述

給出一個 $N$ 個頂點 $M$ 條邊的無向無權圖，

問從頂點 $1$ 開始，到其他每個點的最短路有幾條，

輸入格式

第 $1$ 行包含兩個正整數 $N$，$M$，

接下來 $M$ 行，每行兩個正整數 $x,y$表示存在一條由頂點 $x$ 到頂點 $y$ 的邊，（可能存在重邊和自環）

輸出格式

輸出 $N$ 行，每行一個非負整數，

第 $i$ 行輸出從頂點 $1$ 到頂點 $i$ 的不同最短路個數，

由于資料可能很大，你只需要輸出 $ans\ mod\ 100003$ 的結果，

若頂點 $1$ 不能到達頂點 $i$，請輸出 $0$，

樣例輸入

樣例輸出

資料范圍

$1≤N≤10^6$，$1≤M≤2×10^6$

提示

由于資料量較大，請使用較為快速的輸入/輸出方式，

解題思路

根據資料范圍，我們估計演算法的復雜度至多是$O(N)$，因此想到了動態規劃：

對于節點$i$，有若干個節點與之相連，在與之相連的節點當中從$1$到$k_1,k_2,...,k_n$節點的路徑長度相同且最短，那么我們計算得出，從$1$到節點$i$的最短路徑數為$num[k_1]+num[k_2]+...+num[k_n]$，

以上是思路的主體部分，接下來實作代碼：

資料量龐大，同時也是因為存在重邊，故不能采用二維陣列存圖，因此采用鏈式前向星，

對于代碼主體部分，維護一個佇列與一個路徑長度的陣列，

初始化將$1$節點加入佇列，然后不斷嘗試到達新的節點，

void solve() {
	q.push(1);
	while (!q.empty()) {
		int node = q.front(); q.pop();
		
		for (int i = head[node]; i != -1; i = edges[i].next) {
			int v = edges[i].v;
			q.push(v);
		}
	}
}

利用佇列元素先進先出的特點，我們可以保證，隊首的節點永遠是距離$1$最近的節點，

進而我們可以保證，用隊首去更新路徑長度，得到的一定是最短路徑長度，

void solve() {
	q.push(1);
	path[1] = 0;

	while (!q.empty()) {
		int node = q.front(); q.pop();
		int path_len = path[node] + 1;
		
		for (int i = head[node]; i != -1; i = edges[i].next) {
			int v = edges[i].v;
			if (path_len > path[v]) continue;
			if (path[v] == NaN) {//NaN代表無窮大，即為未到達的節點
				path[v] = path_len;
				q.push(v);
			}
		}
	}
}

以此為基礎，很容易實作最初的思想：

void solve() {
	q.push(1);
	path[1] = 0;
	sum[1] = 1LL;

	while (!q.empty()) {
		int node = q.front(); q.pop();

		int path_len = path[node] + 1;
		
		for (int i = head[node]; i != -1; i = edges[i].next) {
			int v = edges[i].v;
			if (path_len > path[v]) continue;
			sum[v] = (sum[v] + sum[node]) % mod_num;
			if (path[v] == NaN) {
				path[v] = path_len;
				q.push(v);
			}
		}
	}
}

最后，AC代碼如下：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <string.h>
using namespace std;
const int max_n = 1e6;
const int max_m = 2e6;
const int NaN = 0x3F3F3F3F;
const long long mod_num = 100003;

struct edge { int v, next; }edges[2 * max_m];
int tot = -1, head[max_n + 1], path[max_n + 1];
queue<int>q;
long long sum[max_n + 1];

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

void solve() {
	q.push(1);
	path[1] = 0;
	sum[1] = 1LL;

	while (!q.empty()) {
		int node = q.front(); q.pop();

		int path_len = path[node] + 1;
		
		for (int i = head[node]; i != -1; i = edges[i].next) {
			int v = edges[i].v;
			if (path_len > path[v]) continue;
			sum[v] = (sum[v] + sum[node]) % mod_num;
			if (path[v] == NaN) {
				path[v] = path_len;
				q.push(v);
			}
		}
	}
}

int main() {
	memset(head, -1, sizeof(int) * (max_n + 1));
	memset(path, 0x3F, sizeof(int) * (max_n + 1));
	int n, m;
	scanf("%d%d", &n, &m);
	//cin >> n >> m;
	int u, v;
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &u, &v);
		//cin >> u >> v;
		add_edge(u, v);
	}

	solve();
	for (int i = 1; i <= n; i++) {
		printf("%lld\n", sum[i]);
	}
	return 0;
}

[Daimayuan] T10 最后的舞會（C++，DFS）

老師為即將畢業的同學們準備了一場舞會，有$2N$個同學會參加這場舞會，他們會被分成$N$對跳舞，每個人有一個編號，如果編號為$i$的同學和編號為$j$的同學配對，那么這一對的滿意度是$A_{i,j}(i<j)$，我們規定這個舞會的滿意度為每一隊的滿意度的異或和，也就是說，當同學們分成$N$組后，第$i$對同學的滿意度為$A_i$，那么舞會的滿意度為$A1⊕A2⊕...AN$

請你求出本場舞會滿意度的最大值

輸入描述

第一行給出一個數$N$，有$2N$個人參加舞會

接下來給出一個矩陣表示$i$和$j$配對時的滿意度

$A_{1,2},A_{1,3},...A_{1,2N}$

$A_{2,3},...A_{2,2N}$

.. .. ..

$A_{2N?1,2N}$

其中$1≤N≤8,0≤A_{i,j}≤2^{30}$

輸出描述

輸出本場舞會滿意度的最大值

樣例輸入

樣例輸出

樣例解釋

如果$\{1,2\},\{3,4\},ans=A_{1,2}⊕A_{3,4}=4⊕2=6$

如果$\{1,3\},\{2,4\},ans=A_{1,3}⊕A_{2,4}=0⊕3=3$

如果$\{1,4\},\{2,3\},ans=A_{1,4}⊕A_{2,3}=1⊕5=4$

最后答案為$max(6,3,4)=6$

解題思路

因為資料$N\le8$，所以直接$DFS+$剪枝就可以，

問題可能在于如何$DFS$：

寫一個$DFS$需要定義四個部分（并不一定都需要）：狀態部分（函式宣告），停止條件，主體部分，回傳后操作，

我們從簡單到復雜逐個定義，

（1）結束條件：配對數到達$n$；

（2）回傳后操作：將已配對的兩個人取消標記；

（3）狀態部分：狀態部分為已配對數、舞會滿意度；

（4）主體部分：首先利用一個回圈找出第一個未配對的人，然后再用一個回圈去為他搭配所有可能，

void dfs(int couple, int confid) {//狀態
	if (couple == n + 1) {//結束條件
		ans = max(ans, confid);
		return;
	}
	
    //函式主體
	int i, j;
	for (i = 1; i <= 2 * n; i++) {
        if (!vis[i]) {
            for (j = i + 1; j <= 2 * n; j++) {
                if (!vis[j]) {
                    vis[i] = vis[j] = true;
                    dfs(couple + 1, confid ^ relation[i][j]);
                    vis[i] = vis[j] = false;//回傳后操作
                }
            }
        }
	}
}

如何降低時間復雜度：

（1）依靠遍歷順序：$1,2$和$2,1$算一種情況，所以只考慮前者（遞增序），依靠遍歷查找的順序來實作；

（2）依靠$DFS$序：我們在第一層配對$1$和$3$，在第二層配對$2$和$4$這種情況與我們在第一層配對$2$和$4$和在第二層配對$1$和$3$二者是相同的，

優化之后的演算法如下：

void dfs(int couple, int confid) {
	if (couple == n + 1) {
		ans = max(ans, confid);
		return;
	}

	int i, j;
	for (i = 1; i <= 2 * n; i++) {
		if (!vis[i]) break;//DFS序剪枝
	}
	for (j = i + 1; j <= 2 * n; j++) {//遍歷順序剪枝
		if (!vis[j]) {
			vis[i] = vis[j] = true;
			dfs(couple + 1, confid ^ relation[i][j]);
			vis[i] = vis[j] = false;
		}
	}
}

AC代碼如下：

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

int relation[max_n + 1][max_n + 1], n, ans;
bool vis[max_n + 1];

void dfs(int couple, int confid) {
	if (couple == n + 1) {
		ans = max(ans, confid);
		return;
	}

	int i, j;
	for (i = 1; i <= 2 * n; i++) {
		if (!vis[i]) break;
	}
	for (j = i + 1; j <= 2 * n; j++) {
		if (!vis[j]) {
			vis[i] = vis[j] = true;
			dfs(couple + 1, confid ^ relation[i][j]);
			vis[i] = vis[j] = false;
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= 2 * n; i++) {
		for (int j = i + 1; j <= 2 * n; j++) {
			cin >> relation[i][j];
		}
	}

	dfs(1, 0);
	cout << ans << endl;
	return 0;
}

（并沒有什么奇妙的演算法呢$qwq$）

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551104.html

標籤：其他

上一篇：軟體自動化測驗初學者忠告

下一篇：返回列表

[Week 18] 每日一題（C++，動態規劃，線段樹，數學）

[Daimayuan] T1 最長公共子序列（C++，DP，二分）

輸入格式

輸出格式

資料范圍

輸入樣例

輸出樣例

解題思路

[Daimayuan] T2 喵喵序列（C++，序偶）

題目描述

輸入格式

輸出格式

樣例輸入

樣例輸出

樣例說明

資料范圍

雙倍經驗

解題思路：

[Daimayuan] T3 漂亮數（C++，字串）

輸入描述

輸出描述

輸入樣例

輸出樣例

解題思路

[Daimayuan] T4 真偽字串（C++，邏輯推理）

輸入格式

輸出格式

樣例輸入

樣例輸出

樣例解釋

解題思路

[Daimayuan] T5 走不出的迷宮（C++，圖論，DP）

輸入格式

輸出格式

樣例輸入1

樣例輸出1

樣例輸入2

樣例輸出2

樣例輸入3

樣例輸出3

資料規模

解題思路

[Daimayuan] T6 最長同余子陣列（C++，gcd，線段樹）

資料規模

輸入格式

輸出格式

樣例輸入

樣例輸出

解題思路

[Daimayuan] T7 互質（C++，數學）

題目描述

輸入描述

輸出描述

樣例輸入

樣例輸出

資料范圍

解題思路

[Daimayuan] T9 最短路計數（C++，DP）

題目描述

輸入格式

輸出格式

樣例輸入

樣例輸出

資料范圍

提示

解題思路

[Daimayuan] T10 最后的舞會（C++，DFS）

輸入描述

輸出描述

樣例輸入

樣例輸出

樣例解釋

解題思路