coderforces Gym 100803A/Aizu 1345/CSU 1536/UVALive 6832 Bit String Reordering（贪心证明缺）

Portal: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1345

　　　 http://codeforces.com/gym/100803/attachments A题

好题！

坑不多，切入比较难

一开始的想法是暴力，由于求得是最小解且此图太大无边界，所以不能DFS，首先想到BFS

解法1 BFS+STL queue

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 #include<cstdio>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<queue>
 8 using namespace std;
 9 #define FOR(i,j,k) for(int i=j;i<=k;i++)
10 #define FORD(i,j,k) for(int i=j;i>=k;i--)
11 #define LL long long
12 #define SZ(x) x.size()
13 int vis[40000];
14 int x,k,n,m,s,ans,start,end1,end2,dight;
15 int bfs()
16 {
17     queue<int> q1,q2;
18     q1.push(start);
19     q2.push(1);
20     vis[start]=1;
21     while(q1.front()!=end1&&q1.front()!=end2)
22     {
23         int fr=q1.front();
24         int fv=q2.front();
25         FOR(i,0,n-2)
26         {
27             if((fr&(1<<i))&&!(fr&(1<<(i+1))))
28             {
29                 ans=fr+(1<<i);
30                 if(!vis[ans]) {vis[ans]=1;q1.push(ans);q2.push(fv+1);}
31             }
32             else if(!(fr&(1<<i))&&(fr&(1<<(i+1))))
33             {
34                 ans=fr-(1<<i);
35                 if(!vis[ans]) {vis[ans]=1;q1.push(ans);q2.push(fv+1);}
36             }
37         }
38         q1.pop();
39         q2.pop();
40     }
41     return q2.front()-1;
42 }
43 int main()
44 {
45 cin>>n>>m;
46 dight=1;
47 FORD(i,n-1,0)
48 {
49     cin>>x;
50     start+=x<<i;
51 }
52 int c=n;
53 FOR(i,1,m)
54 {
55     cin>>x;
56     FOR(j,1,x)
57     {
58         c--;
59         end1+=dight<<c;
60         end2+=(1-dight)<<c;
61     }
62     dight^=1;
63 }
64 cout<<bfs()<<endl;
65 return 0;
66 }

蛋疼的代码

解法2 BFS+手写queue

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 #include<cstdio>
 5 #include<cstdlib>
 6 #include<cmath>
 7 //#include<queue>
 8 using namespace std;
 9 #define FOR(i,j,k) for(int i=j;i<=k;i++)
10 #define FORD(i,j,k) for(int i=j;i>=k;i--)
11 #define LL long long
12 #define SZ(x) x.size()
13 int vis[40000];
14 int x,k,n,m,s,ans,start,end1,end2,dight;
15 
16 int bfs()
17 {
18     int q1[40000];int L1=1;int R1=0;    
19     int q2[40000];int L2=1;int R2=0;
20     q1[++R1]=start;
21     q2[++R2]=1;
22     vis[start]=1;
23     while(q1[L1]!=end1&&q1[L1]!=end2)
24     {
25         int fr=q1[L1];
26         int fv=q2[L2];
27         FOR(i,0,n-2)
28         {
29             if((fr&(1<<i))&&!(fr&(1<<(i+1))))
30             {
31                 ans=fr+(1<<i);
32                 if(!vis[ans]) {vis[ans]=1;q1[++R1]=ans;q2[++R2]=fv+1;}
33             }
34             else if(!(fr&(1<<i))&&(fr&(1<<(i+1))))
35             {
36                 ans=fr-(1<<i);
37                 if(!vis[ans]) {vis[ans]=1;q1[++R1]=ans;q2[++R2]=fv+1;}
38             }
39         }
40         L1++;
41         L2++;
42     }
43     return q2[L2]-1;
44 }
45 int main()
46 {
47 cin>>n>>m;
48 dight=1;
49 FORD(i,n-1,0)
50 {
51     cin>>x;
52     start+=x<<i;
53 }
54 int c=n;
55 FOR(i,1,m)
56 {
57     cin>>x;
58     FOR(j,1,x)
59     {
60         c--;
61         end1+=dight<<c;
62         end2+=(1-dight)<<c;
63     }
64     dight^=1;
65 }
66 cout<<bfs()<<endl;
67 return 0;
68 }

同样的代码

比较同样情况下STL的queue和手写的queue，我发现STL的queue内存比手写的多了4KB

这是个严重的问题，因为STL经常pop元素，是动态的，它的内存一定较小，但即便在手写的queue固定大小为8e5个int的情况下，仍然多4KB，即1e3个int

STL的queue在此题理论上能够最多有16384个元素，所以事实上同等长度的queue所用内存相当于3到4倍同等int

所以，我们应该谨慎使用STL，为保险起见，用queue时数据输入的极限容量不得多于1e7，即1/10int在32768KB下容量左右

在解法1/2的代码中使用了位运算的黑科技

FORD(i,n-1,0)
{
    cin>>x;
    start+=x<<i;
}
int c=n;
FOR(i,1,m)
{
    cin>>x;
    FOR(j,1,x)
    {
        c--;
        end1+=dight<<c;
        end2+=(1-dight)<<c;
    }
    dight^=1;
}


///


    if((fr&(1<<i))&&!(fr&(1<<(i+1))))
            {
                ans=fr+(1<<i);
                if(!vis[ans]) {vis[ans]=1;q1[++R1]=ans;q2[++R2]=fv+1;}
            }
            else if(!(fr&(1<<i))&&(fr&(1<<(i+1))))
            {
                ans=fr-(1<<i);
                if(!vis[ans]) {vis[ans]=1;q1[++R1]=ans;q2[++R2]=fv+1;}
            }

神奇的做法

其中(fr&(1<<i))&&!(fr&(1<<(i+1)))最妙

fr&(1<<i)表示判断fr的二进制表示中第i位是否为1（黑科技中利用了c++非0为真的机制）

这样使用黑科技的原因是这题中交换相同的二进制位是没有意义

所以仅仅交换01和10来产生当前数字的邻居

解法3 贪心

思路先处理出start[]和两个可能的终点end1[] end2[]

再判断start到end的变换是否可行（检查01数量）

若可行，用K从1到n（maxlength）迭代

则对于 start[K]与endx[K]

若start[K]与endx[K]相同不做任何操作

若start[K]与endx[K]不相同则找到离K最近的J（J<K）使得 start[J]!=start[K] 使start[J]与start[--J]不停交换使得J最终等于K以完成start[K]与endx[K]相同的任务

此时操作增加了J-K次

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 #include<cstdio>
 5 #include<cstdlib>
 6 #include<cmath>
 7 //#include<queue>
 8 using namespace std;
 9 #define FOR(i,j,k) for(int i=j;i<=k;i++)
10 #define FORD(i,j,k) for(int i=j;i>=k;i--)
11 #define LL long long
12 #define SZ(x) x.size()
13 int start[20],end1[20],end2[20];
14 int x,c,k,n,m,s,ans,ans1,ans2,dight;
15 bool check1()
16 {
17     int s[]={0,0};
18     FOR(i,1,n)
19     s[start[i]]++;
20     FOR(i,1,n)
21     s[end1[i]]--;
22     if(s[0]==0&&s[1]==0) return true; else return false;    
23 }
24 bool check2()
25 {
26     int s[]={0,0};
27     FOR(i,1,n)
28     s[start[i]]++;
29     FOR(i,1,n)
30     s[end2[i]]--;
31     if(s[0]==0&&s[1]==0) return true; else return false;    
32 }
33 int find1(int xx,int x)
34 {
35     int ss=x;
36     while(ss<=n&&end1[ss]!=xx)
37     ss++;
38     if(ss==n+1) return 0; else return ss; 
39 }
40 int find2(int xx,int x)
41 {
42     int ss=x;
43     while(ss<=n&&end2[ss]!=xx)
44     ss++;
45     if(ss==n+1) return 0; else return ss; 
46 }
47 int main()
48 {
49 cin>>n>>m;
50 dight=1;
51 FOR(i,1,n)
52 cin>>start[i];
53 FOR(i,1,m)
54 {
55     cin>>k;
56     FOR(j,1,k)
57     {
58         c++;
59         end1[c]=dight;
60         end2[c]=1-dight;
61     }
62     dight^=1;
63 }
64 bool flag1=check1();
65 bool flag2=check2();
66 int zz=0;
67 if(flag1)
68 while(zz!=n)
69 {
70     zz++;
71     if(end1[zz]!=start[zz])
72     {
73         int findd=find1(start[zz],zz);
74         end1[findd]^=1;
75         end1[zz]^=1;
76         ans1+=findd-zz;
77     }
78 }
79 zz=0;
80 if (flag2)
81 while(zz!=n)
82 {
83     zz++;
84     if(end2[zz]!=start[zz])
85     {
86         int findd=find2(start[zz],zz);
87         end2[findd]^=1;
88         end2[zz]^=1;
89         ans2+=findd-zz;
90     }
91 }
92 if(flag1&&flag2) cout<<min(ans1,ans2)<<endl;
93 else if(flag1) cout<<ans1<<endl;
94 else cout<<ans2<<endl;
95 return 0;
96 }

烂代码