T1 足球聯賽 題目 【題目描述】 巴蜀中學新一季的足球聯賽開幕了。足球聯賽有n只球隊參賽，每賽季，每隻球隊要與其他球隊各賽兩場，主客各一場，贏一場得3分，輸一場不得分，平局兩隻隊伍各得一分。 英勇無畏的小鴻是機房的主力前鋒，她總能在關鍵時刻踢出一些匪夷所思的妙球。但是很可惜，她過早的燃燒完了她的職 ...
T1 足球聯賽
題目
【題目描述】
巴蜀中學新一季的足球聯賽開幕了。足球聯賽有n只球隊參賽，每賽季，每隻球隊要與其他球隊各賽兩場，主客各一場，贏一場得3分，輸一場不得分，平局兩隻隊伍各得一分。
英勇無畏的小鴻是機房的主力前鋒，她總能在關鍵時刻踢出一些匪夷所思的妙球。但是很可惜，她過早的燃燒完了她的職業生涯，不過作為一個能夠Burning的girl，
她的能力不止如此，她還能預測這個賽季所有球隊的比賽結果。雖然她能準確預測所有比賽的結果，但是其實她不怎麼厲害，Mr.Gao上數學課時她總是在sleep，因此她的腦里只有整數沒有實數，
而且，她只會10以內非負整數的加法運算，因此她只有結果卻無法知道誰會獲得聯賽的冠軍。
小鴻想給冠軍隊伍的所有隊員一個擁抱，所以她把計算結果的任務交給了你：
現在，給你一個 n*n 的矩陣表示比賽情況。第 i 行第 j 列的字母表示在第 i 只隊伍在主場迎戰第j只隊伍的比賽情況，W 表示主隊贏，L 表示主隊輸，D 表示平局。
現在需要你給出最後能得到小鴻擁抱的隊伍編號，如有多支隊伍分數最高，按字典序輸出編號。
【輸入格式】
第一行一個整數 n。
接下來 n 行,每行 n 個字元，表示輸贏情況。
第 i 行第 i 列為 - ,因為一隻隊伍不可能與自己比賽。
【輸出格式】
輸出得分最高的隊伍編號。如有多個在一行中輸出，用一個空格分開。
【數據規模】
對於40%的數據，滿足N<=20
對於100%的數據，滿足N<=50
解析
純模擬題，直接模擬就行了，沒什麼好說的，就是輸出時要記得判斷最高成績相同的都要輸出。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } int n,ans[51],maxn,temp,ra[51]; char s; int main() { //freopen("soccer.in","r",stdin); //freopen("soccer.out","w",stdout); n=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { cin>>s; if(s=='W') ans[i]+=3; else if(s=='L') ans[j]+=3; else if(s=='D') { ans[i]+=1; ans[j]+=1; } } for(int i=1;i<=n;i++) if(ans[i]>maxn) { maxn=ans[i]; temp=1; ra[temp]=i; } else if(ans[i]==maxn) ra[++temp]=i; for(int i=1;i<=temp;i++) cout<<ra[i]<<" "; return 0; //fclose(stdin); //fclose(stdout); }View Code
T2 生產
題目
【題目描述】
工廠為了生產一種複雜的產品，給各個生產部門制定了詳細的生產計劃。那麼，就經常會有生產部門要把產品送到另一個生產部門作為原料。
這是一個註重產品質量的工廠，所以每當有產品要從A部門運到B部門時，都要先從A部門送到質量檢驗處，檢驗合格後再從質量檢驗處運到B部門。
有些部門之間有傳送帶連接，廠長想知道每次將產品從一個部門運送到另一個部門最少需要多長時間。
【輸入格式】
第一行兩個整數n、m，n表示部門數量，m表示傳送帶數量。出於方便，1號部門是質量檢驗處。
接下來m行，每行三個整數u、v、w，表示有一條從u部門到v部門的傳送帶，傳送過去需要w個單位時間。註意傳送帶是單向的。
接下來一個整數q，表示有q次運送。
接下來q行，每行兩個數a、b，表示這一次要將產品從a部門運送到b部門。
【輸出格式】
輸出q行，每行一個整數，表示這次運送最少需要的時間。若沒有傳送方案，輸出-1。
【數據規模】
30%的數據，n≤100，m≤500，w=1
60%的數據，n≤100，m≤5000
另20%的數據，q=1
100%的數據，2≤n≤3000，m≤100000，2≤a,b≤n，
q≤100000，1≤u,v≤n，1≤w≤10000
有些部門之間可能有多條傳送帶。
工廠的員工都非常盡職盡責，他們的認真和熱情決定了產品的完美，所以不必考慮產品不合格的情況。
解析
很容易看得出來這題是最短路，只不過是兩條最短路：
一條是從a到1，另一條是從1到b，只需要做兩遍最短路即可。
最短路推薦用dijkstra，如果用SPFA的話數據大一點、出題人卡一下就炸了。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <queue> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } const int N=3001; const int M=100001; priority_queue< pair<int,int> > q; int n,m,qq,tot1,tot2,head1[N],ver1[M],edge1[M],next1[M],head2[N],ver2[M],edge2[M],next2[M]; long long d1[N],d2[N]; bool vist[N]; void add1(int x,int y,int z) { ver1[++tot1]=y; edge1[tot1]=z; next1[tot1]=head1[x]; head1[x]=tot1; } void add2(int x,int y,int z) { ver2[++tot2]=y; edge2[tot2]=z; next2[tot2]=head2[x]; head2[x]=tot2; } void dijkstra1() { memset(d1,0x7f7f7f7f,sizeof(d1)); memset(vist,false,sizeof(vist)); d1[1]=0; q.push(make_pair(0,1)); while(q.size()) { int x=q.top().second; q.pop(); if(vist[x]) continue; vist[x]=true; for(int i=head1[x];i;i=next1[i]) { int y=ver1[i],z=edge1[i]; if(d1[y]>d1[x]+z) { d1[y]=d1[x]+z; q.push(make_pair(-d1[y],y)); } } } } void dijkstra2() { memset(d2,0x7f7f7f7f,sizeof(d2)); memset(vist,false,sizeof(vist)); d2[1]=0; q.push(make_pair(0,1)); while(q.size()) { int x=q.top().second; q.pop(); if(vist[x]) continue; vist[x]=true; for(int i=head2[x];i;i=next2[i]) { int y=ver2[i],z=edge2[i]; if(d2[y]>d2[x]+z) { d2[y]=d2[x]+z; q.push(make_pair(-d2[y],y)); } } } } int main() { //freopen("production.in","r",stdin); //freopen("production.out","w",stdout); int u,v,w,a,b; n=read(),m=read(); for(int i=1;i<=m;i++) { u=read(),v=read(),w=read(); add1(u,v,w); add2(v,u,w); } dijkstra1(); dijkstra2(); qq=read(); for(int i=1;i<=qq;i++) { a=read(),b=read(); if(d2[a]>=0x3f3f3f3f||d1[b]>=0x3f3f3f3f) cout<<"-1"<<endl; else cout<<d2[a]+d1[b]<<endl; } return 0; //fclose(stdin); //fclose(stdout); }View Code
T3 最短路徑
題目
【題目描述】
平面內給出 n 個點，記橫坐標最小的點為 A，最大的點為 B，現在小Y想要知道在每個點經過一次（A 點兩次）的情況下從 A 走到 B，再回到 A 的最短路徑。
但他是個強迫症患者，他有許多奇奇怪怪的要求與限制條件：
1.從 A 走到 B 時，只能由橫坐標小的點走到大的點。
2.由 B 回到 A 時，只能由橫坐標大的點走到小的點。
3.有兩個特殊點 b1 和 b2， b1 在 0 到 n-1 的路上，b2 在 n-1 到 0 的路上。
請你幫他解決這個問題助他治療吧！
【輸入格式】
第一行三個整數 n,b1,b2,( 0 < b1，b2 < n-1 且 b1 ≠ b2)。n 表示點數，從 0 到 n-1 編號，b1 和 b2 為兩個特殊點的編號。
以下 n 行，每行兩個整數 x、y 表示該點的坐標(0 <= x，y <= 2000)，從 0 號點順序給出。Doctor Gao為了方便他的治療，已經將給出的點按 x 增序排好了。
【輸出格式】
輸出僅一行，即最短路徑長度（精確到小數點後面 2 位）
【數據規模】
20%的數據n<=20
60%的數據n<=300
100%的數據n<=1000
解析
這道題本蒟蒻做的時候寫了個暴力，果不其然，TLE...
後來才知道原來這題是DP。
他是從A走到B再走回A，所以我們可以將問題轉化為求兩條和最小的不相交線段。
令f[i][j]表示從A到B的線段走到了i點，從B到A的線段走到了j點。
邊界為：f[0][0]=0。
狀態轉移方程：（k=max(i,j)）
k!=n-1時，
1、f[i][k]=min(f[i][k],f[i][j]+d(j,k));（k!=b1）
2、f[k][j]=min(f[k][j],f[i][j]+d(i,k));（k!=b2）
k==n-1時，
3、f[n-1][n-1]=min(f[n-1][n-1],f[i][n-1]+d(i,n-1));（i!=n-1）
4、f[n-1][n-1]=min(f[n-1][n-1],f[n-1][j]+d(j,n-1));（j!=n-1）
PS:由於是從0開始編號，所以最後一個點為n-1，當然，也可以全部+1從1開始編號（會更美觀），主要看個人喜好。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <queue> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } const int N=1005; int n,b1,b2,k; double f[N][N],x[N],y[N]; double d(int i,int j) { return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); } int main() { //freopen("paths.in","r",stdin); //freopen("paths.out","w",stdout); memset(f,0x7f7f7f7f,sizeof(f)); f[0][0]=0; n=read(),b1=read(),b2=read(); for(int i=0;i<n;i++) x[i]=read(),y[i]=read(); for(int i=0;i<n;i++) for(int j=0;j<n;j++) { k=max(i,j); if(k!=n-1) { k++; if(k!=b1) f[i][k]=min(f[i][k],f[i][j]+d(j,k)); if(k!=b2) f[k][j]=min(f[k][j],f[i][j]+d(i,k)); } else { if(i!=n-1) f[n-1][n-1]=min(f[n-1][n-1],f[i][n-1]+d(i,n-1)); if(j!=n-1) f[n-1][n-1]=min(f[n-1][n-1],f[n-1][j]+d(j,n-1)); } } printf("%.2lf",f[n-1][n-1]); return 0; //fclose(stdin); //fclose(stdout); }View Code
T4 簡單的序列
題目
【題目描述】
從前有個括弧序列s，滿足|s|=m。你需要統計括弧序列對(p,q)的數量。
其中(p,q)滿足|p|+|s|+|q|=n，且p+s+q是一個合法的括弧序列。
【輸入格式】
第一行兩個正整數n,m。
第二行一個長度為m的括弧序列，表示s。
【輸出格式】
輸出一行一個整數，表示符合條件的(p,q)的數量對10^9+7取模的值。
【數據規模】
對於10%的數據，n≤20；
對於25%的數據，n≤200；
對於另外5%的數據，n=m；
對於55%的數據，n-m≤200；
對於100%的數據，1≤m≤n≤10^5，n-m≤2000。
解析
這題有點意思，其實是一道DP題。
將'('轉換為1，')'轉換為-1。
令f[i][j]表示前i個括弧總值為j（邊界：f[0][0]=f[1][1]=1）。
而這裡的j是一定不為負數的。為什麼？因為若j為負數，就意味著當前右括弧比左括弧多，
這種情況即使後面加入左括弧，就會變成“)(”這種情況，即右括弧在左，左括弧在右，很顯然是不合法的。
所以初始賦值時，令f[i][0]=f[i-1][1]，因為如果是f[i][0]=f[i-1][-1]的話就成了上面說的情況，不合法。
梳理了這麼多，可以輕易推出狀態轉移方程：
1、f[i][j]=f[i-1][j-1]（添加左括弧）。
2、f[i][j]=f[i-1][j+1]（添加右括弧）。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <queue> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } const long long mod=1000000007; int n,m,temp,a[100100],minn=0x7f7f7f7f,ans; long long f[2010][2010]; char s; int main() { //freopen("bracket.in","r",stdin); //freopen("bracket.out","w",stdout); n=read(),m=read(); for(int i=1;i<=m;i++) { cin>>s; if(s=='(') a[++temp]=1; else a[++temp]=-1; } f[0][0]=f[1][1]=1; for(int i=2;i<=n-m;i++) { f[i][0]=f[i-1][1]; for(int j=1;j<=n-m;j++) f[i][j]=(f[i-1][j-1]+f[i-1][j+1])%mod; } temp=0; for(int i=1;i<=m;i++) { temp+=a[i]; minn=min(minn,temp); } for(int i=-minn;i<=n-m;i++) for(int j=-minn;j<=i;j++) { int l=n-m-i,b=temp+j; if(b>=0) ans=(long long)(f[l][b]*f[i][j]+ans)%mod; } cout<<ans; return 0; //fclose(stdin); //fclose(stdout); }View Code
