现在的位置: 首页 > 综合 > 正文

POJ1029

2018年01月20日 ⁄ 综合 ⁄ 共 1022字 ⁄ 字号 评论关闭

听说这题可以暴力破解掉。。。感觉略麻烦的样纸。。。

然后用标记的方法……

几个注意点:

          1、 出现的等号两边的绝壁的真的!

          2、如果一个钢镚,即出现在重的一边,又出现在轻的一边,那这货绝壁是真的!

        

然后开始做!

遇到等号,将他们全都标记称真的。

重的,标记重的,轻的,标记轻的。

如果最后某个硬币的轻的重的标记等于总的操作数,就重点怀疑~~~

如果就一根这样的,就是那货假的。

如果多个,那就无法判断。

AC Memory : 736 KB    Time : 110 ms

代码:

#include<iostream>
#include<cstring>
#include<fstream>
#include<algorithm>
#include<string>
#include<map>
using namespace std;

const int Max=1000+10,inf=10000000;

int w[Max],s[Max],label[Max];

int main()
{
    int n,k;
    int tot;
    while(cin>>n>>k)
    {
      tot=0;
      memset(label,0,sizeof(label));
      memset(w,0,sizeof(w));

      for(int i=0;i<k;i++)
      {
         int m;
         char c;
         cin>>m;

         for(int i=0;i<2*m;i++)
          cin>>s[i];

          cin>>c;

         if(c=='=')
         for(int i=0;i<2*m;i++)
           label[s[i]]=1;

         else if(c=='<')
         { tot++;

           for(int i=0;i<m;i++)
            if(label[s[i]]==0)
              w[s[i]]--;

           for(int i=m;i<2*m;i++)
             if(label[s[i]]==0)
              w[s[i]]++;
         }


         else if(c=='>')
         {
              tot++;

              for(int i=0;i<m;i++)
                if(label[s[i]]==0)
                    w[s[i]]++;

           for(int i=m;i<2*m;i++)
                if(label[s[i]]==0)
                    w[s[i]]--;
         }

      }
      int ans=0,found=0;

      for(int i=1;i<=n;i++)
        if(label[i]==0 && abs(w[i])==tot)
        {
            found++;
            ans=i;
        }

      if(found!=1)cout<<0<<endl;
      else cout<<ans<<endl;
   }
return 0;
}

抱歉!评论已关闭.