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

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<queue>

 using namespace std;

 #define FOR(i,j,k) for(int i=j;i<=k;i++)

 #define FORD(i,j,k) for(int i=j;i>=k;i--)

 #define LL long long

 #define SZ(x) x.size()

 int vis[];

 int x,k,n,m,s,ans,start,end1,end2,dight;

 int bfs()

 {

     queue<int> q1,q2;

     q1.push(start);

     q2.push();

     vis[start]=;

     while(q1.front()!=end1&&q1.front()!=end2)

     {

         int fr=q1.front();

         int fv=q2.front();

         FOR(i,,n-)

         {

             if((fr&(<<i))&&!(fr&(<<(i+))))

             {

                 ans=fr+(<<i);

                 if(!vis[ans]) {vis[ans]=;q1.push(ans);q2.push(fv+);}

             }

             else if(!(fr&(<<i))&&(fr&(<<(i+))))

             {

                 ans=fr-(<<i);

                 if(!vis[ans]) {vis[ans]=;q1.push(ans);q2.push(fv+);}

             }

         }

         q1.pop();

         q2.pop();

     }

     return q2.front()-;

 }

 int main()

 {

 cin>>n>>m;

 dight=;

 FORD(i,n-,)

 {

     cin>>x;

     start+=x<<i;

 }

 int c=n;

 FOR(i,,m)

 {

     cin>>x;

     FOR(j,,x)

     {

         c--;

         end1+=dight<<c;

         end2+=(-dight)<<c;

     }

     dight^=;

 }

 cout<<bfs()<<endl;

 return ;

 }

蛋疼的代码

解法2 BFS+手写queue

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 //#include<queue>

 using namespace std;

 #define FOR(i,j,k) for(int i=j;i<=k;i++)

 #define FORD(i,j,k) for(int i=j;i>=k;i--)

 #define LL long long

 #define SZ(x) x.size()

 int vis[];

 int x,k,n,m,s,ans,start,end1,end2,dight;

 int bfs()

 {

     int q1[];int L1=;int R1=;

     int q2[];int L2=;int R2=;

     q1[++R1]=start;

     q2[++R2]=;

     vis[start]=;

     while(q1[L1]!=end1&&q1[L1]!=end2)

     {

         int fr=q1[L1];

         int fv=q2[L2];

         FOR(i,,n-)

         {

             if((fr&(<<i))&&!(fr&(<<(i+))))

             {

                 ans=fr+(<<i);

                 if(!vis[ans]) {vis[ans]=;q1[++R1]=ans;q2[++R2]=fv+;}

             }

             else if(!(fr&(<<i))&&(fr&(<<(i+))))

             {

                 ans=fr-(<<i);

                 if(!vis[ans]) {vis[ans]=;q1[++R1]=ans;q2[++R2]=fv+;}

             }

         }

         L1++;

         L2++;

     }

     return q2[L2]-;

 }

 int main()

 {

 cin>>n>>m;

 dight=;

 FORD(i,n-,)

 {

     cin>>x;

     start+=x<<i;

 }

 int c=n;

 FOR(i,,m)

 {

     cin>>x;

     FOR(j,,x)

     {

         c--;

         end1+=dight<<c;

         end2+=(-dight)<<c;

     }

     dight^=;

 }

 cout<<bfs()<<endl;

 return ;

 }

同样的代码

比较同样情况下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-,)

{

    cin>>x;

    start+=x<<i;

}

int c=n;

FOR(i,,m)

{

    cin>>x;

    FOR(j,,x)

    {

        c--;

        end1+=dight<<c;

        end2+=(-dight)<<c;

    }

    dight^=;

}

///

    if((fr&(<<i))&&!(fr&(<<(i+))))

            {

                ans=fr+(<<i);

                if(!vis[ans]) {vis[ans]=;q1[++R1]=ans;q2[++R2]=fv+;}

            }

            else if(!(fr&(<<i))&&(fr&(<<(i+))))

            {

                ans=fr-(<<i);

                if(!vis[ans]) {vis[ans]=;q1[++R1]=ans;q2[++R2]=fv+;}

            }

神奇的做法

其中(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次

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 //#include<queue>

 using namespace std;

 #define FOR(i,j,k) for(int i=j;i<=k;i++)

 #define FORD(i,j,k) for(int i=j;i>=k;i--)

 #define LL long long

 #define SZ(x) x.size()

 int start[],end1[],end2[];

 int x,c,k,n,m,s,ans,ans1,ans2,dight;

 bool check1()

 {

     int s[]={,};

     FOR(i,,n)

     s[start[i]]++;

     FOR(i,,n)

     s[end1[i]]--;

     if(s[]==&&s[]==) return true; else return false;

 }

 bool check2()

 {

     int s[]={,};

     FOR(i,,n)

     s[start[i]]++;

     FOR(i,,n)

     s[end2[i]]--;

     if(s[]==&&s[]==) return true; else return false;

 }

 int find1(int xx,int x)

 {

     int ss=x;

     while(ss<=n&&end1[ss]!=xx)

     ss++;

     if(ss==n+) return ; else return ss;

 }

 int find2(int xx,int x)

 {

     int ss=x;

     while(ss<=n&&end2[ss]!=xx)

     ss++;

     if(ss==n+) return ; else return ss;

 }

 int main()

 {

 cin>>n>>m;

 dight=;

 FOR(i,,n)

 cin>>start[i];

 FOR(i,,m)

 {

     cin>>k;

     FOR(j,,k)

     {

         c++;

         end1[c]=dight;

         end2[c]=-dight;

     }

     dight^=;

 }

 bool flag1=check1();

 bool flag2=check2();

 int zz=;

 if(flag1)

 while(zz!=n)

 {

     zz++;

     if(end1[zz]!=start[zz])

     {

         int findd=find1(start[zz],zz);

         end1[findd]^=;

         end1[zz]^=;

         ans1+=findd-zz;

     }

 }

 zz=;

 if (flag2)

 while(zz!=n)

 {

     zz++;

     if(end2[zz]!=start[zz])

     {

         int findd=find2(start[zz],zz);

         end2[findd]^=;

         end2[zz]^=;

         ans2+=findd-zz;

     }

 }

 if(flag1&&flag2) cout<<min(ans1,ans2)<<endl;

 else if(flag1) cout<<ans1<<endl;

 else cout<<ans2<<endl;

 return ;

 }

烂代码

巴特西

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

最新文章

热门文章