首页 > ACM题库 > HDU-杭电 > hdu 3747 Download[解题报告]C++
2015
02-22

hdu 3747 Download[解题报告]C++

Download

问题描述 :

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~”.

Cyclic Nacklace

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

 

题目意思:  有一个人现在想要下载一些东西,现在呢给定一个字符串T表示所以东西的原始状态,1表示打勾,0表示空,现在给定一个字符串S是这个人所要下载的东西的情况,问我么这个最少需要点击几次,这里上面有三个地方第几需要计算 1 全选 2 反选  3 下载东西对应框

解题思路:      我们先来说明一下规律
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也帮想想, 有想法欢迎来邮件。谢谢