24 Hours – 第 8 页 – Pancake's Personal Website

Timus #1494. Monobilliards

题目：有n个数按照1,2,3…n的顺序入栈，在每一步入栈的过程中（严格按照入栈顺序，即从先到后），可以按顺序出栈（严格按照出栈顺序，即从后到先），如果可以得到题目所input的顺序，则输出not a proof，否则为cheater。

例子讲解：
input:
4
1 3 2 4
output:
not a proof
题目为1,2,3,4入栈顺序
(1). 1入栈，1出栈；
(2). 2,3入栈，3,2出栈；
(3). 4入栈，4出栈
存在这种可能，输出not a proof

input:
3
3 1 2
output:
cheater
题目为1,2,3入栈顺序
(1). 1,2,3入栈，3 出栈
因为接下来出栈必须为2，所以不存在这种可能，输出cheater

解析：堆栈

Using the idea of stack. Input numbers (by order 1,2,3,…,n) to stack one by one, remove it out of the stack (by input number’s order) in each insertion. See if the stack is empty in the end.

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


int main() {
    int n, temp;
    cin >> n >> temp;
    vector<int>arr;
    for (int i = 1; i <= n; i++) {
        arr.push_back(i);
        while (!arr.empty() && arr[arr.size() - 1] == temp) {
            if (i == n && arr.size() == 1) {
                arr.pop_back();
                break;
            }
            cin >> temp;
            arr.pop_back();
        }
    }
    if (arr.empty()) cout << "Not a proof" << endl;
    else cout << "Cheater" << endl;
    return 0;
}

#include<iostream>

#include<vector>

using namespace std;

int main() {

int n, temp;

cin >> n >> temp;

vector<int>arr;

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

arr.push_back(i);

while (!arr.empty() && arr[arr.size() - 1] == temp) {

if (i == n && arr.size() == 1) {

arr.pop_back();

break;

}

cin >> temp;

arr.pop_back();

}

if (arr.empty()) cout << "Not a proof" << endl;

else cout << "Cheater" << endl;

return 0;

}

Timus #1521. War Games 2

题目：约塞夫问题。n个人排成一个圆圈开始报数，报数到k的人出列，输出该人在原队列的位置。

解析：
1. 直接for循环，利用vector和简单的数学计算
2. 线段树解约塞夫环

代码：
1. vector

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

int main() {
	int n, k;
	cin >> n >> k;
	vector <int> arr;
	for (int i = 0; i < n; i++)arr.push_back(i + 1);
	int position = 0;
	while (!arr.empty()) {
		position = (position + k - 1) % arr.size();
		cout << arr[position] << " ";
		arr.erase(arr.begin() + position);
	}
	return 0;
}

#include<iostream>

#include<vector>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

vector <int> arr;

for (int i = 0; i < n; i++)arr.push_back(i + 1);

int position = 0;

while (!arr.empty()) {

position = (position + k - 1) % arr.size();

cout << arr[position] << " ";

arr.erase(arr.begin() + position);

}

return 0;

}

2. 线段树解约塞夫环

CSDN代码

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;

}