使用者經驗

http://www.cc.ntu.edu.tw/chinese/epaper/0027/20131220_2704.html

推推

存檔文

UVA - 1352

1352 - Colored Cubes

弄了好久
這題似乎只能暴力
吧
...

邏輯上有兩點
1.找到所有方塊的旋轉方式
2.更改最少的面

我一開始弄成
找到一種旋轉方式
使其他方塊變成第一種= =
還好範側第六組有測到^^

#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;
void _rotate(char status[][7],int n){
    for(int i=1 ; i<4 ; i++){
        status[n+i][0]=status[n+i-1][0];
        status[n+i][1]=status[n+i-1][3];
        status[n+i][2]=status[n+i-1][1];
        status[n+i][3]=status[n+i-1][4];
        status[n+i][4]=status[n+i-1][2];
        status[n+i][5]=status[n+i-1][5];
        status[n+i][6]='\0';
    }
}
void find_status(char status[][7]){
    strcpy(status[0],"123456");
    strcpy(status[4],"263415");
    strcpy(status[8],"326154");
    strcpy(status[12],"421653");
    strcpy(status[16],"513462");
    strcpy(status[20],"653421");
    _rotate(status,0);
    _rotate(status,4);
    _rotate(status,8);
    _rotate(status,12);
    _rotate(status,16);
    _rotate(status,20);
}
int find_color(string temp, string color[26], int *noc){
    for(int i=0 ; i<*noc ; i++)
        if(color[i]==temp)
            return i;
    color[(*noc)++]=temp;
    return (*noc-1);
}
inline int convert(int i, int k, int j){
    if(k==0)
        return 0;
    if(k==1)
        return i%24;
    if(k==2)
        return (i/24)%24;
    if(k==3)
        return (i/576)%24;
}
int diff(int i, char status[][7], int block[][6], int n){
    int re=0;int color[24],maxi;
    for(int j=0 ; j<6 ; j++){
        memset(color,0,4*24);maxi=0;
        for(int k=0 ; k<n ; k++){
            color[block[k][status[convert(i,k,j)][j]-49]]++;
            maxi=(maxi>=color[block[k][status[convert(i,k,j)][j]-49]]?maxi:color[block[k][status[convert(i,k,j)][j]-49]]);
        }
        re+=(n-maxi);
    }
    return re;
}
int guess(char status[][7], int block[4][6], int n, int top){
    int s=100,ts,i;
    for(i=0 ; i<top && s!=0 ; i++){
        ts=diff(i,status,block,n);
        s=(s<ts?s:ts);
    }
    return s;
}
int main(){
    char status[24][7];
    find_status(status);
    int n,ans,ta,top;
    string color[26];int noc;
    string temp;
    int block[4][6];
    while(cin>>n && n!=0){
        noc=0;top=1;ans=50;
        for(int i=0 ; i<n ; i++)
            for(int j=0 ; j<6; j++){
                cin>>temp;
                block[i][j]=find_color(temp,color,&noc);
            }
        noc=n-1;
        while(noc--)
            top*=24;

        ta=guess(status,block,n,top);
        ans=(ans<ta?ans:ta);

        cout<<ans<<'\n';
    }
return 0;
}

寫得有點冗= =
執行時間也有點慢...

UVA-11464

UVA-11464 - Even Parity

這陣子各種鬼混

然後就練了一下暴搜

我不懂為什麼有人程式執行時間可以達到我的一半...

傳說

每三個男人中

就有一隻魯蛇

不過我們先別管這個了...

#include<iostream>
#include<algorithm>
using namespace std;
int num(int ans[][16],int i,int j,int n){
    int re=0;
    if(i-2>=0)
        re+=ans[i-2][j];
    if(i-1>=0 && j-1>=0)
        re+=ans[i-1][j-1];
    if(i-1>=0 && j+1<n)
        re+=ans[i-1][j+1];
    return (re%2);
}
bool fill(int ans[][16],int map[][16],int n){
    for(int i=1 ; i<n ; i++)
    for(int j=0 ; j<n ; j++){
        ans[i][j]=num(ans,i,j,n);
        if(map[i][j]==1 && ans[i][j]==0)
            return false;
    }
    return true;
}
int diff(int ans[][16],int map[][16],int n){
    int re=0;
    for(int i=0 ; i<n ; i++)
    for(int j=0 ; j<n ; j++)
        if(ans[i][j]==1 && map[i][j]==0)
            re++;
    return re;
}
int guess(int ans[][16], int map[][16], int n, int s){
    int p=-1,ts;bool t1;
    while(++p<=(1<<n)){
        t1=true;
        for(int i=0 ; i<n && t1; i++){
            ans[0][i]=((p>>i)&1);
            if(map[0][i]==1 && ans[0][i]==0)
                t1=false;
        }
        if(t1 && fill(ans,map,n)){
            ts=diff(ans,map,n);
            s=min(s,ts);
        }
    }
    return s;
}

int main(){
    int T,t=0,n,s;
    int map[16][16];
    int ans[16][16];
    cin>>T;
    while(T>t++){
        cin>>n;
        for(int i=0 ; i<n ; i++)
            for(int j=0 ; j<n ; j++)
                cin>>map[i][j];
        s=guess(ans,map,n,256);
        if(s!=256)
            cout<<"Case "<<t<<": "<<s<<'\n';
        else
            cout<<"Case "<<t<<": -1\n";
    }
return 0;
}

UVA-1030

UVA-1030 - Image Is Everything


這題在寫得時候真的很煩人
memset不知道為什麼完全沒有作用...
害我原本==1 找了好久才發現根本不會被set成 1 = =

另外就是再處理某一格是否存在方塊時的邏輯:
1. 先把可以看透的行刪掉
2. 檢查是否每一方塊從每一面看都是同一顏色

想起來很容易
但是在實作上有一些難點:
1.
輸入的格式非常的機車
我在處理的時候就沒弄好
導致投影到真實物件上時要做很多轉換 030
2.
因為在檢查一個方塊是否存在時
不知道隔壁的方塊是否真的存在
還是只是還沒踢除而已
所以就給他跑一個while
直到都沒有更新時就可以判定已經檢查完成

因為邊寫邊RC
寫的超冗
結果DEBUG超久= =

寫這麼冗貼出來有點不好意思///

#include<iostream>
#include<stdio.h>
#include<string.h>
bool check(int obj[][10][10], int n, int i, int j, int k, char side[][10][10]){
    char color=1;
    int m,F;
    m=i+1;F=1;
    if(side[3][k][n-j-1]=='.' || side[1][k][j]=='.' || side[0][k][i]=='.' || side[2][k][n-i-1]=='.' || side[5][n-j-1][i]=='.' || side[4][j][i]=='.')
        return false;
    while(F && m>=0 && m<n){    //3
        if(obj[m][j][k]!=0)
            F=0;
        m++;
    }
    if(F){
        color=side[3][k][n-j-1];
    }
    m=i-1;F=1;
    while(F && m>=0 && m<n){    //1
        if(obj[m][j][k]!=0)
            F=0;
        m--;
    }
    if(F){
        if(color==1)
            color=side[1][k][j];
        else if(color!=side[1][k][j])
            return false;
    }
    m=j+1;F=1;
    while(F && m>=0 && m<n){    //0
        if(obj[i][m][k]!=0)
            F=0;
        m++;
    }
    if(F){
        if(color==1)
            color=side[0][k][i];
        else if(color!=side[0][k][i])
            return false;
    }
    m=j-1;F=1;
    while(F && m>=0 && m<n){    //2
        if(obj[i][m][k]!=0)
            F=0;
        m--;
    }
    if(F){
        if(color==1)
            color=side[2][k][n-i-1];
        else if(color!=side[2][k][n-i-1])
            return false;
    }
    m=k+1;F=1;
    while(F && m>=0 && m<n){    //5
        if(obj[i][j][m]!=0)
            F=0;
        m++;
    }
    if(F){
        if(color==1)
            color=side[5][n-j-1][i];
        else if(color!=side[5][n-j-1][i])
            return false;
    }
    m=k-1;F=1;
    while(F && m>=0 && m<n){    //4
        if(obj[i][j][m]!=0)
            F=0;
        m--;
    }
    if(F){
        if(color==1)
            color=side[4][j][i];
        else if(color!=side[4][j][i])
            return false;
    }
    return true;
}

int main(){
    int ans;
    int obj[10][10][10];
    char side[6][10][10];  //F L BA R T BU
    memset(obj,1,4*10*10*10);
    int n;
    while(scanf("%d",&n)==1 && n!=0){
        ans=0;
        memset(obj,1,4*10*10*10);
        for(int i=0 ; i<n ; i++)
            for(int j=0 ; j<6 ; j++)
                for(int k=0 ; k<n ; k++)
                    scanf(" %c",&side[j][i][k]);
        int FINE=1;
        while(FINE){
            FINE=0;
            for(int i=0 ; i<n ; i++)
                for(int j=0 ; j<n ; j++)
                    for(int k=0 ; k<n ; k++)
                        if(obj[i][j][k]!=0)
                            if(!check(obj, n, i, j, k,side)){
                                obj[i][j][k]=0;
                                FINE=1;
                            }

        }
        for(int i=0 ; i<n ; i++)
            for(int j=0 ; j<n ; j++)
                for(int k=0 ; k<n ; k++)
                    if(obj[i][j][k]!=0)
                        ans+=1;
        printf("Maximum weight: %d gram(s)\n",ans);
    }
return 0;
}

寫程式絕對要專心><

UVA-103

UVA-103   Stacking Boxes

這題要注意題意
當兩個邊重疊時也不能算喔
筆者就卡這個卡了一小時多...

#include<iostream>
#include<stdio.h>
#include<algorithm>
int box[31][10],temp[10];
int b,d;
int ans,ansb[31][31],order[31]={0};
int tempb[31],rm;
bool st(int a,int w){
    for(int q=0;q<d;q++)
        if(box[a][q]!=box[w][q])
            return box[a][q]<box[w][q];
    return true;
} 
bool check(int i,int j){
    bool FT=true;
    for(int k=0;k<d;k++)
        if(box[i][k]>=box[j][k]){
            FT=false;
            break;
        }
    return FT;    
}
using namespace std;
int main(){
    while(scanf("%d%d",&b,&d)!=EOF){
        for(int i=1;i<=b;i++){
            order[i]=i;
            for(int j=0;j<d;j++)
                cin>>temp[j];
            sort(temp,temp+d);
            for(int j=0;j<d;j++)
                box[i][j]=temp[j];
        }
        sort(order+1,order+1+b,st);
        ansb[order[1]][0]=order[1];tempb[order[1]]=1;
        for(int i=2;i<=b;i++){
            ansb[order[i]][0]=order[i];tempb[order[i]]=i;
            int max=0;
            for(int j=i-1;j>0;j--)
                if(check(order[j],order[i]))
                    if(tempb[order[j]]>max){
                        rm=j;
                        max=tempb[order[j]];
                    }
            tempb[order[i]]=max+1;
            for(int j=0;j<max;j++)
                ansb[order[i]][j]=ansb[order[rm]][j];
            ansb[order[i]][max]=order[i];
        }
        int mem=1;
        for(int i=2;i<=b;i++)
            mem=(tempb[order[mem]]>tempb[order[i]])?(mem):(i);    
        cout<<tempb[order[mem]]<<'\n';
        for(int i=0;i<tempb[order[mem]];i++)
            printf("%d ",ansb[order[mem]][i]);
        cout<<endl;
    }
return 0;    
}

UVA-102

UVA-102   Ecological Bin Packing

這題搞笑啊..

#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
    long long int can[3][3];
    long long int pos[6],ans;
    while(scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld",&(can[0][0]),&(can[0][1]),&(can[0][2]),&(can[1][0]),&(can[1][1]),&(can[1][2]),&can[2][0],&can[2][1],&can[2][2])!=EOF){
        pos[1]=can[0][1]*1+can[0][2]*1+can[1][0]*1+can[1][2]*1+can[2][0]*1+can[2][1]*1;
        pos[0]=can[0][1]*1+can[0][2]*1+can[1][0]*1+can[1][1]*1+can[2][0]*1+can[2][2]*1;
        pos[4]=can[0][0]*1+can[0][2]*1+can[1][1]*1+can[1][2]*1+can[2][0]*1+can[2][1]*1;
        pos[5]=can[0][0]*1+can[0][2]*1+can[1][0]*1+can[1][1]*1+can[2][1]*1+can[2][2]*1;
        pos[2]=can[0][0]*1+can[0][1]*1+can[1][1]*1+can[1][2]*1+can[2][0]*1+can[2][2]*1;
        pos[3]=can[0][0]*1+can[0][1]*1+can[1][0]*1+can[1][2]*1+can[2][1]*1+can[2][2]*1;
        ans=pos[0];
        for(int i=1;i<6;i++)
            ans=(ans<pos[i])?(ans):(pos[i]);
        for(int i=0;i<6;i++){
            if(ans==pos[i]){
                switch(i){
                    case 0:
                        cout<<"BCG ";
                        break;
                    case 1:
                        cout<<"BGC ";
                        break;
                    case 2:
                        cout<<"CBG ";
                        break;
                    case 3:
                        cout<<"CGB ";
                        break;
                    case 4:
                        cout<<"GBC ";
                        break;
                    case 5:
                        cout<<"GCB ";
                        break;    
                }
                cout<<pos[i]<<'\n';
                break;
            }
        }
    }
return 0;    
}

完全賣萌030

UVA-101

UVA-101  block problems
這題我無腦亂寫的
純粹貼上來好玩而已
千萬不要學這種爛coding風格..

#include<iostream>
#include<string>
using namespace std;
int main(){
    int blockval[26];
    int stacks[26][26];
    int pile[26],high[26];
    
    int n,a,b,ta,tb,temp,tc,td;
    string temp1,temp2;
    cin>>n;
    for(int i=0;i<n;i++){
        blockval[i]=1;    
        stacks[i][0]=i;
        pile[i]=i;
        high[i]=0;
    }
    while(1){
        cin>>temp1;
        if(temp1=="quit"){
            
            for(int i=0;i<n;i++){
                cout<<i<<":";
                for(int j=0;j<blockval[i];j++){
                    cout<<" "<<stacks[i][j];
                }
            cout<<endl;
            }
        break;
        }
            
        cin>>a>>temp2>>b;
        temp1=temp1+temp2;
        if(a==b || pile[a]==pile[b])
            continue;
        ta=a;tb=b;
        if(temp1=="moveonto"){
            ta=pile[a];tb=high[a];
            tc=pile[b];td=high[b];
            temp=blockval[pile[a]];
            if(pile[a]==pile[b] &&high[a]<high[b]){
                continue;
            }
            for(int i=high[a]+1;i<blockval[pile[a]];i++){
                blockval[stacks[ta][i]]=1;
                pile[stacks[ta][i]]=stacks[ta][i];
                high[stacks[ta][i]]=0;
            }
            for(int i=high[b]+1;i<blockval[pile[b]];i++){
                blockval[stacks[tc][i]]=1;
                pile[stacks[tc][i]]=stacks[tc][i];
                high[stacks[tc][i]]=0;
            }
            pile[a]=pile[b];
            high[a]=high[b]+1;
            stacks[pile[b]][high[a]]=a;
            blockval[ta]=tb;
            blockval[pile[b]]=td+2;
            
        }
        if(temp1=="moveover"){
            ta=pile[a];tb=high[a];
            temp=blockval[pile[a]];
            for(int i=high[a]+1;i<blockval[pile[a]];i++){
                blockval[stacks[pile[a]][i]]=1;
                pile[stacks[pile[a]][i]]=stacks[pile[a]][i];
                high[stacks[pile[a]][i]]=0;
            }
            stacks[pile[b]][blockval[pile[b]]]=a;
            blockval[ta]=tb;
            pile[a]=pile[b];
            high[a]=blockval[pile[b]];
            blockval[pile[b]]+=1;
            //cout<<'\n'<<"pilehigh of "<<pile[a]<<"="<<blockval[pile[a]]<<'\n';
        }
        if(temp1=="pileonto"){
            ta=pile[a];tb=high[a];
            tc=pile[b];td=high[b];
            temp=blockval[pile[a]];
            for(int i=high[b]+1;i<blockval[pile[b]];i++){
                blockval[stacks[tc][i]]=1;
                pile[stacks[tc][i]]=stacks[tc][i];
                high[stacks[tc][i]]=0;
            }
            for(int i=high[a];i<temp;i++){
                high[stacks[ta][i]]=i-tb+high[b]+1;
                stacks[pile[b]][high[stacks[ta][i]]]=stacks[ta][i];
                pile[stacks[ta][i]]=pile[b];
            }
            blockval[ta]=tb;
            blockval[tc]=high[b]+temp-tb+1;
        }
        if(temp1=="pileover"){
            ta=pile[a];tb=high[a];
            temp=blockval[pile[a]];
            if(pile[a]==pile[b] &&high[a]<high[b]){
                continue;
            }
            //cout<<'\n'<<"blockval[pile[a]]="<<blockval[pile[a]]<<", high[a]="<<high[a]<<'\n';
            for(int i=high[a];i<temp;i++){
                high[stacks[ta][i]]=i-tb+blockval[pile[b]];
                //cout<<"high[stacks[ta][i]]="<<high[stacks[ta][i]]<<endl;
                stacks[pile[b]][high[stacks[ta][i]]]=stacks[ta][i];
                pile[stacks[ta][i]]=pile[b];
            }
            blockval[pile[b]]+=temp-tb;
            blockval[ta]=tb;
            //cout<<'\n'<<"pilehigh of "<<pile[b]<<"="<<blockval[pile[b]]<<'\n';
        }
    }

    cin>>temp1;
return 0;    
}

真的亂寫030

UVA-11300

UVA-11330 Spreading the Wealth

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,i;
    unsigned long long ans;
    vector <long long>money;
    long long equal;
    unsigned long long temp;
    while(scanf("%d",&n)==1){
        money.clear();
        equal=0;ans=0;
        for(i=0;i<n;i++){
            scanf("%lld",&temp);
            money.push_back(temp);
            equal+=temp;
        }
        equal/=n;
        for(i=0;i<n;i++){
            money[i]=money[i]-equal;
            if(i>1){
                money[i]+=money[i-1];
            }
        }
        money[0]=0;
        sort(money.begin()++,money.end());
        for(i=0;i<n;i++){
            if(money[n/2]>=money[i])
                temp=money[n/2]-money[i];
            else
                temp=money[i]-money[n/2];
            ans+=temp;
        }
        printf("%lld\n",ans);
    }
return 0;
}

這題是數學分析
在下抓bug抓超久的...

UVA-11292

UVA-11292    The Dragon of Loowater

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
    int n,m,ans;
    int dragon[20000],worrior[20000];
    bool ANS;
    while(scanf("%d%d",&n,&m)==2){
        if(n==0 && m==0)
            break;
        for(int i=0;i<n;i++){
            scanf("%d",&dragon[i]);
        }
        for(int i=0;i<m;i++){
            scanf("%d",&worrior[i]);
        }
        ans=0;ANS=false;
        if(n>m)
            printf("Loowater is doomed!\n");
        else{
            sort(dragon,dragon+n);
            sort(worrior,worrior+m);
            if(dragon[n-1]>worrior[m-1]){
                printf("Loowater is doomed!\n");
                break;
            }
            int count=0;
            for(int i=0;i<n;i++){
                ANS=false;
                for(int j=count;j<m;j++){
                    if(dragon[i]<=worrior[j]){
                        count=j+1;
                        ans+=worrior[j];
                        ANS=true;
                        break;
                    }
                }
                if(!ANS)
                    break;                
            }
            if(!ANS)
                printf("Loowater is doomed!\n");
            else
                printf("%d\n",ans);
        }
    }
    
    
return 0;
}

不知道為什麼，一開始送的時候一直RE= =

UVA-11729

UVA-11729  Commando War

#include<stdio.h>
#include<algorithm>
using namespace std;
int soldier[1000][2];
int ans[1000],temp,out;
bool cmp(int a,int b){
    return soldier[a][1]>soldier[b][1];
}
int main(){
    int cases=0,n;
    while(scanf("%d",&n) && n){
        cases++;
        temp=0;out=0;
        for(int i=0;i<n;i++){
            scanf("%d%d",&(soldier[i][0]),&(soldier[i][1]));
            ans[i]=i;
        }
        sort(ans,ans+n,cmp);
        for(int i=0;i<n;i++){
            out+=soldier[ans[i]][0];
            temp=(temp>out+soldier[ans[i]][1])?(temp):(out+soldier[ans[i]][1]);    
        }
        out+=soldier[ans[n-1]][1];
        printf("Case %d: %d\n",cases,temp>out?temp:out);
    }
return 0;    
}

這題也是一開始一直RE，莫名其妙 030