社区讨论
Why TLE??
AT_abc282_e[ABC282E] Choose Two and Eat One参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lvhw8evc
- 此快照首次捕获于
- 2024/04/27 17:22 2 年前
- 此快照最后确认于
- 2024/05/04 16:35 2 年前
CPP
//思路原于题解QwQ
#include<bits/stdc++.h>
using namespace std;
long long n, MOD, a[502], res, f[502], ans, cnt;
struct Node{
long long x, y, z;
bool operator < (const Node b) {
return z > b.z;
}
};
vector<Node> v;
int qp(long long a, long long b) {
res = 1;
while(b) {
if(b & 1) (res *= a) %= MOD;
(a *= a) %= MOD, b >>= 1;
}
return res;
}
int find(long long x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void bubbleSort(vector<Node>& arr) {
int n = arr.size();
for(int i = 0; i < n - 1; ++i) {
for(int j = 0; j < n - i - 1; ++j) {
if(arr[j] < arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> MOD;
for(int i = 1; i <= n; ++i) cin >> a[i], f[i] = i;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
v.push_back({i, j, (qp(a[i], a[j]) + qp(a[j], a[i])) % MOD});
}
}
bubbleSort(v);
for(Node t : v)
if(find(t.x) != find(t.y)) {
f[find(t.x)] = find(t.y);
cnt++;
ans += t.z;
if(cnt == n - 1) {
cout << ans << endl;
break;
}
}
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...