题目链接：

Bits Equalizer

Time Limit: 1000ms

Memory Limit: 131072KB

 

This problem will be judged on UVA. Original ID: 

64-bit integer IO format: 

%lld      Java class name: 

Main

         

Font Size: 

+ 

-

Type:   None   Graph Theory       2-SAT       Articulation/Bridge/Biconnected Component       Cycles/Topological Sorting/Strongly Connected Component       Shortest Path           Bellman Ford           Dijkstra/Floyd Warshall       Euler Trail/Circuit       Heavy-Light Decomposition       Minimum Spanning Tree       Stable Marriage Problem       Trees       Directed Minimum Spanning Tree       Flow/Matching           Graph Matching               Bipartite Matching               Hopcroft–Karp Bipartite Matching               Weighted Bipartite Matching/Hungarian Algorithm           Flow               Max Flow/Min Cut               Min Cost Max Flow   DFS-like       Backtracking with Pruning/Branch and Bound       Basic Recursion       IDA* Search       Parsing/Grammar       Breadth First Search/Depth First Search       Advanced Search Techniques           Binary Search/Bisection           Ternary Search   Geometry       Basic Geometry       Computational Geometry       Convex Hull       Pick's Theorem   Game Theory       Green Hackenbush/Colon Principle/Fusion Principle       Nim       Sprague-Grundy Number   Matrix       Gaussian Elimination       Matrix Exponentiation   Data Structures       Basic Data Structures       Binary Indexed Tree       Binary Search Tree       Hashing       Orthogonal Range Search       Range Minimum Query/Lowest Common Ancestor       Segment Tree/Interval Tree       Trie Tree       Sorting       Disjoint Set   String       Aho Corasick       Knuth-Morris-Pratt       Suffix Array/Suffix Tree   Math       Basic Math       Big Integer Arithmetic       Number Theory           Chinese Remainder Theorem           Extended Euclid           Inclusion/Exclusion           Modular Arithmetic       Combinatorics           Group Theory/Burnside's lemma           Counting       Probability/Expected Value   Others       Tricky       Hardest       Unusual       Brute Force       Implementation       Constructive Algorithms       Two Pointer       Bitmask       Beginner       Discrete Logarithm/Shank's Baby-step Giant-step Algorithm       Greedy       Divide and Conquer   Dynamic Programming                  

  

Tag it!

You are given two non-empty strings S and T of equal lengths. S contains the characters `0', `1' and `?', whereas T contains `0' and `1' only. Your task is to convertS into T in minimum number of moves. In each move, you can

 

1. change a `0' in S to `1'
2. change a `?' in S to `0' or `1'
3. swap any two characters in S

As an example, suppose S = "01??00" and T = "001010". We can transform S into T in 3 moves:

 

• Initially S = "01??00"
• - Move 1: change S[2] to `1'. S becomes "011?00"
• - Move 2: change S[3] to `0'. S becomes "011000"
• - Move 3: swap S[1] with S[4]. S becomes "001010"
• S is now equal to T

 

Input 

The first line of input is an integer C (C200) that indicates the number of test cases. Each case consists of two lines. The first line is the string S consisting of `0', `1' and `?'. The second line is the string T consisting of `0' and `1'. The lengths of the strings won't be larger than 100.

 

Output 

For each case, output the case number first followed by the minimum number of moves required to convert S into T. If the transition is impossible,output `-1' instead.

 

Sample Input 

 

301??000010100110110001000000

 

Sample Output 

 

Case 1: 3Case 2: 1Case 3: -1

 

Source

 

题目大意：将第一个字符与第二个字符每一个位置都相对应，至少需要移动的次数为多少。有以下的规则：1、0可以变成1；2、？可以变成0 or 1；3、任意0与1的位置可以互换

 

解题思路：统一0和1以及？的个数，因为？一定要变换，所以最少移动次数也得有？个数次，所以在其基础上加就可以了。

分两种情况考虑：（交换、变换）

优先变换情况：

1、存在1/0，并且后面可以找到0/1，那么交换。

2、存在1/0，但是找不到与其对应的0/1可以交换，那么就只能选择？/1,那么交换。

变换情况：

1、存在0/1，这种情况的话就直接把0变换成1即可。

 

综上，只要把所有情况考虑到，AC就不再是梦想啦，哇哈哈~~

 

详见代码。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 using namespace std; 6  7 int main () 8 { 9     int n,len1,flag=1;10     char s[110],t[110];11     scanf("%d",&n);12     while (n--)13     {14         scanf("%s%s",s,t);15         len1=strlen(s);16         //len2=strlen(t);17         int a,b,c,aa,bb;18         a=b=c=aa=bb=0;19         for (int i=0; i
         
          bb)36         {37             printf ("Case %d: -1\n",flag++);38             continue;39         }40         int sum=0;41         int j;42         if (s[i]=='1'&&t[i]=='0')43         {44             for (j=0; j
          
           =len1)55                 break;56 57         }58     }59     for (int i=0; i
           
            =len1)75 break;76 }77 }78 for (int i=0; i