20190308搜索測試
20190308搜索測試
幾道題都不是很難，但考得也不是很理想，還是做的題不夠多啊…
題目
1.簡單題
題目描述：
給定數軸上的N個點，求這些點到其他點的距離總和S。
輸入格式：
第一行一個整數N。 接下來N行每行一個整數，表示每個點的座標xi。
輸出格式：
一個整數S。
樣例數據:
input1:
5
1
5
3
2
4
output1
40
input2
8
10
20
30
40
50
60
70
80
output2
1680
數據規模與約定：
對於30%的數據，1≤N≤10000
對於50%的數據，保證1≤xi、
對於70%的數據，保證1≤N≤300000，且任意兩點的座標不相同。
對於100%的數據，保證1≤N≤3000000，|xi|≤2^15−1。
的確是一道水題，遞推着就出來了。
#include<bits/stdc++.h> using namespace std; long long n,a[3000101]; long long sum=0; int main() { freopen("cowdis.in","r",stdin); freopen("cowdis.out","w",stdout); scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } sort(a+1,a+n+1); for(int i=1;i<=n-1;i++) { sum=(a[i+1]-a[i])*(i*(n-i)*2)+sum; } printf("%lld",sum); }
然而數據範圍有點小大，雙重循環暴力必然是會TLE的；既然求的是所有點到其他點的距離之和，先排序，算出每個相鄰的邊被計算了多少次累加起來就可以了；sum+=(a[i+1]-a[i-1])(i(n-i)2),這條邊從左邊算了i（n-i）次,從右邊算也是i*(n-i)次，所以第i條邊就一共算了(i*(n-i)*2)次。
坑點：用int就會爆，long long才能過。
2.促銷
題目描述：
小x在jzyz開了一家冷飲店，因爲剛開張，他決定做一次促銷活動。而活動的獲獎者可以免費得到一杯聖代。 爲了和同學的生活貼近，小x費勁腦汁想到了一個促銷方案：
1） 當場搖出一個正整數M，再搖出兩個正整數X和Y
2） 每個人可以在1…M1…M這M個自然數中挑出N個不同的數。
3） 如果某人可以在現場把這N個數的倒數的累加和恰好等於X/Y，那麼這個人可以得到一杯聖代。
4） 每種方案只限第一名想到答案的領取一杯聖代。
輸入格式：
四個整數：N,M, X, Y。
輸出格式：
一個整數，表示最多要準備多少杯聖代。
樣例數據：
input
2 4 3 4
output
1
數據範圍與約定：
對於30%的數據，1<=N<=M<=15
對於60%的數據，1<=N<=M<=20
對於100%的數據，1<=N<=M<=25，X<=25,Y<=25
其實就是給定n,m,x,y，使得從1~m個正整數中選取n個使得這些數的倒數之和=x/y，問有多少種取法。
因爲是分數，本蒟蒻考慮的是精度問題，當然qt大佬用的分子分母，約分通分的方法也是可行的。
代碼如下：
#include<bits/stdc++.h> using namespace std; const double p=0.0000005;//精度標準 double q,x,y; int n,m,summ=0; void dfs(int num,double sum,int o)//num表示已經取了幾個數，sum表示這些數的倒數之和，o表示前面已經到了第幾個數 { if(num==n) { if(q+p>=sum&&q-p<=sum) summ++;//判斷兩個double類型的變量是否相等：abs(a-b)<=0.0000005，a=b;，當然可以根據題目調節精度 return; } if(sum>q) return; if(o>m) return; for(int i=o+1;i<=m;i++)//從下一個數開始選 { dfs(num+1,sum+1.0/i,i); } } int main() { freopen("cd.in","r",stdin); freopen("cd.out","w",stdout); scanf("%d%d",&n,&m); cin>>x>>y; q=1.0*x/y; dfs(0,0.0,0); printf("%d\n",summ); }
3.黑洞
題目描述：
李宗澤的愛好是在週末進行物理學實驗，但事與願違，實驗將NN個黑洞(2<=N<=12,N爲even)(2<=N<=12,N爲even)具象化在了他的農場裏，每個都有明確的座標位置。
根據他的計算，李宗澤知道將會形成N/2對連接起來的黑洞。如果黑洞A和B被連成一對，那麼任何物體進入黑洞A，將會以進入黑洞A的方向從黑洞B中出來；
進入黑洞B，也會以進入時的方向從黑洞A中出來。舉例來說，黑洞A在（0,0）（0,0），黑洞B在（1,0）（1,0），牛玉鑫從（1/2,0）（1/2,0）開始向X軸正方向移動，進入黑洞B，從黑洞A中出來，將繼續向X軸正方向移動，再次進入黑洞B被困在一個循環裏。
李宗澤知道每一個黑洞在他的農場上的具體座標，牛玉鑫只會向X軸正方向移動，但卻不知道牛玉鑫目前的位置。
請你幫助李宗澤計算共有多少種黑洞配對方法會使在不幸的位置的牛玉鑫陷入循環。
輸入格式
第一行：一個正整數N；
第二到N+1N+1行：每行兩個整數X，Y描述一個黑洞的位置，每個座標在0…1,000,000,000內。
輸出格式：
一個數，代表所有的會讓牛玉鑫陷入循環的黑洞配對方法數。
樣例數據：
input
4
0 0
1 0
1 1
0 1
有4個黑洞，形成一個正方形的循環。
output
2
註釋：給這4個黑洞編號爲1…4。如果將1和2相連，3和4相連，牛玉鑫從1和2之間或3和4之間出發時會陷入循環。相同的，如果連接1和3,2和4，牛玉鑫也會陷入循環。只有連接1和4,2和3，牛玉鑫從任何一個位置開始移動都不會陷入循環。
數據範圍與約定：
時間限制：1s
空間限制：256MB
點數不多，顯然是暴力枚舉所有的配對方案進行驗證求可行方案總數；
解決以下幾個問題：
1）方案一共多少？
N個蟲洞保持原順序不變，我們要配出N/2對來。
第一對，我們定爲1號蟲洞和任意另一個蟲洞，共N-1種；
第二對，我們定爲剩下的蟲洞中編號最小的蟲洞和任意另一個蟲洞，共N-3種；
第三對，同理，共N-5種……
以此類推，直至配出N/2種。我們來數一數，配對總方案數Sum=(N-1)×(N-3)×…×3*1，取N最大值12，則有Sum最大值10395，並不大。
2）如何判斷有環？
預處理出每個點與它同行的，右邊的，離它最近的點
根據配對方案，看是否能一直走下去，走了N次後，還可以一直走下去，這種方案肯定是可行的。
代碼如下：
#include<bits/stdc++.h> using namespace std; int n,sum=0; int next[20]={0},f[20]={0};//next爲第i個黑洞右邊最近的黑洞，f爲第i個黑洞所連接的黑洞 struct fuc { int x,y; }a[15]; bool mycmp(fuc a,fuc b) { return a.x<b.x||(a.x==b.x&&a.y<b.y);//行小的放前面，行相同的按列數放 } bool check()//判斷是否有循環 { for(int i=1;i<=n;i++)//枚舉每一個起點，只要有一個起點滿足方案數+1 { int t=i; int vis[20]={0};//一開始的點不能賦值爲1（即vis[i]=1），因爲既然是向右出發，不通過i，否則就要傳送與i配對的黑洞 while(next[t])//向右最近的黑洞 { if(vis[next[t]]) return 1;//循環(黑洞重複經過) vis[next[t]]=1; t=f[next[t]];//傳送至連接的黑洞 } } return 0; } void dfs(int now)//已經搭配到第幾個黑洞 { if(now==n+1)//搭配完了 { if(check()) sum++;//存在循環 return; } if(f[now]) dfs(now+1);//目前的黑洞有配對的黑洞了，搜索下一個黑洞 else { for(int i=now+1;i<=n;i++) { if(!f[i])//沒有匹配過 { f[now]=i;//互相連通 f[i]=now; dfs(now+1); f[now]=f[i]=0;//回溯 } } } } int main() { freopen("wormhole.in","r",stdin); freopen("wormhole.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].y,&a[i].x);//按照座標來讀入 （y是列，x是行） sort(a+1,a+n+1,mycmp); for(int i=1;i<=n-1;i++) if(a[i].x==a[i+1].x) next[i]=i+1;//預處理出每個黑洞向右的最近的一個黑洞 dfs(1); printf("%d",sum); }
4.激光通訊
題目描述：
海亮教育園的oiers有了新的通訊工具，採用最先進的系統——激光通訊系統，這樣可以讓他們在整個校園無延時的進行通訊。
海亮教育園校園被設計爲由W∗H個點組成的網格。（1<=W<=100;1<=H<=100）這套系統要求類似視線連通以確保維持通訊，當然了，校園裏還有一些建築和樹，這些東西會干擾通訊，但是oiers早有準備，他們購買了一些斜放的反光鏡（如下圖中的"/「和」"），這些鏡子能通過反射把激光束扭轉90度，下面是問題的一個圖解。 在這個地圖中H=8，W=7，正在通訊的兩名oiers用符號"C"表示，可通訊區域用".「表示，障礙物用」*"表示：
輸入格式：
一個正整數M 接下來M行，每行3個整數Xi，Yi和Ti。分別表示第i顆流星落下的座標和時間。保證所有座標都在第一象限。
輸出格式：
一行，一個整數M，即反光鏡的個數。
樣例數據：
input
. . . . . . .
. . . . . . C
. . . . . . *
** * * * . *
. . . . * . .
. . . . * . .
. C . . * . .
. . . . . . .
output
3
數據規模與約定：
30% w,h<=30.
50% w,h<=50.
迷宮類題目，但不是求路徑而是求起點到終點的最少轉彎個數
顯然是bfs然而我果斷dfs然後完美TLE了
dfs代碼：
#include<bits/stdc++.h> using namespace std; int minn=99999999; int w1=0,w2=0,n,m,z1=0,z2=0; char ch; int a[110][110],vis[110][110]={0}; const int dx[5]={0,1,0,-1};//方向數組 const int dy[5]={1,0,-1,0}; void dfs(int x,int y,int sum,int pos)//pos表示左右或者上下 ，0表示左右，1表示上下 { if(sum>minn) return; if((x==w2)&&(y==z2))//到達終點 { minn=min(minn,sum); return; } for(int i=0;i<=3;i++) { int xx=x+dx[i]; int yy=y+dy[i]; if(vis[xx][yy]) continue;//該點已經被訪問過就跳過 if((xx>m)||(yy>n)||(xx<=0)||(yy<=0)||(a[xx][yy]==1)) continue; if(pos==-1)//未初始化 （起點） { vis[xx][yy]=1; if((i==0)||(i==2)) dfs(xx,yy,sum,0),vis[xx][yy]=0; if((i==1)||(i==3)) dfs(xx,yy,sum,1),vis[xx][yy]=0; } if(pos==0)//zuoyou { vis[xx][yy]=1; if((i==1)||(i==3)) dfs(xx,yy,sum+1,1),vis[xx][yy]=0; else dfs(xx,yy,sum,0),vis[xx][yy]=0; } if(pos==1) { vis[xx][yy]=1; if((i==0)||(i==2)) dfs(xx,yy,sum+1,0),vis[xx][yy]=0; else dfs(xx,yy,sum,1),vis[xx][yy]=0; } } } int main() { freopen("laser.in","r",stdin); freopen("laser.out","w",stdout); scanf("%d%d",&n,&m);//列 行 for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) { cin>>ch; if(ch=='.') a[i][j]=0; if(ch=='*') a[i][j]=1; if((ch=='C')&&(w1==0)&&(z1==0)) { w1=i;//起點 z1=j; } if((ch=='C')&&(w1>0)&&(z1>0)) { a[w2][z2]=0; w2=i;//終點 z2=j; } } dfs(w1,z1,0,-1); printf("%d",minn); }
dfs要求出的是所有的路徑來尋找最短的，這樣肯定會超時。
bfs思路：
獻上bfs代碼：
#include<bits/stdc++.h> using namespace std; struct fuc { int way;//方向:上下或者左右 1 0(-1表示起點的方向，四個方向拓展不需要轉彎) int num;//需要放置反光鏡的個數，即從起點開始的轉彎總數 int x,y;//當前的座標 }q[100000000]; int n,m,a[110][110],w1,w2,z1,z2; int vis[110][110];//標記該點有沒有經過 char ch; int main() { freopen("laser.in","r",stdin); freopen("laser.out","w",stdout); scanf("%d%d",&n,&m);//列 行 for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) { cin>>ch; if(ch=='.') a[i][j]=0; if(ch=='*') a[i][j]=1; if((ch=='C')&&(w1==0)&&(z1==0)) { w1=i;//起點 z1=j; } if((ch=='C')&&(w1>0)&&(z1>0)) { a[w2][z2]=0; w2=i;//終點 z2=j; } } int head=1,tail=1; q[1].way=-1; q[1].num=0; q[1].x=w1; q[1].y=z1; int falg; for(head=1;head<=tail;head++) { int way_to=q[head].way; int xx=q[head].x,yy=q[head].y; vis[xx][yy]=1; if((xx==w2)&&(yy==z2)) { printf("%d\n",q[head].num); return 0; } for(int i=xx-1;i>=1;i--)//向上延伸 { if(a[i][yy]==1) break;//有障礙 falg=0;//不要拐彎 if(way_to==0) falg=1;//原本向左右的需要轉彎 if(!vis[i][yy]) { vis[i][yy]=1; q[++tail].x=i; q[tail].y=yy; q[tail].way=1; if(falg) q[tail].num=q[head].num+1; else q[tail].num=q[head].num; } } for(int i=yy+1;i<=n;i++)//向右延伸 { if(a[xx][i]==1) break;//有障礙 falg=0;//不要拐彎 if(way_to==1) falg=1;//原本向上下方向的需要轉彎 if(!vis[xx][i]) { vis[xx][i]=1; q[++tail].x=xx; q[tail].y=i; q[tail].way=0; if(falg) q[tail].num=q[head].num+1; else q[tail].num=q[head].num; } } for(int i=yy-1;i>=1;i--)//左 { if(a[xx][i]==1) break;//有障礙 falg=0;//不要拐彎 if(way_to==1) falg=1; if(!vis[xx][i]) { vis[xx][i]=1; q[++tail].x=xx; q[tail].y=i; q[tail].way=0; if(falg) q[tail].num=q[head].num+1; else q[tail].num=q[head].num; } } for(int i=xx+1;i<=m;i++)//右 { if(a[i][yy]==1) break;//有障礙 falg=0;//不要拐彎 if(way_to==0) falg=1; if(!vis[i][yy]) { vis[i][yy]=1; q[++tail].x=i; q[tail].y=yy; q[tail].way=1; if(falg) q[tail].num=q[head].num+1; else q[tail].num=q[head].num; } } } }
5.流星雨
題目描述：
流星雨是美麗的，但是流星落下來也能砸死人的。
有一大片流星要在海亮教育園的操場落下，而小qt恰好在操場數星星。小qt面臨最大的問題不是浪漫，而是保住小命。
我們把海亮教育園的操場認爲是座標系的第一象限(以樣例解釋的圖例爲準)。小qt現在位於座標系的原點。
現在有M顆流星會落在海亮教育園的操場上，其中第i顆流星會在時刻T_i砸在座標爲(X_i, Y_i)的格子裏。流星的力量會將它所在的格子，以及周圍4個相鄰的格子都化爲焦土，當然小qt也無法再在這些格子上行走，這樣他會被燒傷。
小ff從0時刻開始逃離，他只能上下左右移動，並且一個時刻只能移動一個格子，當然，這個格子必須是完好的。
現在小ff想知道，最少經過多少時刻，他可以到達一個安全的格子。
輸入格式：
一個正整數M 接下來M行，每行3個整數Xi，Yi和Ti。分別表示第i顆流星落下的座標和時間。保證所有座標都在第一象限。
輸出格式：
一個整數，表示最少逃離時刻。如果逃離不了，那麼輸出-1，表示小ff肯定被流星砸着了。
樣例數據：
input
4
0 0 2
2 1 2
1 1 2
0 3 5
output
5
【樣例說明】：一共有4顆流星將墜落在操場，它們落地點的座標分別是(0, 0)，(2, 1)， (1, 1)以及(0, 3)，時刻分別爲2，2，2，5。
在t=5時的牧場，離小ff最近的安全的格子是(3,0)——不過由於早在第二顆流星落地時，小ff直接跑去(3,0)的路線就被封死了。離小ff第二近的安全格子爲(4,0)，但它的情況也跟(3,0)一樣。再接下來的格子就是在(0,5)-(5,0)這條直線上。在這些格子中，(0,5)，(1,4)以及(2,3)都能在5個單位時間內到達。
BFS，先處理每個格子最早被轟的時間，然後BFS時加個判斷就可以。
Bfs之前
1）哪些格子是安全的（可以用一個數組記錄下最終的地圖來判斷目前點是否是絕對安全的） 2）處理出每個格子最早被轟的時間。
Bfs中間要做的。
1）拓展四個方向，判斷拓展倒的格子的時間和這個格子被轟擊的最早時間大小關係，拓展進隊。 2）記憶化每個格子是否到過，不然會TLE。
代碼如下：
#include<bits/stdc++.h> using namespace std; const int dx[5]={0,1,0,-1};//方向數組 const int dy[5]={1,0,-1,0}; int n; struct fuc { int x,y; int tim; }q[100000000]; int vis[310][310],x,y,tim; int mapp[310][310]={0};//最終的地圖，用來判斷目前點是否是絕對安全的 int falg[310][310]={0};//記憶化，標記點有沒有到過 int main() { freopen("meteor.in","r",stdin); freopen("meteor.out","w",stdout); memset(vis,1,sizeof(vis)); scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d%d%d",&x,&y,&tim); vis[x][y]=min(vis[x][y],tim); mapp[x][y]=1; if(x>=1) vis[x-1][y]=min(vis[x-1][y],tim),mapp[x-1][y]=1; if(y>=1) vis[x][y-1]=min(vis[x][y-1],tim),mapp[x][y-1]=1; mapp[x+1][y]=1; mapp[x][y+1]=1; vis[x+1][y]=min(vis[x+1][y],tim); vis[x][y+1]=min(vis[x][y+1],tim);//記錄下流星轟擊周圍每一個點被炸的最早時間 } q[1].x=q[1].y=q[1].tim=0; falg[0][0]=1; int tail=1; for(int head=1;head<=tail;head++)//bfs { int xx=q[head].x; int yy=q[head].y; if(!mapp[xx][yy])//此點絕對安全 { printf("%d",q[head].tim); return 0 ; } for(int i=0;i<=3;i++) { int x_r=xx+dx[i]; int y_r=yy+dy[i]; if(x_r<0||y_r<0||falg[x_r][y_r]) continue; if(vis[x_r][y_r]>q[head].tim+1)//向四個方向移動，下一時刻不會被炸，拓展 { falg[x_r][y_r]=1; q[++tail].x=x_r; q[tail].y=y_r; q[tail].tim=q[head].tim+1; } } } printf("-1");//必然被炸死 return 0; }
這次考試暴露出了太多的問題，基礎代碼掌握不牢固，思考太片面。還是要多多練習，多多思考，多去請教一下qt大佬。