首页 > 代码库 > 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 比特变换器
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。