Pancake's Personal Website – 第 9 页

Timus #1207

题目说明：二维坐标上有一堆点，选两点作为一条直线，把所有点分成两堆

题目解析：极角排序。找到x轴最小的点，其他所有点求atan2，进行排序，取最小点和排列后中间点的index索引输出。

Problem analysis English version:

Find minimum x in points.
Store atan2 which is theta between minimum x and origin and the index of each point.
Use bubble sort to sort atan2 result.
Output the index of minimum x and the number in the middle of the series.

代码说明：个人写了冒泡排序，没用c++ sort 和结构体，相对来说代码可读性较差，可以对此进行改进

#include<iostream>
#include<cmath>
using namespace std;


int main() {
	int n;
	cin >> n;
	double array[10000][2];
	double theta[10000];
	int position[10000];
	for (int i = 0; i < n; i++)cin >> array[i][0] >> array[i][1];
	int min = array[0][0];
	int minPosition = 0;
	for (int i = 1; i < n; i++) {
		minPosition = min <= array[i][0] ? minPosition : i;
		min = min <= array[i][0] ? min : array[i][0];
	}
	int ii = 0;
	for (int i = 0; i < n; i++) {
		if (i == minPosition)continue;
		position[ii] = i + 1;
		theta[ii] = atan2(array[i][1] - array[minPosition][1], array[i][0] - array[minPosition][0]);
		ii++;
	}
	double temp;
	for (int i = 0; i < n - 2; i++)
	{
		for (int j = 0; j < n - i - 2; j++)
		{
			if (theta[j + 1] < theta[j])
			{
				temp = theta[j];
				theta[j] = theta[j + 1];
				theta[j + 1] = temp;

				temp = position[j];
				position[j] = position[j + 1];
				position[j + 1] = temp;
			}
		}
	}
	cout << minPosition + 1 << " " << position[(n - 1) / 2]<< endl;
	return 0;
}

#include<iostream>

#include<cmath>

using namespace std;

int main() {

int n;

cin >> n;

double array[10000][2];

double theta[10000];

int position[10000];

for (int i = 0; i < n; i++)cin >> array[i][0] >> array[i][1];

int min = array[0][0];

int minPosition = 0;

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

minPosition = min <= array[i][0] ? minPosition : i;

min = min <= array[i][0] ? min : array[i][0];

}

int ii = 0;

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

if (i == minPosition)continue;

position[ii] = i + 1;

theta[ii] = atan2(array[i][1] - array[minPosition][1], array[i][0] - array[minPosition][0]);

ii++;

}

double temp;

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

{

for (int j = 0; j < n - i - 2; j++)

{

if (theta[j + 1] < theta[j])

{

temp = theta[j];

theta[j] = theta[j + 1];

theta[j + 1] = temp;

temp = position[j];

position[j] = position[j + 1];

position[j + 1] = temp;

}

cout << minPosition + 1 << " " << position[(n - 1) / 2]<< endl;

return 0;

}

Timus #1155

题目说明：立方体相邻两点可以同时相加或相减，要把每个点变为0的过程

解题思路：
1. 要有解则A + C + F + H = B + D + E + G
2. 进入循环直至每个点为0
3. 找到最小的位置。如果这个最小的位置旁边3个点都为0，则找到另外一个有数的点，再找这两点分别相邻的相邻的点加1。如果这个最小的位置旁边3个领点有数字，则找一个有数字的点进行相减。（听上去会有点绕）

Firstly, if it possible it will satisfy the equation A + C + F + H = B + D + E + G.
Secondly, go into loop, if every position is 0 quit the loop.
Thirdly, find the maximum position to decrease/increase. If this maximum position doesn’t have adjacent position to decrease, than find another position with value (not 0), increase 1 to two adjacent position adjacent to the maximum position and another position. Else decrease 1 to maximum position and the position adjacent to it.

#include <iostream>
#include <string>
using namespace std;


int judge_done(int arr[8]) {
    for (int i = 0; i < 8; i++) {
        if (arr[i] != 0) {
            return 1;
        }
    }
    return 0;
}

int judge_zero(int arr[3], int arr_all[8]) {
    for (int i = 0; i < 3; i++) {
        if (arr_all[arr[i]] != 0) {
            return 1;
        }
    }
    return 0;
}

int find_same(int arr1[3], int arr2[3]) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (arr1[i] == arr2[j]) {
                return arr1[i];
            }
        }
    }
    return 0;
}


int main() {
    int arr[8];
    string arr_name = "ABCDEFGH";
    for (int i = 0; i < 8; i++)  cin >> arr[i];
    if (arr[0] + arr[2] + arr[5] + arr[7] != arr[1] + arr[3] + arr[4] + arr[6]) {
        cout << "IMPOSSIBLE" << endl;
    }
    else {
        int neighbor[8][3] = { { 1, 3, 4 } ,{ 0, 2, 5 },{ 1, 3, 6 },{ 0, 2, 7 },{ 0, 5, 7 },{ 1, 4, 6 },{ 2, 5, 7 },{ 3, 4, 6 } };
        int max, position, temp_position;
        while (judge_done(arr)) {
            max = arr[0]; position = 0;
            for (int i = 0; i < 8; i++) {
                max = max >= arr[i] ? max : arr[i];
                position = max > arr[i] ? position : i;
            }
            if (max > 0) {
                if (judge_zero(neighbor[position], arr)) {
                    for (int i = 0; i < 3; i++) {
                        if (arr[neighbor[position][i]] != 0) {
                            arr[position]--;
                            arr[neighbor[position][i]]--;
                            cout << arr_name[position] << arr_name[neighbor[position][i]] << "-" << endl;
                            break;
                        }
                    }
                }
                else {
                    for (int i = 0; i < 8; i++) {
                        if (i == position) continue;
                        else if (arr[i] != 0) {
                            temp_position = i;
                            break;
                        }
                    }
                    int position1 = neighbor[position][0];
                    int position2 = find_same(neighbor[position1], neighbor[temp_position]);
                    arr[position1]++; arr[position2]++;
                    cout << arr_name[position1] << arr_name[position2] << "+" << endl;
                }
            }
        }
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int judge_done(int arr[8]) {

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

if (arr[i] != 0) {

return 1;

}

return 0;

}

int judge_zero(int arr[3], int arr_all[8]) {

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

if (arr_all[arr[i]] != 0) {

return 1;

}

return 0;

}

int find_same(int arr1[3], int arr2[3]) {

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

for (int j = 0; j < 3; j++) {

if (arr1[i] == arr2[j]) {

return arr1[i];

}

return 0;

}

int main() {

int arr[8];

string arr_name = "ABCDEFGH";

for (int i = 0; i < 8; i++) cin >> arr[i];

if (arr[0] + arr[2] + arr[5] + arr[7] != arr[1] + arr[3] + arr[4] + arr[6]) {

cout << "IMPOSSIBLE" << endl;

}

else {

int neighbor[8][3] = { { 1, 3, 4 } ,{ 0, 2, 5 },{ 1, 3, 6 },{ 0, 2, 7 },{ 0, 5, 7 },{ 1, 4, 6 },{ 2, 5, 7 },{ 3, 4, 6 } };

int max, position, temp_position;

while (judge_done(arr)) {

max = arr[0]; position = 0;

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

max = max >= arr[i] ? max : arr[i];

position = max > arr[i] ? position : i;

}

if (max > 0) {

if (judge_zero(neighbor[position], arr)) {

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

if (arr[neighbor[position][i]] != 0) {

arr[position]--;

arr[neighbor[position][i]]--;

cout << arr_name[position] << arr_name[neighbor[position][i]] << "-" << endl;

break;

}

else {

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

if (i == position) continue;

else if (arr[i] != 0) {

temp_position = i;

break;

}

int position1 = neighbor[position][0];

int position2 = find_same(neighbor[position1], neighbor[temp_position]);

arr[position1]++; arr[position2]++;

cout << arr_name[position1] << arr_name[position2] << "+" << endl;

}

return 0;

}

Timus #2025

题目说明：有n个人分成了k组，不同组的人两两对打，要求对打局数最大。

题目解析：每组约平均得出结果越大，sum过程纯属数学计算过程。

Problem Analysis English version: We can easily notice from math calculations that the more average of each group, the bigger number we will get.

#include<iostream>
#include<cmath>
using namespace std;

int main() {
	int ii;
	cin >> ii;
	int n, k, sum;
	for (int i = 0; i < ii; i++) {
		cin >> n; cin >> k;
		int group = n / k;
		int rest = n % k;
		sum = group * group * (k - 1) * k / 2 + rest * (rest - 1) / 2 + rest * (k - 1) * group;
		cout << sum << endl;
	}
	return 0;
}

#include<iostream>

#include<cmath>

using namespace std;

int main() {

int ii;

cin >> ii;

int n, k, sum;

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

cin >> n; cin >> k;

int group = n / k;

int rest = n % k;

sum = group * group * (k - 1) * k / 2 + rest * (rest - 1) / 2 + rest * (k - 1) * group;

cout << sum << endl;

}

return 0;

}

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