团体程序设计天梯赛(CCCC) L3015 球队“食物链” 状态压缩

时间：2021-06-30 08:05:20

团体程序设计天梯赛代码。体现代码技巧，比赛技巧。  https://github.com/congmingyige/cccc_code

团体程序设计天梯赛(CCCC) L3015 球队“食物链” 状态压缩

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <iostream>

 using namespace std;

 #define ll long long

 /*

 1肯定是要放在第一位

 节省空间

 所有数字前移一位（k作为k-1，0作为n）。

 2^20 -> 2^19

 如果

 使用康拓展开 19!< max long long

 而不是20进制，使用两个变量

 2^19*19*8 /1024/1024 =76

 */

 const int maxn=;

 const int inf=1e9;

 const double eps=1e-;

 ll value[maxn],num[<<maxn][maxn];

 bool f[<<maxn][maxn],vis[maxn],r[maxn+][maxn+];

 int ii,a[maxn],v=,n,pr[maxn],g_pr=;

 void dfs(int k,int d)

 {

     int i;

     if (k==)

     {

         int j,l,gl;

         ll num1;

         for (i=;i<=ii;i++)

             if (f[v][a[i]])

                 for (j=;j<=n-;j++)

                     if (!vis[j] && r[a[i]][j])

                     {

                         gl=;

                         for (l=;l<j;l++)

                             if (vis[l])

                                 gl++;

                         num1=num[v][a[i]]+value[-ii]*(j-gl);

                         if (!f[v|<<j][j] || num1<num[v|<<j][j])

                         {

                             f[v|<<j][j]=;

                             num[v|<<j][j]=num1;

                         }

                     }

         return;

     }

     for (i=d;i<=n-;i++)

     {

         v+=<<i;

         a[k]=i;

         vis[i]=;

         dfs(k-,i+);

         vis[i]=;

         v-=<<i;

     }

 }

 void work()

 {

     int i;

     if (n==)

     {

         if (r[][] && r[][])

             printf("1 2");

         else

             printf("No Solution");

         exit();

     }

     for (i=;i<=n-;i++)

         if (r[n-][i])

             f[<<i][i]=,num[<<i][i]=value[]*i;

     for (ii=;ii<=n-;ii++)

         dfs(ii,);

 }

 int main()

 {

     int i,j,k,ind,x,y;

     ll v;

     char c;

     value[]=;

     for (i=;i<=;i++)

         value[i]=value[i-]*i;

     scanf("%d",&n);

     for (i=;i<n;i++)   ///start from 0 (2^0 = 1)

     {

         x=(i==)?n-:i-;

         scanf("%c",&c);

         for (j=;j<n;j++)

         {

             y=(j==)?n-:j-;

             scanf("%c",&c);

             if (c=='W')

                 r[x][y]=;

             else if (c=='L')

                 r[y][x]=;

         }

     }

     work();

     j=(<<(n-))-;

     num[j][n-]=9e18;

     ind=n-;

     for (i=;i<=n-;i++)

         if (f[j][i] && r[i][n-] && num[j][i]<num[j][ind])

             ind=i;

     if (ind==n-)

     {

         printf("No Solution");

         return ;

     }

     memset(vis,,sizeof(vis));

     v=num[j][ind];

     printf("%d",);

     for (i=;i>=-n;i--)

     {

         j=v/value[i];

         k=;

         while (vis[k])

             k++;

         while (j--)

         {

             k++;

             while (vis[k])

                 k++;

         }

         printf(" %d",k+);

         vis[k]=;

         v%=value[i];

     }

     return ;

 }

 /*

 20

 -WWWWWWWWWWWWWWWWWWW

 W-WWWWWWWWWWWWWWWWWW

 WW-WWWWWWWWWWWWWWWWW

 WWW-WWWWWWWWWWWWWWWW

 WWWW-WWWWWWWWWWWWWWW

 WWWWW-WWWWWWWWWWWWWW

 WWWWWW-WWWWWWWWWWWWW

 WWWWWWW-WWWWWWWWWWWW

 WWWWWWWW-WWWWWWWWWWW

 WWWWWWWWW-WWWWWWWWWW

 WWWWWWWWWW-WWWWWWWWW

 WWWWWWWWWWW-WWWWWWWW

 WWWWWWWWWWWW-WWWWWWW

 WWWWWWWWWWWWW-WWWWWW

 WWWWWWWWWWWWWW-WWWWW

 WWWWWWWWWWWWWWW-WWWW

 WWWWWWWWWWWWWWWW-WWW

 WWWWWWWWWWWWWWWWW-WW

 WWWWWWWWWWWWWWWWWW-W

 WWWWWWWWWWWWWWWWWWW-

 3

 -WW

 W-W

 WW-

 3

 -WD

 D-W

 WD-

 */

相关文章