MENU

水文 - 友好整数

• May 30, 2017 • Read: 24302 • Codes

上篇文章水成狗,这篇虽水,但至少比上篇要好上一些。

前几天,群里有个小朋友发了一道ACM题,好像自己很搞不定的样子,作为90后空巢老人,几年没碰 ACM题瞬间有点手痒,关键看上去还很简单有木有,装逼之心瞬起,所以本着沉迷游戏终于自拔后,我决定付出自己微薄的力量。

好啦,看题。

题目描述

在成功解决他的数学作业之后,熊孩子感到很无聊,于是他造了N个大整数。

在这N个整数中,他喜欢某些对整数,但不喜欢另一些。

熊孩子称他喜欢的那些对整数为友好整数(Pals)。 

两个整数被称为友好整数(Pals)当且仅当这两个数至少有一个数字相同(不一定在同一位置)。

请帮助熊孩子计算出在他的整数中有多少对友好整数(Pals)。

输入

输入包含多组测试用例。

每组数据第一行包含一个整数$N(1\leqslant N\leqslant 10^{6})$,表示熊孩子的整数个数。

接下来$N$行,每行一个整数$Ai(1\leqslant Ai\leqslant 10^{18})$,每个整数互不相同。

输出

每组数据输出一行,表示Pals的对数。

样例输入

3
4
20
44
4
32
51
123
282

样例输出

1
4

资源限制

时间限制: 1 Sec  

内存限制: 128 MB

好啦,题目就是这样,刚开始没怎么仔细看题,然后哼哧哼哧写了一会,样例输入啥的感觉没啥问题,但据小朋友说超时,后来他把测试用例拿给我我才发现。。尼玛。。果然符合那个破范围。。。整整25W行的数据

一般的方法果然是不行的啊,然后下午出门的时候想了一个方案,跟他说完以后,晚上洗完澡就顺便写了出来。

最初用的方法是直接双层for 循环遍历,对于测试数据小的时候没什么问题,测试数据一大,就特么崩溃了。所以,想来想去还是先把数字归类,毕竟在这个题目里,数字里面,或者说字符串里的数字有哪些是重要的,其他的诸如数字的排列、每种数字的个数等是不许要考虑的。

所以,对每一个数字,都把它当成字符串来看待,这样也就不用考虑18位数字用什么类型存够用的问题,因为根本就没有涉及到计算,然后,对于每一个数字,读入以后,对其进行去重和排序操作,然后将去重排序后的值作为 Key存储到一个 Map里,值就是 Key相同的数字的个数。

例如:

142312321

经过去重加排序后的结果为:

1234

这个数字即为 Key。

把所有数字处理完后,再像之前那样双层遍历,计算总的 Pals的数量。只是计算的方式会略有差别。

懒得说了看代码吧。。。

import java.util.*;

/**
 * Author     : Hran
 * Date       : 2017/5/27
 * Version    :
 * Description:
 */
public class Pals {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int totalNum = Integer.parseInt(scanner.nextLine());

        long start = System.currentTimeMillis();

        Map<String, Integer> sumTests = new HashMap<>(1024);
        String number;

        for (int i = 0; i < totalNum; i++) {
            StringBuilder sb = new StringBuilder();
            scanner.nextLine().chars().distinct().sorted().forEach(value -> sb.append((char) value));
            number = sb.toString();
            sumTests.put(number, sumTests.getOrDefault(number, 0) + 1);
        }

        long palsNum = 0;

        String[] keys = new String[sumTests.size()];
        sumTests.keySet().toArray(keys);
        int sumA, sumB;
        for (int i = 0; i < keys.length; i++) {
            sumA = sumTests.get(keys[i]);
            palsNum += sumA * (sumA - 1) / 2;
            for (int j = i + 1; j < keys.length; j++) {
                if (isPals(keys[i], keys[j])) {
                    sumB = sumTests.get(keys[j]);
                    palsNum += sumA * sumB;
                }
            }
        }
        System.out.println(palsNum);
        System.out.println("Time: " + (System.currentTimeMillis() - start) + "ms");
    }

    private static boolean isPals(String a, String b) {
        String gege;
        char[] didi;
        if (a.length() < b.length()) {
            gege = a;
            didi = b.toCharArray();
        } else {
            gege = b;
            didi = a.toCharArray();
        }
        for (char c : didi) {
            if (gege.contains(String.valueOf(c))) {
                return true;
            }
        }
        return false;
    }
}

大概就是这个样子,然后测试用例在这里:

友好整数测试数据

Last Modified: July 14, 2019
Archives QR Code Tip
QR Code for this page
Tipping QR Code
Leave a Comment

19 Comments
  1. 哈哈 哈哈

    大佬 群怎么加

  2. 大佬的配图可真用心,不会自己拍的吧

    1. @六号博客自己拍就算了。。都是找的图片。。

  3. 我是小朋友?( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃

    1. @WeiのBlog@(滑稽)

  4. 测试一下公式。。。
    $O(n*log(n))$

  5. 给每一个数字处理一下,加入map哈希一下就可以了,时间复杂度O(n*log(n))

    1. @千千大佬@(吐舌)

    2. @千千膜拜acm大佬哈哈@(笑眼)

    3. @千千好厉害@(乖)

    4. @WeiのBlog抓到你啦

    5. @友人C啊嘞,没有啦,蒟蒻一个

    6. @千千向你学习୧(๑•̀⌄•́๑)૭