[关闭]
@Alpacadh 2019-02-19T15:01:39.000000Z 字数 4999 阅读 630

D、E、F

搜索

D - Mobile Computing

题意：

解题思路：

代码：

  1. #include<bits/stdc++.h>
  2. //#include<iostream>
  3. //#include<algorithm>
  4. //#include<cmath>
  5. //#include<cstring>
  6. //#include<stdio.h>
  7. using namespace std;
  8. const int inf=0x3f3f3f3f;
  9. const int N=1e4+5;
  10. const double eps=1e-4;
  11. typedef long long ll;
  12. typedef pair<int,ll> pil;
  13. struct node
  14. {
  15.     double l,r;
  16. }t[N];
  17. int vis[N];
  18. double w[N];
  19. double ans;
  20. double r;
  21. int n;
  22. int len;
  23. void dfs(int x)
  24. {
  25.     if(x==n-1)
  26.     {
  27.         if(t[len].l+t[len].r-r<eps)
  28.             ans=max(ans,t[len].l+t[len].r);
  29.         return;
  30.     }
  31.     for(int i=1;i<=len;i++)
  32.     {
  33.         if(!vis[i])
  34.         {
  35.             for(int j=1;j<=len;j++)
  36.             {
  37.                 if(!vis[j]&&i!=j)
  38.                 {
  39.                     vis[i]=1,vis[j]=1;
  40.                     len++;
  41.                     w[len]=w[i]+w[j];
  42.                     double dl=w[j]/(w[i]+w[j]),dr=1.0-dl;
  43.                     t[len].l=max(t[i].l+dl,t[j].l-dr);
  44.                     t[len].r=max(t[j].r+dr,t[i].r-dl);
  45.                     dfs(x+1);
  46.                     vis[i]=0,vis[j]=0,vis[len]=0;
  47.                     t[len].l=0,t[len].r=0;
  48.                     len--;
  49.                 }
  50.             }
  51.         }
  52.     }
  53. }
  54. int main()
  55. {
  56.     int T;
  57.     scanf("%d",&T);
  58.     while(T--)
  59.     {
  60.         memset(t,0,sizeof(t));
  61.         memset(w,0,sizeof(w));
  62.         memset(vis,0,sizeof(vis));
  63.         scanf("%lf%d",&r,&n);
  64.         for(int i=1;i<=n;i++)
  65.         {
  66.             scanf("%lf",&w[i]);
  67.         }
  68.         len=n;
  69.         ans=-1;
  70.         dfs(0);
  71.         if(ans==-1)
  72.             printf("%.f\n",ans);
  73.         else
  74.             printf("%.8f\n",ans);
  75.     }
  76.     return 0;
  77. }

E - The Morning after Halloween

题意：

解题思路：

代码：

(自己写的太复杂了，贴一下别人hash过的代码)

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cstdlib>
  5. #include <queue>
  6. using namespace std;
  8. const int maxs = 20;
  9. const int maxn = 150;
  11. int n,m,cnt,sum;
  12. int deg[maxn],G[maxn][maxn];
  13. int x[maxn],y[maxn],id[maxn][maxn];
  14. int d[maxn][maxn][maxn];
  15. int vis[maxn][maxn][maxn];
  16. int s[5],t[5];
  17. int dx[] = {0,0,0,-1,1};
  18. int dy[] = {0,1,-1,0,0};
  20. int find_ID(int a,int b,int c){
  21.     return (a<<16)|(b<<8)|c;
  22. }//hash操作，将三位数变成一个整数。
  24. bool conflict(int a,int b,int a2,int b2){
  25.     if((a2==b && a==b2) || a2==b2) return true;
  26.     return false;
  27. }
  29. int bfs(){
  30.     queue<int> que,anti_que;
  31.     d[s[0]][s[1]][s[2]] = 0;
  32.     d[t[0]][t[1]][t[2]] = 0;
  34.     que.push(find_ID(s[0],s[1],s[2]));
  35.     anti_que.push(find_ID(t[0],t[1],t[2]));
  37.     vis[s[0]][s[1]][s[2]] = 1;
  38.     vis[t[0]][t[1]][t[2]] = 2;
  40.     while(!que.empty() && !anti_que.empty()){
  41.         int num = que.size(),anti_num = anti_que.size();
  42.         while(num--){
  43.             int top = que.front();que.pop();
  44.             int a = (top>>16)&0xff,b = (top>>8)&0xff,c = (top&0xff);
  46.             for(int i = 0;i < deg[a];i++){
  47.                 int a2 = G[a][i];
  48.                 for(int j = 0;j < deg[b];j++){
  49.                     int b2 = G[b][j];
  50.                     if(conflict(a,b,a2,b2)) continue;
  51.                     for(int k = 0;k < deg[c];k++){
  52.                         int c2 = G[c][k];
  53.                         if(conflict(a,c,a2,c2)) continue;
  54.                         if(conflict(b,c,b2,c2)) continue;
  56.                         if(vis[a2][b2][c2] == 0){
  57.                             d[a2][b2][c2] = d[a][b][c]+1;
  58.                             vis[a2][b2][c2] = 1;
  59.                             que.push(find_ID(a2,b2,c2));
  60.                         }
  61.                         else if(vis[a2][b2][c2] == 2){
  62.                             return d[a][b][c]+d[a2][b2][c2]+1;
  63.                         }
  64.                     }
  65.                 }
  66.             }
  67.         }
  69.         while(anti_num--){
  70.             int top = anti_que.front();anti_que.pop();
  71.             int a = (top>>16)&0xff,b = (top>>8)&0xff,c = (top&0xff);
  73.             for(int i = 0;i < deg[a];i++){
  74.                 int a2 = G[a][i];
  75.                 for(int j = 0;j < deg[b];j++){
  76.                     int b2 = G[b][j];
  77.                     if(conflict(a,b,a2,b2)) continue;
  78.                     for(int k = 0;k < deg[c];k++){
  79.                         int c2 = G[c][k];
  80.                         if(conflict(a,c,a2,c2)) continue;
  81.                         if(conflict(b,c,b2,c2)) continue;
  83.                         if(vis[a2][b2][c2] == 0){
  84.                             d[a2][b2][c2] = d[a][b][c]+1;
  85.                             vis[a2][b2][c2] = 2;
  86.                             anti_que.push(find_ID(a2,b2,c2));
  87.                         }
  88.                         else if(vis[a2][b2][c2] == 1){
  89.                             return d[a][b][c]+d[a2][b2][c2]+1;
  90.                         }
  91.                     }
  92.                 }
  93.             }
  94.         }
  95.     }
  96.     return -1;
  97. }
  99. int main()
  100. {
  101.     //freopen("input.txt","r",stdin);
  102.     //freopen("output.txt","w",stdout);
  103.     while(~scanf("%d%d%d\n",&m,&n,&sum) && (m||n||sum)){
  104.         char gra[maxs][maxs];
  105.         cnt = 0;
  106.         memset(d,-1,sizeof(d));
  107.         memset(vis,0,sizeof(vis));
  108.         for(int i = 0;i < n;i++) fgets(gra[i],maxs,stdin);
  110.         for(int i = 0;i < n;i++){
  111.             for(int j = 0;j < m;j++){
  112.                 if(gra[i][j] != '#'){
  113.                     x[cnt] = i,y[cnt] = j,id[i][j] = cnt;
  114.                     if(islower(gra[i][j])) s[gra[i][j]-'a'] = cnt;
  115.                     else if(isupper(gra[i][j])) t[gra[i][j]-'A'] = cnt;
  116.                     cnt++;
  117.                 }
  118.             }
  119.         }
  121.         for(int i = 0;i < cnt;i++){
  122.             int X = x[i],Y = y[i];
  123.             deg[i] = 0;
  124.             for(int k = 0;k < 5;k++){
  125.                 int xx = X+dx[k],yy = Y+dy[k];
  126.                 if(gra[xx][yy] != '#') G[i][deg[i]++] = id[xx][yy];
  127.             }
  128.         }
  130.         if(sum <= 2){
  131.             s[2] = t[2] = G[cnt][0] = cnt;
  132.             deg[cnt++] = 1;
  133.         }
  134.         if(sum <= 1){
  135.             s[1] = t[1] = G[cnt][0] = cnt;
  136.             deg[cnt++] = 1;
  137.         }
  139.         printf("%d\n",bfs());
  140.     }
  141.     return 0;
  142. }

F - Editing a Book

题意：

解题思路：

代码：

  1. //#include<bits/stdc++.h>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<stdio.h>
  7. #include<cstdlib>
  8. #include<cstdio>
  9. using namespace std;
  10. const int inf=0x3f3f3f3f;
  11. const int N=10;
  12. const double eps=1e-4;
  13. typedef long long ll;
  14. typedef pair<int,ll> pil;
  15. int a[N];
  16. int n;
  17. bool check()
  18. {
  19.     for(int i=0;i<n-1;i++)
  20.     if(a[i]>a[i+1])
  21.         return false;
  22.     return true;
  23. }
  24. int h()
  25. {
  26.     int cnt=0;
  27.     for(int i=0;i<n-1;i++)
  28.     {
  29.         if(a[i]+1!=a[i+1])
  30.             cnt++;
  31.     }
  32.     if(a[n-1]!=n)
  33.         cnt++;
  34.     return cnt;
  35. }
  36. int dfs(int d,int dep)
  37. {
  38.     if(3*d+h()>3*dep)
  39.         return 0;
  40.     if(check())
  41.         return 1;
  42.     int b[N],tep[N];
  43.     memcpy(tep,a,sizeof(a));
  44.     for(int i=0;i<n;i++)
  45.     {
  46.         for(int j=i;j<n;j++)
  47.         {
  48.             int cnt=0;
  49.             for(int k=0;k<n;k++)
  50.             {
  51.                 if(k<i||k>j)
  52.                 {
  53.                     b[cnt++]=a[k];
  54.                 }
  55.             }
  56.             for(int k=0;k<=cnt;k++)
  57.             {
  58.                 int cnt1=0;
  59.                 for(int kk=0;kk<k;kk++)
  60.                     a[cnt1++]=b[kk];
  61.                 for(int kk=i;kk<=j;kk++)
  62.                     a[cnt1++]=tep[kk];
  63.                 for(int kk=k;kk<cnt;kk++)
  64.                     a[cnt1++]=b[kk];
  65.                 if(dfs(d+1,dep))
  66.                     return 1;
  67.                 memcpy(a,tep,sizeof(tep));
  68.             }
  69.         }
  70.     }
  71.     return 0;
  72. }
  73. int main()
  74. {
  75.     int tot=1;
  76.     while(scanf("%d",&n))
  77.     {
  78.         if(n==0)
  79.             break;
  80.         for(int i=0;i<n;i++)
  81.             scanf("%d",&a[i]);
  82.         int ans=5;
  83.         if(check())
  84.             ans=0;
  85.         else
  86.         {
  87.             for(int i=1;i<5;i++)
  88.             {
  89.                 if(dfs(0,i))
  90.                 {
  91.                     ans=i;
  92.                     break;
  93.                 }
  94.             }
  95.         }
  96.         printf("Case %d: %d\n",tot++,ans);
  97.     }
  98.     return 0;
  99. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注