目錄
- T1 [Daimayuan] Collision（C++，多源最短路）
- 題目描述
- 輸入描述
- 輸出描述
- 樣例輸入1
- 樣例輸出1
- 樣例輸入2
- 樣例輸處2
- 資料范圍
- 解題思路
- T2 [Daimayuan] 農田劃分（C++，數學，BFS）
- 題目描述
- 題目輸入
- 題目輸出
- 樣例輸入1
- 樣例輸出1
- 樣例輸入2
- 樣例輸出2
- 資料范圍
- 解題思路
- T3 [Daimayuan] 三段式（C++，陣列前綴和）
- 輸入描述
- 輸出描述
- 樣例輸入
- 樣例輸出
- 樣例解釋
- 解題思路
- T4 [Daimayuan] 模擬輸出受限制的雙端佇列（C++，模擬）
- 輸入格式
- 輸出格式
- 樣例輸入
- 樣例輸出
- 資料規模
- 解題思路
- T5 [Daimayuan] 簡單差分（C++，線段樹）
- 輸入格式
- 輸出格式
- 樣例輸入
- 樣例輸出
- 資料規模
- 解題思路
- T6 [Daimayuan] 非遞減的01序列（C++，前綴和）
- 題面
- 輸入格式
- 輸出格式
- 輸入樣例
- 輸出樣例
- 解題思路
- T7 [Daimayuan] 數學（C++，最大公約數）
- 輸入格式
- 輸出格式
- 樣例輸入
- 樣例輸出
- 資料規模
- 解題思路
- T8 [Daimayuan] pSort（C++，強連通分量）
- 題目描述
- 輸入格式
- 輸出格式
- 輸入 #1
- 輸出 #1
- 輸入 #2
- 輸出 #2
- 資料范圍
- 補充說明
- 解題思路
- T9 [Daimayuan] Owwwwwwwwwww...f（C++，強連通分量）
- 輸入格式：
- 輸出格式：
- 樣例輸入:
- 樣例輸出：
- 解題思路：
- T10 [Daimayuan] 樹（C++，動態規劃，01背包方案數）
- 輸入格式
- 輸出格式
- 樣例輸入1
- 樣例輸出1
- 資料規模
- 解題思路
T1 [Daimayuan] Collision（C++，多源最短路）
題目描述
\(siyisss\) 的王國是由 \(n\) 個村鎮和 \(n?1\) 條雙向道路構成的，村鎮從 \(1\) 到 \(n\) 依次編號，每條雙向道路連接兩個不同的村鎮，使得從任意一個村鎮出發都可以到達任意一個村鎮，接下來請你回答 \(q\) 個問題，每次給出兩個整數 \(c\), \(d\)，表示現在分別有一個人在村鎮 \(c\),一個人在村鎮 \(d\)，現在在 \(c\) 的人要用最短的時間到達村鎮\(d\)，在村鎮 \(d\) 的人要以最短的時間到達村鎮$ c$，假設兩人同時出發，兩人的速度也是一樣的，每條雙向道路的長度也是一樣的，請問兩人相遇的時候是在某一個村鎮，還是在某條雙向道路上？
輸入描述
第一行輸入兩個整數 \(n\), \(q\) 代表村鎮的數量和詢問的數量
接下來 \(n?1\) 行，每行兩個整數用來描述一條雙向道路
最后 \(q\)，每行兩個整數代表 \(c\), \(d\)
輸出描述
對于每個詢問，如果他們在某個村鎮相遇，請示出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
資料范圍
\(2≤n≤100000\)
\(1≤q≤100000\)
對于每一個詢問 \(1≤c_i<d_i≤n\)
解題思路
題意是給出一張無向連通圖，然后詢問\(q\)次，每次要求判斷\(c\),\(d\)兩人相遇的位置，
根據資料范圍，我們需要將每次詢問的時間復雜度降至\(O(1)\)或者\(O(log\ q)\)，
理解題意之后，第一個問題就是如何判斷兩人相遇的位置：
（1）如果最短路的長度為奇數，那么兩人在Road相遇；
（2）如果最短路的長度為偶數，那么兩人在Town相遇，
關于最短路的演算法，我們最容易想到的是Floyd，但是\(n\in [2,100000]\)，直接\(T\)飛掉，
回顧題意：\(n\)個節點、\(n-1\)條邊、全連通，
這不就是一棵樹嘛，
那么我們要知道樹的特點：任意兩個節點之間只有一條通路，
我們只需要找出最近公共父節點（LCA），就可以得出兩個節點之間的通路長度，
采用倍增尋訪演算法，時間復雜度為\(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] 農田劃分（C++，數學，BFS）
題目描述
約翰是一個農場主，他的農場有n塊田，編號從 \(1\)到 \(n\)，這 \(n\)塊田通過 \(m\)條雙向道路相連(資料保證這\(n\)塊田都是聯通的)，我們假設第\(i\)塊田會產生 \(2^ikg\) 的收益，現在約翰想把農田的作業全部交給自己的兩個孩子，劃分方式必須滿足以下規則:
1.每一塊田都需要恰好被分給一個孩子.
2.分給兩個孩子的農田必須是聯通的.就是說對于任意一個孩子在劃分給自己的任意一塊田，都可以不經過另外一個孩子的田，到達自己的任意一塊田.
3.劃分給兩個孩子的收益必須盡可能的相等，如果無法相等，年長的孩子會得到大的那一份.
對于第 \(i\)塊田，如果你要把它分給年長的孩子，請輸出A,否則輸出B.
題目輸入
第一行輸入兩個整數分別代表 \(n,m\) 接下來 \(m\)行，每個兩個整數\(u,v\)，代表這兩塊農田通過一條雙向道路直接相連，資料保證沒有重邊和自環
題目輸出
輸出一個字串，代表答案
樣例輸入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
資料范圍
\(2≤n≤3e5,1≤m≤3e5\)
解題思路
首先，我們要知道：
對于數列\([1,2,2^2,...,2^{n-1},2^n]\)，\(2^n\)是大于之前所有的數加和的，
利用這個性質，因為我們要保證年長的孩子分得的土地更多，所以\(n\)號田地一定會被分給年長的孩子，
繼續利用這個性質，因為我們又要保證劃分盡可能的相等，所以\(n-1\)號田地一定會被劃分給另外一個孩子，
這有什么用呢？
我們的具體演算法是這樣的：
洗掉\(n\)號田地及與其相連的所有通路，然后從\(n-1\)號田地開始\(BFS\)，所有被搜索到的田地均分給另外一個孩子，剩下的田地歸年長的孩子，
演算法時間復雜度為\(O(n)\)，
最后，AC代碼如下：
#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();//取出首節點
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;//重復訪問
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++，陣列前綴和）
有一個長度為\(n\)的序列，現在我們想把它切割成三段(每一段都是連續的），使得每一段的元素總和都相同，請問有多少種不同的切割方法
輸入描述
第一行給出一個數\(n\)，(\(1≤n≤10^5\))
第二行給出序列\(a_1\)，\(a_2\)，\(a_3\)，...，\(a_n\)，(\(|a_i|≤10^5\))
輸出描述
輸出一個數表示有多少種不同的切割方法
樣例輸入
4
1 2 3 3
樣例輸出
1
樣例解釋
可以將它分成第一組\(1\)，\(2\)，第二組\(3\)，第三組\(3\)
解題思路
根據題意，很容易得到下面的公式：
\[sum_1+sum_2+sum_3=sum\\ sum_1=sum_2=sum_3\\ \\ sum_1=sum_2=sum_3=\frac{1}{3}sum \]要滿足題意有兩個前提條件（特殊判定）：
（1）\(sum\ \%\ 3==0\)；
（2）\(n\ge3\)，
if (n < 3 || sum % 3 != 0) {
cout << 0 << endl;
return 0;
}
然后我們來尋找可能的分割方式，
如果有多于\(1\)種的分割方法，那么一定存在子段和為\(0\)，
與其去找子段和為\(0\)的部分，不如轉化思維，使用前綴和的概念（經常用于連續區間和問題），
這樣我們就只需要尋找前綴和同為\(\frac13sum\)的部分了，
然后具體問題具體分析，因為題目中只要求分割為三段，所以我們直接找出前后兩段\(\frac13sum\)即可，
注意，至少要為中間的\(\frac13sum\)預留一個元素的位置，
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++，模擬）
給你一個輸出受限的雙端佇列，限制輸出的雙端佇列即可以從一端插入元素，彈出元素，但是另一端只可以插入不可以洗掉元素，即每次你可以執行以下三種操作的其中一種：
- 在左邊壓入一個字符
- 在右邊壓入一個字符
- 彈出最左邊的字符
現在給你 \(n\) 個字符作為佇列的輸入，請問最多有多少可能的出隊次序，并按字典序列印這些出隊次序，
輸入格式
第一行一個數 \(n\)，表示輸入的長度
第二行一個長度為 \(n\) 的字串
輸出格式
第一行一個整數 \(k\)，表示可能的出隊方案數
下面 \(k\) 行，按字典序輸出每種出隊方案
樣例輸入
3
123
樣例輸出
6
123
132
213
231
312
321
資料規模
對于全部資料保證 \(1≤n≤7\)，
解題思路
雖然題目說是模擬，但是我們不嘗試一下別的方法肯定不會甘心的，所以嘗試理解序列滿足的規則，
以樣例輸入為例子，我們留出三個位置\(□□□\)，
考慮一種簡單的情況，我們在所有元素入隊之后再進行出隊操作，那么一下邏輯成立：
首先對于\(a_1\)，我們可以任意指定它的位置；
然后對于\(a_2\)，因為\(a_1\)的位置已經確定了，\(a_2\)必須在\(a_1\)的前方或者\(a_1\)的后方，其位置選擇受限；
同理可知\(a_3\)位置選擇同樣受限，
似乎并沒有可以用來優化代碼的規律存在，所以我們還是老老實實回去模擬，
模擬雙端佇列采用STL提供的deque容器，由于搜索的結果存在重復，采用set存盤結果去重（同時set會自動將結果按字典序排序），
#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狀態
//終止條件
//dfs主體
//回傳后操作
}
接下來我們對dfs代碼功能進行實作，
實作具體的代碼之前我們需要知道每一步有幾種可能的操作：
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();
}
以上步驟實作完后，終止條件顯而易見：
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狀態
//終止條件
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狀態
//終止條件
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\) 陣列 \(A\)，執行以下操作 \(m\) 次：
選擇一段區間 \([l,r]\)，將區間中所有的數加上整數 \(x\)，
操作完成后回答 \(k\) 個問題：
每個問題給定一段區間 \([l,r]\)，輸出區間中所有數的和，
輸入格式
第一行三個正整數 \(n,m,k\)，
接下來一行 \(n\) 個數，表示陣列 \(A\)，
接下來 \(m\) 行，每行輸入三個整數 \(l,r,x\)，
接下來 \(k\) 行，每行輸入兩個整數 \(l,r\)，
輸出格式
輸出 \(k\) 行，每行一個數表示對應問題的和，
樣例輸入
10 1 1
1 2 3 4 5 6 7 8 9 10
5 8 1
8 9
樣例輸出
18
資料規模
對于全部資料，保證 \(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\)）
求最少翻轉其中的幾位可以使得該序列變為非遞減序列
輸入格式
第一行輸入一個整數 \(n\) (\(1≤n≤10^6\))
第二行輸入一個長度為 \(n\) 的且僅包含 0 和 1 的字串
輸出格式
輸出一個整數，為該序列變為非遞減序列的最少操作次數
輸入樣例
6
010110
輸出樣例
2
解題思路
其實題意描述有一點問題，求的應該是將該序列變為單調不減的01序列（因為沒有單調性其實也是非遞減），
我們的目標具體來說就是選定某個位置，之前的均為0，之后的均為1，同時保證與原序列相似性最高，
根據這個目標，我們只需要遍歷每一個可能的位置，選出其中需要操作次數最少的就可以了，
問題在于如何快速獲取操作次數，
因為只有兩種元素：0和1，所以我們只需要知道其中一種的數量，剩下的都是另外一種，
那么采用前綴和的概念，累計指定位置前\(0\)的數量，
//首元素特殊處理
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] 數學（C++，最大公約數）
給定整數 \(n\)，胖教授想將\(1～n\)這\(n\)個數字分成兩組，每一組至少有一個數，并且使得兩組數字的和的最大公約數最大，請輸出最大的最大公約數，
輸入格式
一行一個整數\(n\)，
輸出格式
輸出一行一個整數表示答案，
樣例輸入
6
樣例輸出
7
資料規模
對于\(20\%\)的資料，保證\(n≤100\)，
對于\(100\%\)的資料，保證\(n≤10^9\)，
解題思路
我們從最大公約數的概念入手：
若\(x\)和\(y\)的最大公約數是\(z\)，那么\(x\)和\(y\)都是\(z\)的倍數，
那么我們所要尋找的最大公約數一定能夠整除\(sum=(1+n)*n/2\)，
要找到最大的最大公約數，我們就只需要找到一個最小的數，使其能整除\(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\) 個元素當且僅當滿足 \(|i?j|=d_i\)，
題目給出序列 \(b_1,b_2,…,b_n\) 和 \(d_1,d_2,…,d_n\)，詢問是否可以通過若干次交換，使得序列 \(a\) 和序列 \(b\) 完全相同，
輸入格式
第 \(1\) 行一個正整數 \(n\)，含義如上，
第 \(2\) 行 \(n\) 個正整數表示 \(b_1,b_2,…,b_n\)，
第 \(3\) 行 \(n\) 個正整數表示 \(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
資料范圍
\(1≤n,d_i≤100\)，保證序列 \(b\) 中元素不重復，
補充說明
原題：CF28B pSort | 洛谷
解題思路
對于題意的理解如下：
if (abs(i - j) == d[i] || abs(i - j) == d[j]) {
/* i,j是可交換的 */
}
那么我們可以把\(a\)序列抽象為一張無向圖，可交換關系為無向邊，
則強連通分量之內的節點可以隨意交換，
也就是說，如果需要交換所有節點都在同一個強連通分量之中，就輸出YES；
反之，如果需要交換的任意一對節點不在一個強連通分量中，就輸出NO，
接下來實作代碼：
我們采用染色法標記不同的強連通分量，用廣度優先搜索對整張圖進行染色，時間復雜度為\(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);
}
}
}
我們需要遍歷每一個節點進行嘗試，所以演算法總時間復雜度為\(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\)的地盤上開始了，
規則如下：
該游戲有許多輪，每個人都會開始一輪游戲，如果編號為 \(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\) 當第 \(x\) 個人開始的一局游戲使 \(y\) 成為了 \(Joon\) ，也使得由 \(y\) 開始的一局游戲 \(x\) 成為 \(Joon\) ，請為小\(A\)找這個最小的 \(t\)， 注意：可能有的人傳話物件是自己，
輸入格式：
第一行輸入一個 \(n\) (\(1≤n≤150\))，表示小A地盤上的人數，
第二行輸入\(a_1\)，\(a_2\)，\(a_3\)，...\(a_n\)，第 \(i\) 個數表示第 \(i\) 個人傳話的物件 \(a_i\)，
輸出格式：
輸出最小的 \(t\)，如果沒有請輸出 \(?1\)，
樣例輸入:
4
2 3 1 4
樣例輸出：
3
解題思路：
把題中序列抽象為一張有向圖，有\(n\)個節點、\(n\)條有向邊\(<i,a_i>\)，
如果能夠達成題中所述的雙向傳話，兩個人必須在一個環中，
如果環的長度為偶數，那么這個環的傳話次數為其長度一半；
如果環的長度為奇數，那么這個環的傳話次數為其長度，
我們需要做的就是統計每一個環的傳話次數，然后計算最小公倍數即可，
很簡單對吧qwq？
那么現在來實作代碼，
首先是搜索環的長度：
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的最小公倍數：
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++，動態規劃，01背包方案數）
有一棵 \(n\) 個節點的以 \(1\) 號點為根的有根樹，現在可以對這棵樹進行若干次操作，每一次操作可以選擇樹上的一個點然后刪掉連接這個點和它的兒子的所有邊，
現在我們想知道對于每一個 \(k\) (\(1≤k≤n\))，最少需要多少次操作能讓圖中恰好存在 \(k\) 個聯通塊，
輸入格式
第一行輸入一個正整數 \(n\)，
第二行輸入 \(n?1\) 個整數 \(f_1,f_2,...,f_{n?1}\)，\(f_i\) 表示 \(i+1\) 號點的父親，保證 \(1≤f_i≤i\)，
輸出格式
輸出 \(n\) 個整數，第 \(i\) 個數表示 \(k=i\) 時的答案，如果無法讓圖中恰好存在 \(i\) 個聯通塊，則輸出 -1，
樣例輸入1
6
1 2 1 1 2
樣例輸出1
0 -1 1 1 -1 2
資料規模
共 \(10\) 個測驗點，
測驗點 \(1,2,3\) 滿足 \(n≤20\)，
測驗點 \(4,5,6\) 滿足 \(n≤100\)，
對于所有資料，滿足 \(1≤n≤3000\)，
解題思路
對于一棵樹來說，刪去任意一條邊都會使連通塊數目\(+1\)，
那么要判斷能否得到\(k\)個連通塊，我們只需要判斷能否恰好刪去\(k-1\)條邊，
題目要求操作為：洗掉一個節點與子節點之間的所有邊，
那么統計每個節點的子節點數目，然后就變為了01背包可行性問題：
每一個節點都是一個物品，問能否恰好裝滿容量為\(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];
}
}
以上我們只是檢驗了可行性問題，但是題目中還有另外一個要求：操作次數最少，
因為在物品組合中沒有先后順序，所以我們可以通過物品組合中的物品數量來確定操作次數，
只有新的操作次數小于舊的操作次數的時候，我們才進行更新，
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中元素的含義發生了變化：可行/不可行 -> 物品數量；
2）為了與不存在的組合（ans[i][j] = 0）相區分，我們為所有存在的組合物品數量添加偏置bias，也就是說，物品數量 = ans[i][j] - bias，
以上代碼的空間復雜度、時間復雜度均可以接受，可以AC，接下來是優化部分qwq，
因為嫌棄這個演算法的空間復雜度，所以我們對其進行優化，壓縮到二維陣列：
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]];
}
}
還是嫌棄？繼續壓，壓縮到一維陣列：
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554808.html
標籤：其他
上一篇：帶你體驗AI系列之云原生最佳實踐--免費體驗GPT-4教程
下一篇：返回列表