现有串x=11110000,y=11001100,z=10101010,通过这三个串只用与或非三种操作到达给定的串，优先级非>或>与，可以加括号，问表达式最短的里面字典序最小的是谁，有<=10000个询问。
一个串，经过某种变换，到达另一个串，这种转移关系用图论极其合适。那么问题就转化成了一个最短路问题，其中最短包含题目的两个条件。
然而，“某种变换”，即与或非，能否进行，跟优先级息息相关的。这里所关系到的优先级其实指的是最后一次操作的优先级。因此把最后一次操作是谁也列入状态。
然后就划一下优先级，可以发现括号和非同级(3)，然后与(2)，然后或(1)。这样就可以转移了：>=3级的可以加非，>=2级的可以加与，>=1级的可以加或，而与和或都需要枚举其他所有不低于当前状态优先级的状态来转移，所以复杂度(n^2*log(n)*字符串比较)，大约是(n^3)。
1 #include<string.h> 2 #include<stdlib.h> 3 #include<stdio.h> 4 //#include<assert.h> 5 #include<algorithm> 6 #include<string> 7 #include<queue> 8 #include<iostream> 9 using namespace std; 10 11 int n=256,x=240,y=204,z=170; 12 13 bool ls(const string &a,const string &b) 14 { 15 if (a.length()!=b.length()) return a.length()<b.length(); 16 return a<b; 17 } 18 19 #define maxn 311 20 string dis[maxn][3]; 21 struct qnode 22 { 23 int id,p; 24 bool operator < (const qnode &b) const {return ls(dis[id][p],dis[b.id][b.p]);} 25 bool operator > (const qnode &b) const {return ls(dis[b.id][b.p],dis[id][p]);} 26 }; 27 priority_queue<qnode,vector<qnode>,greater<qnode> > q; 28 void insert(int a,int b,string s) 29 { 30 if (dis[a][b].empty() || ls(s,dis[a][b])) 31 { 32 dis[a][b]=s; 33 q.push((qnode){a,b}); 34 } 35 } 36 void dijkstra() 37 { 38 insert(x,2,"x"); 39 insert(y,2,"y"); 40 insert(z,2,"z"); 41 while (!q.empty()) 42 { 43 const qnode now=q.top(); q.pop(); 44 if (now.p==2) 45 { 46 insert(now.id^(n-1),2,"!"+dis[now.id][now.p]); 47 insert(now.id,1,dis[now.id][now.p]); 48 } 49 else if (now.p==1) 50 { 51 for (int i=0;i<n;i++) if (i!=now.id) 52 for (int j=1;j<=2;j++) 53 if (!dis[i][j].empty()) 54 { 55 insert(now.id&i,1,dis[now.id][1]+"&"+dis[i][j]); 56 insert(now.id&i,1,dis[i][j]+"&"+dis[now.id][1]); 57 } 58 insert(now.id,0,dis[now.id][now.p]); 59 insert(now.id,2,"("+dis[now.id][now.p]+")"); 60 } 61 else 62 { 63 for (int i=0;i<n;i++) if (i!=now.id) 64 for (int j=0;j<3;j++) 65 if (!dis[i][j].empty()) 66 { 67 insert(now.id|i,0,dis[now.id][0]+"|"+dis[i][j]); 68 insert(now.id|i,0,dis[i][j]+"|"+dis[now.id][0]); 69 } 70 insert(now.id,2,"("+dis[now.id][now.p]+")"); 71 } 72 } 73 } 74 75 int T; 76 int main() 77 { 78 dijkstra(); 79 scanf("%d",&T); 80 while (T--) 81 { 82 int now=0; 83 for (int j=0,x;j<8;j++) scanf("%1d",&x),(x && (now+=(1<<j))); 84 cout<<dis[now][0]<<endl; 85 } 86 return 0; 87 }
然而由于最长串是非常短的，所以也可以n^2*最长串*字符串比较，即更新到没有状态被更新时退出最短路。