首页 > ACM题库 > HDU-杭电 > HDU 3927-Math Geek-随机算法-[解题报告]HOJ
2015
04-14

HDU 3927-Math Geek-随机算法-[解题报告]HOJ

Math Geek

问题描述 :

Sheldon’s board has been changed! Someone drew a N * N grid on his board. Although he has no idea who’s the bad guy, but as a math geek, he decide to play a game on it. He will fill in the grids with integer 1 to N*N. And the sum of each row, each column and each diagonal are distinct (2N+2 distinct integers in total).

输入:

The first line contains a single positive integer T( T <= 200 ), indicates the number of test cases.
For each test case: an integer N (3 <= N <= 200).

输出:

The first line contains a single positive integer T( T <= 200 ), indicates the number of test cases.
For each test case: an integer N (3 <= N <= 200).

样例输入:

2
3
4

样例输出:

Case #1:
7 5 2
1 4 8
3 6 9
Case #2:
2 8 15 1
5 12 10 16
6 9 4 14
3 7 11 13

Hint
Huge output. C/C++ user please use printf. Java user please use PrintWriter. Because of Special Judge, please use .print() method shown as below: PrintWriter out = new PrintWriter(System.out); out.print( "Case #" + caseT + ":\n" ); out.close(); // Important!!!

    题意:构造一个N*N的矩阵,使得每行之和、每列之和、两个对角线上数字之和都不同。

    解法:推出来的(http://w3.math.sinica.edu.tw/math_media/d164/16419.pdf)都不是好孩子,随机算法才是王道。在比赛的时候不可能有那么多时间推,也许也推不出来。随机算法方法:首先随便构造一个矩阵,可能有多行、多列或者对角线之和相同。然后每次随机选取矩阵中的两个数字,试着交换它们,如果交换后每行、每列、对角线的不同的和的数字增加,则保持交换,否则交换回来。重复这一过程直至所有数字之和都不同。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <memory.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>

#define ll long long

using namespace std;

const int N = 200;

int mtx[N][N], n;
int row[N], col[N], dia[2];
map<int, int> M;
int cunt;

void Change(int r1, int c1, int r2, int c2) {
    int d = mtx[r1][c1] - mtx[r2][c2];
    if (d == 0) return;
    
    int res = 0;
    if ((M[row[r1]]--) == 1) res--;
    if ((M[col[c1]]--) == 1) res--;
    if ((M[row[r2]]--) == 1) res--;
    if ((M[col[c2]]--) == 1) res--;
    if (r1 == c1 && (M[dia[0]]--) == 1) res--;
    if (r1 == n - c1 - 1 && (M[dia[1]]--) == 1) res--;
    if (r2 == c2 && (M[dia[0]]--) == 1) res--;
    if (r2 == n - c2 - 1 && (M[dia[1]]--) == 1) res--;
    
    swap(mtx[r1][c1], mtx[r2][c2]);
    row[r1] -= d; col[c1] -= d; row[r2] += d; col[c2] += d;
    if (r1 == c1) dia[0] -= d;
    if (r1 == n - c1 - 1) dia[1] -= d;
    if (r2 == c2) dia[0] += d;
    if (r2 == n - c2 - 1) dia[1] += d;

    if ((M[row[r1]]++) == 0) res++;
    if ((M[col[c1]]++) == 0) res++;
    if ((M[row[r2]]++) == 0) res++;
    if ((M[col[c2]]++) == 0) res++;
    if (r1 == c1 && (M[dia[0]]++) == 0) res++;
    if (r1 == n - c1 - 1 && (M[dia[1]]++) == 0) res++;
    if (r2 == c2 && (M[dia[0]]++) == 0) res++;
    if (r2 == n - c2 - 1 && (M[dia[1]]++) == 0) res++;

    if (res >= 0) {
        cunt += res;
        return;
    }
    
    M[row[r1]]--; M[col[c1]]--; M[row[r2]]--; M[col[c2]]--;
    if (r1 == c1) M[dia[0]]--;
    if (r1 == n - c1 - 1) M[dia[1]]--;
    if (r2 == c2) M[dia[0]]--;
    if (r2 == n - c2 - 1) M[dia[1]]--;
    
    swap(mtx[r1][c1], mtx[r2][c2]);
    row[r1] += d; col[c1] += d; row[r2] -= d; col[c2] -= d;
    if (r1 == c1) dia[0] += d;
    if (r1 == n - c1 - 1) dia[1] += d;
    if (r2 == c2) dia[0] -= d;
    if (r2 == n - c2 - 1) dia[1] -= d;

    M[row[r1]]++; M[col[c1]]++; M[row[r2]]++; M[col[c2]]++;
    if (r1 == c1)  M[dia[0]]++;
    if (r1 == n - c1 - 1) M[dia[1]]++;
    if (r2 == c2) M[dia[0]]++;
    if (r2 == n - c2 - 1) M[dia[1]]++;
}

int main() {
    int T, C, m, idx, s1, s2;
    int r1, c1, r2, c2;
    scanf("%d", &T);
    for (C = 1; C <= T; C++) {
        scanf("%d", &n);
        idx = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                mtx[i][j] = ++idx;
        M.clear();
        cunt = 0;
        for (int i = 0; i < n; i++) {
            s1 = 0, s2 = 0;
            for (int j = 0; j < n; j++) {
                s1 += mtx[i][j];
                s2 += mtx[j][i];
            }
            row[i] = s1; col[i] = s2;
            if ((M[s1]++) == 0) cunt++;
            if ((M[s2]++) == 0) cunt++;
        }
        s1 = s2 = 0;
        for (int i = 0; i < n; i++) {
            s1 += mtx[i][i];
            s2 += mtx[i][n-i-1];
        }
        dia[0] = s1; dia[1] = s2;
        if ((M[s1]++) == 0) cunt++;
        if ((M[s2]++) == 0) cunt++;
        m = 2 * n + 2;
        while (cunt < m) {
            r1 = rand() % n;
            r2 = rand() % n;
            c1 = rand() % n;
            c2 = rand() % n;
            
            Change(r1, c1, r2, c2);
        }
        printf("Case #%d:\n", C);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) printf(" ");
                printf("%d", mtx[i][j]);
            }
            printf("\n");
        }
        /*
        for (int i = 0; i < n; i++) {
            s1 = s2 = 0;
            for (int j = 0; j < n; j++) {
                s1 += mtx[i][j];
                s2 += mtx[j][i];
            }
            printf("%d %d ", s1, s2);
        }
        s1 = s2 = 0;
        for (int i = 0; i < n; i++) {
            s1 += mtx[i][i];
            s2 += mtx[i][n-i-1];
        }
        printf("%d %d\n", s1, s2);*/
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/racebug2010/article/details/6681103


  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。