Parity Game
Time Limit:1000MS
Memory Limit:65536K
Description
Now and then you play the following game with your friend. Your friend writes down a sequence consisting of zeroes and ones. You choose a continuous subsequence (for example the subsequence from the third to the fifth digit inclusively) and ask him, whether this subsequence contains even or odd number of ones. Your friend answers your question and you can ask him about another subsequence and so on. Your task is to guess the entire sequence of numbers.
You suspect some of your friend’s answers may not be correct and you want to convict him of falsehood. Thus you have decided to write a program to help you in this matter. The program will receive a series of your questions together with the answers you have received from your friend. The aim of this program is to find the first answer which is provably wrong, i.e. that there exists a sequence satisfying answers to all the previous questions, but no such sequence satisfies this answer.
Input
The first line of input contains one number, which is the length of the sequence of zeroes and ones. This length is less or equal to 1000000000. In the second line, there is one positive integer which is the number of questions asked and answers to them. The number of questions and answers is less or equal to 5000. The remaining lines specify questions and answers. Each line contains one question and the answer to this question: two integers (the position of the first and last digit in the chosen subsequence) and one word which is either ‘even’ or ‘odd’ (the answer, i.e. the parity of the number of ones in the chosen subsequence, where ‘even’ means an even number of ones and ‘odd’ means an odd number).
Output
There is only one line in output containing one integer X. Number X says that there exists a sequence of zeroes and ones satisfying first X parity conditions, but there exists none satisfying X+1 conditions. If there exists a sequence of zeroes and ones satisfying all the given conditions, then number X should be the number of all the questions asked.
Example
Example 1:
PARITY.IN
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
PARITY.OUT
3
Example 2:
PARITY.IN
10
5
1 2 even
1 4 even
2 4 odd
1 10 even
3 10 even
PARITY.OUT
5
Solution
挖个坑先……要是比赛中的话我怎么可能想到这题是并查集呢！
终于搞定。
首先有一步关键转化要做。我们同时处理一个范围内数字1的个数的奇偶比较麻烦。如果a到b之间有n个1，那么可以看成0到b之间1的个数减去0到a-1之间1的个数为n。我们假想知道了所有1的位置，那么0到任意i之间1的个数就是确定的。也就是说，通过这种转化，数据范围内每个数都对应了一个确定的数，它表示0到此数之间数字1的个数。
而我们事实上并不知道这些数确切是什么。我们知道的是一些数对之间奇偶性的关系。而这种关系是可以传递转移的。我们需要判断在给出关系的过程中是否出现矛盾。
于是就可以用并查集来解决这个问题了。它与我前面做过的食物链相比，本质上是一样的，但是处理起来还简单。你可以参照那个题的题解来理解这个题。
除了这步转化以外，对我而言处理起来比较麻烦的就是离散化了。这题串最大长度为10亿，而仅仅给出最多5千条询问，明显不离散化是不行了。我用的Hash。Hash和并查集的联合我从前是没搞过的。
P.S.这题其实是个骗分的好题（ACMer们别打我。。。）。不离散化最少70分。如果内存放宽一点就有80分。即使奇偶搞反了都有50分……总之怎么着都能得分的。CEOI的标程好像不是用并查集做的，但是要慢一些。就不管它了。
时空开销：
URAL的数据ms有问题，就再不管了。
源码：
#include <fstream>
#include <string>
using namespace std;
const long P=29989;
const string odd="odd";
long N,K;
struct elem{
long key,rank;
bool p_r;//false means same
elem *next,*p;
elem(long _key){key=_key,rank=0,p=this,p_r=false,next=NULL;}
}*set[P];
elem* Hash_Search(long key){
elem* p=set[key%P];
while(p&&p->key!=key) p=p->next;
return p;
}
void Hash_Insert(elem* toAdd){
long h = toAdd->key%P;
toAdd->next=set[h];
set[h]=toAdd;
}
elem *Set_Find(elem* A, bool &ch_r){
if(A->p!=A){
A->p=Set_Find(A->p,A->p_r);
ch_r=(ch_r!=A->p_r);
}
return A->p;
}
bool istrue(long a,long b, bool flag){
bool tmp=0;
elem *A=Hash_Search(a),*B=Hash_Search(b);
if(!A) A = new elem(a),Hash_Insert(A);
if(!B) B = new elem(b),Hash_Insert(B);
if(Set_Find(A,tmp)!=Set_Find(B,tmp)) return true;
if(!flag) return A->p_r==B->p_r;
else return A->p_r!=B->p_r;
}
void Set_Union(long a,long b, bool flag){
elem *A=Hash_Search(a),*B=Hash_Search(b);
if(!A) A = new elem(a),Hash_Insert(A);
else A=Set_Find(A,flag);
if(!B) B = new elem(b),Hash_Insert(B);
else B=Set_Find(B,flag);
if(A==B) return;
if(A->rank<B->rank) A->p=B,A->p_r=flag;
else{
B->p=A,B->p_r=flag;
if(A->rank==B->rank) A->rank++;
}
}
int main(){
ifstream fin("PARITY.IN");
ofstream fout("PARITY.OUT");
fin >> N >> K;
unsigned long a,b,ans=0;
string parity;
for(ans=1;ans<=K;ans++){
fin >> a >> b >> parity;
bool flag = parity==odd;//false means same
if(istrue(a-1,b,flag)) Set_Union(a-1,b,flag);
else break;
}
fout << --ans << endl;
fin.close(),fout.close();
return 0;
}
最近评论