程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2012金華邀請賽 (持續更新)

POJ 2012金華邀請賽 (持續更新)

編輯:C++入門知識

第一題,水題,但是題目讀了很久,英語功底果然很差,主要是第二次排序的時候是按位排序,先按個位從小到大,然後是十位從小到大。題目描述太奇葩,這句話領會了很久。。
POJ 4044
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <string> 
#include <cmath> 
#include <cstring> 
#include <queue> 
#include <set> 
#include <vector> 
#include <stack> 
#include <map> 
#include <iomanip> 
#define PI acos(-1.0) 
#define Max 2005 
#define inf 1<<28 
#define LL(x) (x<<1) 
#define RR(x) (x<<1|1) 
#define FOR(i,s,t) for(int i=(s);i<=(t);++i) 
#define ll long long 
using namespace std; 
 
int a[50],b[50]; 
int v[200]; 
bool cmp(int a,int b) 

    return a>b; 

bool cmp1(int a,int b) 

    if(a%10!=b%10)return (a%10)<(b%10); 
    return (a/10)<(b/10); 

int main() 

    int T; 
    int n,m; 
    cin>>T; 
    while(T--) 
    { 
        cin>>n>>m; 
        int t; 
        memset(v,0,sizeof(v)); 
        memset(a,0,sizeof(a)); 
        memset(b,0,sizeof(b)); 
        int num1=0; 
        for(int i=0;i<n;i++) 
        { 
            cin>>t; 
            if(!v[t]) 
            { 
                a[num1++]=t; 
                v[t]=1; 
            } 
        } 
        memset(v,0,sizeof(v)); 
        int num2=0; 
        for(int i=0;i<m;i++) 
        { 
            cin>>t; 
            if(!v[t]) 
            { 
                v[t]=1; 
                b[num2++]=t; 
            } 
        } 
        sort(a,a+num1,cmp); 
        sort(b,b+num2,cmp); 
        int mm=0; 
        int index=-1; 
        int k; 
        for(int i=0;i<num1;i++) 
        { 
            for(int j=0;j<num2;j++) 
            { 
                if(a[i]==b[j]) 
                { 
                    for(k=1;k+i<num1&&k+j<num2;k++) 
                    { 
                        if(a[i+k]!=b[j+k]) 
                        break; 
                    } 
                    if(mm<k) 
                    { 
                        mm=k; 
                        index=i; 
                    } 
                } 
            } 
        } 
        int ans[105]; 
        int ans1=0; 
        if(!mm) 
        { 
            cout<<"NONE"<<endl; 
            continue; 
        } 
        bool flag=0; 
        for(int i=index;i<index+mm;i++) 
        { 
            ans[ans1++]=a[i]; 
            if(flag) 
            cout<<" "; 
            cout<<a[i]; 
            flag=1; 
        } 
        cout<<endl; 
        sort(ans,ans+ans1,cmp1); 
        cout<<ans[0]; 
        for(int i=1;i<ans1;i++) 
        cout<<" "<<ans[i]; 
        cout<<endl; 
 
    } 
    return 0; 

/*
4
4 4
10 10 30 20
50 50 30 20
8 8
10 38 27 55 44 66 75 66
38 27 77 44 55 66 66 98
7 8
50 40 30 20 10 5 25
50 40 30 20 10 5 24 23
4 4
10 20 30 40
50 60 70 80
*/ 
poj 4045 樹形DP,下次寫注釋
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <string> 
#include <cmath> 
#include <cstring> 
#include <queue> 
#include <set> 
#include <vector> 
#include <stack> 
#include <map> 
#include <iomanip> 
#define PI acos(-1.0) 
#define Max 2005 
#define inf 1<<28 
#define LL(x) (x<<1) 
#define RR(x) (x<<1|1) 
#define FOR(i,s,t) for(int i=(s);i<=(t);++i) 
#define ll long long 
using namespace std; 
 
int head[100005]; 
struct kdq 

    int u,v; 
    int next; 
} edge[100005]; 
int num=0; 
int n; 
ll node[50005],dp[50005]; 
bool vis[50005]; 
void addedge(int u,int v) 

    edge[num].u=u; 
    edge[num].v=v; 
    edge[num].next=head[u]; 
    head[u]=num++; 

void dfs(int k) 

    vis[k]=1; 
    dp[k]=0; 
    node[k]=1; 
    for(int i=head[k]; i!=-1; i=edge[i].next) 
    { 
        int v=edge[i].v; 
        if(!vis[v]) 
        { 
            dfs(v); 
            dp[k]=dp[k]+dp[v]+node[v]; 
            node[k]+=node[v]; 
        } 
    } 

void dfs1(int k) 

    vis[k]=1; 
    for(int i=head[k]; i!=-1; i=edge[i].next) 
    { 
        int v=edge[i].v; 
        if(!vis[v]) 
        { 
            dp[v]=dp[k]-2*node[v]+n; 
            dfs1(v); 
        } 
    } 

int main() 

    int T; 
    cin>>T; 
    int I,R; 
    int a,b; 
    while(T--) 
    { 
        cin>>n>>I>>R; 
        int d=n-1; 
        num=0; 
        memset(head,-1,sizeof(head)); 
        while(d--) 
        { 
            scanf("%d%d",&a,&b); 
            addedge(a,b); 
            addedge(b,a); 
        } 
        memset(vis,0,sizeof(vis)); 
        dfs(1); 
        memset(vis,0,sizeof(vis)); 
        dfs1(1); 
        ll MIN=(((ll)1)<<61); 
        for(int i=1;i<=n;i++) 
        { 
            if(dp[i]<MIN) 
            MIN=dp[i]; 
        } 
        bool flag=0; 
        cout<<I*I*R*MIN<<endl; 
        for(int i=1;i<=n;i++) 
        if(dp[i]==MIN) 
        { 
            if(flag) 
            cout<<" "; 
            cout<<i; 
            flag=1; 
        } 
        cout<<endl<<endl; 
    } 
    return 0; 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved