NEUQ-ACM實驗班訓練001，1-10部分題解，待補充
7-4 字串的冒泡排序 (10分)
我們已經知道了將N個整數按從小到大排序的冒泡排序法，本題要求將此方法用于字串序列，并對任意給定的K（<N），輸出掃描完第K遍后的中間結果序列，
輸入格式：
輸入在第1行中給出N和K（1≤K<N≤100），此后N行，每行包含一個長度不超過10的、僅由小寫英文字母組成的非空字串，
輸出格式：
輸出冒泡排序法掃描完第K遍后的中間結果序列，每行包含一個字串，
輸入樣例：
6 2
best
cat
east
a
free
day
輸出樣例：
best
a
cat
day
east
free
核心思路:確定第K次的排序，理解冒泡排序原理是本質；
冒泡排序
先敲一遍冒泡：
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[100];
int n=0;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){//這里存在了多次重復判斷 復雜度O(n^2);
if(a[j]>a[j+1])
swap(a[j],a[j+1]);
for(int i=0;i<n;i++) cout<<a[i]<<" ";
//優化：
for(int i=0;i<n;i++)
for(int j=0;j<n-i-1;j++)//已經歸位的就沒必要排了
//復雜度為O((n^2-n)/2)
而最外層實際就是控制掃描次數（最多n-1次）因此K<n-1，最里層
通過調整最外層K的引數，就可以實作輸出任意K的遍歷中間排序狀況；
在字串的冒泡排序中，利用string字串自帶的字典序排序即可實作判斷
string a[100]
for(int i=0;i<n;i++){
for(int j=0;i<n-j-1;j++
if(a[j]>a[j+1]) swap balabala.....
7-6 房間 (10分)
終于到了假期了，老師決定帶領ACM隊員們出去游山玩水，計劃出行兩天，這樣的話中間就需要找個地方住宿一晚，
恰巧，老師帶領隊員們來到了這么一所酒店，這所酒店只有雙人間（最多住兩人）和三人間（最多住三人），但是價格不同，現在我們算上老師，一共有 n 個人，酒店的雙人間價格是 a 元，三人間價格是 b 元，現在老師想知道怎樣安排房間才能使得花銷最小，你能幫助老師計算出最小的花銷嗎？
輸入格式:
第一行給出一個正整數 T(1≤T≤1000)，代表測驗資料的組數，
接下來 T 行每行給出三個正整數 n,a,b,1≤n,a,b≤10
?9
?? ，含義如題，
輸出格式:
輸出包含 T 行，每行對應一組樣例的輸出，
輸入樣例:
2
2 20 200
3 20 20
輸出樣例:
20
20
分析：需要明確的是，雙人間價格未必比三人間價格便宜，再此基礎上，如果遍歷所有組合是肯定超時的，因此需要推出最優子結構———利用每個人的性價比，也就是每個人住房的價格進行分類討論，
if(a/2<b/3){
if(a%2==0) cout<<n/2*a<<endl;
else cout<<min((n/2+1)*a,(n/2-1)*a+b)<<endl;
//一個數不能整除2，只能余1，因此這個人要么住二人間，要么和其中兩個人一起住三人間，在最小值的公式左邊中，考慮到二人間此時性價比最高，因此是歸進二人間而不是一起住三人間，
//在三人間性價比最高的前提下
if(n%3==0)
cout<<n/3*b<<endl;
else if(n%3==1)//產生三種討論，第一種是和三個人一起住兩個二人間，第二種是1個人住二人間，第三種是1個人住三人間；
cout<<min(min((n/3-1)*b+2*a,n/3*b+a),(n/3+1)*b)<<endl;
else if(n%3==2)
cout<<min(n/3*b+a,(n/3+1)*b)<<endl;
附完整代碼
#include<bits/stdc++.h>
using namespace std;
int main(){
int t=0;
cin>>t;
while(t--){
long long n,a,b;
cin>>n>>a>>b;
if(n==1||n==2) cout<<min(a,b)<<endl;
else{
if(a*3<=b*2){
if(n%2==0)
cout<<n*a/2<<endl;
else cout<<min((n/2+1)*a,(n/2-1)*a+b)<<endl;
}
else{
if(n%3==0) cout<<n/3*b<<endl;
else if(n%3==1) cout<<min(min((n/3-1)*b+2*a,(n/3)*b+a),(n/3+1)*b)<<endl;
else if(n%3==2)
cout<<min((n/3+1)*b,(n/3)*b+a)<<endl;
}
}
}
return 0;
}
7-9 求區間和 (10分)
本題會給你一段長度為N的整數序列，并進行K次詢問，每次詢問要求你給出區間a到b的和（序列下標由1到N），由于區間和可能較大，請你輸出它對10000019取模的結果，
（注意：如果你想不到高效的做法，可以用樸素演算法得到一部分分，但本題滿分需要你用一個比較高效的做法，）
輸入格式:
首先一行整數N，代表序列長度，
接下來一行N個整數，為序列內容，
接下來一行整數K，代表對區間和的詢問次數，
接下來K行，每行兩個整數a和b，請你輸入序列的第a到b號元素（含）的和取模后的結果，
輸出格式:
一共K行，每行一個整數，代表詢問的區間和取模后的結果，
輸入樣例:
在這里給出一組輸入，例如：
5
1 2 3 4 5
3
1 5
2 3
3 3
輸出樣例:
在這里給出相應的輸出，例如：
15
5
3
資料限制:
N<=1e6;
??K<=1e5;
分析：樸素思路：每詢問一次就處理一次，時間復雜度為O(n*k) 題里的資料限制使得樸素演算法是超時的，Omax（nk)=1e11>1e8;
正常思路：利用前綴和處理詢問時直接做差即可，復雜度O（N+K）
樸素思路：
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
int main(){
int n=0;
long a[maxn];
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int k=0;
cin>>k;
while(k--){
long long sum=0;
int l,r=0;
cin>>l>>r;
for(int i=l;i<=r;i++)
sum+=a[i];
cout<<sum%10000019<<endl;
}
return 0;
優化思路：
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int main(){
int n=0;
int sum[maxn];
cin>>n;
for(int i=1;i<=n;i++)
long x=0;
cin>>x;
sum[i]=sum[i-1]+x;//先做前綴和，準備進行k次詢問；
int k=0;
cin>>k;
while(k--){
int l,r=0;
cin>>l>>r;
cout<<(sum[r]-sum[l-1])%10000019<<endl;//類似數列已知和求其中幾項，例如s4-s2=a3+a4;
}
return 0;
7-10 抽卡游戲 (10分)
本題的靈感來源于一個古典的概率模型，
Alice 在一個卡池里抽卡，里面有 x 張 s 卡和 y 張 a 卡，
Alice 每次會不放回的隨機從卡池中抽出一張卡，
Bob 在一旁看 Alice 抽卡并對每次的結果進行預測：
若卡池里 s 卡的數量多于 a 卡，Bob 會猜 Alice 抽出 s 卡，
反之則會猜測 Alice 抽出 a 卡，
但是如果當卡池里的兩種卡的數量相等的時候，Bob 就不對抽卡的結果做任何的猜測了，
Alice 會一直抽卡，直到卡池空為止，
現在告訴你初始的時候卡池里 s 卡和 a 卡的數量，你能算算 Bob 期望下猜對多少次？
輸入格式:
在一行中給出兩個整數 a,b(1≤a,b≤1e5)
輸出格式:
一個實數表示期望，四舍五入保存兩位小數，
輸入樣例:
1 1
輸出樣例:
1.00
樣例解釋：
初始局面的時候 Bob 不做任何猜測，第一次抽完之后，第二次抽的時候不管剩下的是哪一種卡，Bob 都能猜對，所以期望是1.00
分析: 難點在于，1.Bob不做猜測則概率是0；
2.抽和猜是兩部分,抽是具象的，猜有猜對和猜錯，因此兩部分的期望都要算;
3:利用遞推公式計算E(a,b);
??證明如下，我們令Ex(a,b)表示相應的期望，
Ex(1,1) = 1; Ex(1,2) = Ex(2,1) = 2/3+(2/3)(0+1)+(1/3)(1+1) = 2;
EX(a,b) =(a/a+b)+ (a/a+b)*Ex(a-1,b)+(b/a+b)Ex(a,b-1) //前提是a>b; 第二部分是條件概率，在第一次抽的基礎上進行下一次的概率計算
數學歸納法：Ex(a-1,b) = a-1;Ex(a,b-1) = b-1;
EX(a,b) =(a/a+b)+ (a/a+b)(a-1)+(b/a+b)*a = a(a+b)/(a+b) = a;
同理當a = b 或 a < b證法相同
因此，結論是，只要判斷a,b中的最大值即可
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b=0;
cin>>a>>b;
cout<<(a>b? a:b)<<endl;
return 0;
7-8 最長上升子序列 (10分)
給定一個序列，求它的一個遞增子序列，使它的元素個數盡量多，求該序列的最長上升子序列中元素個數，例如序列1,6,2,5,4,7的最長上升子序列是1,2,5,7或1,2,4,7，則其最長上升子序列中的元素個數為4，
輸入格式:
第一行中輸入序列的個數（不超過100），第二行中輸入每個元素，以空格隔開，
輸出格式:
輸出該序列中最長上升子序列中的元素個數，
輸入樣例:
在這里給出一組輸入，例如：
6
1 6 2 5 4 7
輸出樣例:
在這里給出相應的輸出，例如：
4
分析：初始的每一個子序列長度均為1,當到達第i位的時候，從第1位進行判斷，如果滿足小于，那么子序列的長度++，反之，保留當前最大值，保留之后要進行下次判斷！直到第i-1位結束，也就是說，是回溯而不是向前遞推！！！
每次比較可以得出狀態轉移方程 dp[i]=max(dp[i],dp[j]+1)
經典的dp動態規劃入門 反正我也不會
1.O(n^2)復雜度代碼
#include<bits/stdc++.h>
using namespace std;
int main(){
int n=0;
int a[1005],dp[1005];
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
dp[i]=1;
for(int j=1;j<i;j++)
if(a[i]>a[j])
dp[i]=max(dp[i],dp[j]+1);
//通過O(n^2)遍歷，得到了所有子序列長度，進行一次o(n)遍歷求最大值即可
int res=0;
for(int i=0;i<n;i++)
res=max(res,dp[i]);
cout<<res<<endl;
2，二分求子序列，咕了咕了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/245756.html
標籤：其他
上一篇：打家劫舍