2022 年 4 月 – 第 4 页 – Pancake's Personal Website

Timus #1322

题目：Burrows-Wheeler逆变换，具体读题即可读懂

解析：Burrows-Wheeler 压缩(转换)算法(BWT)。

1. 百度百科上的例子：加列，排序循环

2.我也不知道什么原理，我用的是这种方法。vector of inverse transform.

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

struct BWT
{
	string ch;
	int index;
}bwt[200000];

int f(BWT& a, BWT& b) {
	if (a.ch == b.ch) return a.index < b.index;
	return a.ch < b.ch;
}

int main() {
	int k;
	string line;
	cin >> k >> line;
	int n = line.size();
	for (int i = 0; i < n; i++) {
		bwt[i].index = i;
		bwt[i].ch = line[i];
	}
	sort(bwt, bwt + n, f);
	int temp = k - 1;
	for (int i = 0; i < n; i++) {
		cout << line[bwt[temp].index];
		temp = bwt[temp].index;
	}
	return 0;
}

#include<iostream>

#include<algorithm>

#include<string>

using namespace std;

struct BWT

{

string ch;

int index;

}bwt[200000];

int f(BWT& a, BWT& b) {

if (a.ch == b.ch) return a.index < b.index;

return a.ch < b.ch;

}

int main() {

int k;

string line;

cin >> k >> line;

int n = line.size();

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

bwt[i].index = i;

bwt[i].ch = line[i];

}

sort(bwt, bwt + n, f);

int temp = k - 1;

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

cout << line[bwt[temp].index];

temp = bwt[temp].index;

}

return 0;

}

Timus #1444

题目说明：二维数组上有一些点，以第一个点为起点，把剩下的点连起来形成一个没有边相交的多边形，类似于一笔画，无需回到起点，只需把n个点连起来。

题目解析：类似于Timus #1607，极角排序，但排序顺序难想很多。首先找到x轴最小的点作为算法中整个图形的起点。计算每个点的atan2。对atan2进行升序排序，但是其中atan2角度可能相同，你可以画画图想想一下，对相同的距离也进行进行升序排序，距离越大连的越后面。但是我们这道题起点必须为输入的第一个点，这就意味着我们取x轴最小的点作为起的时候需要收尾也要相连，所以如果有大于两个的点位于x轴最小的点的正上方，就会出现收尾不可能相连的错误，这就需要对距离进行降序排序。具体sort函数排序方法可见代码f函数

Problem analysis English version:

Find the point with minimum x, exchange it to the first position.
Cal atan2.
Sort atan2 exclude the point with minimum x which is in the first position.
Find the index which is 1 and output the result.

Difference of sort definition between problem 1207:
Increasing order by theta. When theta is same, use increasing order of the distance from min_x point besides one situation. However if the points have same theta and is directly above the min_x point , we must use descending order of the distance from min_x point.

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

struct point {
    int x, y, index;
    double theta;
} p[30000], temp;

int f(point& a, point& b) {
    if (a.theta == b.theta) {
        if (a.x == b.x && a.y > 0) return a.y * a.y > b.y * b.y;
        else return a.x * a.x + a.y * a.y < b.x* b.x + b.y * b.y;
    }
    return a.theta < b.theta;
}

int main() {
    int n;
    cin >> n;
    //input
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> p[i].x >> p[i].y;
        p[i].index = i + 1;
    }
    //exchange min_x to first position
    int min = p[0].x, minPosition = 0;
    for (int i = 1; i < n; i++) {
    	minPosition = min <= p[i].x ? minPosition : i;
    	min = min <= p[i].x ? min : p[i].x;
    }
    temp = p[0]; p[0] = p[minPosition]; p[minPosition] = temp;
    //cal atan2
    for (int i = 1; i < n; i++) {
        p[i].x -= p[0].x;
        p[i].y -= p[0].y;
        p[i].theta = atan2(p[i].y, p[i].x);
    }
    //sort exclude min_x
    sort(p + 1, p + n, f);
    //output
    cout << n << endl;
    for (int i = 0; i < n; i++) {
        if (p[i].index == 1) {
            for (int j = i; j < n; j++) cout << p[j].index << endl;
            for (int j = 0; j < i; j++) cout << p[j].index << endl;
            break;
        }
    }
}

#include<iostream>

#include<cmath>

#include<algorithm>

using namespace std;

struct point {

int x, y, index;

double theta;

} p[30000], temp;

int f(point& a, point& b) {

if (a.theta == b.theta) {

if (a.x == b.x && a.y > 0) return a.y * a.y > b.y * b.y;

else return a.x * a.x + a.y * a.y < b.x* b.x + b.y * b.y;

}

return a.theta < b.theta;

}

int main() {

int n;

cin >> n;

//input

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

int x, y;

cin >> p[i].x >> p[i].y;

p[i].index = i + 1;

}

//exchange min_x to first position

int min = p[0].x, minPosition = 0;

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

minPosition = min <= p[i].x ? minPosition : i;

min = min <= p[i].x ? min : p[i].x;

}

temp = p[0]; p[0] = p[minPosition]; p[minPosition] = temp;

//cal atan2

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

p[i].x -= p[0].x;

p[i].y -= p[0].y;

p[i].theta = atan2(p[i].y, p[i].x);

}

//sort exclude min_x

sort(p + 1, p + n, f);

//output

cout << n << endl;

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

if (p[i].index == 1) {

for (int j = i; j < n; j++) cout << p[j].index << endl;

for (int j = 0; j < i; j++) cout << p[j].index << endl;

break;

}

Timus #1604

题目说明：有k种速度，种类1的个数为n₁，种类 2的个数为n₂……种类k的个数为n_k。对种类进行排序，使得变化的次数最大。eg:
input:
2
2 3
output is not:
1 2 1 2 2
output is:
2 1 2 1 2

题目解析：对所有n进行降序排序，把每种种类保存在一维数组中，利用sub2inedx操作（类似于matlab操作）把二维数组坐标用index表示并输出对应一维数组中的数。
二维数组说明：为了变换次数最大，把最大的种类放在第一列，行数为最大的个数，然后按降序升序一起从上往下从左往右填充剩下的种类并输出。
该算法精髓：sub2index

Problem analysis English version:

Sort signs in descending order
Using one dimensional array to story type.
Output two dimension matrix using sub2index function likely in Matlab program.

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

struct Sign
{
	int type, number;
}sign[20000];

struct Position
{
	int x, y;
};

int f(Sign& a, Sign& b) {
	return a.number > b.number;
}


int sub2index(struct Position position, int width) {
	return position.y * width + position.x;
}


int main() {
	int k;
	cin >> k;
	int array[20000] = { 0 };
	for (int i = 0; i < k; i++) {
		cin >> sign[i].number;
		sign[i].type = i + 1;
	}
	sort(sign, sign + k, f);
	int temp = 0;
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < sign[i].number; j++) {
			array[temp] = sign[i].type;
			temp++;
		}
	}
	struct Position position;
	int max = (temp - 1)/ sign[0].number;
	for (int i = 0; i < sign[0].number; i++) {
		position.x = i;
		for (int j = 0; j <= max; j++) {
			position.y = j;
			int number = array[sub2index(position, sign[0].number)];
			if (number != 0) cout << number << " ";
		}
	}
	return 0;
}

#include<iostream>

#include<algorithm>

using namespace std;

struct Sign

{

int type, number;

}sign[20000];

struct Position

{

int x, y;

};

int f(Sign& a, Sign& b) {

return a.number > b.number;

}

int sub2index(struct Position position, int width) {

return position.y * width + position.x;

}

int main() {

int k;

cin >> k;

int array[20000] = { 0 };

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

cin >> sign[i].number;

sign[i].type = i + 1;

}

sort(sign, sign + k, f);

int temp = 0;

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

for (int j = 0; j < sign[i].number; j++) {

array[temp] = sign[i].type;

temp++;

}

struct Position position;

int max = (temp - 1)/ sign[0].number;

for (int i = 0; i < sign[0].number; i++) {

position.x = i;

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

position.y = j;

int number = array[sub2index(position, sign[0].number)];

if (number != 0) cout << number << " ";

}

return 0;

}

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;

}