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

高消 47MS,给大家个模版

Posted by smile291779386 at 2014-08-24 15:39:32 on Problem 2965
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

int a[24][24],x[24];
int equ,var;//方程数和变元数
struct Locate
{
    int x,y;
}locate[24];

void Debug()
{
    for(int i=0; i<equ; i++)
    {
        for(int j=0; j<=var; j++)
            printf("%d ",a[i][j]);
        puts("");
    }
    puts("");
}

int gauss()
{
    int max_r,col=0;
    for(int i=0; i<equ&&col<var; i++,col++)
    {
        max_r=i;
        for(int j=i+1; j<equ; j++)
        {
            if(a[j][col]>a[max_r][col]) max_r=j;
        }
        if(max_r!=i)
        {
            for(int k=0; k<=var; k++)
            {
                swap(a[i][k],a[max_r][k]);
            }
        }
        if(a[i][col]==0)
        {
            i--;
            continue;
        }

        for(int j=i+1; j<equ; j++)
            if(i!=j&&a[j][col])
            {
                for(int k=col; k<=var; k++)
                    a[j][k]=a[i][k]^a[j][k];
            }
    }

    //Debug();

    int ans=0;
    for(int i=equ-1; i>=0; i--)
    {
        int temp=a[i][var];
        for(int j=i+1; j<var; j++)
        {
            temp-=a[i][j]*x[j];
        }
        x[i]=temp/a[i][i];
    }

    for(int i=0; i<var; i++)
    if(x[i]%2!=0)
    {
        locate[ans].x=i/4+1;
        locate[ans].y=i%4+1;
        ans++;
    }
    return ans;
}


void init()
{
    memset(a,0,sizeof(a));
    memset(x,0,sizeof(x));
    for(int i=0; i<4; i++)
        for(int j=0; j<4; j++)
        {
            for(int k=0; k<4; k++)
                a[i*4+j][k*4+j]=1;
            for(int k=0; k<4; k++)
                a[i*4+j][i*4+k]=1;
        }
    //Debug();
}
int main()
{
    equ=var=16;
    char s[20],t[5];
    memset(t,0,sizeof(t));
    memset(s,0,sizeof(s));
    while(scanf("%s",t)!=EOF)
    {
        strcpy(s,t);
        for(int i=0; i<3; i++)
        {
            scanf("%s",t);
            strcat(s,t);
        }
        init();
        for(int i=0; i<16; i++)
        {
            if(s[i]=='+') a[i][var]=1;
            else a[i][var]=0;
        }
        //Debug();
        int ans=gauss();
        printf("%d\n",ans);
        for(int i=0;i<ans;i++)
        {
            printf("%d %d\n",locate[i].x,locate[i].y);
        }
    }
    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