hdu 4272 LianLianKan

  1. 云栖社区>
  2. 博客>
  3. 正文

hdu 4272 LianLianKan

陈国林 2012-09-09 09:16:41 浏览392
展开阅读全文

点击打开链接4272


题目意思:就是和平时玩的连连看类似,只是这里只能找距离小于6的。


解题思路

1 map版 , 判断当前的水果的个数是否全为偶数

2vector版,直接模拟整个过程即可


3代码:

vector版:

/*
用vector模拟:只要模拟整个删除的过程即可,中间注意vector迭代器的使用,如果v.erase(it),那么它将返回下一个迭代器这里注意。
*/
#include <algorithm>  
#include <iostream> 
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
#define MAXN 1010   
#define INF 0xFFFFFFF

int n;
vector<int>v;

void solve() {
    int flag, i;
    vector<int>::iterator it1, it2;
    while (1) {
        flag = 0;
        if (v.size() <= 1) break;/*只有一个元素的肯定不行*/
        it1 = v.begin();
        for (; it1 != v.end(); it1++) {
            for (it2 = it1 + 1, i = 1; i < 6 && it2 != v.end(); i++ , it2++) {
                if (*it1 == *it2) {
                    v.erase(it1);/*这里删除了it1后it2会往回移动一个*/
                    v.erase(it2-1);/*所以由上面的可知这里删除it2-1位置*/
                    flag = 1 ; break;
                }
            }
            if (flag) break;
        }
        if (!flag || !v.size()) break;/*如果flag为0或v为空退出*/
    }
    if (v.size()) printf("0\n");
    else printf("1\n");
}

int main() {
    //freopen("input.txt", "r", stdin);
    int tmp;
    while (scanf("%d", &n) != EOF) {
        v.clear();
        for (int i = 0; i < n; i++) {
            scanf("%d", &tmp);
            v.push_back(tmp);/*全部插入vector*/
        }
        solve();
    }
    return 0;
}

map版

/*
map版:
因为只要是能够消除的都可以选择,那么看下面这个例子
12
1 2 2 1 3 1 1 1 1 1 1 3
第一步消去 1 1得  2 2 3 1 1 1 1 1 1 3
第二步消去 2 2得  3 1 1 1 1 1 1 3
第三步由于两个3之间差距大于等于6,那么我们先消去1,得 3 1 1 1 1 3
第四步 消去3 3得 1 1 1 1 
......
那么从上面这个例子可以看出,并不是要求必须一个一个的消除过去,而是可以选择的。那么这样就可以知道只要相同的水果个数为偶数那么肯定是可以消去的,否则不行。
*/
 #include <algorithm>  
#include <iostream> 
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
#define MAXN 1010   
#define INF 0xFFFFFFF

int n , ans;
map<int , int>m;

void solve(){
    ans = 1;
    map<int , int>::iterator it;
    for(it = m.begin() ; it != m.end() ; it++){
        if((it->second)%2){/*判断it->second值是否全为偶数*/
           ans = 0 ; break;
        }   
    }
    printf("%d\n" , ans);
}

int main(){
    //freopen("input.txt", "r", stdin);
    int tmp;
    while(scanf("%d" , &n) != EOF){
        m.clear() ; map<int , int>::iterator it;
        for(int i = 0 ; i < n ; i++){
            scanf("%d" , &tmp);
            it = m.find(tmp);
            if(it != m.end()) m[tmp]++;/*找到则加1*/
            else m[tmp] = 1;/*没有找到则插入*/
        }
        solve();
    }
    return 0;
}



网友评论

登录后评论
0/500
评论
陈国林
+ 关注