2014西安全国邀请赛

陪人训练，只A了四个题，赛后五分钟AC J，难受

写题解的时候有点困，语言组织有点问题，有时间再更新 sorry

D - Wow! Such String!

题意：给你一个n（n<=5000000）,然后让你构造一个只包含小写字母的字符串，使得每一个长度大于等于4的子串在构造串中最多出现1次。

分析：由于限制长度大于等于4的子串只出现1次，我们想到长度为4的子串共有26*26*26*26种情况，可以直接枚举，对于每位我们枚举a到z的某一个，然后每次枚举后面的时候，我们需要判断这个序列在之前的串中是否出现过。当然这样枚举再碰到z之后会继续枚举aaa,这个时候就会无法枚举后一个，因此我们在没法继续枚举后一个的时候，加一个回溯，这样就能继续向下枚举了，最后只需要在最后把a加上就行。当n大于26*26*26*26+3时，输出 Impossible。学弟用枚举26进制的方法也过了，在枚举26进制，连接数字的时候需要注意一下，其他没什么情况。

AC代码：

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 long long a[500005];
 6 bool mp[27][27][27][27];
 7 int main(){
 8     ios_base::sync_with_stdio(0);
 9     cin.tie(0);
10     int n;
11     for(int i=1;i<=4;i++){
12         a[i]=0;
13     }
14     memset(mp,false,sizeof(mp));
15     memset(a,0,sizeof(a));
16     mp[a[1]][a[2]][a[3]][a[4]]=true;
17     int d=26*26*26*26;
18     int p=0;
19     for(int i=5;i<=d;i++){
20         p=0;
21         for(int j=0;j<26;j++){
22             a[i]=j;
23             if(!mp[a[i-3]][a[i-2]][a[i-1]][a[i]]){
24                 mp[a[i-3]][a[i-2]][a[i-1]][a[i]]=true;
25                 p=1;
26                 break;
27             }
28         }
29         if(p==0){
30             i=i-2;
31         }
32     }
33     while(cin>>n){
34         if(n>d+3) {cout<<"Impossible"<<endl;continue;}
35         for(int i=1;i<=n;i++){
36             char c=('a'+a[i]);
37             cout<<c;
38         }
39         cout<<endl;
40     }
41 
42 return 0;
43 }

View Code

J - Tunnels

题意：给你n，m分别代表正方形地图的边长和管道的个数，在这个地图中有m个管道，分别有入口和出口。从入口到出口不需要花费时间，然后问你从任意管道进入，遍历完其他管道，且每个管道只经过一次，求所需要的最短路是多少。n,m<=15

分析：由于题目限制每个管道只经过一次，然后看一下数据范围，可以确定是状态压缩。首先我们需要bfs预处理每个管道之间的距离，接下来我们就可以利用状压DP来解决了。

　　对于某一个状态dp[i][j]表示经过的管道为i的二进制位为1的管道，最后一个经过的管道是j管道。现在我们要转移到下一个状态。从i状态可以到达的状态是把i的二进制为0 的某一位变为1的状态。比如从dp[i][j]状态要求再经过第k个管道，那么最终状态就会变成dp[i|(1<<(k-1))]，那么我们的状态转移方程就是dp[i|(1<<(k-1))][k]=min(dp[i|(1<<(k-1))][k],dp[i][j]+mp[j][k]) 我的管道编号是从1开始的。然后进行状态转移时我们必须保证i的第j位为1，且第k位为0，且状态i是存在的，这样就可以了。（我这个bfs写的是真jb恐怖，这样写不好，大家别学我，还是把方向存在数组里比较稳 23333）

AC代码：、

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 char c[20][20];
  6 struct st{
  7     int a,b,c,d;
  8 }s[25];
  9 int dj[25][25];
 10 int mp[25][25];
 11 bool vis[25][25];
 12 int n,m;
 13 int result;
 14 int dp[32768+5][25];
 15 struct qt{
 16     int x,y;
 17     qt(int _x,int _y){
 18         x=_x;
 19         y=_y;
 20     }
 21 };
 22 void bfs(int x1,int y1){
 23     queue<qt>q;
 24     q.push(qt(x1,y1));
 25     while(!q.empty()){
 26         qt p=q.front();
 27         q.pop();
 28         if((!vis[p.x+1][p.y])&&c[p.x+1][p.y]=='.'){
 29             dj[p.x+1][p.y]=dj[p.x][p.y]+1;
 30             vis[p.x+1][p.y]=true;
 31             q.push(qt(p.x+1,p.y));
 32         }
 33         if((!vis[p.x-1][p.y])&&c[p.x-1][p.y]=='.'){
 34             dj[p.x-1][p.y]=dj[p.x][p.y]+1;
 35             vis[p.x-1][p.y]=true;
 36             q.push(qt(p.x-1,p.y));
 37         }
 38         if((!vis[p.x][p.y+1])&&c[p.x][p.y+1]=='.'){
 39             dj[p.x][p.y+1]=dj[p.x][p.y]+1;
 40             vis[p.x][p.y+1]=true;
 41             q.push(qt(p.x,p.y+1));
 42         }
 43         if((!vis[p.x][p.y-1])&&c[p.x][p.y-1]=='.'){
 44             dj[p.x][p.y-1]=dj[p.x][p.y]+1;
 45             vis[p.x][p.y-1]=true;
 46             q.push(qt(p.x,p.y-1));
 47         }
 48     }
 49 }
 50 int main(){
 51     ios_base::sync_with_stdio(0);
 52     cin.tie(0);
 53     while(cin>>n>>m){
 54         memset(c,'#',sizeof(c));
 55         for(int i=1;i<=n;i++){
 56             for(int j=1;j<=n;j++){
 57                 cin>>c[i][j];
 58             }
 59         }
 60         memset(mp,0x3f3f3f3f,sizeof(mp));
 61         for(int i=1;i<=m;i++){
 62             cin>>s[i].a>>s[i].b>>s[i].c>>s[i].d;
 63         }
 64         for(int i=1;i<=m;i++){
 65             memset(dj,0x3f3f3f3f,sizeof(dj));
 66             dj[s[i].c][s[i].d]=0;
 67             memset(vis,false,sizeof(vis));
 68             vis[s[i].c][s[i].d]=true;
 69             bfs(s[i].c,s[i].d);
 70             for(int j=1;j<=m;j++){
 71                 if(i!=j){
 72                     mp[i][j]=dj[s[j].a][s[j].b];
 73                 }
 74             }
 75         }
 76         int d=1;
 77         memset(dp,0x3f3f3f3f,sizeof(dp));
 78         for(int i=1;i<=m;i++){
 79             dp[d][i]=0;
 80             d*=2;
 81         }
 82         for(int i=1;i<d;i++){
 83             for(int j=1;j<=m;j++){
 84                 if(!i&(1<<(j-1))) continue;
 85                 for(int k=1;k<=m;k++){
 86                     if(i&(1<<(k-1))||mp[j][k]==0x3f3f3f3f) continue;
 87                     if(dp[i][j]==0x3f3f3f3f) continue;
 88                     dp[i|(1<<(k-1))][k]=min(dp[i|(1<<(k-1))][k],dp[i][j]+mp[j][k]);
 89                 }
 90             }
 91         }
 92         result=0x3f3f3f3f;
 93         for(int i=1;i<=m;i++){
 94             result=min(dp[d-1][i],result);
 95         }
 96         if(result==0x3f3f3f3f){
 97             cout<<-1<<endl;
 98         }
 99         else cout<<result<<endl;
100     }
101 return 0;
102 }

View Code

然后就一共过了5个题其他题一个人也没时间读了，英语比较菜，加油加油