菜单

水文 - 友好整数

June 16, 2018 • Read: 116 • 教程

博客最近在备案,文章不定期删除,等待备案结束将会转移数据!

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

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

好啦,看题。

题目描述

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

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

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

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

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

输入

输入包含多组测试用例。

每组数据第一行包含一个整数 N(1⩽N⩽106),表示熊孩子的整数个数。

接下来 N 行,每行一个整数 Ai(1⩽Ai⩽1018),每个整数互不相同。

输出

每组数据输出一行,表示 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;
    }
}


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

友好整数测试数据




Tags: None
Archives Tip
QR Code for this page
Tipping QR Code
发表新观点

已有 1 条评论
  1. 你好 你好

    @(太开心)