AtCoder ABC 126 A&B&C&D AtCoder - 126
A - Changing a Character
――Ich habe es früher so geschrieben, aber ist es schwierig zu lesen, wenn ich es noch einmal überprüfe? ?? ??
private void solveA() {
int n = nextInt();
int k = nextInt() - 1;
StringBuilder builder = new StringBuilder(next());
out.println(builder.replace(k, k + 1, builder.substring(k, k + 1).toLowerCase()).toString());
}
――Hmm. Nicht gut genug. .. ..
private void solveA() {
int n = nextInt();
int k = nextInt();
String[] wk = next().split("");
wk[k - 1] = wk[k - 1].toLowerCase();
String res = Arrays.stream(wk).collect(Collectors.joining(""));
out.println(res);
}
B - YYMM or MMYY
private void solveB() {
int wk = nextInt();
int front = wk / 100;
int back = wk % 100;
if ((0 < front && front <= 12) && (back <= 0 || back > 12)) {
out.println("MMYY");
} else if ((0 < back && back <= 12) && (front <= 0 || front > 12)) {
out.println("YYMM");
} else if ((0 < front && front <= 12) && (0 < back && back <= 12)) {
out.println("AMBIGUOUS");
} else {
out.println("NA");
}
}
C - Dice and Coin
--Big Decimal wird verwendet, da die Verarbeitung von Brüchen schwierig ist
Beispiel 1: Weil ich einen dreiseitigen Würfel würfle
Wenn 1 gewürfelt wird, muss die Münze viermal hintereinander angezeigt werden Wenn 1 erscheint: $ 1 x 2 x 2 x 2 x 2 = 16 $ Wahrscheinlichkeit: $ \ frac {1} {3} × (\ frac {1} {2}) ^ 4 $
Wenn 2 gewürfelt wird, muss die Münze dreimal hintereinander angezeigt werden Wenn 2 erscheint: $ 2 x 2 x 2 x 2 = 16 $ Wahrscheinlichkeit: $ \ frac {1} {3} × (\ frac {1} {2}) ^ 3 $
Wenn 3 gewürfelt wird, muss die Münze zweimal hintereinander angezeigt werden Wenn 3 erscheint: $ 3 x 2 x 2 = 12 $ Wahrscheinlichkeit: $ \ frac {1} {3} × (\ frac {1} {2}) ^ 2 $
Die Summe (wenn 1 herauskommt, wenn +2 herauskommt, wenn +3 herauskommt) ist wie folgt $ \frac{1}{3} × (\frac{1}{2})^4 + \frac{1}{3} × (\frac{1}{2})^3 +\frac{1}{3} × (\frac{1}{2})^2 = \frac{7}{48} $
Vereinfachen Sie die Formel, indem Sie sie einschließen ** (Da es schwierig ist, zum Zeitpunkt der Implementierung über die Verarbeitung von Brüchen nachzudenken, werde ich die Unterteilung am Ende bringen) ** $ ((\frac{1}{2})^4 + (\frac{1}{2})^3 + (\frac{1}{2})^2) × \frac{1}{3} = \frac{7}{48} $
private void solveC() {
int n = nextInt();
int k = nextInt();
BigDecimal res = new BigDecimal("0");
for (int i = 1; i <= n; i++) {
int pow = recursiveC(i, k);
/*
*Die Vorder- und Rückseite der Münze ist 1/2 so 0.5 zur n-ten Potenz
*0, wenn die Matrizenoberfläche i ist.5^pow
*/
BigDecimal powB = new BigDecimal("0.5").pow(pow);
//Hinzufügen
res = res.add(powB);
}
//Zum Schluss sofort durch die Matrizenseite teilen
out.println(res.divide(new BigDecimal(n), 11, RoundingMode.HALF_UP));
}
/**
*Gibt zurück, wie oft x 2 n überschreiten soll
* @param i
* @param n
* @return
*/
private int recursiveC(int i, int n) {
if (i >= n) {
return 0;
}
return recursiveC(i * 2, n) + 1;
}
AtCoder ABC 126 D - Selbst Beziehung (400 Punkte)
――Die oben genannte Referenzstelle von Herrn Kenchon verfügt über eine Lösungsmethode in der DFS. Ich habe darauf hingewiesen. ――Ich habe es selbst mit DFS gelöst, werde es aber nicht veröffentlichen, da Kenchons Website leichter zu verstehen ist. ――Es ist kein Round-Robin, aber eine Wurzel wird entsprechend der Gleichmäßigkeit der Entfernung von dort entschieden und gemalt (ich wusste es nicht, ohne die Erklärung zu sehen). »Kannst du vielleicht mit Dyxtra gehen? ?? ?? Lass es uns das nächste Mal versuchen.
private void solveD() {
int n = nextInt();
int[] u = new int[n - 1];
int[] v = new int[n - 1];
int[] w = new int[n - 1];
/*
*Erstellen Sie eine Karte mit Kanten
*/
Map<Integer, List<Edge>> wk = new TreeMap<Integer, List<Edge>>();
for (int i = 0; i < n - 1; i++) {
Edge e = null;
List<Edge> tmp = null;
u[i] = nextInt() - 1;
v[i] = nextInt() - 1;
w[i] = nextInt();
/*
*Die Kosten sind unnötig, außer für Gewinnchancen und Gewinnchancen. Deshalb habe ich sie geändert, musste sie aber nicht separat durchführen. .. ..
*/
int cost = w[i] % 2;
e = new Edge();
e.from = u[i];
e.to = v[i];
e.cost = cost;
tmp = wk.getOrDefault(e.from, new ArrayList<Edge>());
tmp.add(e);
wk.put(e.from, tmp);
e = new Edge();
e.from = v[i];
e.to = u[i];
e.cost = cost;
tmp = wk.getOrDefault(e.from, new ArrayList<Edge>());
tmp.add(e);
wk.put(e.from, tmp);
}
/*
*Warteschlange für BFS
*/
Deque<Edge> ek = new ArrayDeque<Edge>();
/*
*Auswahl der ersten Warteschlange, um den Baum zu erkunden
*Nicht alles ist in Ordnung, das Kind wählt einen
*N Eckpunkte und N Seiten-Da es nur einen gibt, gibt es immer einen, der diese Bedingung erfüllt.
* while()Nur in der ersten Warteschlange in der Liste werden nicht alle meine Ziele angezeigt.
*Nun, während()Ich habe das Gefühl, dass ich vor dem Betreten einfach alle Kanten an Position 0 in der Warteschlange platzieren sollte.
*/
for (List<Edge> edges : wk.values()) {
if (edges.size() == 1) {
ek.addLast(edges.get(0));
break;
}
}
// ek.addLast(wk.get(0).get(0));
int[] res = new int[n];
//Zum Speichern von Farben
res[0] = 0;
while (!ek.isEmpty()) {
Edge e = ek.removeLast();
/*
*Entscheiden Sie die Farbe zu malen durch die Gleichmäßigkeit der Kosten
*/
if (e.cost % 2 == 0) {
//Wenn es gerade ist, haben beide von und die gleiche Farbe
res[e.to] = res[e.from];
} else {
//Wenn es seltsam ist, müssen Sie in einer anderen Farbe als von malen
res[e.to] = 1 - res[e.from];
}
//Auf der Suche nach Kindern in
List<Edge> edges = wk.get(e.to);
for (Edge edge : edges) {
/*
*Um zu verhindern, dass Eltern und Kinder zirkulieren
*/
if (e.from == edge.to) {
continue;
}
/*
*Zur Warteschlange hinzufügen, da es sich um ein Suchziel handelt
*/
ek.addLast(edge);
}
}
for (int resN : res) {
out.println(resN);
}
}
/**
*Innere Klasse zur Darstellung von Kanten
*/
private static class Edge {
private int from;
private int to;
private int cost;
}
Recommended Posts