P9661 [ICPC 2021 Macao R] Sandpile on Clique

题目描述

阿贝尔沙堆模型（Abelian Sandpile Model）是一个著名的显示自组织临界性的动力学系统。自从它由 Per Bak、Chao Tang 和 Kurt Wiesenfeld 在 1987 年的一篇论文中引入以来，它已经被研究了数十年。沙堆模型的预测引起了物理学、计算机科学和数学的广泛关注，这不仅是因为它美丽的代数结构，还因为它与负载平衡和内部扩散有关的模型的应用，如去随机化。沙堆模型与许多其他模型和物理现象相关，如转子路由模型、雪崩模型。

在沙堆模型中，给定一个顶点编号从 $1$ 到 $n$ 的无向图 $G$。我们还给出了 $n$ 个整数 $a_1,a_2,\cdots ,a_n$，其中 $a_i$ 表示初始时放置在顶点 $i$ 上的筹码数量。每个回合，我们将选择一个任意的顶点 $v$，使得 $v$ 上的筹码数量不小于与 $v$ 相连的边数，记为 $d_v$。对于 $v$ 的每个邻居，它将从 $v$ 接收一枚筹码。因此，$v$ 将失去 $d_v$ 枚筹码。这个过程被称为 firing 或 toppling。直到没有顶点 $v$ 至少有 $d_v$ 枚筹码时，firing 才会停止。

可以证明，firing 的顺序不会影响结果。同时，也可能 firing 永远不会终止。这种情况被描述为“recurrent”。现在给定一个团和初始筹码数量，请确定这个实例是否是一个 recurrent 实例。如果不是，请分别输出每个节点的最终筹码数量。

团（也称为完全图）是一个图，其中任意两个顶点都有边相连。

输入格式

每个测试文件中只有一个测试用例。

输入的第一行包含一个整数 $n$（$2\le n\le 5\times 10^5$），表示团的大小。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n$（$0\le a_i\le 10^9$），其中 $a_i$ 表示放置在顶点 $i$ 上的初始筹码数量。

输出格式

输出一行。如果给定的沙堆实例将终止，则输出由空格分隔的 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 个顶点上的最终筹码数量。否则输出 Recurrent（不包括引号）。

请不要在每行末尾输出额外的空格，否则您的解决方案可能被认为是错误的！

【样例解释】

对于第一个样例测试用例：

• 我们只能在开始时选择顶点 $1$。筹码数量变为 { 1 , 1 , 4 , 1 , 4 } \{1, 1, 4, 1, 4\} {1,1,4,1,4}。
• 现在我们可以选择顶点 $3$ 或 $5$，因为它们都至少有 $4$ 枚筹码。我们选择顶点 $3$，筹码数量变为 { 2 , 2 , 0 , 2 , 5 } \{2, 2, 0, 2, 5\} {2,2,0,2,5}。选择顶点 $5$ 会得到相同的结果。
• 现在我们选择顶点 $5$。筹码数量变为 { 3 , 3 , 1 , 3 , 1 } \{3, 3, 1, 3, 1\} {3,3,1,3,1}。没有顶点至少有 $4$ 枚筹码，因此 firing 终止。

对于第二个样例测试用例，我们可以重复选择顶点 $1$ 和 $2$。firing 永远不会终止。

翻译来自于：ChatGPT

输入输出样例 #1

输入 #1

5
5 0 3 0 3

输出 #1

3 3 1 3 1

输入输出样例 #2

输入 #2

2
1 0

输出 #2

Recurrent

C++实现

#include <iostream>
#include <cstdio>
const int N = 500005;
int a[N], qz[N];
bool vis[N];
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for(int i = 1; i <= n; ++i) {
		qz[0] += a[i] / n;
		int t = (a[i] / n + 1) * n - a[i];
		qz[t]++;
		vis[t - 1] = true;
	}
	int s = 0, v = -1;
	for(int i = 0; i < n; ++i) {
		s += qz[i];
		if(s == i && vis[i] == false) {
			v = i;
			break;
		}
	}
	if(v == -1)
		printf("Recurrent");
	else {
		for(int i = 1; i <= n; ++i)
			printf("%d ", (a[i] + v) % n);
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容