使用者經驗

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