请大家帮忙看一下一道ACM题。。。。。。
原题:http://acm.pku.edu.cn/JudgeOnline/problem?id=1063
不知道是我的算法错了,还是代码有问题,请各位高手指点一下:
算法:
我想大致可以分为两类:第一类是可以通过转换自动把他们分开,由于本题的特点FLIT一组数,在串中在奇数位的使用在奇数位,偶数为的始终的偶数位,如: 101001,有2个奇数,和一个偶数,所以可以转换成111000,同样多的奇偶数目,所以第一类为(这里把奇数用odd代替,偶数用even)odd -1==even或者odd==even。
而第二类则是把串可以转换到1110100或110100,的时候,即0为奇数个的条件下(这个很重要)有odd-2=even或odd=even-1,这样我们可以通过把最后的那个1向右移,直到移到左边(这是个循环)再用FLIT就能得到分开的1和0了。
不知道这个想法错了么。。。。
以下是代码:
#include <iostream>
using namespace std;
int main()
{
int n,i,count;
int odd,even;
int NUM,Temp;
cin> > n;
while(n)
{
cin> > NUM;
odd=0,even=0,count=0;
i=NUM;
if(NUM==2){cin> > Temp;cin> > Temp;cout < < "YES " < <endl;continue;}
while(i)
{
cin> > Temp;
if(Temp==1){
if(i%2)odd++;
else even++;
}
else count++;
i--;
}
if(odd==(even+2)||(odd+1)==even){
if(count%2!=0)cout < < "YES " < <endl;
else cout < < "NO " < <endl;
}
else
{
if((odd==even)||((odd-1)==even))cout < < "YES " < <endl;
else cout < < "NO " < <endl;
}
n--;
}
return 0;
}
[解决办法]
#include <iostream>
using namespace std;
int main()
{
int n,i;
int odd,even;
int NUM,Temp;
cin> > n;
while(n--)
{
cin> > NUM;
odd=0,even=0;
i=NUM;
while(i)
{
cin> > Temp;
if(Temp==1){
if(i%2)odd++;
else even++;
}
i--;
}
if(NUM%2){cout < < "YES " < <endl;continue;}
if(odd-even> 1 || even-odd> 1)
cout < < "NO " < <endl;
else
cout < < "YES " < <endl;
}
return 0;
}