2015
02-22

Computer networks, the widespread sharing of information among groups of computers and their users, are a central part of the information age. In this age, every local personal computer(PC) can download applications and documents from the distance database, which makes it convenient to our entertainment by using the internet.

CC is a such fanatical lover of TV plays. Each TV play is consisted by a lot number of sections. When he open his download software and select one of his favourite TV plays, a “section selected window” jumped out. “Please mark the sections you want to download~”.

Each section has its CheckBox to be marked stands for choosing this section or not.
There are two special buttons as follow:
1, All-clicked: you can mark all of section with ‘√’ by click this button.
2, Inverse-clicked: you can change each section to its inverse state by click this button.

At first, the state of each section is in disorder, and there is no need to CC to download all of the sections in this TV play. When he are about to begin his crazy clicking, he come up with a good idea that finding the minimum times of click by programming. Now he tell you the information of the original download window, can you tell him how many click times at least to choose the sections he wants to download.

Input contains multiple test cases. Each test case contains three lines:
The first line contains only one number N (5 <= N <= 50) indicating the total number of sections.
The second line is a string S only consisted by ’0′ and ’1′, the ith charactor is stand for the ith section of TV play, ’1′ is stand for the ‘√’ state and ’0′ is not.
The third line is a string T, just like S, it shows the sections CC wants to download.
You can assume the length of S and T are equal to N.

Input contains multiple test cases. Each test case contains three lines:
The first line contains only one number N (5 <= N <= 50) indicating the total number of sections.
The second line is a string S only consisted by ’0′ and ’1′, the ith charactor is stand for the ith section of TV play, ’1′ is stand for the ‘√’ state and ’0′ is not.
The third line is a string T, just like S, it shows the sections CC wants to download.
You can assume the length of S and T are equal to N.

5
00010
10111
5
10101
01010

2
1

1： 全选大于等于两次都是和全选一次相同   2：反选一次状态相反，全选两次回到原来效果。（反选奇数次状态相反，反选偶数次不变）

1：不全选也不反选单个选  2：先全选再单个选  3：先反选在单个选    4先全选再反选再单个选  5 先反选再全选再单个选（其实这个是不用考虑的效果和直接全选一样），所以只要去一一求出取最小值即可

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;

int n , ans;
char T[55] , S[55];

void solve(){
ans = 999999999;
//1直接单个选
int num = 0;
for(int i = 0 ; i < n ; i++){
if(T[i] != S[i]) num++;
}
if(ans > num) ans = num;
//2全选+单个选
num = 1;
for(int i = 0 ; i < n ; i++){
if(S[i] == '0') num++;
}
if(ans > num) ans = num;
//3反选+单个选
num = 1;
for(int i = 0 ; i < n ; i++){
if(T[i] == '0') T[i] = '1';
else T[i] = '0';
}
for(int i = 0 ; i < n ; i++){
if(T[i] != S[i]) num++;
}
if(ans > num) ans = num;
//4先全选在反选
num = 2;
for(int i = 0 ; i < n ; i++) T[i] = '0';
for(int i = 0 ; i < n ; i++){
if(T[i] != S[i]) num++;
}
if(ans > num) ans = num;
printf("%d\n" , ans);
}

//主函数
int main(){
//freopen("input.txt" , "r" , stdin);
while(scanf("%d" , &n) != EOF){
getchar();//注意换行
gets(T) ; gets(S);
solve();
}
return 0;
}

1. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢