第三次训练赛题解

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;
}