Lösen mit Ruby, Perl und Java AtCoder ABC 128 C.

Einführung

• Verwenden Sie die Empfehlungen in AtCoder-Probleme *, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

AtCoder Beginner Contest 128 C - Switches Difficulty: 807

Das Thema ist diesmal etwas arithmetisch Ruby

ruby.rb

n, m = gets.split.map(&:to_i)
k = []
1.upto(m) do |i|
  s = "0" * n
  h = gets.split.map(&:to_i)
  h.shift
  h.each do |j|
    s[j - 1] = "1"
  end
  k[i] = s.to_i(2)
end
p = gets.split.map(&:to_i)
ans = 0
0.upto(2 ** n - 1) do |i|
  f = 1
  1.upto(m) do |j|
    if (i & k[j]).to_s(2).count("1") % 2 != p[j - 1]
      f = 0
      break;
    end
  end
  ans += f
end
puts ans

Wenn Sie beispielsweise 10 Schalter haben, bereiten Sie die Zeichenfolge "0000000000" vor und ersetzen Sie die gewünschte Schalterposition durch 1. => 0010011011 Vergleichen Sie die Zeichenfolge mit allen Bitkombinationen (** 2 bis zur n-ten Potenz **) und vergleichen Sie sie mit den Lichtverhältnissen.

bit.rb

k[i] = s.to_i(2)
 # =>Konvertieren Sie eine Zeichenfolge in eine Ganzzahl mit binärer Notation

if (i & k[j]).to_s(2).count("1") % 2 != p[j - 1]
 # =>Konvertiert eine Ganzzahl in eine binäre Notationszeichenfolge und zählt die Anzahl der Einsen

• C +++ verwendet builtin_popcount, um die Anzahl der Einsen zu ermitteln, während * Ruby * die count-Methode verwendet. Perl

perl.pl

use v5.18; # strict say state

chomp (my ($n, $m) = split / /, <STDIN>);
my @k;
for my $i (1..$m) {
  my $s = '0' x $n;
  chomp (my @in = split / /, <STDIN>);
  shift @in;
  for my $j (0..$#in) {
    substr($s, $in[$j]-1, 1) = 1;
  }
  $k[$i] = $s;
}
chomp (my @p = split / /, <STDIN>);
my $ans = 0;
for my $i (0..2**$n-1) {
  my $s = sprintf "%0".$n."b", $i;
  my $f = 1;
  for my $j (1..$m) {
    $f = 0 if ((grep {$_ == 1} split('', ($s & $k[$j]))) % 2 != $p[$j-1]);
    last if $f == 0;
  }
  $ans += $f;
}
say $ans;

and.pl

$f = 0 if ((grep {$_ == 1} split('', ($s & $k[$j]))) % 2 != $p[$j-1]);

In * Ruby * verursacht die Bitoperation der Zeichenfolge einen Fehler, in * Perl * kann das Produkt so genommen werden, wie es ist. Überprüfen Sie die Anzahl der Einsen mit grep.

** Nachtrag **

• Sorgfältig ausgewählt! 25 Standardbibliotheken, die zur Implementierung von Perl-Algorithmen verwendet werden können [Teil 1] * Sie können auch die vec-Funktion verwenden, um Bitoperationen auszuführen. Java

java.java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        int k[] = new int[m];
        for (int i = 0; i < m; i++) {
            StringBuilder s = new StringBuilder("0000000000".substring(0, n));
            int x = Integer.parseInt(sc.next());
            for (int j = 0; j < x; j++) {
                int y = Integer.parseInt(sc.next());
                s.replace(y - 1, y, "1");
            }
            k[i] = Integer.parseInt(s.toString(), 2);
        }
        int p[] = new int[m];
        for (int i = 0; i < m; i++) {
            p[i] = Integer.parseInt(sc.next());
        }
        sc.close();
        int ans = 0;
        for (int i = 0; i < Math.pow(2, n); i++) {
            int f = 1;
            for (int j = 0; j < m; j++) {
                String bin = Integer.toBinaryString(i & k[j]);
                int c = 0;
                for (int v = 0; v < bin.length(); v++) {
                    if (bin.substring(v, v + 1).equals("1")) {
                        c++;
                    }
                }
                if (c % 2 != p[j]) {
                    f = 0;
                    break;
                }
            }
            ans += f;
        }
        System.out.println(ans);
    }
}

Da es basierend auf der * Perl * -Quelle in * Java * umgeschrieben wurde, werden Bitoperationen mit Zeichenfolgen ausgeführt, aber Sie können natürlich auch mit Shift-Operationen antworten.

Zusammenfassung

• ABC 128 C gelöst
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Perl vertraut
• Machen Sie sich mit Java vertraut
• Wurde mit Bit-Arithmetik vertraut

Referenzierte Site

• [So führen Sie eine Basiskonvertierung in Java durch] (https://qiita.com/munieru_jp/items/6288988293958850bddd)*