上篇文章水成狗,这篇虽水,但至少比上篇要好上一些。
前几天,群里有个小朋友发了一道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;
}
}
大概就是这个样子,然后测试用例在这里:
小朋友\#(喜极而泣)
有什么问题吗@(小乖)
给大佬跪一个
\#(喷血)一点都看不懂。
中文和英文我都懂,但是连在一起,我就不懂了...
QWQ
\#(阴暗)