组队练习赛（Regionals 2012, North America

组队练习赛（Regionals 2012, North America - East Central NA）

阅读量：6841 次

发布时间：2019-06-26

本文共 4053 字，大约阅读时间需要 13 分钟。

A.Babs' Box Boutique

给定n个盒子，每个盒子都有长宽高（任意两个盒子长宽高不完全相同），现在选盒子的任意两面，要求x1 <= x2 && y1 <= y2,问最多能选多少盒子满足这需求。

直接dfs暴搞................

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          # define INF 0x7FFFFFFFusing namespace std;int vis[11];struct node { int a[3];}p[11];int ans,n;int dx[] = {0,0,1};int dy[] = {1,2,2};//bool cmp(int a,int b) {// return a > b;//}void dfs(int step,int x,int y) { if(step > ans) ans = step; if(step == n) return ; for(int i=0; i
           
            = x && yy >= y ) { vis[i] = 1; dfs(step + 1,xx,yy); vis[i] = 0; } } }}int main() { int casee = 1; while(scanf("%d",&n) && n) { if(n == 0) break; int tmp[3]; for(int i=0; i

C.Hexagon Perplexagon

题意就不写了：

dfs暴搞，每一层传入三个参数，层数，每一块需要匹配的前驱点，和最后一块需要匹配的点..........

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int map[8][8];int ans[8];int save[8];int vis[8];int n,ok;void change(int x,int pos) { int i; for(i=0; i<6; i++) { if(map[x][i] == pos) break; } pos = i; int cnt = 0; for(int i=0; i<6; i++) { save[cnt++] = map[x][pos]; pos ++; if(pos >= 6) pos -= 6; }}int getpre(int pos,int t) { t --; if(t < 0) t = 5; return map[pos][t];}int getsuc(int pos,int t) { t ++; if(t > 5) t = 0; return map[pos][t];}void dfs(int step,int p1,int p2) { if(step == 7) return ; if(ok == 1) return ; for(int i=0; i<7; i++) { if(vis[i] == 1) continue; int j; for(j=0; j<6; j++) { if(map[i][j] == save[step-1]) break; } int tmp1 = getpre(i,j); int tmp2 = getsuc(i,j); if(step == 1) { ans[step] = i; vis[i] = 1; dfs(step + 1,tmp1,tmp2); vis[i] = 0; } if(step > 1 && step < 6) { if(tmp2 == p1 ) { ans[step] = i; vis[i] = 1; dfs(step+1,tmp1,p2); vis[i] = 0; } } if(step == 6) { if(tmp2 == p1 && tmp1 == p2 ) { ans[step] = i; ok = 1; } } if(ok == 1) return ; }}int main() { int T; cin >> T; int casee = 1; while(T --) { for(int i=0; i<7; i++) { for(int j=0; j<6; j++) { scanf("%d",&map[i][j]); } } ok = 0; for(int i=0; i<7; i++) { memset(vis,0,sizeof(vis)); vis[i] = 1; change(i,1); ans[0] = i; dfs(1,0,0); if(ok) break; } printf("Case %d: ",casee++); if(ok == 0) { printf("No solution\n"); continue; } printf("%d",ans[0]); for(int i=1; i<7; i++) { printf(" %d",ans[i]); } puts(""); } return 0;}

D.I've Got Your Back(gammon)

暴搞，每一种排列分别保存它的各个点的情况，并且用map保存每种排列的顺序下标

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;struct node{ int pos[10];} p[20000];map 
          
           mm;int cnt ;string str = "";string str2 = "";string change(int x){ str = ""; str2 = ""; if(x == 0) { str += '0'; return str; } int cn = 0; while(x) { int t = x % 10; str += t + '0'; x = x / 10; } int len = str.length(); for(int i=len-1; i>=0; i--) str2 += str[i]; str2 += '\0'; return str2;}void init(){ cnt = 0; for(int i=0; i<=15; i++) { for(int j=0; j<=15; j++) { for(int k=0; k<=15; k++) { for(int l=0; l<=15; l++) { for(int x=0; x<=15; x++) { for(int y=0; y<=15; y++) { int t = i + j + k + l + x + y; if(t > 15) break; if(t == 15) { string tmp; p[cnt].pos[0] = i; p[cnt].pos[1] = j; p[cnt].pos[2] = k; p[cnt].pos[3] = l; p[cnt].pos[4] = x; p[cnt].pos[5] = y; tmp += change(i); tmp += ' '; tmp += change(j); tmp += ' '; tmp += change(k); tmp += ' '; tmp += change(l); tmp += ' '; tmp += change(x); tmp += ' '; tmp += change(y); mm[tmp] = cnt; cnt ++; } } } } } } }}int n;int main(){ init(); char c; int a,b,d,e,f,g; int casee = 1; while(cin >> c) { if(c == 'e') break; printf("Case %d: ",casee++); if(c == 'm') { scanf("%d%d%d%d%d%d",&a,&b,&d,&e,&f,&g); string tmp; tmp += change(a); tmp += ' '; tmp += change(b); tmp += ' '; tmp += change(d); tmp += ' '; tmp += change(e); tmp += ' '; tmp += change(f); tmp += ' '; tmp += change(g); //cout << tmp << endl; printf("%d\n",mm[tmp]); } if(c == 'u') { scanf("%d",&a); printf("%d",p[a].pos[0]); for(int i=1; i<6; i++) { printf(" %d",p[a].pos[i]); } puts(""); } } return 0;}