首页 > 其他分享 >Weird Sum (二维图->拆分为x和y, 整体贡献转化为单个贡献)

Weird Sum (二维图->拆分为x和y, 整体贡献转化为单个贡献)

时间:2022-11-02 14:44:47浏览次数:60  
标签:int Sum long 贡献 二维 Weird ri

 

思路:

  • 二维图, 朴素做法:一个一个枚举
  • 优化: 发现规律, 将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

相关文章

  • 线上kafka消息堆积,consumer掉线,怎么办?
    线上kafka消息堆积,所有consumer全部掉线,到底怎么回事?最近处理了一次线上故障,具体故障表现就是kafka某个topic消息堆积,这个topic的相关consumer全部掉线。整体排查过程和......
  • 1分钟学会SUMIFS函数,从此山水永相逢 ,莫问兄长谁更强
    Hi,大家好,本专栏将会从零开始和大家用图文的方式,30天让你从不会到熟练使用函数,0基础开始学习Excel函数,让你喜欢上它!有兴趣的小伙伴可以持续关注我,或者在专栏进行查看学习,愿与......
  • 15. 3Sum
    Givenanarray S of n integers,arethereelements a, b, c in S suchthat a + b + c =0?Findalluniquetripletsinthearraywhichgivesthe......
  • SUMPRODUCT函数10倍提效,只需一步就可秒变大神
    Hi,大家好,本专栏将会从零开始和大家用图文的方式,让你从零基础学会VBA!有兴趣的小伙伴可以持续关注我,或者在专栏自我查看学习,愿与君携手共进!有的小伙伴们说很想了解一下SUMPROD......
  • array_sum/array_column(二维数组指定字段求和)
    二维数组指定字段求和<?php$arr=[["goods_id"=>37,"goods_name"=>"铁砂锅37","goods_weight"=>2,"goods_price"=>......
  • 1005.maximize-sum-of-array-after-k-negations K次取反后最大化数组和
    问题描述1005.K次取反后最大化的数组和解题思路贪心算法代码classSolution{staticboolcmp(inta,intb){returnabs(a)>abs(b);}public:intlar......
  • 在gitee上给别人的项目贡献自己的代码
    在网络上搜索自己感兴趣的项目时,在gitee上找到一个合心意的项目,想要直接下载ZIP,但是需要登录,于是注册了gitee的账号。研究项目的过程中,修改了一些bug以及完善了一些小功能,......
  • 【XSY3313】异或和(xorsum)(结论)
    先上一个结论。一个长度为\(n\)的\(01\)序列,其每个子序列的异或和的和为\([序列中包含1]2^{n-1}\)。证明:考虑若不存在\(1\),则显然。否则若存在\(1\),随便选一个......
  • 用sumif取代vlookup
    问题:将补贴表里的数据按姓名填入工资表中。 解题思路:这是一个典型的查找问题,可以使用VLookup函数。=VLOOKUP(B3,P:Q,2,)事实上,只要单位里不存在同名同姓,这题还可......
  • P4213 【模板】杜教筛(Sum)
    题目链接P4213【模板】杜教筛(Sum)题目描述给定一个正整数,求\[ans_1=\sum_{i=1}^n\varphi(i)\]\[ans_2=\sum_{i=1}^n\mu(i)\]输入格式本题单测试点内有多组数据。......