L1-111 大幂数

如果一个正整数可以表示为从 $1$ 开始的连续自然数的非 $0$ 幂次和，就称之为“大幂数”。例如 $2025$ 就是一个大幂数，因为

$2025 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + 6^3 + 7^3 + 8^3 + 9^3$

本题请你判断一个给定的数字 $n$ 是否是大幂数；如果是，就输出其幂次和。

另一方面，大幂数的幂次和表示可能不是唯一的，例如 $91$ 可以表示为

$91 = 1^1 + 2^1 + 3^1 + 4^1 + 5^1 + 6^1 + 7^1 + 8^1 + 9^1 + 10^1 + 11^1 + 12^1 + 13^1$

同时也可以表示为

$91 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2$

这时你只需要输出幂次最大的那个和即可。

输入格式

输入在一行中给出一个正整数 $n$ ，满足：

$2 < n < 2^{31}$

输出格式

如果 $n$ 是大幂数，则在一行中输出幂次最大的那个和，格式为：
1^k+2^k+...+m^k

其中 $k$ 是所有幂次和中最大的幂次。

如果解不存在，则在一行中输出：
Impossible for n.

其中 n 是输入的 $n$ 的值。

题面解读

一个正整数，分解成从1开始连续数字的幂次方之和，要求幂最大。

解题思路

先看最大长度，如果幂全部都是1的情况，n=1+2+…+m，等差数列求和m最大不超过 $\sqrt(n)$ 也就是 $2^{16}$ 。再看幂最大是多少，如果只有一个数的话，也就是n= $2^p$ 幂最大也就是31，保守点可以枚举到32。这样就可以通过暴力枚举来A这道题，最高次复杂度大约是32* $2^{16}$ 就可以做出来。

题解代码

#include <bits/stdc++.h>
using namespace std;

#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
typedef long long ls;
typedef unsigned long long uls;
//const int N = 1010;
const int mx = 1LL<<16;

uls n;
uls a[mx + 10];

bool isprime(uls x){
	if (x < 2) return false;
	if (x == 2) return true;
	if (x % 2 == 0) return false;
	for (uls i = 3; i * i <= x; i += 2)
		if (x % i == 0)
			return false;
	return true;
}

void sol(){
	cin >> n;
	for (int i = 1; i <= mx; i++)
		a[i] = i;
	int cnt = 0;
	int max_ed = -1, max_p = -1;
	for (int i = 1; i <= 32; i++){
		cnt++;
		uls sum = 0;
		for (int i = 1; i <= mx; i++){
			sum += a[i];
			a[i] *= i;
			if (sum == n){
				max_ed = i, max_p = cnt;
				break;
			}
			if (sum > n)
				break;
		}
	}
	if (max_ed == -1)
		cout << "Impossible for " << n << '.' << endl;
	else{
		for (int i = 1; i <= max_ed; i++){
			cout << i << "^" << max_p;
			if (i < max_ed)
				cout << "+";
		}
		cout << endl;
	}
}

int main(){
	IO
	sol();
	return 0;
}

L1-112 现代战争

在最新的《命运召唤：现代战争》中，你要扮演 B 国的一名战斗机飞行员，前往轰炸 A 国的高价值建筑。A 国的建筑群可视为一个由 $n \times m$ 个小方格组成的地图，每个小方格中有一幢建筑，并且你已经知道了所有建筑的价值。作为一名优秀的战斗机飞行员，你打算实施如下轰炸方式：每次选择当前所有还存在的建筑里价值最高的一幢投下炸弹，这个炸弹会将该建筑所在的一整行和一整列都炸平。随后系统将行列中被炸平的建筑移除，剩下的地块合并成一个 $(n-1) \times (m-1)$ 的新地图。例如对原始地图

$\begin{matrix} 1 & 2 & 3 \\ 7 & 9 & 8 \\ 6 & 5 & 4 \end{matrix}$

进行一次轰炸后，更新后的地图为

$\begin{matrix} 1 & 3 \\ 6 & 4 \end{matrix}$

请你编写程序，输出你轰炸了 $k$ 幢建筑后的地图。注意：游戏纯属虚构，如有雷同纯属巧合。

输入格式

输入第一行给出三个正整数 $n$ 、 $m$ 和 $k$ （ $2 \le n, m \le 1000$ ，且 $k < \min\{n,m\}$ ），依次对应地图中建筑的行数、列数，以及轰炸步数。随后 $n$ 行，每行 $m$ 个整数，为地图中对应建筑的价值。题目保证所有元素在 $[-2^{30}, 2^{30}]$ 区间内，且互不相等。同一行数字间以空格分隔。

输出格式

输出轰炸 $k$ 幢建筑后的地图。同一行数字间以 1 个空格分隔，行首尾不得有多余空格。

题面解读

一个方阵，每次删掉最大值所在的行和列，输出方阵。

解题思路

用tuple存储这个方阵，按照值从大到小排序，再用bool数组来标记哪些行和列被删除了，最后输出没有被标记过的点。

题解代码

#include <bits/stdc++.h>
using namespace std;

#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
typedef long long ls;
typedef unsigned long long uls;
const int N = 1010;

int n, m, k, x;
int a[N][N];
vector<tuple<int, int, int> > v;
bool row[N], col[N];

void sol(){
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			cin >> x;
			a[i][j] = x;
			v.push_back({x, i, j});
		}
	sort(v.begin(), v.end(), greater<>());
	int ed = m, cnt = 0;
	for (int i = 0; i < (int)v.size(); i++){
		auto [x, j, t] = v[i];
		if (row[j] || col[t])
			continue;
		row[j] = col[t] = true;
		ed--;
		if (++cnt == k)
			break;
	}
	for (int i = 1; i <= n; i++){
		int c = 0;
		for (int j = 1; j <= m; j++)
			if (!row[i] && !col[j]){
				cout << a[i][j]; 
				if (++c < ed)
					cout << ' ';
				else
					cout << endl;
			}
	}
}

int main(){
	IO
	sol();
	return 0;
}

L2-001 紧急救援

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往出事地点，同时一路上召集尽可能多的救援队。

输入格式

输入第一行给出 4 个正整数 $N$ 、 $M$ 、 $S$ 、 $D$ ，其中 $N$ （ $2 \le N \le 500$ ）是城市的个数，顺便假设城市的编号为 $0\sim(N-1)$ ； $M$ 是快速道路的条数； $S$ 是出发地的城市编号； $D$ 是目的地的城市编号。

第二行给出 $N$ 个正整数，其中第 $i$ 个数是第 $i$ 个城市的救援队的数量，数字间以空格分隔。随后的 $M$ 行中，每行给出一条快速道路的信息，分别是：城市 1、城市 2、快速道路的长度，中间用空格分开，数字均为整数且不超过 500。输入保证救援可行且最优解唯一。

输出格式

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从 $S$ 到 $D$ 的路径中经过的城市编号，数字间以空格分隔，输出结尾不能有多余空格。

题面解读

给你一个图，找到一条路径，要求距离最短且路径上节点的权值和最大，最后输出这条路径。

解题思路

dijkstra求最短距离基础上维护三个数组：记录之前节点、权值最大、最短路个数。

题解代码

#include <bits/stdc++.h>
using namespace std;

#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
typedef long long ls;
#define PII pair<int, int> 

const int N = 510;
const int inf = 0x3f3f3f3f;

int n, m, s, d;
vector<pair<int, int> > h[N];
vector<int> path;
priority_queue<PII, vector<PII>, greater<PII> >q;
int a[N], dist[N], cnt[N], sum[N], pre[N];
bool vis[N];

void dijkstra(){
	memset(dist, 0x3f, sizeof dist);
	memset(pre, -1, sizeof pre);
	dist[s] = 0;
	cnt[s] = 1;
	sum[s] = a[s];
	q.push({0, s}); 
	while (!q.empty()){
		auto t = q.top();
		int p = t.second;
		q.pop();
		if (vis[p] == true)
			continue;
		vis[p] = true;
		for (auto [u, v] : h[p])
			if (dist[u] > dist[p] + v){
				dist[u] = dist[p] + v;
				cnt[u] = cnt[p];
				sum[u] = sum[p] + a[u];
				pre[u] = p;
				q.push({dist[u], u});	
			}
			else if (dist[u] == dist[p] + v){
				cnt[u] += cnt[p];
				if (sum[u] < sum[p] + a[u]){
					sum[u] = sum[p] + a[u];
					pre[u] = p;
				}
			}
	}
}

void get_path(int x){
	if (x == -1)
		return;
	get_path(pre[x]);
	path.push_back(x);
}

void sol(){
	cin >> n >> m >> s >> d;
	s++, d++;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	while (m--){
		int x, y, z; cin >> x >> y >> z;
		h[x + 1].push_back({y + 1, z});
		h[y + 1].push_back({x + 1, z});
	}
	dijkstra();
	get_path(d);
	cout << cnt[d] << ' ' << sum[d] << endl;
	for (auto it = path.begin(); it != path.end(); it++){
		cout << *it - 1;
		if (next(it) != path.end()) 
			cout << ' ';
	}
}

int main(){
	IO
	sol();
}