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

Timus #1450. Russian Pipelines

题目：有n个点，接下来输入m行，表示从a点到b点有向边距离为c，求从S（start）起点到F（Final）终点最大路径。

解析：求最大路径问题
1. Bellman-Ford算法
2. 拓扑，利用入度（In-degree）。从入度等于0（只可能有出度）的点开始拓扑，相邻的点入度-1代表还剩in-degree个点还没拓扑到他，如果该点所有可到他的点均已经寻找完，则把该点加入queue，即可以从该点进行下一步拓扑。

错误提示：
1. WA3 Dijskra算法写错
2. TLE16 Dijskra算法因为只要小于就要加入queue，比入度算法复杂度高，不要用Dijskra改版算法，换算法
3. WA9和WA10。小部分神奇原因：输出强制类型转换成int。大部分原因：不要第一个就从开始点开始拓扑（我也不知道为什么，就是错的）。

Bellman-Ford算法

#include<iostream>
#include<unordered_map>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;

int n, m, beginPoint, endPoint;

struct Point
{
	Point() {
		distence = INF;
		done = false;
	}
	vector<pair<int, int>> neighbor;
	long long distence;
	bool done;
}point[500];


void SPFA() {
	queue<int> q;
	point[beginPoint - 1].distence = 0;
	q.push(beginPoint - 1);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		point[x].done = false;
		for (auto ptr : point[x].neighbor) {
			if (point[ptr.first].distence > point[x].distence - ptr.second) {
				point[ptr.first].distence = point[x].distence - ptr.second;
				if (!point[ptr.first].done) {
					point[ptr.first].done = true;
					q.push(ptr.first);
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		point[a - 1].neighbor.push_back(make_pair(b - 1, c));
	}
	cin >> beginPoint >> endPoint;
	SPFA();
	if (point[endPoint - 1].distence == INF) cout << "No solution" << endl;
	else cout << -point[endPoint - 1].distence << endl;
}

#include<iostream>

#include<unordered_map>

#include<vector>

#include<queue>

#define INF 0x3f3f3f3f

using namespace std;

int n, m, beginPoint, endPoint;

struct Point

{

Point() {

distence = INF;

done = false;

}

vector<pair<int, int>> neighbor;

long long distence;

bool done;

}point[500];

void SPFA() {

queue<int> q;

point[beginPoint - 1].distence = 0;

q.push(beginPoint - 1);

while (!q.empty()) {

int x = q.front();

q.pop();

point[x].done = false;

for (auto ptr : point[x].neighbor) {

if (point[ptr.first].distence > point[x].distence - ptr.second) {

point[ptr.first].distence = point[x].distence - ptr.second;

if (!point[ptr.first].done) {

point[ptr.first].done = true;

q.push(ptr.first);

}

int main() {

cin >> n >> m;

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

int a, b, c;

cin >> a >> b >> c;

point[a - 1].neighbor.push_back(make_pair(b - 1, c));

}

cin >> beginPoint >> endPoint;

SPFA();

if (point[endPoint - 1].distence == INF) cout << "No solution" << endl;

else cout << -point[endPoint - 1].distence << endl;

}

In-degree

#include<iostream>
#include<unordered_map>
#include<vector>
#define INF 0x3f3f3f3f
using namespace std;

int n, m, beginPoint, endPoint;

struct Point
{
	Point() {
		distence = -INF;
	}
	unordered_map<Point*, int> neighbor;
	long long distence;
	int degree;
}point[500];

void extend() {
	vector<Point*>queue;
	point[beginPoint - 1].distence = 0;
	Point* now;
	unordered_map<Point*, int>::iterator ptr;
	for (int i = 0; i < n; i++) 
		if (point[i].degree == 0) 
			queue.push_back(&point[i]);
	while (!queue.empty()) {
		now = *queue.begin();
		queue.erase(queue.begin());
		for (ptr = now->neighbor.begin(); ptr != now->neighbor.end(); ptr++) {
			ptr->first->distence = max(ptr->first->distence, now->distence + ptr->second);
			ptr->first->degree--;
			if (ptr->first->degree == 0) queue.push_back(ptr->first);
		}
		if (point[endPoint - 1].degree == 0) return;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		point[a - 1].neighbor.insert({ &point[b - 1], c });
		point[b - 1].degree++;
	}
	cin >> beginPoint >> endPoint;
	extend();
	if (point[endPoint - 1].distence < 0) cout << "No solution" << endl;
	else cout << point[endPoint - 1].distence << endl;
}

#include<iostream>

#include<unordered_map>

#include<vector>

#define INF 0x3f3f3f3f

using namespace std;

int n, m, beginPoint, endPoint;

struct Point

{

Point() {

distence = -INF;

}

unordered_map<Point*, int> neighbor;

long long distence;

int degree;

}point[500];

void extend() {

vector<Point*>queue;

point[beginPoint - 1].distence = 0;

Point* now;

unordered_map<Point*, int>::iterator ptr;

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

if (point[i].degree == 0)

queue.push_back(&point[i]);

while (!queue.empty()) {

now = *queue.begin();

queue.erase(queue.begin());

for (ptr = now->neighbor.begin(); ptr != now->neighbor.end(); ptr++) {

ptr->first->distence = max(ptr->first->distence, now->distence + ptr->second);

ptr->first->degree--;

if (ptr->first->degree == 0) queue.push_back(ptr->first);

}

if (point[endPoint - 1].degree == 0) return;

}

int main() {

cin >> n >> m;

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

int a, b, c;

cin >> a >> b >> c;

point[a - 1].neighbor.insert({ &point[b - 1], c });

point[b - 1].degree++;

}

cin >> beginPoint >> endPoint;

extend();

if (point[endPoint - 1].distence < 0) cout << "No solution" << endl;

else cout << point[endPoint - 1].distence << endl;

}

Timus #1806. Mobile Telegraphs

题目：有n个数，每个数都由10个数字组成。并输入int costs[10];作为传递时间。每两个数之间要是有一位不同或有两位可以通过交换得到则这两个数可以互相传递，且传递时间为costs[有多少位相同的前缀]。输出从第一个数到最后一个数所要的最短时间。

解析：最短路径问题。记录两两之间的时间，用Dijkstra算法求解。

代码解析：
建议写代码前阅读以下条目
1. 存储数的方式可以是string，但是最好是long long，所占位数少，但对最终结果及是否通过没有太大关系。string好判断更简单，用long long判断比较烦，看个人喜好了。
2. 如果你卡在TLE(Time Limit Exceeded)8见此条。若用两个for循环依次记录相互之间的可达性会卡在Test 8。因为输入N非常大，导致超时。解决办法：建立所有数字/字符串的哈希表（map），改变每个数字一位/两位，看是否有相同的数字/字符串在输入中。因为哈希表的查找迅速，尽管改变次数多，但依旧比两个for循环来得快。
3. 如果你卡在WA(Wrong Answer)3见此条。你写的Dijkstra路径记录错误，Dijkstra算法是会更新路径，不是简单的输出此迭代得到的路径最短的点。
4. 如果你卡在WA8见此条。计算可达两点距离时出现错误，可能你写成了if(i == j)应写if(int(name[i] – ‘0’) == j)←对于储存形式为string来说。
5. 如果你卡在MLE(Memory Limit Exceeded)11见此条。在Dijkstra算法中只需要当前point相邻的点即可，并不需要全部的。最好不要在结构体中加入类似于unordered_map <Point*, int> neighbor;导致每个点都储存了可达点的数据，很容易造成内存溢出，并且没有这必要，造成内存浪费。记得new不用之后要delete。
7. 为了更加节省内存，你可以修改unordered_map <Point*, int> neighbor;为vector <int, int> neighbor;这样可能你放在结构体里面也不会MLE。
6. 推荐:
INF = 0x3f3f3f3f;
neighbor用unordered_map存储

#include<iostream>
#include<unordered_map>
#include<map>
#include<vector>
#include<set>
#define INF 0x3f3f3f3f
using namespace std;

int costs[10];
int n;
vector<int>result;
map<long long, int>names;

struct Point
{
	Point(int i) {
		distence = INF;
		done = false;
		index = i;
	}
	long long name;
	Point* parent;
	long long distence;
	bool done;
	int index;
};

unordered_map<Point*, int>* neighbor;
vector<Point>point;

void cal_diff(Point* pointNow) {
	delete neighbor;
	neighbor = new unordered_map<Point*, int>;
	map<long long, int>::iterator ptr;
	long long name = pointNow->name;
	long long temp;
	for (int i = 0; i < 10; i++) {
		temp = name - name % long long(pow(10, i + 1)) / long long(pow(10, i)) * long long(pow(10, i)) - long long(pow(10, i));;
		for (int j = 0; j < 10; j++) {
			temp += long long(pow(10, i));
			if (temp == name)continue;
			ptr = names.find(temp);
			if (ptr != names.end()) (*neighbor).insert({ &point[ptr->second], costs[9 - i] });
		}
	}
	for (int i = 0; i < 10; i++) {
		int a = name % long long(pow(10, i + 1)) / long long(pow(10, i));
		for (int j = i + 1; j < 10; j++) {
			int b = name % long long(pow(10, j + 1)) / long long(pow(10, j));
			temp = name + long long(pow(10, i)) * (b - a) + long long(pow(10, j)) * (a - b);
			ptr = names.find(temp);
			if (ptr != names.end()) (*neighbor).insert({ &point[ptr->second], costs[9 - j] });
		}
	}
}

void dijkstra()
{
	set<pair<int, Point*>>queue;
	point[0].distence = 0;
	queue.insert(make_pair(0, &point[0]));
	Point* now;
	unordered_map<Point*, int>::iterator ptr;
	while (!queue.empty())
	{
		now = queue.begin()->second;
		if (now->index == n) return;
		queue.erase(queue.begin());
		if (now->done)
			continue;
		cal_diff(now);
		now->done = true;
		for (ptr = neighbor->begin(); ptr != neighbor->end(); ptr++) {
			Point* n = ptr->first;
			int cost = ptr->second;
			if (!n->done && n->distence > now->distence + cost) {
				n->parent = now;
				n->distence = now->distence + cost;
				queue.insert(make_pair(n->distence, n));
			}
		}
	}
}


void chaseBack() {
	result.push_back(n);
	Point* pointTemp = point[n - 1].parent;
	while (pointTemp != &point[0]) {
		result.insert(result.begin(), pointTemp->index);
		pointTemp = pointTemp->parent;
	}
	result.insert(result.begin(), 1);
}

int main() {
	cin >> n;
	for (int i = 0; i < 10; i++)cin >> costs[i];
	for (int i = 0; i < n; i++) {
		point.push_back(*new Point(i + 1));
		cin >> point[i].name;
		names.insert({ point[i].name, i });
	}
	dijkstra();
	if (point[n - 1].distence >= INF) cout << -1 << endl;
	else {
		chaseBack();
		cout << point[n - 1].distence << endl;
		cout << result.size() << endl;
		for (auto i : result)cout << i << " ";
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

#include<iostream>

#include<unordered_map>

#include<map>

#include<vector>

#include<set>

#define INF 0x3f3f3f3f

using namespace std;

int costs[10];

int n;

vector<int>result;

map<long long, int>names;

struct Point

{

Point(int i) {

distence = INF;

done = false;

index = i;

}

long long name;

Point* parent;

long long distence;

bool done;

int index;

};

unordered_map<Point*, int>* neighbor;

vector<Point>point;

void cal_diff(Point* pointNow) {

delete neighbor;

neighbor = new unordered_map<Point*, int>;

map<long long, int>::iterator ptr;

long long name = pointNow->name;

long long temp;

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

temp = name - name % long long(pow(10, i + 1)) / long long(pow(10, i)) * long long(pow(10, i)) - long long(pow(10, i));;

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

temp += long long(pow(10, i));

if (temp == name)continue;

ptr = names.find(temp);

if (ptr != names.end()) (*neighbor).insert({ &point[ptr->second], costs[9 - i] });

}

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

int a = name % long long(pow(10, i + 1)) / long long(pow(10, i));

for (int j = i + 1; j < 10; j++) {

int b = name % long long(pow(10, j + 1)) / long long(pow(10, j));

temp = name + long long(pow(10, i)) * (b - a) + long long(pow(10, j)) * (a - b);

ptr = names.find(temp);

if (ptr != names.end()) (*neighbor).insert({ &point[ptr->second], costs[9 - j] });

}

void dijkstra()

{

set<pair<int, Point*>>queue;

point[0].distence = 0;

queue.insert(make_pair(0, &point[0]));

Point* now;

unordered_map<Point*, int>::iterator ptr;

while (!queue.empty())

{

now = queue.begin()->second;

if (now->index == n) return;

queue.erase(queue.begin());

if (now->done)

continue;

cal_diff(now);

now->done = true;

for (ptr = neighbor->begin(); ptr != neighbor->end(); ptr++) {

Point* n = ptr->first;

int cost = ptr->second;

if (!n->done && n->distence > now->distence + cost) {

n->parent = now;

n->distence = now->distence + cost;

queue.insert(make_pair(n->distence, n));

}

void chaseBack() {

result.push_back(n);

Point* pointTemp = point[n - 1].parent;

while (pointTemp != &point[0]) {

result.insert(result.begin(), pointTemp->index);

pointTemp = pointTemp->parent;

}

result.insert(result.begin(), 1);

}

int main() {

cin >> n;

for (int i = 0; i < 10; i++)cin >> costs[i];

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

point.push_back(*new Point(i + 1));

cin >> point[i].name;

names.insert({ point[i].name, i });

}

dijkstra();

if (point[n - 1].distence >= INF) cout << -1 << endl;

else {

chaseBack();

cout << point[n - 1].distence << endl;

cout << result.size() << endl;

for (auto i : result)cout << i << " ";

}

Timus #1080. Map Coloring

题目：有k行，每行包含第i个点相邻的点。现有0/1两种颜色，相邻的颜色必须不一样，如果能进行涂色，输出每个点的颜色，如果不能进行涂色，则输出-1。

解析：
1. BFS
2. 我没用那么高级的方法，就只用vector迭代涂色。

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

vector<vector<int>>connection;
vector<pair<int, int>>color;
set<int>finish;

int coloring(vector<int> &singleConnection, int colorNow, int point) {
	set<int>::iterator ptr;
	ptr = finish.find(point);
	finish.erase(ptr);
	int colorTemp;
	for (int i = 0; i < singleConnection.size(); i++) {
		colorTemp = color[singleConnection[i]].second;
		if (colorTemp == -1) {
			color[singleConnection[i]].second = 1 - colorNow;
			int error = coloring(connection[singleConnection[i]], 1 - colorNow, singleConnection[i]);
			if (error == -1)return -1;
		}
		else if(colorNow == colorTemp) {
			return -1;
		}
	}
	return 0;
}

int main() {
	int n, temp;
	cin >> n;
	for (int i = 0; i < n; i++) {
		vector<int>connectTemp;
		connection.push_back(connectTemp);
	}
	for (int i = 0; i < n; i++) {
		color.push_back(make_pair(i, -1));
		finish.insert(i);
		while (1) {
			cin >> temp;
			if (temp != 0) { 
				connection[i].push_back(temp - 1); 
				connection[temp - 1].push_back(i);
			}
			else break;
		}
	}
	while (!finish.empty()) {
		color[*finish.begin()].second = 0;
		int error = coloring(connection[*finish.begin()], 0, *finish.begin());
		if(error == -1) {
			cout << -1 << endl;
			return 0;
		}
	}
	for (auto i : color)cout << i.second;
}

#include<iostream>

#include<vector>

#include<map>

#include<set>

using namespace std;

vector<vector<int>>connection;

vector<pair<int, int>>color;

set<int>finish;

int coloring(vector<int> &singleConnection, int colorNow, int point) {

set<int>::iterator ptr;

ptr = finish.find(point);

finish.erase(ptr);

int colorTemp;

for (int i = 0; i < singleConnection.size(); i++) {

colorTemp = color[singleConnection[i]].second;

if (colorTemp == -1) {

color[singleConnection[i]].second = 1 - colorNow;

int error = coloring(connection[singleConnection[i]], 1 - colorNow, singleConnection[i]);

if (error == -1)return -1;

}

else if(colorNow == colorTemp) {

return -1;

}

return 0;

}

int main() {

int n, temp;

cin >> n;

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

vector<int>connectTemp;

connection.push_back(connectTemp);

}

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

color.push_back(make_pair(i, -1));

finish.insert(i);

while (1) {

cin >> temp;

if (temp != 0) {

connection[i].push_back(temp - 1);

connection[temp - 1].push_back(i);

}

else break;

}

while (!finish.empty()) {

color[*finish.begin()].second = 0;

int error = coloring(connection[*finish.begin()], 0, *finish.begin());

if(error == -1) {

cout << -1 << endl;

return 0;

}

for (auto i : color)cout << i.second;

}

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;

}

二重积分计算网站——懒人专用

https://www.osgeo.cn/app/sb140

https://www.wolframalpha.com/calculators/integral-calculator/

第二个网站相对来说更好用，应用范围更广，输入更加方便自然简洁。第一个网站更便捷，因为是国内网站访问速度更快。