Timus – 第 3 页 – Pancake's Personal Website

Timus #1726

题目：有n个人相互访问访问各自的坐标，所有道路正交，沿直线行走，求平均路程。

解析：首先对x,y分别进行排序。每个x[i + 1] – x[i] 会经过 (i + 1) * (n – (i + 1)) * 2次，y也一样，然后进入循环进行计算。

代码及精度问题：使用long long int，不要使用int，在测试样例中会超出int范围。计算过程中加入long long temp;避免在计算过程中强制类型转换造成计算错误。

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


int main() {
	int n;
	cin >> n;
	int x[100000], y[100000];
	for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
	long long int sum = 0;
	sort(x, x + n);
	sort(y, y + n);
	for (int i = 0; i < n - 1; i++) {
		long long temp;
		temp = x[i + 1] - x[i] + y[i + 1] - y[i];
		temp *= i + 1;
		temp *= n - i - 1;
		sum +=  temp * 2;
	}
	cout << sum / n / (n - 1) << endl;
	return 0;
}

#include<iostream>

#include<algorithm>

using namespace std;

int main() {

int n;

cin >> n;

int x[100000], y[100000];

for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

long long int sum = 0;

sort(x, x + n);

sort(y, y + n);

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

long long temp;

temp = x[i + 1] - x[i] + y[i + 1] - y[i];

temp *= i + 1;

temp *= n - i - 1;

sum += temp * 2;

}

cout << sum / n / (n - 1) << endl;

return 0;

}

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;

}