北華大學計算機程序設計算法提高訓練營個人賽（無L）

明明是北華大學的訓練賽，結果被屠榜了hhh，L防ak題吧這也太難了

A-洛姐打題日記

題目描述

洛姐開開心心地打題，可是她看不懂評測機給的判定結果，你能幫幫她嗎。

摘自ACM評分標準：

競賽進行5個小時，一般有7道或以上試題，由同隊的三名選手使用同一臺計算機協作完成。當解決了一道試題之后，將其提交給評測機，由評測機判斷其是否正確。若提交的程序運行不正確，則該程序將被退回給參賽隊，參賽隊可以進行修改后再一次提交該問題。程序判定結果有如下7種：
1、Accepted. ——通過！(AC)
2、Wrong Answer.——答案錯。(WA)
3、Runtime Error.——程序運行出錯，意外終止等。(RE)
4、Time Limit Exceeded. ——超時。程序沒在規定時間內出答案。(TLE)
5、Presentation Error. ——格式錯。程序沒按規定的格式輸出答案。(PE)
6、Memory Limit Exceeded. ——超內存。程序沒在規定空間內出答案。(MLE)
7、Compile Error. ——編譯錯。程序編譯不過。(CE)

（部分OJ還有不同的判定結果，不過在這里不予考慮）

輸入描述:

輸入一行，表示判定結果的簡寫

輸出描述:

輸出一行，表示判定結果的英文全稱

輸入

AC

輸出

Accepted

AC代碼

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n' #define int ll typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PII; const int N = 2e5 + 50, MOD = 1e9 + 7;signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);string s;cin>>s;if(s=="AC")cout<<"Accepted";else if(s=="WA")cout<<"Wrong Answer";else if(s=="RE")cout<<"Runtime Error";else if(s=="TLE")cout<<"Time Limit Exceeded";else if(s=="PE")cout<<"Presentation Error";else if(s=="MLE")cout<<"Memory Limit Exceeded";else cout<<"Compile Error";return 0; }

B-雞兔同籠

題目描述

雞兔同籠，但，這是外星牧場！！

已知每只外星雞有一頭 x 只腳，每只外星兔有一頭 y 只腳。（x≠y）

外星人為了數學教育，曾出過這樣一道題。現將一些外星雞和外星兔關進同一個籠子中，已知籠子中有 H 個頭、F 只腳，求籠子中有多少只外星雞和多少只外星兔。

輸入描述:

輸入由多個測試用例組成。第一行包含一個整數 ttt，表示測試案例的數量。測試用例的描述如下。（1≤t≤2?105） 每個測試樣例輸入一行四個正整數 x,y,H,Fx,y,H,Fx,y,H,F ，含義見題目描述。（1≤x,y,H,F≤109,x!=y）

輸出描述:

對于每個測試樣例，輸出一行兩個正整數（用空格分隔），分別表示外星雞的數量和外星兔的數量。

輸入

2 2 4 8 24 3 4 12 41

輸出

4 4 7 5

問題解析

設有a個雞，b個兔子。方程就是a+b=H和a*x+b *y=F。解方程即可。

AC代碼

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n' #define int ll typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PII; const int N = 2e5 + 50, MOD = 1e9 + 7;void solve() {int x,y,h,f;cin>>x>>y>>h>>f;int b=(h*x-f)/(x-y);int a=h-b;cout<<a<<" "<<b<<endl; }signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t;cin>>t;while(t--)solve();return 0; }

C-小杜的簽到

題目描述

小袁經常苦惱于找不到好題，于是，一旁的小杜獻上了一道錦囊妙題。

現有一個長為 n 的數組 a。定義 ：
$$F(a)=\sum _{i=1}^{n?1}(a_{i+1}?a_i)$$

每次操作可以選擇一個 i，滿足
$$1\le i<n$$
，并交換
$$ai和ai+1$$
任意次數操作后（可能是 0 次），小杜想知道 F(a) 的最小值和最大值分別是多少。

輸入描述:

第一行輸入一個正整數 n，表示數組 a 的長度。（2≤n≤106） 第二行輸入 n 個正整數 ai，表示這個數組。（1≤ai≤109）

輸出描述:

輸出一行兩個正整數，分別表示 F(a)F(a)F(a) 的最小值和最大值。（用空格分隔）

輸入

3 3 2 1

輸出

-2 2

問題解析

把數組升序排序后得到的就是最大值，乘上-1（或把數組降序排序后再算一遍）得到的就是最小值。

AC代碼

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n' #define int ll typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PII; const int N = 2e5 + 50, MOD = 1e9 + 7;signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cin>>n;vector<int>v(n);for(int i=0;i<n;i++)cin>>v[i];sort(v.begin(),v.end());int sum=0;for(int i=1;i<n;i++){sum+=v[i]-v[i-1];}cout<<-1*sum<<" "<<sum<<endl;return 0; }

D-我超！原！

題目描述

你在城中，見過枯萎的櫻花樹么?這種「枯」之美，讓我想到春天盛開之景。不過別人似乎并不這么想，不再開花的櫻樹會被移走…就算一次也好，真想看到它再次開放。

什么？原來你也玩原神。

作為神里凌華的單推人，小袁在神里凌華上線的第一天就將她拿下了。小袁想快速培養她。

小袁想要將神里凌華升到 x 級，角色的初始等級為 1 級，第一次升級需要 1000 經驗，之后每升一級需要花費比上一次升級多 y 點的經驗值。小袁不想浪費經驗材料。

原神中有三種可以加經驗的材料：

? 大英雄的經驗：20000點；

? 冒險者的經驗：5000 點；

? 流浪者的經驗：1000 點。

已知小袁三種材料擁有的數量分別是：A,B,C，求小袁將神里凌華升至 x 級后，溢出的經驗最少是多少；或者告訴小袁，他擁有的材料不足以將其升至 x 級。

輸入描述:

第一行輸入兩個正整數 x,y 的含義如題目描述所述。（1≤x,y≤106） 第二行輸入三個整數 A,B,C，表示小袁三種材料擁有的數量。（0≤A,B,C≤109）

輸出描述:

如果小袁能將神里凌華升至 x 級，輸出一行一個非負整數，表示溢出的經驗的最小值。 否則輸出一個字符串"QAQ"（不含引號），委婉地告訴小袁他不能將神里凌華升至 x 級。

輸入

5 750 1 2 5

輸出

500

說明

升至5級需花費8500經驗，使用1“冒險者的經驗”和4“流浪者的經驗”后，溢出500經驗。

問題解析

一開始還想著完全背包，一看復雜度就肯定不是。

直接貪心模擬，先等差數列前n項和算出需要多少經驗才能升到x級，但是要注意初始是1級，所以我們算的是前x-1項和。再算一下我們全部資源有多少經驗，如果全部資源都用上經驗也不夠就輸出QAQ。

直接貪心，能用20000的就用，用完了或用了會超就用5000，再是1000，最后離升滿級就差不到1000經驗，我們再看1000的有沒有，沒有用5000，再沒有用20000。

但是有一點，比如所需經驗是17000，5000的有4個，1000的有1個，如果我們用了三個5000后用一個1000的，這樣還剩1000經驗才到目標，此時1000的用完了，我們只能用5000的，超出經驗4000，但我們要是一開始就用4個5000的，那超出經驗3000。所以我們在算的過程中可以多加一個步驟，我們不繼續細分而是直接用當前檔次升滿級看需要多少經驗。最后這兩種途徑的取最小值即可。

AC代碼

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n' #define int ll typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PII; const int N = 2e5 + 50, MOD = 1e9 + 7;signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);ll n, m, a, b, c;cin >> n >> m >> a >> b >> c;ll res = 1000 * (n-1) + ((n-2) * (n - 1)) / 2 * m;ll ans = a * 20000 + b * 5000 + c * 1000;if (res > ans){cout << "QAQ" << endl;return 0;}ans=1e18;if (a * 20000 >= res){a -= res / 20000;res %= 20000;if(a>0)ans=min(ans,20000-res);}else{res -= a * 20000;a = 0;}if (b * 5000 >= res){b -= res / 5000;res %= 5000;if(b>0)ans=min(ans,5000-res);}else{res -= b * 5000;b = 0;}if (c * 1000 >= res){c -= res / 1000;res %= 1000;if(c>0)ans=min(ans,1000-res);}else{res -= c * 1000;c = 0;}if (res == 0)cout << res << endl;else if (c != 0)cout << min(ans,1000 - res) << endl;else if (b != 0)cout << min(ans,5000 - res) << endl;else if (a != 0)cout << min(ans,20000 - res) << endl;return 0; }

E-佳樂的迷宮

題目描述

佳樂特別喜歡玩走迷宮，是當今世界的迷宮大師。現在，有一座特殊的二維矩陣迷宮橫空出世，佳樂想前去挑戰一下。已知有 k 個入口和 1 個出口，請你幫佳樂看看，從哪幾個入口進入能夠走到出口。

輸入描述:

第一行輸入三個正整數 n,m,k ，分別表示二維矩陣迷宮的長寬，入口的數量。（1≤n,m≤1000） 接下來 n 行每行輸入 m 個字符， '.' 表示為道路，'#' 表示為墻壁。 接下來 k 行每行輸入兩個正整數 xi,yi，表示入口的位置。保證入口所在的地方為 '.' 。 接下來 1 行輸入兩個正整數X,Y，表示出口的位置。保證出口所在的地方為 '.' 。保證所有出口入口互不相同。（1≤xi,X≤n,1≤yi,Y≤m）

輸出描述:

第一行輸出一個整數 p，表示有幾個入口進入能走到出口。 第二行輸出 p 個整數，第 i 個數 si ，表示從第 si 個入口進入可以走到出口。(si 按順序輸出，之間用空格隔開）

輸入

3 3 2 .## #.. ..# 1 1 3 1 2 3

輸出

1 2

問題解析

可以先把入口的位置都記錄下來，然后我們以出口位置進行bfs(dfs)，看那些位置是出口能走到的，那么對應的，這個位置就是能走到出口的，我們再去判斷之前那些出口位置有哪些是出口能走到的即可。

AC代碼

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n' #define int ll typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PII; const int N = 2e5 + 50, MOD = 1e9 + 7;int st[1050][1050]; int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }; signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n, m, k;cin >> n >> m >> k;vector<string>v(n);for (int i = 0; i < n; i++)cin >> v[i];vector<PII>ans(k);for (int i = 0; i < k; i++)cin >> ans[i].first >> ans[i].second;int x, y;cin >> x >> y;queue<PII>que;que.push({ x,y });st[x][y] = 1;while (!que.empty()){int len = que.size();for (int i = 0; i < len; i++){auto t = que.front();que.pop();for (int j = 0; j < 4; j++){int a = t.first + dx[j], b = t.second + dy[j];if (a >= 1 && b >= 1 && a <= n && b <= m &&v[a-1][b-1] == '.' && st[a ][b] == 0){st[a ][b] = 1;que.push({ a,b });}}}}vector<int>res;int cnt = 0;for (auto i : ans){cnt++;if (st[i.first][i.second]){res.push_back(cnt);}}cout << res.size() << endl;for (auto i : res)cout << i << " ";return 0; }

F-三四五

題目描述

杰哥和洛姐在玩游戲，他們在玩經典的石子游戲。

現在有三堆石子，分別有 n0,n1,n2 個石子。

杰哥和洛姐輪流進行游戲，每次游戲將同時從三堆石子中分別拿走 x0,x1,x2 個石子，滿足 x0∈[1,3],x1∈[1,4],x2∈[1,5]，保證石堆中石子數量時刻為非負整數。

當一個人在任意一堆中無法拿走石子（即石堆中，有至少一堆的余量為0），他將輸掉游戲。

洛姐先手杰哥后手。洛姐想知道，她能否戰勝博弈天才杰哥。（雙方都使用最優策略進行游戲）

輸入描述:

多組輸入，第一行輸入 t，表示樣例數量。（1≤t≤106） 接下去 t 行每行輸入三個正整數 n0,n1,n2，表示三堆石子的初始數量。（0≤n0,n1,n2≤109）

輸出描述:

如果洛姐獲勝，則輸出一行字符串 "(^-^)" （不包含引號）。 否則輸出一行字符串 "(T-T)" （不包含引號）。

輸入

2 3 4 5 0 0 0

輸出

(^-^) (T-T)

問題解析

升級辦nim游戲，這里先說一個nim游戲的必勝秘訣，如果你每次能拿最多x個石頭，那么只要總石頭數不是（x+1）的倍數，你就可以贏，如果是則必輸。

所以只要第一堆石頭是4的倍數or第二堆是5的倍數or第三堆是6的倍數，那么這堆石頭我們肯定會輸。但這題不是單純的看是否必輸or必贏，而是看誰先輸，比如石頭數是1，100，20，雖然第二堆石頭是5的倍數，我們必輸，但是第一堆石頭只有1個，我們拿完后對面就直接輸了，第一堆石頭可以在第一輪分出勝負，而第二堆要20輪才能分出勝負，顯然是我們贏。所以我們要看，輸最快會在第幾輪輸，贏最快會在第幾輪贏，誰小，那就說明我們會贏（輸）。

AC代碼

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n' #define int ll typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PII; const int N = 2e5 + 50, MOD = 1e9 + 7;void solve() {int a,b,c;cin>>a>>b>>c;bool flag=true;int winer=1e9,loser=1e9;if(a%4==0)loser=min(loser,a/4);else winer=min(winer,a/4);if(b%5==0)loser=min(loser,b/5);else winer=min(winer,b/5);if(c%6==0)loser=min(loser,c/6);else winer=min(winer,c/6);if(winer<loser)cout<<"(^-^)"<<endl;else cout<<"(T-T)"<<endl; }signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t;cin>>t;while(t--)solve();return 0; }

G-杰哥的疑問

題目描述

有一個巨大的數組，這個數組充滿了神秘感。

杰哥給出了一個數 m。杰哥想知道，這個數組中有多少對數的和等于給定的數，即，有多少對 (i,j) 滿足 ai+aj=m 且 1≤i<j≤n。

快幫幫杰哥！

輸入描述:

第一行輸入兩個正整數 n,m，分別表示數組的元素個數，以及杰哥給定的數。（1≤n≤106,0≤m≤109） 第二行輸入 n 個正整數，第 i 個正整數為 ai。（0≤ai≤109）

輸出描述:

輸出一行一個正整數，表示滿足條件的對的數量。

輸入

5 5 1 1 2 3 4

輸出

3

問題解析

可以用哈希表記錄一下每個數的出現次數，然后對于一個數x來說，能和他相加后等于m的數肯定是m-x。那我們只要看m-x這個數出現了多少次，且x又出現了多少次，就可以知道x和m-x一共可以組合出多少個滿足條件的數對。

AC代碼

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n' #define int ll typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PII; const int N = 2e5 + 50, MOD = 1e9 + 7;signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n,m,x,cnt=0;cin>>n>>m;unordered_map<int,int>mymap;for(int i=0;i<n;i++){cin>>x;cnt+=mymap[m-x];mymap[x]++;}cout<<cnt;return 0; }

H-墨染的斯汀木

題目描述

一天，佳樂拿來了一塊神奇的斯汀木作為禮物送給洛姐，這塊木頭上印有一串神秘的字符。字符僅包含大寫或小寫的拉丁字母。

洛姐對其上的字符串著了迷，于是，她通過某種操作，將這一串字符轉譯成了屬于自己的字符串，并記錄了下來。

已知洛姐轉譯中可以進行多次（可能是 0 次）以下的操作：

? 將相鄰兩個小寫字符合并成一個對應的大寫字符，如 “aa” -> “A”；

? 將一個大寫字符拆分成兩個對應的相鄰的小寫字符，如 “B” -> “bb”；

春去秋來。一天，洛姐發現斯汀木不知什么時候被墨水浸透了，其上的部分字符已經看不清了。意外的是，所有字符均還能區分出大小寫。

于是，洛姐拿出了轉譯的字符串，試圖還原斯汀木上的原字符串。

輸入描述:

第一行輸入一行一個字符串 s0，表示斯汀木上的原字符串。該字符串包含大寫或小寫的拉丁字母，以及 '!' 和 '?' 。'!' 代表一個看不清的大寫拉丁字母，'?' 代表一個看不清的小寫拉丁字母。 第二行輸入一行一個字符串 s1，表示洛姐轉譯后的字符串。該字符串僅包含大寫或小寫的拉丁字母。 （1≤∣s0∣,∣s1∣≤106）

輸出描述:

輸出一行一個字符串，表示還原后斯汀木上的原字符串。該字符串僅包含大寫或小寫的拉丁字母。

輸入

ac!b acccb

輸出

acCb

問題解析

為了方便，我們可以先把沒被污染的字符串全部變成小寫字母的形式，然后我們再根據第一個字符串中大小寫的情況來還原字符串即可。

AC代碼

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n' #define int ll typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PII; const int N = 2e5 + 50, MOD = 1e9 + 7;signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);string a,b,s,c;cin>>a>>b;int n=a.size(),m;for(auto i:b){if(i>='a'&&i<='z')c+=i;else {c+=(i+32);c+=(i+32);}}m=c.size();int l=0,r=0;while(l<n&&r<m){if(a[l]=='?'||(a[l]>='a'&&a[l]<='z'))s+=c[r++];else {s+=(c[r]-32);r+=2;}l++;}cout<<s<<endl;return 0; }

I-Darling（Easy.)和J-Darling（Hard.）

題目描述

那似乎是比翼鳥，這種鳥天生單翼，須靠雌雄二鳥相互依偎，否則無法翱翔天際，是種有缺陷的生物。但是，不知為何，我卻認為這種生活方式是美好的，感受到了其中的美妙。

注：本題與Hard.版唯一的區別在數據范圍上

有 n 窩比翼鳥棲息在森林中，同一窩的比翼鳥性別相同。因為天生單翼的原因，他們并不能通過飛翔來尋找另一半，只能通過森林中的 m 條陸路，來尋找彼此。

（n 個點與 m 條邊形成了一個無向連通圖，每條雙向邊的長度都為 1）

小袁了解了這種情況，不禁感慨萬分。

小袁想知道，一只比翼鳥想要找到另一半，最短需要走多少的路程，即，比翼鳥到異性窩的最短路程。（假設每一窩比翼鳥的數量為無限大）

小袁總共有 ttt 個疑問，每個疑問相互獨立。

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-aZiQIgcg-1657286971919)(https://uploadfiles.nowcoder.com/images/20220704/0_1656925795549/05266877D72B9576E8D907074DDDA274)]

輸入描述:

第一行輸入 n,m,t ，分別表示比翼鳥的數量、比翼鳥之間的道路數量，以及小袁疑問的數量。（1≤n,t≤1000,(n?1)≤m≤min(1000,n?(n?1)2)(n-1)\leq m\leq min(1000,2n?(n?1))） 第二行輸入 nnn 個整數 si，表示每一窩比翼鳥性別，'0' 表示雌性，'1' 表示雄性。（si∈{0,1}） 接下去 m 行，每行輸入兩個正整數 ui,vii，表示 ui 與 vi 之間有一條長為 1 的雙向邊。（1≤ui,vi≤n，ui!=vi） 接下去 t 行，每行一個正整數 qi，表示詢問的比翼鳥在第 qi 窩。（1≤qi≤n）

輸出描述:

輸出 t 行，每個疑問輸出一行一個正整數，表示第 qi 窩的比翼鳥到異性窩的最短路程，如果無法到達異性窩，則輸出 ′?1′（不包含引號）。

輸入

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

輸出

1 2 2 3 1 1

問題解析

i題數據類型教少，建圖之后對于每次詢問我們都跑一便bfs來求最近的異性即可。

每次向和自己鏈接的其它點看去，如果這個點和我們的性別不同，那根據bfs特性，這個就是我們最近的異性，如果周圍沒有異性，那我們就把和自己相鄰的點再送去下一輪bfs，同時步數+1。

AC代碼

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n' #define int ll typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PII; const int N = 2e5 + 50, MOD = 1e9 + 7;unordered_map<int,vector<int>>mymap; signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n,m,t,x,y;cin>>n>>m>>t;vector<int>sex(n+1);for(int i=1;i<=n;i++)cin>>sex[i];for(int i=0;i<m;i++){cin>>x>>y;mymap[x].push_back(y);mymap[y].push_back(x);}while(t--){int res=0;cin>>x;queue<int>que;que.push(x);y=-1;vector<int>st(1001);while(!que.empty()){res++;int len=que.size();for(int i=0;i<len;i++){int tt = que.front();que.pop();for(auto j:mymap[tt]){if(st[j]==0){if(sex[j]!=sex[x]){//找到了，我們直接結束bfsy=res;break;}else {que.push(j);st[j]=1;}}}if(y!=-1)break;}if(y!=-1)break;}cout<<y<<endl;}return 0; }

至于j題，數據提到了1e6，這樣再用上面的方法肯定會t。但還是可以用bfs來寫。

我們可以把問題分成兩部分：給性別為0的找最近的1，給性別為1的找最近的0。用一個二維數組f來存結果：f[i] [0]表示i到最近的0的距離，f[i] [1]表示i到最近的1的距離。

求哪個性別，就可以先遍歷全部的點，把那個性別的點存入隊列里，并且把f[i] [當前性別]設為0，因為里它最近的這個性別就是他自己。再進行bfs，我們只bfs到哪些性別和我們不同的點上，如果j是和i相連且性別不同的點，那么就有：

f[j] [當前性別]=f[i] [當前性別]+1；（注意當前性別不是說j的性別，而是我們現在求的性別）

這樣在k次詢問時，我們可以先判斷詢問的點是哪個性別，再去對應的數組找結果。

AC代碼

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n' #define int ll typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PII; const int N = 1e6 + 50, MOD = 1e9 + 7; unordered_map<int, vector<int>>mymap; int f[N][2], sex[N]; int n, m, t, x, y;void bfs(int x) {queue<int>que;for(int i=1;i<=n;i++)if (sex[i] == x){que.push(i);f[i][x] = 0;}while (!que.empty()){int ans = que.front();que.pop();for (auto i : mymap[ans]){if (f[i][x] == -1 && sex[i] != x){f[i][x] = f[ans][x] + 1;que.push(i);}}} }signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m >> t;for (int i = 1; i <= n; i++)cin >> sex[i];for (int i = 0; i < m; i++){cin >> x >> y;mymap[x].push_back(y);mymap[y].push_back(x);}memset(f, -1, sizeof f);bfs(0);bfs(1);while (t--){cin >> x;if (sex[x]){cout << f[x][0] << endl;}else cout << f[x][1] << endl;}return 0; }

K-小杜返校記

題目描述

小杜因為家鄉疫情原因，不能及時返校，可是等他花費 n 元訂好返校機票后，學校這邊卻因疫情原因封校，禁止出入。無可奈何的小杜只能取消機票，在家安心上網課。

已知小杜是在起飛前 t 小時退的票。現在小杜想知道退票并扣除手續費后，自己還能得到多少錢。

以下為小杜機票所屬航空公司的自愿退票手續費收費標準表格。

艙位等級航班起飛前 14 天（ 336 小時）（含）之前航班起飛前 14 天（不含）至 48 小時（含）航班起飛前 48 小時（不含）至 4 小時（含）航班起飛前 4 小時（不含）至航班起飛后

頭等艙	免費	p1,1%	p1,2%	p1,3%
商務艙	免費	p2,1%	p2,2%	p2,3%
經濟艙	免費	p3,1%	p3,2%	p3,3%

（根據真實事件改編）

輸入描述:

第一行輸入兩個正整數 n 和 t ，n 和 t 的含義如題目描述所示。 第二行輸入一行字符，表示小杜機票的艙位等級。（“First Class”表示頭等艙；“Business Class”表示商務艙；“Economy Class”表示經濟艙） 接下來輸入3行，每行3個正整數。第 i 行第 j 列表示 pi,j。 (1≤n,t≤109，1≤pi,j≤100)

輸出描述:

輸出一個小數，四舍五入保留 2 位小數，表示小杜退票后還能得到的錢

輸入

742 30 Economy Class 5 5 10 5 10 15 5 20 40

輸出

593.60

問題解析

按照艙位和時間找對應的手續費率pi，計算式：n=n(1-pi/100)*。

AC代碼

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip>#define endl '\n' #define int ll typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PII; const int N = 2e5 + 50, MOD = 1e9 + 7;signed main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);vector<vector<double>>v(3,vector<double>(3));double money;int h=0;cin>>money>>h;string s,fw;cin>>s>>fw;for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>v[i][j];int x;if(s[0]=='F')x=0;else if(s[0]=='B')x=1;else x=2;if(h>=336)money=money;else if(h>=48)money=money*(1-v[x][0]/100);else if(h>=4)money=money*(1-v[x][1]/100);else money=money*(1-v[x][2]/100);cout << fixed << setprecision(2) << money << endl;return 0; }

總結

以上是生活随笔為你收集整理的北华大学计算机程序设计算法提高训练营个人赛（无L）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。