Codeforces Round #207 (Div. 2)

A. Group of Students

链接：http://codeforces.com/contest/357/problem/A

描述：一共m(2<=m<=100)个人，c1，c2，c3....cm(0<=ci<=100)代表分数为1，2，3...m的人数。求一个分界分数点，使得该分界点左边所有人数和右边所有人数（右边包括分界点人数）都在x和y之内（包括x，y).(1<=x<=y<=10000).

思路：水题，直接模拟。

1 for white, 2 for red, 3 for blue）使得条件满足。
思路：一开始想多了，想用dfs染色。但是后来注意到一个条件非常重要“ Your agency cannot allow that to happen, so each dance has at most one dancer who has danced in some previous dance.”这样一来就变成一个大水题了。只要记录以前被染色过的点，以后遇到一个三人组里有一个被染色的，就随便给另外两个染色就可以了。要是三人都没有被染色，就可以随便给这仨货染色。看题要仔细，抓住一个信息就变成大水题了。代码有点逆天，还好一次过。
#include <cstdio>#include <iostream>#include <vector>#include <algorithm>#include <cstring>#include <set>using namespace std;set<int> s;typedef set<int>::iterator s_it;typedef vector<s_it>::iterator v_it;int a[300000+10];int main(){int n, m;while (scanf("%d %d", &n, &m) != EOF){s.clear();memset(a, 0, sizeof(a));for (int i = 1; i <= n; ++i)s.insert(i);int li, ri, xi;s_it it, beg, end;vector<s_it> t;v_it vit;while (m--){scanf("%d %d %d", &li, &ri, &xi);beg = s.lower_bound(li), end = s.upper_bound(ri);for (it = beg; it != end; ++it)if (*it != xi){a[*it] = xi;t.push_back(it);  //为了防止迭代器失效，先将需要删除的保存，后面一起删除}for (vit = t.begin(); vit != t.end(); ++vit)//将保存的点删除s.erase(*vit);t.clear();}for (int i = 1; i <= n; ++i)printf(i == n ? "%d\n" : "%d ", a[i]);}return 0;}


思路：