首页 > 其他分享 >C - Sigma Problem

C - Sigma Problem

时间:2024-05-12 10:53:13浏览次数:34  
标签:ai sum aj long 1e8 Problem Sigma 溢出

C - Sigma Problem

https://atcoder.jp/contests/abc353/tasks/abc353_c

 

思路

暴力TLE

观察 a1 a2 ... an 序列

计算目标是, 两两结合并并求 模

sum = sigma (ai + aj)%1e8

ai , aj <= 1e8

ai + aj 可能溢出,也可能不溢出

于是我们考虑, 统计所有溢出的个数。

 

对数组进行排序,

从左到右依次遍历, 对于每个元素x, lower_bound寻找其右边大1e8-x第一个元素位置,

计算得到 此为止到序列末尾 都是溢出的贡献, 进行累计。

 

最后定义不考虑溢出的总和

sum = sigma (ai + aj)

 

答案 = sum - 溢出总贡献 * 1e8

 

Code

https://atcoder.jp/contests/abc353/submissions/53397070

int n;

vector<long long> a;

const long long base = 1e8;


int main()
{
    cin >> n;
    a.resize(n);

    long long sum = 0;
    
    for(int i=0; i<n; i++){
        cin >> a[i];

        sum += a[i];
    }
    
    long long total = (n-1) * sum;

    sort(a.begin(), a.end());
    
    long long cnt = 0;
    for(int i=0; i<n; i++){
        long long complement = base - a[i];
        
        // Search for first element x such that complement ≤ x
        auto lower = lower_bound(a.begin()+i+1, a.end(), complement);
        if (lower == a.end()){
            continue;
        }
        
        int lower_index = lower - a.begin();
        int great_cnt = n - lower_index;

        cnt += great_cnt;
    }
    
    long long minus_num = cnt*base;
    long long ans = total - minus_num;
    
    cout << ans << endl;
    
    return 0;
}

 

标签:ai,sum,aj,long,1e8,Problem,Sigma,溢出
From: https://www.cnblogs.com/lightsong/p/18187572

相关文章

  • Week 9 Problems
    T1用等值演算、构造指派等方式判断公式的永真性(1)\[(\forallxP(x)\rightarrow\existxQ(x))\rightarrow\existx(P(x)\rightarrowQ(x))\](2)\[(\forallxP(x)\rightarrow\forallxQ(x))\rightarrow\forallx(P(x)\rightarrowQ(x))\]T2以下哪一步出现错误?......
  • Codeforces 954I Yet Another String Matching Problem
    考虑到这个答案怎么算。能发现相当于是对应的字符间相连边,那么一个连通块中的字符就要变成同一个字符。于是一个连通块的代价就是\(sz-1\)。所以令有\(x\)个连通块,最后的代价就是\(|\Sigma|-x\)。考虑到因为\(|\Sigma|=6\),而\(B_6=203\)(贝尔数,\(B_n\)意义为大......
  • 「主席树维护高精度」 CF464E The Classic Problem
    发现难点在于维护\(dis_u\)(起点\(s\)到\(u\)的最短路)。如果使用暴力高精度,复杂度会乘上一个\(len\)。考虑边权\(2^w\)的特殊性质,如果使用一个二进制串来维护\(dis\),那么加上边权\(2^w\)相当于将二进制下某一段\(1\)置为\(0\),然后再将一个\(0\)置为\(1\)。说白了......
  • 196. 删除重复的电子邮箱【Problem:Every derived table must have its own alias】
    SQL-Boy上线,最近在写SQL语句遇到了这样的问题。Problem:Everyderivedtablemusthaveitsownalias错误语句如下deletefromPersonwhereidnotin(selectidfrom(selectmin(id)asidfromPersongroupbyemail)......
  • P1480 A/B Problem
    P1480A/BProblem题目描述输入两个整数\(a,b\),输出它们的商。输入格式两行,第一行是被除数,第二行是除数。输出格式一行,商的整数部分。样例输入102输出5提示\(0\lea\le10^{5000}\),\(1\leb\le10^9\)。思路通过题目数据范围可以发现是高精度除以单精度的题目......
  • P1303 A*B Problem
    P1303A*BProblem题目给出两个非负整数,求它们的乘积。输入输入共两行,每行一个非负整数。输出输出一个非负整数表示乘积。样例输入12输出2提示每个非负整数不超过\(10^{2000}\)。思路根据题意,乘数的数据最大范围是\(10^{2000}\),需要使用高精度乘高精度的算......
  • CF1618G Trader Problem 题解
    CF1618GTraderProblem题解题目链接:CF|洛谷提供一个在线做法。分析1我们不妨把\(a\)和\(b\)合并为一个序列,称合并后的序列为\(c\),并将其不降序排序。把玩样例后不难发现:对于一个物品序列\(c_1,c_2,\cdots,c_l\),满足\(\foralli<l,c_{i+1}-c_i\lek\)(即任意......
  • 52 Things: Number 11: What are the DLP, CDH and DDH problems?
    52Things:Number11:WhataretheDLP,CDHandDDHproblems?52件事:数字11:DLP、CDH和DDH问题是什么? Thisisthelatestinaseriesofblogpoststoaddressthelistof'52ThingsEveryPhDStudentShouldKnowToDoCryptography':asetofquestion......
  • 52 Things: Number 10: What is the difference between the RSA and strong-RSA prob
    52Things:Number10:WhatisthedifferencebetweentheRSAandstrong-RSAproblem?52件事:数字10:RSA和强RSA问题有什么区别?Thisisthelatestinaseriesofblogpoststoaddressthelistof'52ThingsEveryPhDStudentShouldKnowToDoCryptography......
  • CF1748E Yet Another Array Counting Problem の Solution
    Link有些人还是啥都不会。看到题目应该能想到这是笛卡尔树的性质,因为每一对\((l,r)\)都满足最左端最大值位置相同,所以说明在笛卡尔树上,每一对点的lca相同,说明\(a\)和\(b\)序列的笛卡尔树相同。我们以下标为键,\(a_i\)为值建立大根笛卡尔树,现在题目就转换成在这个树上填......