这里再次强烈推荐USACO,因为他们每一题的题解现在有视频了!!
在这一题上花了一天时间,想到用recursion来解决问题,想到检测loop的方法,不过还是出了错误,loop解决方案参考了http://blog.csdn.net/thestoryofsnow/article/details/39821333
通过之后,看了USACO自己的题解,他们有更简洁和高效的解决方案,发现大家看问题的方式真的是不一样,这个人应该是那种大牛的赶脚,同时突然很庆幸自己在USACO上花时间,因为这一次比以往的任何一次学到的东西都多,包括对问题抽象化的方式也跟以前大不相同。
下面是我的代码,我比较喜欢用容器,因为不会越界,同时兼容大的数据。但是。。显然没有USACO题解给出的解决方案好:
/* ID: bbsunch2 PROG: wormhole LANG: C++ */ //#include "stdafx.h" #include <map> #include <vector> #include <iostream> #include <fstream> #include <algorithm> using namespace std; struct UNI_PAIR{ int x; int y; }; // given an enter index, find the corresponding out index int get_exit_index(int enterIndex, vector<UNI_PAIR> chosen_pairs){ for (int i = 0; i < chosen_pairs.size(); i++){ UNI_PAIR p = chosen_pairs[i]; if (enterIndex == p.x){ //cout << p.x << "&" << p.y << endl; return p.y; } if (enterIndex == p.y){ //cout << p.x << "&" << p.y << endl; return p.x; } } return -1; } // getting out of the exit index, find the next corresponding enter index int get_enter_index(int beforeIndex, vector<UNI_PAIR> points, map<int, vector<int> > coordinate_y__x){ UNI_PAIR beforePoint = points[beforeIndex]; int before_y = beforePoint.y; int before_x = beforePoint.x; UNI_PAIR enterPoint; enterPoint.y = before_y; vector<int> xVector = coordinate_y__x[before_y]; //bool found_enter = false; for (int i = 0; i < xVector.size(); i++){ if (before_x == xVector[i]){ if (i == xVector.size() - 1){ return -1; } else{ enterPoint.x = xVector[i + 1]; break; } } } for (int i = 0; i < points.size(); i++){ if (points[i].x == enterPoint.x && points[i].y == enterPoint.y){ return i; } } } int add_path(int point, vector<int> & path){ for (int i = 0; i < path.size(); i++){ if (point == path[i]){ path.push_back(point); return 0; } } path.push_back(point); return 1; } // for each combination and each entry, check if there is a loop exist bool check_loop(vector<UNI_PAIR > points, map<int, vector<int> > coordinate_y__x, vector<UNI_PAIR> chosen_pairs){ //for each entry, check if there is loop for (int i = 0; i < points.size(); i++){ //int entryIndex = i; int enterIndex = i; int exitIndex = get_exit_index(enterIndex, chosen_pairs); vector<int> path; path.push_back(enterIndex); //path.push_back(exitIndex); bool is_loop = false; while (get_enter_index(exitIndex, points, coordinate_y__x) >= 0){ enterIndex = get_enter_index(exitIndex, points, coordinate_y__x); exitIndex = get_exit_index(enterIndex, chosen_pairs); if (enterIndex == -1 || exitIndex == -1){ cout << "Error in check_loop" << endl; } if (! add_path(enterIndex, path) ){ //return true; is_loop = true; break; } //path.push_back(exitIndex); } /*for (int i = 0; i < path.size(); i++){ cout << path[i]; if (i != path.size() - 1){ cout << "->"; } } cout << endl;*/ if (is_loop) return true; } return false; } vector<vector<UNI_PAIR> > generate_combinations(const vector<int> point_indexs){ if (point_indexs.size() % 2 != 0){ cout << "Error in generate_combinations, odd num: " << point_indexs.size() << endl; } if (point_indexs.size() == 2){ UNI_PAIR singlePair; singlePair.x = point_indexs[0]; singlePair.y = point_indexs[1]; vector<UNI_PAIR> singleVector; singleVector.push_back(singlePair); vector<vector<UNI_PAIR> > singleCombination; singleCombination.push_back(singleVector); return singleCombination; } else{ vector<vector<UNI_PAIR> > combinations; for (int i = 1; i < point_indexs.size(); i++){ UNI_PAIR firstPair; vector<int> left_indexs; for (int j = 0; j < point_indexs.size(); j++){ left_indexs.push_back(point_indexs[j]); } firstPair.x = left_indexs[0]; firstPair.y = left_indexs[i]; left_indexs.erase(left_indexs.begin() + i); left_indexs.erase(left_indexs.begin()); vector<vector<UNI_PAIR> > left_combinations = generate_combinations(left_indexs); for (int k = 0; k < left_combinations.size(); k++){ combinations.push_back(left_combinations[k]); int lastIndex = combinations.size() - 1; combinations[lastIndex].push_back(firstPair); } } return combinations; } } // test function generate_combinations void output_combinations(vector<vector<UNI_PAIR> > combinations){ //vector<int> point_indexs; //point_indexs.push_back(0); //point_indexs.push_back(1); //point_indexs.push_back(2); //point_indexs.push_back(3); //vector<vector<UNI_PAIR> > combinations = generate_combinations(point_indexs); for (int i = 0; i < combinations.size(); i++){ cout << "combination " << i << ": "; for (int k = 0; k < combinations[i].size(); k++){ cout << combinations[i][k].x << "-" << combinations[i][k].y << " "; } cout << endl; } } // given coordinates, count the number of combinations that will cause loop int count_loops(vector<UNI_PAIR > points, map<int, vector<int> > coordinate_y__x){ //iterate all combinations int loopCount = 0; vector<int> point_indexs; for (int i = 0; i < points.size(); i++){ point_indexs.push_back(i); //cout << points[i].x << "-" << points[i].y << "\t"; } //cout << endl; vector<vector<UNI_PAIR> > combinations = generate_combinations(point_indexs); //store index in points //output_combinations(combinations); // foreach combination, check if there is loop; for (int i = 0; i < combinations.size(); i++){ vector<UNI_PAIR> chosen_pairs = combinations[i]; bool is_loop = check_loop(points, coordinate_y__x, chosen_pairs); if (is_loop){ loopCount ++; } /*cout << "combination " << i << ": "; for (int k = 0; k < combinations[i].size(); k++){ cout << combinations[i][k].x << "-" << combinations[i][k].y << " "; } cout << ": " << is_loop; cout << endl;*/ } return loopCount; } int main(int argc, char* argv[]) { ofstream fout("wormhole.out"); ifstream fin("wormhole.in"); int N = 0; fin >> N; map<int, vector<int> > coordinate_y__x; // key is y, value is all x coordinates using the same y vector<UNI_PAIR > points; map<int, int> testMap; for (int i = 0; i < N; i++){ int x, y; fin >> x >> y; UNI_PAIR singlePoint; singlePoint.x = x; singlePoint.y = y; points.push_back(singlePoint); if (coordinate_y__x.find(y) == coordinate_y__x.end()){ vector<int> tempVector; tempVector.push_back(x); coordinate_y__x.insert(pair<int, vector<int> >(y, tempVector)); } else{ coordinate_y__x[y].push_back(x); } } for (map<int, vector<int> >::iterator it = coordinate_y__x.begin(); it != coordinate_y__x.end(); it++){ int y = it->first; sort(coordinate_y__x[y].begin(), coordinate_y__x[y].end()); //for (int i = 0; i < coordinate_y__x[y].size(); i++){ // cout << y << coordinate_y__x[y][i] << endl; //} } int loopCount = count_loops(points, coordinate_y__x); //test_combinations(); cout << loopCount << endl; fout << loopCount << endl; //stay //int i; //cin >> i; return 0; }
相关推荐
USACO所有题目的题解 NOCOW整理版
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
USACO月赛题解1
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
丰富的USACO1.1--2.3.4的所有题解
非常详细的题解,个人觉得很好,帮助非常大。nocow关闭后不太好找资源了。
非常详细的题解,比较全的,个人觉得刷题者可以入手,帮助非常大。
非常详细的题解,比较全的,个人觉得刷题者可以入手,帮助非常大。
非常详细的题解,个人觉得比较全的,刷题者可以入手,帮助会非常大。
我的USACO题解和程序
USACO题解(NOCOW整理版).doc
usaco全部题解。 网址:blog.csdn.net/jiangshibiao
USACO题解及中文译题1.1.1-2.4.5 题目为TXT格式文档,代码为C++语言所编写
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
里面有usaco前几节的程序和代码,欢迎使用,希望对你有所帮主。
usaco的某道题的题解
USACO(即美国高中生的编程竞赛网站)中的 pprime 题的题解
数据结构机考所参考的USACO网站所有题目的解题思路,资源比较稀有!