第三次训练赛题解
A.POJ-2255
理解二叉树就自然知道了
typedef struct tree { char data; struct tree *l,*r; } Tree; Tree *creat(char a[],char b[],int n) { if(n==0) return NULL; Tree *t; t=(Tree*)malloc(sizeof(Tree)); t->l=t->r=NULL; t->data=a[0]; int i; for(i=0;i<n;i++) { if(b[i]==a[0]) break; } t->l=creat(a+1,b,i); t->r=creat(a+1+i,b+i+1,n-i-1); return t; } void postorder(Tree* tree) { if(tree!=NULL) { postorder(tree->l); postorder(tree->r); printf("%c",tree->data); } } int main() { char a[30],b[30]; while(~scanf("%s%s",a,b)) { Tree *root; root=(Tree*)malloc(sizeof(Tree)); root->l=root->r=NULL; root=creat(a,b,strlen(a)); postorder(root); printf("\n"); } return 0; }
B.POJ-3268
先求x到各个点的最短路,所有牛去x可以把边反向然后求x到各个点的最短路,所以就是求两次x出发的最短路(矩阵转置),Floyd会超时,这里用的dijkstra。然后找个最大值即可
int n,m,x; int edge[1005][1005],d[1005],v[1005]; void dijkstra() { memset(v,0,sizeof(v)); for(int i=1;i<=n;i++) d[i]=(i==x?0:edge[x][i]); for(int i=1;i<=n;i++) { int minn=inf,p; for(int j=1;j<=n;j++) { if(!v[j]&&d[j]<minn) { minn=d[j]; p=j; } } v[p]=1; for(int j=1;j<=n;j++) if(!v[j]) d[j]=min(d[j],d[p]+edge[p][j]); } int ans=-1; return ; } int main() { while(scanf("%d%d%d",&n,&m,&x)!=EOF) { int from,to,w; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j) edge[i][j]=0; else edge[i][j]=inf; } while(m--) { scanf("%d%d%d",&from,&to,&w); edge[from][to]=w; } dijkstra(); int d1[1005]; for(int i=1;i<=n;i++) d1[i]=d[i]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { swap(edge[i][j],edge[j][i]); } dijkstra(); int ans=-1; for(int i=1;i<=n;i++) { d1[i]+=d[i]; if(ans<d1[i]) ans=d1[i]; } printf("%d\n",ans); } return 0; }
C.POJ-2524
并查集板题
int a[50010]; int ff(int x) { if(a[x]==x) return x; else return a[x]=ff(a[x]); } int main() { int n,m,T=1; while(~scanf("%d%d",&n,&m)&&(n!=0||m!=0)) { for(int i=1;i<=n;i++) a[i]=i; int x,y; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); a[max(ff(x),ff(y))]=min(ff(x),ff(y)); } int ans=0; for(int i=1;i<=n;i++) if(a[i]==i) ans++; printf("Case %d: %d\n",T,ans); T++; } return 0; }
D.POJ-3494
// #include<bits/stdc++.h> #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<stack> using namespace std; typedef long long ll; #define For(i,x,y) for(int i=x; i<(int)y; ++i) #define mem(x,y) memset(x,y,sizeof(x)) #define ALL(a) a.begin(),a.end() #define PII pair<int,int> #define INF 0x3f3f3f3f #define DOF 0x7f7f7f7f #define se second #define fi first #define endl '\n' // #pragma GCC optimize(2) template <typename T> inline void read(T &r){ static char c; r=0; int f=1; for(c=getchar(); c<'0'||c>'9'; c=getchar()) if(c=='-')f=-1; for(; c>='0'&&c<='9'; r=(r<<1)+(r<<3)+(c^48),c=getchar()); r*=f; } // -_- const int N=2e3+25; int a[N][N]={0},dp[N][N]={0},n,m,h[N]; int f(int x){ For(i,0,m) h[i]=dp[x][i+1]; stack<int>sta; int ans=0,l=0,len=m; while(l<len){ if(sta.empty()||h[sta.top()]<=h[l]){ sta.push(l++); } else{ int mh=sta.top(); sta.pop(); int w =sta.empty()?l:l-sta.top()-1; ans=max(ans,h[mh]*(w)); } } while(!sta.empty()){ int mh=sta.top(); sta.pop(); int w =sta.empty()?len:len-sta.top()-1; ans=max(ans,h[mh]*(w)); } return ans; } void solve(){ For(i,1,n+1){ For(j,1,m+1){ read(a[i][j]); if(!a[i][j]) dp[i][j]=0; else dp[i][j]=dp[i-1][j]+1; } } int ans=0; For(i,1,n+1){ ans=max(ans,f(i)); } cout<<ans<<endl; } int main(){ int t; while(cin>>n>>m) solve(); // system("pause"); }
E.POJ-3495
我印象中没有加这题,可能是误操作加进去的,想知道的自己百度吧,做出来了的跟我搜的代码一样ORZ
F.HDU-1556
前缀和
int ans[100007]; int main() { int n,sum,l,r; while(cin>>n) { if(n==0) break; sum=0; memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++) { cin >> l >> r; ans[l]++; ans[r+1]--; } sum=ans[1]; cout << sum; for(int i=2;i<=n;i++) { sum+=ans[i]; cout << " " << sum; } cout << endl; } return 0; }
G.CodeForces-1157A
签到题
int main() { int n; cin>>n; int s=0; while(n>=10) { n++; while(n%10==0) { n/=10; } s++; } cout<<s+9<<endl; return 0; }