思路:
- 二维图, 朴素做法:一个一个枚举
- 优化: 发现规律, 将x和 y分开看来计算 是没有影响的
- 单看 x , 颜色相同的点, 按照x从小到大的顺序排序, 来计算贡献的时候:
- 通用的 按照最小的单位看他对整体的贡献, 比如 x1---x2---x3--x4--x5l
- x2到x3的贡献就是 2*3*距离,如果有相同x的点,不影响结果
- y同理可得
#include <bits/stdc++.h> using namespace std; #define ri register int #define M 2000005 int n,m; int T; struct dian{ int pos; }; long long p[M]; vector <int> x[M]; vector <int> y[M]; int num[M]; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m; for(ri i=1;i<=n;i++) { for(ri j=1;j<=m;j++) { int a; cin>>a; x[a].push_back(j); y[a].push_back(i); } } long long ans=0; for(ri i=1;i<=100000;i++) { if(x[i].size()==0) continue; int cnt=0; for(ri j=0;j<x[i].size();j++) { int a=x[i][j]; p[++cnt]=a; } sort(p+1,p+1+cnt); if(cnt==1) continue; for(ri j=1;j<cnt;j++) { ans+=1ll*(p[j+1]-p[j])*(1ll*j*(1ll*cnt-j)); } cnt=0; for(ri j=0;j<y[i].size();j++) { int a=y[i][j]; p[++cnt]=a; } sort(p+1,p+1+cnt); if(cnt==1) continue; for(ri j=1;j<cnt;j++) { ans+=1ll*(p[j+1]-p[j])*(1ll*j*(1ll*cnt-j)); } } cout<<ans; return 0; }View Code
标签:int,Sum,long,贡献,二维,Weird,ri From: https://www.cnblogs.com/Lamboofhome/p/16850957.html