首页 > 代码库 > HDU 4858 分块
HDU 4858 分块
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4858
题意：中文题面
思路：来自此博客
对每个点定义两个值：val，sum，val记录自己的特征值，sum记录周边所有点特征值的和。
现在我们把所有的节点分成两类，重点(度数>=sqrt(m))，轻点(度数sqrt(m))。
插入：
轻点更新自己的val，同时更新所有的邻点的sum值
重点更新自己的val,同时只更新相邻重点的sum值（所以重点不需要连边到轻点）
查询：
轻点：暴力周边的所有邻点的val值。
重点：直接输出自己的sum值。
性质：
与重点相邻的重点不超过sqrt(m)个。
与轻点相邻的所有点不超过sqrt(m)个。
#define _CRT_SECURE_NO_DEPRECATE#include<stdio.h> #include<string.h> #include<cstring>#include<algorithm> #include<queue> #include<math.h> #include<time.h>#include<vector>#include<iostream>using namespace std;typedef long long int LL;const int MAXN = 100000 + 10;struct Edges{ int u, v; Edges(int u = 0, int v = 0) :u(u), v(v){};};vector<Edges>edge;vector<int>G[MAXN];int val[MAXN],du[MAXN];LL sum[MAXN];int main(){//#ifdef kirito// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);//#endif// int start = clock(); int t, n, m, q; scanf("%d", &t); while (t--){ scanf("%d%d", &n, &m); edge.clear(); int block = (int)sqrt(m + 0.5); for (int i = 0; i <= n; i++){ G[i].clear(); val[i] = 0; du[i] = 0; sum[i] = 0; } for (int i = 1; i <= m; i++){ int u, v; scanf("%d%d", &u, &v); edge.push_back(Edges(u, v)); du[u]++; du[v]++; } for (int i = 0; i < edge.size(); i++){ int u = edge[i].u, v = edge[i].v; if (du[u] >= block&&du[v]>=block){ G[u].push_back(v); G[v].push_back(u); } if (du[u] < block){ G[u].push_back(v); } if (du[v] < block){ G[v].push_back(u); } } scanf("%d", &q); while (q--){ int type, pos, v; scanf("%d", &type); if (type){ LL cnt = 0; scanf("%d", &pos); if (du[pos] < block){ for (int i = 0; i < G[pos].size(); i++){ cnt += val[G[pos][i]]; } } else{ cnt = sum[pos]; } printf("%I64d\n", cnt); } else{ scanf("%d %d", &pos, &v); val[pos] += v; for (int i = 0; i < G[pos].size(); i++){ sum[G[pos][i]] += v; } } } }//#ifdef LOCAL_TIME// cout << "[Finished in " << clock() - start << " ms]" << endl;//#endif return 0;}
思路2：另一种方法。 可能由于数据弱，所以本题可以完全按照题意暴力。 不过暴力的复杂度是O(n^2)的。只是本题没卡该做法。
#define _CRT_SECURE_NO_DEPRECATE#include<stdio.h> #include<string.h> #include<cstring>#include<algorithm> #include<queue> #include<math.h> #include<time.h>#include<vector>#include<iostream>using namespace std;typedef long long int LL;const int MAXN = 100000 + 10;vector<int>G[MAXN];int val[MAXN];int main(){//#ifdef kirito// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);//#endif// int start = clock(); int t, n, m, q; scanf("%d", &t); while (t--){ scanf("%d%d", &n, &m); for (int i = 0; i <= n; i++){ G[i].clear(); val[i] = 0; } for (int i = 1; i <= m; i++){ int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } scanf("%d", &q); for (int i = 1; i <= q; i++){ int type, pos, v; scanf("%d", &type); if (type){ LL cnt = 0; scanf("%d", &pos); for (int k = 0; k < G[pos].size(); k++){ cnt += val[G[pos][k]]; } printf("%I64d\n", cnt); } else{ scanf("%d %d", &pos, &v); val[pos] += v; } } }//#ifdef LOCAL_TIME// cout << "[Finished in " << clock() - start << " ms]" << endl;//#endif return 0;}
HDU 4858 分块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。