Timus – 第 2 页 – Pancake's Personal Website

Timus #1650. Billionaires

题目：有n个富豪（数据包含：姓名，开始时的所在地，拥有财富），某地财富即为在此的所有富豪财富相加。在接下来的m天，会有k个土豪在某一天晚上离开所在地，在第二天早上到达所在地。求每天拥有财富最多的城市，按照字母表顺序输出某城市财富最多的天数。ps：若某一天有两个及以上的城市财富相同则该天不算在这几个城市的天数中，若最终有城市天数为0则不输出此城市。

解析：该题目逻辑很简单，建立Person和City结构体，Person储存姓名，所在地，财富；City储存城市名，拥有财富。循环查找/插入/删除/更新City和Person中的数据，并找到City中财富最大的城市。

代码分析：你必须建立map或set容器或写自己的Tree结构来完成此题，否则必会超时。比如，如果你用顺序的方式遍历City中最大的城市/城市名必定会超时。
1. 我的解决方法是用map<string, City*>cityptr;用指针快速修改和查找。
2. 更加快捷的方式是map<string, pair<City*, long long>>Person;
3. 傻一点的方法是建立map<string, int>index;这种方法缺点是每次都要更新index。

#include<iostream>
#include<map>
#include<set>
using namespace std;

struct City {
	string name;
	long long money;
	City(string nameIN, long long moneyIN):name(nameIN),money(moneyIN) {}
	bool operator< (const City& a)const
	{
		if (this->money == a.money) return this->name < a.name;
		return this->money > a.money;
	}
};

void add(set<City>& city, map<string, City*>& cityptr, string cityname, long long money) {
	map<string, City*>::iterator ptr;
	ptr = cityptr.find(cityname);
	City * cityNow = new City(cityname, money);
	if(ptr == cityptr.end()){
		city.insert(*cityNow);
		cityptr.insert({ cityNow->name, cityNow });
	}
	else {
		cityNow->money += ptr->second->money;
		city.erase(*ptr->second);
		ptr->second = cityNow;
		city.insert(*cityNow);
	}

}

void insertResult(set<City>& city, map<string, int> &result, int day) {
	string name;
	if (city.size() >= 2) {
		set<City>::iterator ptr = city.begin();
		if (ptr->money - (++ptr)->money != 0) name = city.begin()->name;
		else return;
	}
	else if (city.size() == 0) return;
	else if (city.size() == 1) name = city.begin()->name;
	map<string, int>::iterator ptr;
	ptr = result.find(name);
	if (ptr != result.end()) ptr->second += day;
	else result.insert({ name, day });
}


void del(set<City>& city, map<string, City*>& cityptr, string cityName, long long money) {
	map<string, City*>::iterator ptr;
	ptr = cityptr.find(cityName);
	City *tempCity = new City(cityName, ptr->second->money - money);
	city.erase(*ptr->second);
	delete ptr->second;
	ptr->second = tempCity;
	if (tempCity->money == 0) {
		cityptr.erase(ptr);
		return;
	}
	city.insert(*tempCity);
}

int main() {
	map<string, pair<string, long long>>Person;
	map<string, int>result;
	map<string, City*>cityptr;
	set<City>city;
	int n, m, k, day = 0, preday;
	cin >> n;
	string namePerson;
	string nameCity;
	string namePreCity;
	long long money;
	for (int i = 0; i < n; i++) {
		cin >> namePerson >> nameCity >> money;
		Person.insert({ namePerson,make_pair(nameCity,money) });
		add(city, cityptr, nameCity, money);
	}
	cin >> m >> k;
	for (int i = 0; i < k; i++) {
		preday = day;
		cin >> day >> namePerson >> nameCity;
		insertResult(city, result, day - preday);
		map<string, pair<string, long long>>::iterator ptr;
		ptr = Person.find(namePerson);
		money = ptr->second.second;
		add(city, cityptr, nameCity, money);
		namePreCity = ptr->second.first;
		ptr->second.first = nameCity;
		del(city, cityptr, namePreCity, money);
	}
	insertResult(city, result, m - day);
	for (auto i : result) {
		if (i.second == 0)continue;
		cout << i.first << " " << i.second << endl;
	}
}

#include<iostream>

#include<map>

#include<set>

using namespace std;

struct City {

string name;

long long money;

City(string nameIN, long long moneyIN):name(nameIN),money(moneyIN) {}

bool operator< (const City& a)const

{

if (this->money == a.money) return this->name < a.name;

return this->money > a.money;

}

};

void add(set<City>& city, map<string, City*>& cityptr, string cityname, long long money) {

map<string, City*>::iterator ptr;

ptr = cityptr.find(cityname);

City * cityNow = new City(cityname, money);

if(ptr == cityptr.end()){

city.insert(*cityNow);

cityptr.insert({ cityNow->name, cityNow });

}

else {

cityNow->money += ptr->second->money;

city.erase(*ptr->second);

ptr->second = cityNow;

city.insert(*cityNow);

}

void insertResult(set<City>& city, map<string, int> &result, int day) {

string name;

if (city.size() >= 2) {

set<City>::iterator ptr = city.begin();

if (ptr->money - (++ptr)->money != 0) name = city.begin()->name;

else return;

}

else if (city.size() == 0) return;

else if (city.size() == 1) name = city.begin()->name;

map<string, int>::iterator ptr;

ptr = result.find(name);

if (ptr != result.end()) ptr->second += day;

else result.insert({ name, day });

}

void del(set<City>& city, map<string, City*>& cityptr, string cityName, long long money) {

map<string, City*>::iterator ptr;

ptr = cityptr.find(cityName);

City *tempCity = new City(cityName, ptr->second->money - money);

city.erase(*ptr->second);

delete ptr->second;

ptr->second = tempCity;

if (tempCity->money == 0) {

cityptr.erase(ptr);

return;

}

city.insert(*tempCity);

}

int main() {

map<string, pair<string, long long>>Person;

map<string, int>result;

map<string, City*>cityptr;

set<City>city;

int n, m, k, day = 0, preday;

cin >> n;

string namePerson;

string nameCity;

string namePreCity;

long long money;

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

cin >> namePerson >> nameCity >> money;

Person.insert({ namePerson,make_pair(nameCity,money) });

add(city, cityptr, nameCity, money);

}

cin >> m >> k;

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

preday = day;

cin >> day >> namePerson >> nameCity;

insertResult(city, result, day - preday);

map<string, pair<string, long long>>::iterator ptr;

ptr = Person.find(namePerson);

money = ptr->second.second;

add(city, cityptr, nameCity, money);

namePreCity = ptr->second.first;

ptr->second.first = nameCity;

del(city, cityptr, namePreCity, money);

}

insertResult(city, result, m - day);

for (auto i : result) {

if (i.second == 0)continue;

cout << i.first << " " << i.second << endl;

}

Timus #1628. White Streaks

题目：有m*n的矩形，每个方块默认为白色，现给k个方块图上黑色，问有多少连续的num*1或1*num的长方形。如果一个1*1的方块周围没有白色方块，那么这个方块也包含在答案里面。

解析：行列遍历。对行和列分别进行查找，对行和列查找过程中单独成一个方块的坐标分别记录在两个集合中，最终只需要在结果上加上两个集合的交集中元素的个数。

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

struct Point
{
	int x, y;
	bool operator< (const Point & a)const
	{
		if (this->x == a.x)return this->y < a.y;
		return this->x < a.x;
	}
}point[60000];

int fx(Point& a, Point& b) { 
	if (a.x == b.x)return a.y < b.y;
	return a.x < b.x; 
}

int fy(Point& a, Point& b) {
	if (a.y == b.y)return a.x < b.x;
	return a.y < b.y;
}

void insert(set<Point>& a, int x, int y) {
	Point tempPoint;
	tempPoint.x = x;
	tempPoint.y = y;
	a.insert(tempPoint);

}

int main() {
	int m, n, k, ans = 0;
	cin >> n >> m >> k;
	set<Point> A;
	set<Point> B;
	set<Point> C;
	for (int i = 0; i < k; i++)cin >> point[i].x >> point[i].y;
	int now = 0, row = 0, col = 0;

	if (n == 1) {
		sort(point, point + k, fx);
		if (point[0].y == 1) ans++; 
		for (int i = 1; i < k; i++) {
			if (point[i].y - point[i - 1].y == 1) ans++;
		}
		if (point[k - 1].y == m) ans++;
		cout << k + 1 - ans;
		return 0;
	}

	if (m == 1) {
		sort(point, point + k, fy);
		if (point[0].x == 1) ans++;
		for (int i = 1; i < k; i++) {
			if (point[i].x - point[i - 1].x == 1) ans++;
		}
		if (point[k - 1].x == n) ans++;
		cout << k + 1 - ans;
		return 0;
	}

	sort(point, point + k, fx);
	while (row < n) {
		if (point[now].x != row + 1) {
			ans++;
			row++;
			continue;
		}
		if (point[now].y == 2) insert(A, point[now].x, 1);
		else if (point[now].y > 2) ans++;
		now++;
		while (now < k)
		{
			if (point[now].x == point[now - 1].x) {
				if (point[now].y - point[now - 1].y == 2) insert(A, point[now].x, point[now].y - 1);
				else if (point[now].y - point[now - 1].y > 2) ans++;
			}
			else {
				break;
			}
			now++;
		}
		if (point[now - 1].y == m - 1) insert(A, point[now - 1].x, m);
		else if (point[now - 1].y < m - 1) ans++;
		row++;
	}

	sort(point, point + k, fy);
	now = 0;
	while (col < m) {
		if (point[now].y != col + 1) {
			ans++;
			col++;
			continue;
		}
		if (point[now].x == 2) insert(B, 1, point[now].y);
		else if (point[now].x > 2) ans++;
		now++;
		while (now < k)
		{
			if (point[now].y == point[now - 1].y) {
				if (point[now].x - point[now - 1].x == 2) insert(B, point[now].x - 1, point[now].y);
				else if (point[now].x - point[now - 1].x > 2) ans++;
			}
			else {
				break;
			}
			now++;
		}
		if (point[now - 1].x == n - 1) insert(B, n, point[now - 1].y);
		else if (point[now - 1].x < n - 1) ans++;
		col++;
	}

	set_intersection(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()));
	ans += C.size();
	cout << ans << endl;

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include<iostream>

#include<algorithm>

#include<iterator>

#include<set>

using namespace std;

struct Point

{

int x, y;

bool operator< (const Point & a)const

{

if (this->x == a.x)return this->y < a.y;

return this->x < a.x;

}

}point[60000];

int fx(Point& a, Point& b) {

if (a.x == b.x)return a.y < b.y;

return a.x < b.x;

}

int fy(Point& a, Point& b) {

if (a.y == b.y)return a.x < b.x;

return a.y < b.y;

}

void insert(set<Point>& a, int x, int y) {

Point tempPoint;

tempPoint.x = x;

tempPoint.y = y;

a.insert(tempPoint);

}

int main() {

int m, n, k, ans = 0;

cin >> n >> m >> k;

set<Point> A;

set<Point> B;

set<Point> C;

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

int now = 0, row = 0, col = 0;

if (n == 1) {

sort(point, point + k, fx);

if (point[0].y == 1) ans++;

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

if (point[i].y - point[i - 1].y == 1) ans++;

}

if (point[k - 1].y == m) ans++;

cout << k + 1 - ans;

return 0;

}

if (m == 1) {

sort(point, point + k, fy);

if (point[0].x == 1) ans++;

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

if (point[i].x - point[i - 1].x == 1) ans++;

}

if (point[k - 1].x == n) ans++;

cout << k + 1 - ans;

return 0;

}

sort(point, point + k, fx);

while (row < n) {

if (point[now].x != row + 1) {

ans++;

row++;

continue;

}

if (point[now].y == 2) insert(A, point[now].x, 1);

else if (point[now].y > 2) ans++;

now++;

while (now < k)

{

if (point[now].x == point[now - 1].x) {

if (point[now].y - point[now - 1].y == 2) insert(A, point[now].x, point[now].y - 1);

else if (point[now].y - point[now - 1].y > 2) ans++;

}

else {

break;

}

now++;

}

if (point[now - 1].y == m - 1) insert(A, point[now - 1].x, m);

else if (point[now - 1].y < m - 1) ans++;

row++;

}

sort(point, point + k, fy);

now = 0;

while (col < m) {

if (point[now].y != col + 1) {

ans++;

col++;

continue;

}

if (point[now].x == 2) insert(B, 1, point[now].y);

else if (point[now].x > 2) ans++;

now++;

while (now < k)

{

if (point[now].y == point[now - 1].y) {

if (point[now].x - point[now - 1].x == 2) insert(B, point[now].x - 1, point[now].y);

else if (point[now].x - point[now - 1].x > 2) ans++;

}

else {

break;

}

now++;

}

if (point[now - 1].x == n - 1) insert(B, n, point[now - 1].y);

else if (point[now - 1].x < n - 1) ans++;

col++;

}

set_intersection(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()));

ans += C.size();

cout << ans << endl;

}

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代码