首页 > 代码库 > UVa 12545 比特变换器

UVa 12545 比特变换器

 

https://vjudge.net/problem/UVA-12545

题意:输入两个等长的串S和T,其中S包含字符0,1,?,但T只包含0和1。

        用尽量少的步数把S变成T。每步有3种操作:

        ①把S中的0变成1;②把S中的“?”变成0或者1;交换S中任意两个字符。

思路:题目不是很难。首先考虑交换,然后再看有多少不同的,就需要再加上多少次。

 1 #include<string> 2 #include<iostream>   3 #include<algorithm> 4 using namespace std; 5  6 string s1, s2; 7 int cnt; 8  9 10 void solve()11 {12     int l = s1.size();13     cnt = 0;14     int num1 = 0, num2 = 0;15     for (int i = 0; i < l; i++)16     {17         if (s1[i] == 1)    num1++;18         if (s2[i] == 1)    num2++;19     }20     if (num1>num2)21     {22         cnt = -1;23         return;24     }25 26 27     for (int i = 0; i < l; i++)28     {29         if (s1[i] != s2[i] && s1[i] != ?)30         {31             for (int j = i + 1; j < l; j++)32             {33                 if (s1[j] == s2[i] && s2[j] == s1[i])34                 {35                     cnt++;36                     char temp;37                     temp = s1[i];38                     s1[i] = s1[j];39                     s1[j] = temp;40                     break;41                 }42             }43         }44     }45     for (int i = 0; i < l; i++)46     {47         if (s1[i] != s2[i])     cnt++;48     }49 50 }51 52 int main()53 {54     //freopen("D:\\txt.txt", "r", stdin);55     int t, kase = 0;56     cin >> t;57     while (t--)58     {59         cin >> s1 >> s2;60         solve();61         cout << "Case " << ++kase << ": " << cnt << endl;62     }63 64     return 0; 65 }

 

UVa 12545 比特变换器