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

Timus #1067. Disk Tree

题目：输入N个文件/文件夹位置关系，输出层级关系。看题目例子就可以看懂。

解析：利用树状结构

代码缺点：该代码内存占用太多。在insert函数中，可以选择更高效的查找及插入算法，但这道题对运行时间要求没那没高，可以写的相对简单一点。Tree* child[70]这个数字70根据题目可以调整，只是越大消耗内存越大，可以存放的子节点越多，Timus这道题写70就够了。

代码优化建议：
1. 把Tree中改成vector<pair<string, Tree>> child;这样可以大大减少内存以及提供更高效的对string排序操作。
2. 把Tree中改成set<Tree> child;并对<运算符(根据string name;)进行重载。set提供了高效的insert和find函数，这种方法更高效。

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

class Tree {
public:
	Tree() {
		level = 0;
	}
	Tree(const Tree& tree) {
		this->level = tree.level + 1;
	}
	int level;
	vector<pair<string, int>> name;
	Tree* child[70];
};

Tree * insert(Tree* tree, string word) {
	for (int i = 0; i < tree->name.size(); i++) 
		if (tree->name[i].first == word) 
			return tree->child[i];
	tree->name.push_back(make_pair(word, tree->name.size()));
	tree->child[tree->name.size() - 1] = new Tree(*tree);
	return tree->child[tree->name.size() - 1];

}

int f(pair<string, int>& a, pair<string, int>& b) {
	return a.first < b.first;
}

void show(Tree* tree) {
	for (int i = 0; i < tree->name.size(); i++) {
		sort(tree->name.begin(), tree->name.end(), f);
		for (int j = 0; j < tree->level; j++)cout << " ";
		cout << (tree->name[i].first) << endl;
		show(tree->child[tree->name[i].second]);
	}
}

int main() {
	int n, count = 0;
	cin >> n;
	string temp;
	Tree tree;
	Tree* tempTree;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		string single = "";
		tempTree = &tree;
		for (int j = 0; j < temp.size(); j++) {
			if (temp[j] == '\\') {
				tempTree = insert(tempTree, single);
				single = "";
			}
			else single += temp[j];
		}
		tempTree = insert(tempTree, single);
	}
	show(&tree);
}

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

class Tree {

public:

Tree() {

level = 0;

}

Tree(const Tree& tree) {

this->level = tree.level + 1;

}

int level;

vector<pair<string, int>> name;

Tree* child[70];

};

Tree * insert(Tree* tree, string word) {

for (int i = 0; i < tree->name.size(); i++)

if (tree->name[i].first == word)

return tree->child[i];

tree->name.push_back(make_pair(word, tree->name.size()));

tree->child[tree->name.size() - 1] = new Tree(*tree);

return tree->child[tree->name.size() - 1];

}

int f(pair<string, int>& a, pair<string, int>& b) {

return a.first < b.first;

}

void show(Tree* tree) {

for (int i = 0; i < tree->name.size(); i++) {

sort(tree->name.begin(), tree->name.end(), f);

for (int j = 0; j < tree->level; j++)cout << " ";

cout << (tree->name[i].first) << endl;

show(tree->child[tree->name[i].second]);

}

int main() {

int n, count = 0;

cin >> n;

string temp;

Tree tree;

Tree* tempTree;

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

cin >> temp;

string single = "";

tempTree = &tree;

for (int j = 0; j < temp.size(); j++) {

if (temp[j] == '\\') {

tempTree = insert(tempTree, single);

single = "";

}

else single += temp[j];

}

tempTree = insert(tempTree, single);

}

show(&tree);

}

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;

}