社区讨论

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 条回复,欢迎继续交流。

正在加载回复...