SCU 4437 Carries (思维)

el/2024/7/17 3:46:52

题目地址:http://acm.scu.edu.cn/soj/problem.action?id=4437

Carries

frog has nn integers a1,a2,…,ana1,a2,…,an, and she wants to add them pairwise.

Unfortunately, frog is somehow afraid of carries (进位). She defines hardness h(x,y)h(x,y)for adding xx and yy the number of carries involved in the calculation. For example, h(1,9)=1,h(1,99)=2h(1,9)=1,h(1,99)=2.

Find the total hardness adding nn integers pairwise. In another word, find

∑1≤i<j≤nh(ai,aj)∑1≤i<j≤nh(ai,aj)

.

Input

The input consists of multiple tests. For each test:

The first line contains 11 integer nn (2≤n≤1052≤n≤105). The second line contains nnintegers a1,a2,…,ana1,a2,…,an. (0≤ai≤1090≤ai≤109).

Output

For each test, write 11 integer which denotes the total hardness.

Sample Input

    25 5100 1 2 3 4 5 6 7 8 9

Sample Output

    120

 首先就是一个转化,分别对10, 100,   ..... 1e9 取余, 然后按照余数排序,

两两之间相加如果大于当前的取余的数(10,1e9),就有进位

用二分搜索就可以过了

#include<bits/stdc++.h>
using namespace std;
using lon = long long;const int M = 1e5 + 5;
int a[M], b[M];int main()
{int n;while(cin >> n){for(int i = 0; i < n; i++)scanf("%d", a+i);lon ans = 0, num = 1;for(int i = 1; i <= 9; i++){num *= 10;for(int k = 0; k < n; k++)b[k] = a[k] % num;sort(b, b+n);for(int k = 0; k < n; k++){int id = lower_bound(b+k+1, b+n, num - b[k]) - b;ans += n - id;}}cout << ans << endl;}return 0;
}

 


http://www.ngui.cc/el/3419462.html

相关文章

SCU4438 Censor(字符串哈希)

http://acm.scu.edu.cn/soj/problem.action?id4438 Censor frog is now a editor to censor so-called sensitive words (敏感词). She has a long text pp. Her job is relatively simple -- just to find the first occurence of sensitive word ww and remove it. frog…

hdu 1166 敌兵布阵 ( 线段树)

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 151658 Accepted Submission(s): 62898 Problem Description C国的死对头A国这段时间正在进行军事演习&#xff0c;所以C国间谍头子Derek和他手下Ti…

NBUT 1723 有多少三元组 (思维)

https://ac.2333.moe/Problem/view.xhtml?id1723 有三个数组A&#xff0c;B&#xff0c;C&#xff0c;每个数组中有n个数&#xff0c;你可以从每个数组中找一个数&#xff0c;使得Ai<Bj<Ck ,(1<I,j,k<n)(1<n<100000,1<Ai,Bj,Ck<1000000)&#xff0c;…

NBUT 1746 可怕的班主任(思维)

https://vjudge.net/problem/2082745/origin 在学校里&#xff0c;一个班由n名学生组成。 在上午晨跑之前&#xff0c;同学们在班主任面前排成一条直线。 班主任对同学们的对齐方式不满意; 确实&#xff0c;同学们按照他们的学号顺序排列&#xff1a;1,2,3&#xff0c;......&…

NBUT 1749 论WC串的唯一性(思维)

https://ac.2333.moe/Problem/view.xhtml?id1749 wc 在爬塔时遇到了一串神秘字符&#xff0c;隐隐之中有一股力量从中透出 wc 很快发现了玄机&#xff0c;这个字符串中每一个含有“wc”的连续子序列都能为wc提供魔法值 找出字符串能为wc提供多少魔法值 注意如果某个连续子…

hud 5690 All X (快速幂 or 循环节)

https://vjudge.net/problem/387912/origin F(x,m)F(x,m) 代表一个全是由数字xx组成的mm位数字。请计算&#xff0c;以下式子是否成立&#xff1a; F(x,m) mod k ≡ cF(x,m) mod k ≡ c Input 第一行一个整数TT&#xff0c;表示TT组数据。 每组测试数据占一行&#xff0c;…

hdu 5694 BD String (递推)

http://acm.hdu.edu.cn/showproblem.php?pid5694 众所周知&#xff0c;度度熊喜欢的字符只有两个&#xff1a;B和D。 今天&#xff0c;它发明了一种用B和D组成字符串的规则&#xff1a; S(1)BS(1)B S(2)BBDS(2)BBD S(3)BBDBBDDS(3)BBDBBDD … S(n)S(n−1)Breverse(flip…

hdu 5695 Gym Class (拓扑排序)

https://vjudge.net/problem/387991/origin 众所周知&#xff0c;度度熊喜欢各类体育活动。 今天&#xff0c;它终于当上了梦寐以求的体育课老师。第一次课上&#xff0c;它发现一个有趣的事情。在上课之前&#xff0c;所有同学要排成一列&#xff0c; 假设最开始每个人有一个…

hud 5689 瞬间移动(组合数+逆元)

http://acm.hdu.edu.cn/showproblem.php?pid5698 有一个无限大的矩形&#xff0c;初始时你在左上角&#xff08;即第一行第一列&#xff09;&#xff0c;每次你都可以选择一个右下方格子&#xff0c;并瞬移过去&#xff08;如从下图中的红色格子能直接瞬移到蓝色格子&#xf…

多态中成员变量的使用

Dog 继承 Animal 类&#xff0c; 多态中成员变量没有重写。