我一直在尝试在 ACM Timus 上解决这个问题
http://acm.timus.ru/problem.aspx?space=1&num=1932
我的第一种方法是 O(n^2)，它肯定不够快，无法通过所有测试。下面的 O(n^2) 代码给出了测试 10 的 TL。
import java.util.*;
import java.io.*;
public class testtest
{
public static void main(String[] args) throws IOException
{
BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(rr.readLine());
String[] p = new String[n];
for (int i = 0; i < n; i ++)
{
p[i] = rr.readLine();
}
int[] diff = new int[]{0, 0, 0, 0};
for (int i = 0; i < n - 1; i ++)
{
for (int j = i + 1; j < n; j ++)
{
int ans = (p[i].charAt(0) == p[j].charAt(0) ? 0 : 1) +
(p[i].charAt(1) == p[j].charAt(1) ? 0 : 1) +
(p[i].charAt(2) == p[j].charAt(2) ? 0 : 1) +
(p[i].charAt(3) == p[j].charAt(3) ? 0 : 1);
diff[ans - 1] ++;
}
}
System.out.print(diff[0] + " " + diff[1] + " " + diff[2] + " " + diff[3]);
}
}
有什么想法可以使这种方法更快吗？我注意到输入中只允许一组有限的字符('0'..'9'，'a'..'f')所以我们可以创建数组(内存限制就足够了)来快速检查是否以前输入过字符。
谢谢......我不需要实际的实现，只是快速的想法/想法会很棒。 编辑:感谢您提出的好主意。我已经尝试使用位逻辑对 O(n^2) 进行改进，但仍然超出了时间限制。帕斯卡代码如下。
program Project2;
{$APPTYPE CONSOLE}
var
i, j, n, k, bits: integer;
arr: array[1..65536] of integer;
diff: array[1..4] of integer;
a, b, c, d: char;
function g(c: char): integer; inline;
begin
if ((c >= '0') and (c <= '9')) then
begin
Result := Ord(c) - 48;
end
else
begin
Result := Ord(c) - 87;
end;
end;
begin
Readln(n);
for i := 1 to n do
begin
Read(a); Read(b); Read(c); Readln(d);
arr[i] := g(a) * 16 * 16 * 16 + g(b) * 16 * 16 + g(c) * 16 + g(d);
for j := 1 to i - 1 do
begin
bits := arr[i] xor arr[j];
k := ((bits or (bits shr 1) or (bits shr 2) or (bits shr 3)) and $1111) mod 15;
Inc(diff[k]);
end;
end;
Write(diff[1], ' ', diff[2], ' ', diff[3], ' ', diff[4]);
{$IFNDEF ONLINE_JUDGE}
Readln;
{$ENDIF}
end.
所以我想，我必须尝试其他更好的建议..
编辑: 我试过 Daniel 的算法，它非常有前途，也许下面的代码有错误，它在测试 10 上不断得到错误的答案...有人可以看一下吗？非常感谢...
import java.util.*;
import java.io.*;
public class testtest
{
private static int g(char ch)
{
if ((ch >= '0') && (ch <= '9'))
{
return (int)ch - 48;
}
return (int)ch - 87;
}
public static void main(String[] args) throws IOException
{
BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(rr.readLine());
int[] p = new int[n];
int[] all = new int[65536];
int[][] miss = new int[4][4096];
int[] g12 = new int[256];
int[] g13 = new int[256];
int[] g14 = new int[256];
int[] g23 = new int[256];
int[] g24 = new int[256];
int[] g34 = new int[256];
int[][] gg = new int[4][16];
int same3, same2, same1, same0, same4;
for (int i = 0; i < n; i ++)
{
String s = rr.readLine();
int x = g(s.charAt(0)) * 4096 + g(s.charAt(1)) * 256 + g(s.charAt(2)) * 16 + g(s.charAt(3));
p[i] = x;
all[x] ++;
miss[0][x >> 4] ++;
miss[1][(x & 0x000F) | ((x & 0xFF00) >> 4)] ++;
miss[2][(x & 0x00FF) | ((x & 0xF000) >> 4)] ++;
miss[3][x & 0x0FFF] ++;
g12[x >> 8] ++;
g13[((x & 0x00F0) >> 4) | ((x & 0xF000) >> 8)] ++;
g14[(x & 0x000F) | ((x & 0xF000) >> 8)] ++;
g23[(x & 0x0FF0) >> 4] ++;
g24[(x & 0x000F) | ((x & 0x0F00) >> 4)] ++;
g34[x & 0x00FF] ++;
gg[0][x >> 12] ++;
gg[1][(x & 0xF00) >> 8] ++;
gg[2][(x & 0xF0) >> 4] ++;
gg[3][x & 0xF] ++;
}
same4 = 0;
for (int i = 0; i < 65536; i ++)
{
same4 += (all[i] - 1) * (all[i]) / 2;
}
same3 = 0;
for (int i = 0; i < 4096; i ++)
{
same3 += (miss[0][i] - 1) * (miss[0][i]) / 2;
same3 += (miss[1][i] - 1) * (miss[1][i]) / 2;
same3 += (miss[2][i] - 1) * (miss[2][i]) / 2;
same3 += (miss[3][i] - 1) * (miss[3][i]) / 2;
}
same2 = 0;
for (int i = 0; i < 256; i ++)
{
same2 += (g12[i] - 1) * g12[i] / 2;
same2 += (g13[i] - 1) * g13[i] / 2;
same2 += (g14[i] - 1) * g14[i] / 2;
same2 += (g23[i] - 1) * g23[i] / 2;
same2 += (g24[i] - 1) * g24[i] / 2;
same2 += (g34[i] - 1) * g34[i] / 2;
}
same1 = 0;
for (int i = 0; i < 16; i ++)
{
same1 += (gg[0][i] - 1) * gg[0][i] / 2;
same1 += (gg[1][i] - 1) * gg[1][i] / 2;
same1 += (gg[2][i] - 1) * gg[2][i] / 2;
same1 += (gg[3][i] - 1) * gg[3][i] / 2;
}
same3 -= 4 * same4;
same2 -= 6 * same4 + 3 * same3;
same1 -= 4 * same4 + 3 * same3 + 2 * same2;
same0 = (int)((long)(n * (n - 1) / 2) - same4 - same3 - same2 - same1);
System.out.print(same3 + " " + same2 + " " + same1 + " " + same0);
}
}
编辑 终于拿到了 AC...感谢 Daniel 提供了如此出色的算法!
最佳答案
对于较小的 n，检查每一对的强力 O(n²) 算法当然更快，所以人们会想找到一个好的截止点点切换算法。在不进行测量的情况下，出于粗略的考虑，我希望值在 200 到 3000 之间。
通过将海盗 ID 解析为十六进制数，将其转换为 int。将 ID 存储在
int[] pirates = new int[n];
首先，统计具有相同ID的海盗对的数量(这一步可以省略，因为问题陈述中没有)。
int[] allFour = new int[65536];
for(int i = 0; i < n; ++i) {
allFour[pirate[i]] += 1;
}
int fourIdentical = 0;
for(int i = 0; i < 65536; ++i) {
fourIdentical += allFour[i]*(allFour[i] - 1) / 2;
}
接下来，计算 ID 中具有三个相同半字节的海盗对，
int oneTwoThree(int p) {
return p >> 4;
}
int oneTwoFour(int p) {
return (p & 0x000F) | ((p & 0xFF00) >> 4);
}
int oneThreeFour(int p) {
return (p & 0x00FF) | ((p & 0xF000) >> 4);
}
int twoThreeFour(int p) {
return p & 0x0FFF;
}
int[] noFour = new int[4096];
int[] noThree = new int[4096];
int[] noTwo = new int[4096];
int[] noOne = new int[4096];
for(int i = 0; i < n; ++i) {
noFour[oneTwoThree(pirate[i])] += 1;
noThree[oneTwoFour(pirate[i])] += 1;
noTwo[oneThreeFour(pirate[i])] += 1;
noOne[twoThreeFour(pirate[i])] += 1;
}
int threeIdentical = 0;
for(int i = 0; i < 4096; ++i) {
threeIdentical += noFour[i]*(noFour[i]-1) / 2;
}
for(int i = 0; i < 4096; ++i) {
threeIdentical += noThree[i]*(noThree[i]-1) / 2;
}
for(int i = 0; i < 4096; ++i) {
threeIdentical += noTwo[i]*(noTwo[i]-1) / 2;
}
for(int i = 0; i < 4096; ++i) {
threeIdentical += noOne[i]*(noOne[i]-1) / 2;
}
但是，每对具有四个相同半字节的海盗在这里都被计算为 4 选择 3 = 4 次，对于三个半字节的每个可能选择，所以我们需要减去那个(好吧，不是为了问题，而是原则上):
threeIdentical -= 4*fourIdentical;
然后，计算 ID 中有两个相同半字节的海盗对:
int oneTwo(int p) {
return p >> 8;
}
int oneThree(int p) {
return ((p & 0x00F0) >> 4) | ((p & 0xF000) >> 8);
}
int oneFour(int p) {
return (p & 0x000F) | ((p & 0xF000) >> 8);
}
int twoThree(int p) {
return (p & 0x0FF0) >> 4;
}
int twoFour(int p) {
return (p & 0x000F) | ((p & 0x0F00) >> 4);
}
int threeFour(int p) {
return p & 0x00FF;
}
分配六个 256 个 int 数组，并在 a 和 b 位置计算相应半字节的海盗数量，例如
int twoIdentical = 0;
int[] firstTwo = new int[256];
for(int i = 0; i < n; ++i) {
firstTwo[oneTwo(pirate[i])] += 1;
}
for(int i = 0; i < 256; ++i) {
twoIdentical += firstTwo[i]*(firstTwo[i] - 1) / 2;
}
// analogous for the other five possible choices of two nibbles
但是，具有四个相同半字节的对已被计数 4 选择 2 = 6 次，具有三个相同半字节的对已被计数 3 选择 2 = 3 > 次，所以我们需要减去
twoIdentical -= 6*fourIdentical + 3*threeIdentical;
接下来，具有一个相同半字节的对数。我相信您能猜出需要什么四个函数和数组。然后我们将计算具有四个相同半字节的对 4 选择 1 = 4 次，具有三个相同半字节的对 3 选择 1 = 3 次，具有两个的对相同的半字节 2 选择 1 = 2 次，所以
oneIdentical -= 4*fourIdentical + 3*threeIdentical + 2*twoIdentical;
最后，没有相同半字节的对数是
int noneIdentical = (int)((long)n*(n-1) / 2) - oneIdentical - twoIdentical - threeIdentical - fourIdentical;
(转换为 long 以避免 n*(n-1) 溢出)。
关于java - O(n^2) 解决这个问题的速度不够快。任何更快的方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13435771/