首页 ❯

O（n^2）在解决这个问题方面不够快。任何更快的方法？

string algorithm java
2022-09-03 07:01:41

我一直在尝试在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);
    }
}

编辑终于得到了空调...感谢丹尼尔这么棒的算法！


答案 1

当然，对于小的，检查每对的蛮力算法更快，所以人们希望为切换算法找到一个好的截止点。如果不进行测量，由于不均匀的包络式考虑，我预计值在200到3000之间。nO(n²)

通过将盗版 ID 解析为十六进制数字，将其转换为 。将 ID 存储在int

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 choose 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秒的数组，并计算海盗的数量，并在一些地方使用相应的小点子，例如intab

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 choose 2 = 63 choose 2 = 3

twoIdentical -= 6*fourIdentical + 3*threeIdentical;

接下来，具有一个相同小块的对数。我相信你可以猜到需要哪四个函数和数组。然后，我们将计算具有四个相同啃点时间的对，具有三个相同啃点时间的对，以及具有两个相同啃点时间的对，因此4 choose 1 = 43 choose 1 = 32 choose 1 = 2

oneIdentical -= 4*fourIdentical + 3*threeIdentical + 2*twoIdentical;

最后，没有相同啃咬的对数为

int noneIdentical = (int)((long)n*(n-1) / 2) - oneIdentical - twoIdentical - threeIdentical - fourIdentical;

（强制转换以避免溢出 ）。longn*(n-1)


答案 2

这可能是比较标识符对的快速方法。它假定两个标识符都已读入为十六进制数字而不是字符串。

int bits = p[i] ^ p[j];
int ans = ((bits | bits >> 1 | bits >> 2 | bits >> 3) & 0x1111) % 15;
diff[ans - 1]++;

推荐
更多 »
标签
更多 »
php pass-by-reference optional-parameters default-value javascript arrays dom function string object serialization tostring visibility syntax jslint use-strict operators equality equality-operator identity-operator datetime timestamp date-arithmetic redirect angularjs loops foreach iteration scope variables
推荐
更多 »