zoj 3202?Second-price Auction

水題，不解釋了，直接貼代碼 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;struct node{int x;int y; };struct node number[105];int cmp(struct node a,struct node b){return a.x>b.x; } int main(){int t;scanf("%d",&t);int i;while(t--){int n;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&number[i].x);number[i].y=i;}sort(number,number+n,cmp);printf("%d %d\n",number[0].y+1,number[1].x);}return 0; }

zoj 3203?Light Bulb

簡單的數學題，也不解釋了，搞成一個雙鉤函數，最要要注意判斷有沒有射到墻上即可，直接貼代碼 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> using namespace std;int main(){int t,i;scanf("%d",&t);while(t--){double H,h,D;scanf("%lf%lf%lf",&H,&h,&D);double tmp=sqrt((H-h)*D);if(tmp+h/H*D<D){printf("%.3lf\n",h/H*D);}else if(tmp<D){printf("%.3f\n",H+D-tmp-tmp);}else{printf("%.3lf\n",h);}} }

zoj 3204?Connect them

最小生成樹水題，依舊不解釋 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> using namespace std;struct node{int a,b;int n; };struct rea{int a,b; };struct node edge[10005]; int father[105]; int cmp(struct node a,struct node b){if(a.n==b.n){if(a.a==b.a){return a.b<b.b;}else return a.a<b.a;}return a.n<b.n; }int cmp1(struct rea x,struct rea y){if(x.a==y.a) return x.b<y.b;else return x.a<y.a; }int Find(int n){if(father[n]==n) return n;else return father[n]=Find(father[n]); }struct rea relans[500]; int main(){int t,i,j;scanf("%d",&t);while(t--){int n;scanf("%d",&n);int k=0;for(i=1;i<=n;i++) father[i]=i;for(i=1;i<=n;i++){for(j=1;j<=n;j++){int tmp;scanf("%d",&tmp);if(tmp!=0){edge[k].a=i;edge[k].b=j;edge[k++].n=tmp;}}}sort(edge,edge+k,cmp);int ans=0;for(i=0;i<k;i++){int ta=Find(edge[i].a);int tb=Find(edge[i].b);if(ta!=tb){father[ta]=tb;relans[ans].a=edge[i].a;relans[ans++].b=edge[i].b;}if(ans==n-1) break;}sort(relans,relans+ans,cmp1);if(ans==n-1){for(i=0;i<ans;i++){if(i==0)printf("%d %d",relans[i].a,relans[i].b);else printf(" %d %d",relans[i].a,relans[i].b);}printf("\n");}else{printf("-1\n");}} }
zoj 3205 直接貼代碼 #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<cmath> using namespace std;const int mo= 1000000007;int c[200],p[200][200],a[200]; long long po[105][105];long long power(int x,int y) {long long res=1;long long sum=x;while (y) {if (y%2==1) res=(res*sum) % mo;sum=(sum*sum) % mo;y/=2;}return res; }int main() {int t;scanf("%d",&t);for (int i=0; i<105; i++)for (int j=0; j<105; j++)po[i][j]=power(i,j);while (t) {int n,m,k;scanf("%d %d ",&n,&m);for (int i=0; i<n; i++) {scanf("%d",&c[i]);for (int j=0; j<m; j++) scanf("%d",&p[i][j]);}scanf("%d",&k);while (k--) {for (int i=0; i<m; i++) scanf("%d",&a[i]);for (int j=0; j<m; j++) {long long ans=0;for (int i=0; i<n; i++) {long long sum=0;if (p[i][j]>0) {sum=c[i]*p[i][j];for (int k=0; k<m; k++) {if (k==j) sum=(sum*po[a[k]][p[i][k]-1] ) % mo;else sum=(sum*po[a[k]][p[i][k]]) % mo;}}ans=(ans+sum) % mo;}if (j==m-1) cout<<ans<<endl;else cout<<ans<<" ";}}if (--t) cout<<endl;}return 0; }
zoj 3206 ?Disaster Area Reconstruction
這道題目還是比較麻煩的，題目是叫你求一個連通分量，這個連通分量里面的頂點數是最多的，并輸出這個連通分量。 首先，如果這是一個無環圖的話，直接樹形DP求出最長鏈就好，所以就要預先處理成環情況。 接著，只要做一遍強連通分量縮點，然后對每個點記錄一個頂點數量，再DP一下即可。 代碼如下： #include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <stack>using namespace std;const int maxn = 50010; const int inf = 1000000; int n, m; vector<int> edge[maxn];int dfn[maxn], low[maxn], tim; stack<int>s; bool instack[maxn]; int belong[maxn], minId[maxn], num[maxn]; int cnt;void init(){for(int i = 0; i <= n; i++)edge[i].clear();while(!s.empty())s.pop();memset(instack, 0, sizeof(instack));memset(num, 0, sizeof(num));memset(low, 0, sizeof(low));memset(dfn, 0, sizeof(dfn));fill(minId, minId+maxn, inf);cnt = tim = 0; }void tarjan(int u){dfn[u] = low[u] = ++tim;s.push(u);instack[u] = 1;int len = edge[u].size();for(int i = 0; i < len; i++){int v = edge[u][i];if(dfn[v] == 0){tarjan(v);low[u] = min(low[u], low[v]);} else if (instack[v] == 1){low[u] = min(low[u], dfn[v]);}}if (dfn[u] == low[u]){int v;cnt ++;do {v = s.top();s.pop();instack[v] = 0;belong[v] = cnt;//這點縮給哪個新點num[cnt]++;//縮了多少點minId[cnt] = min(minId[cnt], v);//縮點的最小點標號}while(u != v);} }vector<int> newEdge[maxn]; void build(){for(int i = 0; i <= n; i ++)newEdge[i].clear();for(int u = 1; u <= n; u++){int len = edge[u].size();for(int i = 0; i < len; i++){int v = edge[u][i];if(belong[u] != belong[v]){newEdge[belong[u]].push_back(belong[v]) ;}}} }int vis[maxn]; int dp[maxn]; int tail[maxn];void init_new(){for(int i = 0; i <= cnt; i++) newEdge[i].clear();memset(vis, 0, sizeof(vis));memset(dp, 0, sizeof(dp)); }void dfs(int u){vis[u] = 1;dp[u] = num[u];tail[u] = u;int len = newEdge[u].size();for(int i = 0; i < len; i++){int v = newEdge[u][i];if(vis[v] == 0){dfs(v);}if(dp[u] < dp[v]+num[u]){dp[u] = dp[v]+num[u];tail[u] = tail[v];} else if( dp[u] == dp[v]+num[u]){if(minId[tail[u]] > minId[tail[v]])tail[u] = tail[v];}} }int main(){int t;int a, b;scanf("%d", &t);while(t--){scanf("%d %d", &n, &m);init();for(int i = 0; i <m; i++){scanf("%d%d", &a, &b);edge[a].push_back(b);}for(int i = 1; i <= n; i++){if(dfn[i] == 0){tarjan(i);}}int ans = 0;init_new();build();for(int i = 1; i <= cnt; i ++){if(vis[i] == 0){dfs(i);}}pair<int, int> res = make_pair(inf, inf);for(int i = 1; i <= cnt; i ++){a = minId[tail[i]], b = minId[i];pair<int, int> tmp = make_pair(a, b);if(dp[i] > ans){ans = dp[i];res = tmp;} else if( dp[i] == ans ) {if ( tmp < res && res.first != res.second || tmp.first == tmp.second ){res = tmp;}}}if(res.first == res.second) {res = make_pair(1, 2);}printf("%d\n%d %d\n", ans, res.first, res.second);} }
zoj 3207 ?80ers' Memory?
水題，不解釋了，代碼也不上了
zoj 3208?Reforestation
這道題目講多一點，題目意思是：有一個觀測者正在觀測周圍情況，觀測者一直在(0,0)的位置。 題目給你一些樹的圓心，這些樹每秒鐘半徑為多1，如果這些樹相互碰撞或者碰到了觀測者，那它們就會停止生長，它們會擋住觀測者的視線，題目問的是觀測者什么時候被擋住？如果擋不住的話就輸出-1.
思路： 首先可以先預處理出來每顆樹什么時候停止生長，就是每棵樹和其他所有的樹算一個相交時間取最小即可。然后就可以想到二分時間，取所有停止時間中最大的作為最大時間進行二分，對于每一個時間只要計算觀測者是否被擋住即可。 具體的計算的話，只需要看是否[0,2π]范圍內的視野全被擋住了，如果擋住了，你懂得。 代碼如下 #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<cmath> using namespace std;const double o=1e-8; const double pi = acos(-1.0);struct da {double x,y,t; } a[10000];struct da1 {double l,r; }q[10000];int n,bo[400]; double ti[100000];double min(double x, double y) {return x<y?x:y; }double max(double x,double y) {return x>y?x:y; } double dis(int i,int j) {return sqrt( (a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y) ); }bool cmp(da1 a, da1 b) {return a.l<b.l; }bool cmp2(double a,double b) {return a<b; }bool check(double res) {int sum=0;for (int i=1; i<=n; i++) {double r = min(res,a[i].t);double ph1,ph2;ph1 = atan2(a[i].y,a[i].x);if (ph1<0) ph1+=pi*2;if ( r-dis(0,i)<o ) ph2 = asin(r/dis(0,i));else ph2=pi/2.0;double lnow=ph1-ph2,rnow=ph1+ph2;if (lnow<0) {q[sum].l=lnow+pi*2;q[sum].r=pi*2;sum++;q[sum].l=0;q[sum].r=rnow;sum++;}else if (rnow>pi*2) {q[sum].l=lnow;q[sum].r=pi*2;sum++;q[sum].l=0;q[sum].r=rnow-pi*2;sum++;}else {q[sum].l=lnow;q[sum].r=rnow;sum++;}}sort(q,q+sum,cmp);double rnow=o;for (int i=0; i<sum; i++) {if (q[i].l>rnow) return true;rnow = max(rnow,q[i].r);}if (rnow<pi*2) return true;return false; }int main() {int t;scanf("%d",&t);while (t--) {scanf("%d",&n);a[0].x=0,a[0].y=0; a[0].t=0;for (int i=1; i<=n; i++) {int x,y;scanf("%d %d",&x,&y);a[i].x=x,a[i].y=y;a[i].t=999999;}double l=0.0,r=0.0;memset(bo,0,sizeof bo);bo[0]=true;for (int i=1; i<=n; i++) {int tt=0;double mint=999999;for (int j=1; j<=n; j++) if (!bo[j]) {double tmp=dis(0,j);for (int k=1; k<=n; k++) if (j!=k){if (!bo[k]) tmp=min(tmp,dis(j,k)/2.0);else tmp=min(tmp,dis(j,k)-a[k].t);}if (tmp<mint) {tt=j;mint=tmp;}}bo[tt]=true; a[tt].t=mint;}for (int i=1; i<=n; i++) r=max(r,a[i].t);r+=1.0;if ( check(r) ) cout<<"-1.0"<<endl;else {while (r-l>1e-8) {double mid=(l+r)/2.0;if (check(mid)) l=mid;else r=mid;}printf("%.8f\n",l);}}return 0; }
zoj 3209?Treasure Map
用n*m作為列,每個矩陣作為行,Dancing Link不解釋了 #include<stdio.h> #include<string.h>const int ROW = 505; const int V = 452000; const int LIE = 905;int R[V],L[V],U[V],D[V],C[V]; int H[ROW],S[LIE]; int n,m; int size; int ans;void link(int r,int c) {S[c]++;C[size]=c;U[size]=U[c];D[U[c]]=size;D[size]=c;U[c]=size;if(H[r]==-1) H[r]=L[size]=R[size]=size;else{L[size]=L[H[r]];R[L[H[r]]]=size;R[size]=H[r];L[H[r]]=size;}size++; } void remove(int c) {int i,j;L[R[c]]=L[c];R[L[c]]=R[c];for(i=D[c];i!=c;i=D[i]){for(j=R[i];j!=i;j=R[j]){S[C[j]]--;U[D[j]]=U[j];D[U[j]]=D[j];}} } void resume(int c) {int i,j;for(i=U[c];i!=c;i=U[i]){for(j=L[i];j!=i;j=L[j]){S[C[j]]++;U[D[j]]=D[U[j]]=j;}}L[R[c]]=c;R[L[c]]=c; }void Dance(int k){int Min,i,j,c;if(R[0]==0){if(ans>k){ans=k;}return ;} for(Min=ROW,i=R[0];i;i=R[i]){if(Min>S[i]) {Min=S[i];c=i;}}remove(c);for(i=D[c];i!=c;i=D[i]){for(j=R[i];j!=i;j=R[j]){remove(C[j]); }Dance(k+1);for(j=L[i];j!=i;j=L[j]){resume(C[j]);}}resume(c); }int main(){int t,i,j,row;scanf("%d",&t);while(t--){int p;scanf("%d%d%d",&n,&m,&p);int count=n*m;for(i=0;i<=n*m;i++){S[i]=0;U[i]=D[i]=i;L[i+1]=i;R[i]=i+1;}R[n*m]=0;size=n*m+1;for(row=1;row<=p;row++){H[row]=-1;int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);for(i=x1;i<x2;i++){for(j=y1;j<y2;j++){link(row,i*m+j+1);}}}ans=ROW;Dance(0);if(ans==ROW){printf("-1\n");}else{printf("%d\n",ans);}} }
zoj 3210 3211 3212 都是水題不解釋了

總結

以上是生活随笔為你收集整理的浙江省第6届程序设计竞赛结题报告汇总 zoj3202-3212的全部內容，希望文章能夠幫你解決所遇到的問題。

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