文章目錄

• 暢通工程
• • 題意：
  • 題解：
  • 代碼：
• 小希的迷宮
• • 題解：
  • 代碼：
• Express Mail Taking
• • 題意：
  • 題解：
  • 代碼：
• Reports
• • 題意：
  • 題解：
  • 代碼：
• 放蘋果
• • 題意：
  • 題解：
  • 代碼：
• Monthly Expense
• • 題意：
  • 題解：
  • 代碼：
• String Typing
• • 題意：
  • 題解：
  • 代碼：
• Diagonal Walking
• • 題意：
  • 題解：
  • 代碼：

暢通工程

題意：

最少建多少道路使得兩兩城鎮(zhèn)之間都能連通

題解：

利用并查集
題意很清楚，我們來分析下例子：第一行告訴你，一共有4個點，2條路。下面兩行告訴你，1、3之間有條路，4、3之間有條路。那么整幅圖就被分成了1-3-4和2兩部分。只要再加一條路，把2和其他任意一個點連起來，暢通工程就實現(xiàn)了，那么這個這組數(shù)據(jù)的輸出結(jié)果就是1。

那該怎么辦呢？可以運用學(xué)過的并查集啊！給每個父數(shù)組一個初值-1，代表尚未與其他路接通，每連通一個路，便將-1置去，因此和普通并查集不同的地方為初始化應(yīng)為如下：

for(int i=0;i<=n;i++)pre[i]=-1;

此時Find函數(shù)應(yīng)為：

int Find(int x) {if(pre[x]==-1) return x;return pre[x]=Find(pre[x]);

然后即可簡單的寫出程序，需要注意的是，需要創(chuàng)建的邊數(shù)永遠為城鎮(zhèn)數(shù)減一，然后永遠有一個根節(jié)點未置去-1，程序如下

代碼：

#include<cstdio> int pre[1010]; int find(int a)//find函數(shù)查找他的領(lǐng)導(dǎo) {int leader=a;while(pre[leader]!=leader)//領(lǐng)導(dǎo)不是自己，找自己的上一級領(lǐng)導(dǎo) leader=pre[leader]; int t,b=a;while(b!=leader){t=pre[a];pre[a]=leader;b=t;}return leader; } int main() {int n,m,point1,point2,all,lead1,lead2;//point表示城鎮(zhèn)編號 while(scanf("%d",&n),n){all=n-1;//n個點不連成環(huán)需要n-1條邊 for(int i=1;i<=n;i++){pre[i]=i;//初始化為自己的領(lǐng)導(dǎo)是自己 }scanf("%d",&m);for(int j=0;j<m;j++){scanf("%d%d",&point1,&point2);lead1=find(point1);lead2=find(point2);if(lead1!=lead2){pre[lead2]=lead1;all--;//根據(jù)題目給出的條件每連通一條總數(shù)減一 }}printf("%d\n",all);}return 0; }

小希的迷宮

題解：

該題用并查集做難度不大，判斷是否成環(huán)即判斷是否要合并的兩個結(jié)點的根結(jié)點相同即可，因此稍稍改變了一下join函數(shù)。
需要注意的是還有一點是每個房間必須連通，這一點我一開始忽視了于是過樣例卻WA（因為樣例都是保證全連通）；

代碼：

#include<bits/stdc++.h> using namespace std; int pre[100005]; bool vis[100005];int find(int x){int r = x;while(pre[r] != r){r = pre[r];}int i = x, j;while(i != r){j = pre[i];pre[i] = r;i = j;}return r; }bool join(int x, int y){int i = find(x), j = find(y);if (i != j){pre[j] = i;return true;}else return false; }int main() {int a, b;while(scanf("%d%d", &a, &b) != EOF){for (int i = 1; i <= 100005; ++i) pre[i] = i;memset(vis, 0, sizeof(vis));if (a == -1 && b == -1) break;if (a == 0 && b == 0){printf("Yes\n");continue;}bool flag = 1;while(a != 0){vis[a] = vis[b] = 1;//判斷是否成環(huán)if(!join(a, b)) flag = 0;scanf("%d%d", &a, &b);}int root = 0;//判斷是否全連通for (int i = 1; i <= 100005; ++i)if (vis[i] && pre[i] == i) ++root;if (root > 1) flag = 0;if (flag) printf("Yes\n");else printf("No\n");}return 0; }

Express Mail Taking

題意：

現(xiàn)在有n個柜子依次排列，這些柜子編號從1~n。每個柜子之間距離為1 ，其中柜子編號為k的是特殊的，這是個密碼柜，要向打開其他柜子就必須在這個柜子輸入密碼?，F(xiàn)在你有m個快遞在這些柜子中，你從入口進入，取完快遞后從入口出來，問你需要走的最小距離。

題解：

貪心做法：
由于這些快遞這件是沒有關(guān)聯(lián)的，所以這道題是非常簡單的，在沒有取完快遞之前我們都需要先去密碼柜再輸入密碼再去取快遞，這些步驟都是等效的。 那么這道題為什么會有最小距離呢？重要的就是在取最后一個快遞的時候，我們?nèi)⊥曜詈笠粋€快遞是不是沒必要回到密碼柜了，直接走到出口，故：最后一個快遞的位置顯得極為重要，這也是決定性因素。所以我們想要讓最后一個快遞的位置靠近入口即可。此題則易解。

代碼：

#include<bits/stdc++.h> //POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i為循環(huán)變量，a為初始值，n為界限值，遞增 #define per(i,a,n) for (int i=a;i>=n;i--)//i為循環(huán)變量， a為初始值，n為界限值，遞減。 #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define fi first #define se second #define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//無窮大 const int maxn = 1e6;//最大值。 typedef long long ll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<int, int> pii; //*******************************分割線，以上為自定義代碼模板***************************************//ll t,n,m,k; ll a[maxn]; int main(){//freopen("in.txt", "r", stdin);//提交的時候要注釋掉IOS;while(cin>>t){while(t--){cin>>n>>m>>k;rep(i,0,m-1){cin>>a[i];}sort(a,a+m);ll ans=k-1;per(i,m-1,1){ans+=abs((a[i]-k)*2);}if(a[0]<=k)ans+=k-1;else{ans+=abs((a[0]-k)*2)+k-1;}cout<<ans<<endl;}}return 0; }

Reports

題意：

給你某一天的報告，在這一天總共報告n nn次，其中1 11表示入校，0 00表示離校，當且僅當不連續(xù)存在兩個相同的報告類型時這份報告才算正確?，F(xiàn)在請你判斷這份報告是否有誤。

題解：

根據(jù)題意，直接判斷是否有相鄰元素相等就行

代碼：

#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++)//i為循環(huán)變量，a為初始值，n為界限值，遞增 #define per(i,a,n) for (int i=a;i>=n;i--)//i為循環(huán)變量， a為初始值，n為界限值，遞減。 #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define fi first #define se second #define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//無窮大 const int maxn = 1e5;//最大值。 typedef long long ll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<int, int> pii;int t,n; int a[maxn]; int main(){//freopen("in.txt", "r", stdin);//提交的時候要注釋掉IOS;while(cin>>t){while(t--){cin>>n;rep(i,0,n-1){cin>>a[i];}bool flag=false;rep(i,0,n-2){if(a[i]==a[i+1]){flag=true;break;}}if(flag)cout<<"NO"<<endl;elsecout<<"YES"<<endl;}}return 0; }

放蘋果

題意：

把M個同樣的蘋果放在N個同樣的盤子里，允許有的盤子空著不放，問共有多少種不同的分法？（用K表示）5，1，1和1，5，1 是同一種分法。

題解：

：首先，設(shè) i個蘋果放在 k個盤子里的放法總數(shù)是 f(i,k) ，分類討論有兩種情況
（1）當 k > i 時，f ( i , k ) = f ( i , i )
（2）當 k <= i時，總放法 = 有盤子為空的放法+沒盤子為空的放法
f ( i , k ) = f ( i , k - 1 ) + f ( i - k , k )

代碼：

#include<iostream> using namespace std; //設(shè) i個蘋果放在 k個盤子里的放法總數(shù)是 f(i,k) int f(int i,int k){if(k > i){//當 k > i時，f(i,k) = f(i,i) return f(i,i);}if(i == 0)return 1;if(k == 0){return 0;}//k <= i時，總放法 = 有盤子為空的放法+沒盤子為空的放法//f(i,k) = f(i,k-1) + f(i-k,k) return f(i,k-1)+f(i-k,k); }int main(){int t,i,k,count=0;cin>>t;while(t--){cin>>i>>k; cout<<f(i,k)<<endl;}return 0; }

Monthly Expense

題意：

給出農(nóng)夫在n天中每天的花費，要求把這n天分作m組，每組的天數(shù)必然是連續(xù)的，要求分得各組的花費之和應(yīng)該盡可能地小，最后輸出各組花費之和中的最大值

題解：

各組最小和的最大值應(yīng)該用二分做，枚舉一個答案，然后驗證是否合理，不斷縮小范圍最后確定答案

代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 100001 #define MOD 123 #define E 1e-6 using namespace std; int n,m; int a[N]; bool judge(int value)//判斷當前花費可把n分成幾組 {int sum=0;//花費總和int cnt=1;//初始時只有一組for(int i=0;i<n;i++)//枚舉每天花費{if(sum+a[i]<=value)sum+=a[i];else{sum=a[i];cnt++;}}if(cnt>m)//若分組數(shù)比規(guī)定數(shù)要多，則mid偏小，需調(diào)整左值return false;else//若分組數(shù)比規(guī)定數(shù)要少，則mid偏大，需調(diào)整右值return true; } int main() {while(scanf("%d%d",&n,&m)!=EOF){int left=0,right=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);left=max(left,a[i]);right+=a[i];}int mid;while(left<=right){mid=(left+right)/2;if(judge(mid))right=mid-1;elseleft=mid+1;}printf("%d\n",mid);}return 0;}

String Typing

題意：

給一個字符串，可以復(fù)制某一段字符，問最少需要多少步能將其輸出，比如abcabcd，先輸入abc然后再賦值abc再輸入d就只需要5步。
復(fù)制的這段字符 必須是從字符串的0位置開始復(fù)制的 而且只能粘貼一次 例abcabcabc 輸出為7

題解：

string中的str.substr（i，j） 截取字符串str第i位置開始的長度為j的一段字符
從開始截取長度為i的一段，看是否和后面有重復(fù)的

代碼：

#include <bits/stdc++.h> //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 10010, INF = 0x7fffffff;int main() {int n;string str;cin>> n >> str;int res = n;for(int i=1; i<=n/2; i++)if(str.substr(0, i) == str.substr(i, i)) res = n - i + 1;cout<< res <<endl;return 0; }

Diagonal Walking

題意：

給出n個操作，相連的U和R 可以看為一步，問一共多少步

題解：

直接按照題目模擬即可，遇到UR或者RU就跳過，其他的計算步數(shù)

代碼：

#include <bits/stdc++.h> typedef long long ll; using namespace std; int main(){int n;cin >> n;string s;cin >> s;int u = 0, r = 0, ans = 0;int len = s.size();for(int i = 0; i < s.size(); i++){if((s[i] == 'U' && s[i+1] == 'R') || (s[i] == 'R' && s[i+1] == 'U')){i++; // 相連的U和R看為一步}ans++;}cout << ans << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的一起开心寒假训练总复习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。