这里再次强烈推荐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题解】全集包含了各类不同的编程竞赛题目,旨在帮助参赛者提升算法思维和编程能力。本文主要解析其中三个题目:“Your Ride Is Here (ride)”,“Greedy Gift Givers (gift1)”,以及“Friday the Thirteenth...
本压缩包包含了USACO比赛的题解、源代码以及对应的中文翻译,对于想要参加或者正在准备USACO的同学们来说,无疑是一份宝贵的资源。 首先,让我们来详细了解USACO题解部分。USACO的比赛题目通常涉及各种算法,包括但...
"USACO题解(NOCOW整理版).pdf"可能是某个特定用户或团队整理的题解版本,可能包含了一些独特的解题方法或者技巧,或者是对原题解的补充和完善,使得学习者可以从不同的角度理解问题。 最后,"USACO全部测试数据.rar...
### USACO Chap3 题解概览 #### Agri-Net (agrinet) - **知识点**:本题是一道经典的最小生成树问题。最小生成树问题是指在一个连通带权图中找到一棵包含所有顶点的树,使得这棵树上的所有边的权重之和最小。 - *...
### USACO Chap4 题解概览 #### BeefMcNuggets(nuggets) **问题背景**:本节讨论了如何确定一系列特定数量的牛肉麦乐鸡块(nuggets)是否能够通过给定的基本包装组合而成。这是一个典型的背包问题,在实际问题中...
### USACO Chap1 题解概览 #### YourRideIsHere(ride) - **题目概述**:此题目属于“adhoc”类别,即它并不需要特别复杂的算法或高级技巧来解决,而是需要一些基本逻辑思维和细心观察。 - **解题策略**:题目给出...
通过学习这些USACO题解,你可以逐步提升自己的编程能力和算法理解,为参与更高难度的计算机竞赛或实际的软件开发打下坚实基础。记住,实践是检验理解的最好方式,不断动手编写和调试代码,才能真正掌握这些知识。
【USACO月赛题解1】中的知识点涵盖了多种算法和问题解决策略,适用于计算机科学,尤其是算法竞赛。以下是对各个题目及其所涉及算法的详细解释: 1. **Fiber Communications** - 这是一个并查集(Disjoint Set Union...
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
我的USACO题解和程序
USACO 题解 USACO 题解是美国计算机奥林匹克(USACO)竞赛的题解集合,本文档提供了多个题目的解释和解决方案,涵盖了 Greedy Algorithm、Hash 表、动态规划、搜索等多种算法和技术。 Chapter 1 Section 1.1 Your ...
1. 题解:这些题解详细解释了如何理解和解决USACO比赛中的各种问题。通常会涵盖问题分析、算法设计、代码实现和时间复杂度分析等方面,有助于读者理解解决问题的关键思路。 2. 程序:每道题目的解决方案通常会有一...
usaco全部题解。 网址:blog.csdn.net/jiangshibiao
这份压缩包包含了USACO训练教程的部分题解及中文译题,覆盖了从基础到进阶的多个章节,帮助学习者逐步提升编程和算法技能。 1. **基础篇(1.1.1)** - **数据结构基础**:在这一部分,通常会介绍数组、链表、栈和...
本压缩包“ACM----USACO Training(解题博客网)”提供了USACO Training的解题代码资源,这对于参赛者或者想要提升算法能力的学习者来说是一份宝贵的参考资料。通过研究这些代码,你可以了解到各种算法的实际应用和...
usaco的某道题的题解
USACO(United States of America Computing Olympiad,美国信息学奥林匹克竞赛)是一个面向中学生的计算机编程竞赛,题解整理版中涉及的几个题目,下面将一一介绍它们的解题思路和涉及的关键知识点。 首先,...