当前位置: 萬仟网 > IT编程>软件设计>面向对象 > 数据结构算法求边权和【数学 | 模拟】

数据结构算法求边权和【数学 | 模拟】

2020年10月12日  | 萬仟网IT编程  | 我要评论
题目链接题目描述:初始给出一个 n 个点顺次连接而成的环,点有点权,边权是两个端点的点权乘积。现在给出一些特殊点,这些特殊点是向其他所有点都有连边,如果连边时发现两点之间已经有边,不会再次连接(即图中不会有重边)。求图中边权和。做法1(模拟):首先我们先将这个环边的权值累加到答案中,然后求特殊点产生的权值和,我们令sum等于所有点的权值和,对于第一个特殊点 x,它的贡献为a[x] * sum - (a[x] - 相邻点的权值),因为不会有重边,也就是说每个边只能产生一次贡献,此时 x 连的边都已经

题目链接

题目描述:

初始给出一个 n 个点顺次连接而成的环,点有点权,边权是两个端点的点权乘积。现在给出一些特殊点,这些特殊点是向其他所有点都有连边,如果连边时发现两点之间已经有边,不会再次连接(即图中不会有重边)。求图中边权和。


做法1(模拟):

首先我们先将这个环边的权值累加到答案中,然后求特殊点产生的权值和,我们令sum等于所有点的权值和,对于第一个特殊点 x,它的贡献为a[x] * sum - (a[x] - 相邻点的权值),因为不会有重边,也就是说每个边只能产生一次贡献,此时 x 连的边都已经贡献完了,所以此时将 x 从 sum 中减去,并用done数据进行标记,所以在前面说的减去“相邻点的权值”时,要先看他它是不是已经被标记了,若被标记就不用再减了。


做法2(数学):

a,b,c三个数互相相乘一次转换为多项式,2ab + 2ac + 2bc = (a + b + c) * (a + b + c) - (a * a + b * b + c * c),多个数类似,所以互相乘一次的结果为右式除以2。
所以先假设所有点都是特殊点,然后求出总的边权和,然后减去非特殊点为被假设为特殊点时的总的边权和,此时可能环上的边被减去了,所以最后要加回来。


做法1 AC Codes:

#include <iostream> #include <vector> #include <queue> #include <stack> #include <set> #include <map> //#include <unordered_set> //#include <unordered_map> #include <deque> #include <list> #include <iomanip> #include <algorithm> #include <fstream> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> //#pragma GCC optimize(2) using namespace std; typedef long long ll; //cout << fixed << setprecision(2); //cout << setw(2); const int N = 2e5 + 6, M = 1e9 + 7, INF = 0x3f3f3f3f; int main() { //freopen("/Users/xumingfei/Desktop/ACM/test.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n; cin >> n; vector<int> a(n), b(n), done(n); ll sum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; } ll ans = 0; for (int i = 0; i < n; i++) { ans += a[i] * a[(i + 1) % n]; } for (int i = 0; i < n; i++) { cin >> b[i]; if (b[i]) { ll now = sum - a[i]; if (!done[(i + 1) % n]) now -= a[(i + 1) % n]; if (!done[(i - 1 + n) % n]) now -= a[(i -1 + n) % n]; ans += a[i] * now; sum -= a[i]; done[i] = 1; } } cout << ans << '\n'; return 0; } 

做法2 AC Codes:

 #include <iostream> #include <vector> #include <queue> #include <stack> #include <set> #include <map> //#include <unordered_set> //#include <unordered_map> #include <deque> #include <list> #include <iomanip> #include <algorithm> #include <fstream> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> //#pragma GCC optimize(2) using namespace std; typedef long long ll; //cout << fixed << setprecision(2); //cout << setw(2); const int N = 2e5 + 6, M = 1e9 + 7, INF = 0x3f3f3f3f; int main() { //freopen("/Users/xumingfei/Desktop/ACM/test.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n; cin >> n; ll all = 0; vector<int> a(n), b(n); for (int i = 0; i < n; i++) { cin >> a[i]; all += a[i]; } ll ans = 0, sum = 0; for (int i = 0; i < n; i++) { cin >> b[i]; if (b[i]) { sum += a[i]; ans -= a[i] * a[i]; } } ans += sum * sum; ans /= 2; for (int i = 0; i < n; i++) { ans += a[i] * a[(i + 1) % n]; if (b[i]) ans += (all - sum) * a[i]; if (b[i] || (!b[i] && b[(i + 1) % n])) ans -= a[i] * a[(i + 1) % n]; } cout << ans << '\n'; return 0; } 

本文地址:https://blog.csdn.net/weixin_44258590/article/details/109031063

如您对本文有疑问或者有任何想说的,请点击进行留言回复,万千网友为您解惑!

相关文章:

验证码:
Copyright © 2017-2020  萬仟网 保留所有权利. 粤ICP备17035492号