Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

那可以快速判断无解的情况吗?

Posted by yygy at 2014-07-04 09:48:24 on Problem 2965
In Reply To:高效解法,供路人借鉴~ Posted by:yingxiang720 at 2011-03-15 15:20:51
> /*
> 
> 参考高手的高效解法:
> *********************************
> 此上证其可以按以上步骤使数组中值都为‘-’
> ********************************
> 在上述证明中将所有的行和列的位置都加1后,在将其模2之前,对给定的数组状态,将所有的位置操作其所存的操作数个次数,举例,如果a[i][j]==n,则对(i,j)操作n次,当所有的操作完后,即全为‘-’的数组。
> 其实就是不模2的操作,作了许多的无用功。
> 以上的操作次序对结果无影响,如果存在一个最小的步骤,则此步骤一定在以上操作之中。(简单说下:因为以上操作已经包含了所有可改变欲改变位置的操作了)
> 而模2后的操作是去掉了所有无用功之后的操作,此操作同样包含最小步骤。
> 但模2后的操作去掉任何一个或几个步骤后,都不可能再得到全为‘-’的。(此同样可证明:因为操作次序无影响,先进行最小步骤,得到全为‘-’,如果还剩下m步,则在全为‘-’的数组状态下进行这m步操作后还得到一个全为
> ‘-’的数组状态,此只能是在同一个位置进行偶数次操作,与前文模2后矛盾,所以m=0),因此模2后的操作即为最小步骤的操作。
> */
> #include <iostream>
> using namespace std;
> 
> bool mark[4][4];
> char s[4][4];
> 
> int main()
> {
>     int i,j,k;
>     int ci[16],cj[16];
>     int nas = 0;
>     memset(mark,0,sizeof(mark));
> 	for(i = 0;i < 4;i++)
> 		cin >> s[i];
>     for(i = 0;i < 4;i++)
>         for(j = 0;j < 4;j++)
>         {
>             char c = s[i][j];
>             if(c == '+')
>             {
>                 mark[i][j] = !mark[i][j];
>                 for(k = 0;k < 4;k++)
>                 {
>                     mark[i][k] = !mark[i][k];
>                     mark[k][j] = !mark[k][j];
>                 }
>             }
> 
>         }
>     for(i = 0;i < 4;i++)
>         for(j = 0;j < 4;j++)
>             if(mark[i][j] == true)
>             {
>                 ci[nas] = i + 1;
>                 cj[nas] = j + 1;
>                 nas ++;
>             }
>     printf("%d\n",nas);
>     for(i = 0;i < nas;i++)
>     {
>         printf("%d %d\n",ci[i],cj[i]);
>     }
>     return 0;
> }
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator