HDU-ITMO – 第 6 页 – Pancake's Personal Website

Timus #1401

题目说明：给定一个起点，剩下的用L形的三个方块进行填充。

题目解析：迭代。最大的正方形切成四个小正方形，一步步切下去直到最后剩余2*2的小正方形。在大正方形正中间四个方块，除起点所在象限的方块，即另外三个方块标记上相同数字。

Title Analysis English version: We can using iteration to solve problems. From the start position, starting to binary cut the matrix into four pieces until every sub-matrix is 2*2. I will mark the start position and the other three positions in the middle which has different quadrants besides the quadrant the start position in.

#include<iostream>
#include<cmath>
#include <memory.h>
using namespace std;


int matrix[512][512];
int mark = 0;


void generator(int beginx, int beginy, int endx, int endy, int x2, int y2) {
    int order = endx - beginx + 1;
    int positions[4][2] = { {order / 2 - 1 + beginx, order / 2 - 1 + beginy}, {order / 2 - 1 + beginx, order / 2 + beginy}, {order / 2 + beginx, order / 2 + beginy}, {order / 2 + beginx, order / 2 - 1 + beginy} };
    int min = abs(positions[0][0] - x2) + abs(positions[0][1] - y2), positionMin = 0;
    for (int i = 1; i < 4; i++) {
        int length = abs(positions[i][0] - x2) + abs(positions[i][1] - y2);
        positionMin = min < length ? positionMin : i;
        min = min < length ? min : length;
    }
    mark++;
    for (int i = 0; i < 4; i++) {
        if (i == positionMin) continue;
        else matrix[positions[i][0]][positions[i][1]] = mark;
    }
    if (order == 2) return;

    if (positionMin == 0)generator(beginx, beginy, positions[0][0], positions[0][1], x2 , y2);
    else generator(beginx, beginy, positions[0][0], positions[0][1], positions[0][0], positions[0][1]);

    if (positionMin == 1)generator(beginx, positions[1][1], positions[1][0], endy, x2, y2);
    else generator(beginx, positions[1][1], positions[1][0], endy, positions[1][0], positions[1][1]);

    if (positionMin == 2)generator(positions[2][0], positions[2][1], endx, endy, x2, y2);
    else generator(positions[2][0], positions[2][1], endx, endy, positions[2][0], positions[2][1]);

    if (positionMin == 3)generator(positions[3][0], beginy, endx, positions[3][1], x2, y2);
    else generator(positions[3][0], beginy, endx, positions[3][1], positions[3][0], positions[3][1]);


}

int main()
{
    int n, x, y, n2;
    cin >> n;
    cin >> x;
    cin >> y;
    n2 = pow(2, n);
    matrix[x - 1][y - 1] = 0;

    generator(0, 0, n2 - 1, n2 - 1, x - 1, y - 1);

    for (int i = 0; i < n2; i++)
    {
        for (int j = 0; j < n2 - 1; j++) cout << matrix[i][j] << " "; 
        cout << matrix[i][n2 - 1] << endl;
    }
}

#include<iostream>

#include<cmath>

#include <memory.h>

using namespace std;

int matrix[512][512];

int mark = 0;

void generator(int beginx, int beginy, int endx, int endy, int x2, int y2) {

int order = endx - beginx + 1;

int positions[4][2] = { {order / 2 - 1 + beginx, order / 2 - 1 + beginy}, {order / 2 - 1 + beginx, order / 2 + beginy}, {order / 2 + beginx, order / 2 + beginy}, {order / 2 + beginx, order / 2 - 1 + beginy} };

int min = abs(positions[0][0] - x2) + abs(positions[0][1] - y2), positionMin = 0;

for (int i = 1; i < 4; i++) {

int length = abs(positions[i][0] - x2) + abs(positions[i][1] - y2);

positionMin = min < length ? positionMin : i;

min = min < length ? min : length;

}

mark++;

for (int i = 0; i < 4; i++) {

if (i == positionMin) continue;

else matrix[positions[i][0]][positions[i][1]] = mark;

}

if (order == 2) return;

if (positionMin == 0)generator(beginx, beginy, positions[0][0], positions[0][1], x2 , y2);

else generator(beginx, beginy, positions[0][0], positions[0][1], positions[0][0], positions[0][1]);

if (positionMin == 1)generator(beginx, positions[1][1], positions[1][0], endy, x2, y2);

else generator(beginx, positions[1][1], positions[1][0], endy, positions[1][0], positions[1][1]);

if (positionMin == 2)generator(positions[2][0], positions[2][1], endx, endy, x2, y2);

else generator(positions[2][0], positions[2][1], endx, endy, positions[2][0], positions[2][1]);

if (positionMin == 3)generator(positions[3][0], beginy, endx, positions[3][1], x2, y2);

else generator(positions[3][0], beginy, endx, positions[3][1], positions[3][0], positions[3][1]);

}

int main()

{

int n, x, y, n2;

cin >> n;

cin >> x;

cin >> y;

n2 = pow(2, n);

matrix[x - 1][y - 1] = 0;

generator(0, 0, n2 - 1, n2 - 1, x - 1, y - 1);

for (int i = 0; i < n2; i++)

{

for (int j = 0; j < n2 - 1; j++) cout << matrix[i][j] << " ";

cout << matrix[i][n2 - 1] << endl;

}

Python matrix 3种解矩阵方程方法

高斯消元法，简单迭代法(Jacobi迭代)，高斯迭代法(Gauss-Seidel迭代)。参考文章，该参考文章可以让你明白简单迭代和高斯迭代的方法。
总结：高斯迭代和简单迭代法会遇到矩阵存在解但迭代不收敛的情况，推荐使用高斯消元法。

高斯消元 O(n³)

def solveByGauss(matrix):
    array = []
    for i in range(0, len(matrix) - 1):
        aii = matrix[i][i]
        if aii == 0:
            continue
        for j in range(i + 1, len(matrix)):
            aji = matrix[j][i]
            for k in range(i, len(matrix[j])):
                matrix[j][k] = matrix[j][k] - aji / aii * matrix[i][k]
    for i in range(len(matrix) - 1, -1, -1):
        if matrix[i][i] == 0:
            return ["The system has no roots of equations or has an infinite set of them."]
        array.append(matrix[i][-1] / matrix[i][i])
        for j in range(0, i):
            matrix[j][-1] -= matrix[j][i] * array[-1]
    array.reverse()
    return array

def solveByGauss(matrix):

array = []

for i in range(0, len(matrix) - 1):

aii = matrix[i][i]

if aii == 0:

continue

for j in range(i + 1, len(matrix)):

aji = matrix[j][i]

for k in range(i, len(matrix[j])):

matrix[j][k] = matrix[j][k] - aji / aii * matrix[i][k]

for i in range(len(matrix) - 1, -1, -1):

if matrix[i][i] == 0:

return ["The system has no roots of equations or has an infinite set of them."]

array.append(matrix[i][-1] / matrix[i][i])

for j in range(0, i):

matrix[j][-1] -= matrix[j][i] * array[-1]

array.reverse()

return array

简单迭代 O(k*n²)

def simpleIteration(matrix, epsilon):
    n = len(matrix)
    solutions = [0 for i in range(n)]
    temp = solutions[:]
    epsilons = [float("inf") for i in range(n)]
    for i in range(n):
        if matrix[i][i] == 0:
            for j in range(n + 1):
                matrix[i][j] += 1
    while max(epsilons) > epsilon:
        for i in range(n):
            solution = matrix[i][-1]
            for j in range(n):
                if j == i:
                    continue
                solution -= matrix[i][j] * solutions[j]
            temp[i] = solution / matrix[i][i]
        epsilons = [abs(solutions[i] - temp[i]) for i in range(n)]
        solutions = temp[:]
        if max(epsilons) >= float("inf"):
            return ["The system has no roots of equations or has an infinite set of them."]
    solutions = list(map(lambda x: round(x, 3), solutions))
    return solutions

def simpleIteration(matrix, epsilon):

n = len(matrix)

solutions = [0 for i in range(n)]

temp = solutions[:]

epsilons = [float("inf") for i in range(n)]

for i in range(n):

if matrix[i][i] == 0:

for j in range(n + 1):

matrix[i][j] += 1

while max(epsilons) > epsilon:

for i in range(n):

solution = matrix[i][-1]

for j in range(n):

if j == i:

continue

solution -= matrix[i][j] * solutions[j]

temp[i] = solution / matrix[i][i]

epsilons = [abs(solutions[i] - temp[i]) for i in range(n)]

solutions = temp[:]

if max(epsilons) >= float("inf"):

return ["The system has no roots of equations or has an infinite set of them."]

solutions = list(map(lambda x: round(x, 3), solutions))

return solutions

高斯迭代基本思路和简单迭代差不多 O(k*n²)

def gaussIteration(matrix, epsilon):
    n = len(matrix)
    solutions = [0 for i in range(n)]
    temp = solutions[:]
    epsilons = [float("inf") for i in range(n)]
    for i in range(n):
        if matrix[i][i] == 0:
            for j in range(n + 1):
                matrix[i][j] += 1
    while max(epsilons) > epsilon:
        for i in range(n):
            solution = matrix[i][-1]
            for j in range(n):
                if j == i:
                    continue
                elif i > j:
                    solution -= matrix[i][j] * solutions[j]
                else:
                    solution -= matrix[i][j] * temp[j]
            temp[i] = solution / matrix[i][i]
        epsilons = [abs(solutions[i] - temp[i]) for i in range(n)]
        solutions = temp[:]
        if max(epsilons) >= float("inf"):
            return ["The system has no roots of equations or has an infinite set of them."]
    solutions = list(map(lambda x: round(x, 3), solutions))
    return solutions

def gaussIteration(matrix, epsilon):

n = len(matrix)

solutions = [0 for i in range(n)]

temp = solutions[:]

epsilons = [float("inf") for i in range(n)]

for i in range(n):

if matrix[i][i] == 0:

for j in range(n + 1):

matrix[i][j] += 1

while max(epsilons) > epsilon:

for i in range(n):

solution = matrix[i][-1]

for j in range(n):

if j == i:

continue

elif i > j:

solution -= matrix[i][j] * solutions[j]

else:

solution -= matrix[i][j] * temp[j]

temp[i] = solution / matrix[i][i]

epsilons = [abs(solutions[i] - temp[i]) for i in range(n)]

solutions = temp[:]

if max(epsilons) >= float("inf"):

return ["The system has no roots of equations or has an infinite set of them."]

solutions = list(map(lambda x: round(x, 3), solutions))

return solutions

Timus #1005

题目说明：把全部石头分成两部分，使得两堆石头质量相差最小

题目解析：dp动态规划

因为本人不会/没写过动态规划，该代码实为CSDN上的代码，本人做法为全排列，算法复杂度太高，runtime error。

#include <iostream>
#include <cstdio>
#include <cstring>                  //for memset 
#include <algorithm>                //for max
using namespace std;
const int M = 100;
int w[M];
int dp[M * 100000];
int main()
{
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
        sum += w[i];
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; ++i)
        for (int j = sum / 2; j >= w[i]; --j)
            dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
    cout << sum - dp[sum / 2] * 2 << endl;
    return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring> //for memset

#include <algorithm> //for max

using namespace std;

const int M = 100;

int w[M];

int dp[M * 100000];

int main()

{

int n;

cin >> n;

int sum = 0;

for (int i = 0; i < n; ++i) {

cin >> w[i];

sum += w[i];

}

memset(dp, 0, sizeof(dp));

for (int i = 0; i < n; ++i)

for (int j = sum / 2; j >= w[i]; --j)

dp[j] = max(dp[j], dp[j - w[i]] + w[i]);

cout << sum - dp[sum / 2] * 2 << endl;

return 0;

}

Timus #1296

题目解释：最大子序列的和

#include <iostream>
using namespace std;

int main() {
    int n, sum = 0, ans = 0, temp;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> temp;
        sum += temp;
        sum = sum > 0 ? sum : 0;
        ans = sum > ans ? sum : ans;
    }
    cout << ans << endl;
}

#include <iostream>

using namespace std;

int main() {

int n, sum = 0, ans = 0, temp;

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> temp;

sum += temp;

sum = sum > 0 ? sum : 0;

ans = sum > ans ? sum : ans;

}

cout << ans << endl;

}