AtCoder ABC 129 A&B&C&D AtCoder - 129
Ich habe es mehr als 50 Minuten in B geschmolzen und dabei fast geweint
E und F werden später in diesem Monat aktualisiert, um die Lösung zu sehen!
A - Airplane
Das Eingabebeispiel hat mich verwirrt, aber wenn Sie es normal lesen, können Sie sehen, dass Folgendes gefragt wird. .. ..
--Für die Zeit, die erforderlich ist, um A-B, B-C und C-A zu bewegen, finden Sie die kürzeste Zeit, die alle A-B-C umrunden können.
private void solveA() {
int p = nextInt();
int q = nextInt();
int r = nextInt();
out.println(Math.min(q + r, Math.min(p + q, p + r)));
}
B - Balance
Ich konnte nicht verstehen, warum Eingabebeispiel 2 so war, also habe ich es viel geschmolzen. .. .. Grund? Aus irgendeinem Grund sollten Sie sortieren, was Sie eingegeben haben! Weil ich dachte. Ich lasse eine Art im Kommentar für Selbstdisziplin aus. .. ..
Die Lösung ist wie folgt
Also habe ich in der eigentlichen Produktion kumulative Summen verwendet (ich konnte Eingabebeispiel 2 nicht verstehen und dachte, dass es keine vollständige Suche ist, oder?), Aber es war übertrieben. ..
private void solveB() {
int n = nextInt();
int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();
//Ich werde sortiert setzen... int[] wk = IntStream.range(0, n).map(i -> nextInt()).sorted().toArray();
int[] rui = new int[n];
//0-Führen Sie die kumulative Summe von N durch
rui[0] = wk[0];
for (int i = 1; i < rui.length; i++) {
rui[i] = rui[i - 1] + wk[i];
}
long res = Integer.MAX_VALUE / 10;
/*
*I bis n von 1, um tatsächlich den numerischen Wert des T-Kandidaten zu finden-Gehen Sie zu 1
*Gehen Sie nicht zum Anfang oder zum Ende, um sich in zwei Gruppen zu teilen
* (rui[n - 1] - rui[i]) -> i+Summe von 1 bis N.
* rui[i] ->Summe von 0 bis i
*/
for (int i = 1; i < n - 1; i++) {
res = Math.min(res, Math.abs((rui[n - 1] - rui[i]) - rui[i]));
}
out.println(res);
}
――Ich denke, Sie können in sum1 und sum2 schöner schreiben, aber ich habe es mir nicht ausgedacht.
private void solveB2() {
int n = nextInt();
int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();
long res = Integer.MAX_VALUE / 10;
for (int i = 1; i < n - 1; i++) {
int sum1 = 0;
int sum2 = 0;
for (int j = 0; j < n; j++) {
if (j <= i) {
sum1 += wk[j];
} else {
sum2 += wk[j];
}
}
res = Math.min(res, Math.abs(sum1 - sum2));
}
out.println(res);
}
C - Typical Stairs
―― Wie der Problemname schon sagt, ein wirklich typischer DP
Ich habe noch nicht alles beendet (ich kann das Highscore-Problem überhaupt nicht lösen!), Aber die folgenden Wettbewerbe sind nützlich.
AtCoder - Bildungs-DP-Wettbewerb / DP-Zusammenfassungswettbewerb AtCoder - Typical DP Contest drkens Artikel: Super Einführung in die dynamische Planung! Pädagogischer DP-Wettbewerb A bis E Problemerklärungen und ähnliche Probleme drkens Artikel: Erklärung und ähnliche Probleme von F bis J-Problemen im Bildungs-DP-Wettbewerb
private void solveC() {
int n = nextInt();
int m = nextInt();
Set<Integer> key = new HashSet<Integer>();
for (int i = 0; i < m; i++) {
key.add(nextInt());
}
long[] dp = new long[n + 1];
dp[0] = 1;
long CONST_MOD = (long) (Math.pow(10, 9) + 7);
for (int i = 0; i <= n; i++) {
if (key.contains(i)) {
continue;
}
if (i + 2 <= n) {
dp[i + 2] = dp[i + 2] % CONST_MOD + dp[i] % CONST_MOD;
}
if (i + 1 <= n) {
dp[i + 1] = dp[i + 1] % CONST_MOD + dp[i] % CONST_MOD;
}
}
out.println(dp[n] % CONST_MOD);
}
D - Lamp
――Ich denke, es war ein ziemlich typisches kumulatives Summenproblem.
Ich schreibe während des Kommentierens während des Wettbewerbs, daher denke ich, dass es langsam ist, Code zu schreiben
private void solveD2() {
int h = nextInt();
int w = nextInt();
char[][] wk = new char[h][w];
for (int i = 0; i < wk.length; i++) {
wk[i] = next().toCharArray();
}
int[][] rui1 = new int[h][w];
/*
*Erstellen Sie eine kumulative Summe für W.
*/
for (int i = 0; i < h; i++) {
int cnt = 0;
/*
*Das Eingabebeispiel 1 sieht wie folgt aus(Seite an Seite)
* 012012
* 123450
* 123401
* 010123
*/
for (int j = 0; j < w; j++) {
if (wk[i][j] == '.') {
cnt++;
} else {
cnt = 0;
}
rui1[i][j] = cnt;
}
/*
*Glätten Sie die gesammelten Ergebnisse(Seite an Seite)
* 012012
* 123450
* 123401
* 010123
*Zu
* 022022
* 555550
* 444401
* 010333
*Umstellung auf
*/
for (int j = w - 1; j > 0; j--) {
if (rui1[i][j - 1] != 0 && rui1[i][j] != 0) {
rui1[i][j - 1] = rui1[i][j];
}
}
}
int[][] rui2 = new int[h][w];
/*
*Erstellen Sie eine kumulative Summe für H.
*/
for (int j = 0; j < w; j++) {
int cnt = 0;
/*
*Das Eingabebeispiel 1 sieht wie folgt aus(Vertikal)
* 011011
* 122120
* 233201
* 040312
*/
for (int i = 0; i < h; i++) {
if (wk[i][j] == '.') {
cnt++;
} else {
cnt = 0;
}
rui2[i][j] = cnt;
}
/*
*Glätten Sie die gesammelten Ergebnisse(Vertikal)
* 011011
* 122120
* 233201
* 040312
*Zu
* 043021
* 243320
* 243302
* 040312
*Umstellung auf
*/
for (int i = h - 1; i > 0; i--) {
if (rui2[i - 1][j] != 0 && rui2[i][j] != 0) {
rui2[i - 1][j] = rui2[i][j];
}
}
}
/*
*Da es kumulativ ist, leck alles
*Der mittlere Teil, in dem sich oben, unten, links und rechts überlappen-1
*/
long res = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
long cnt = rui1[i][j] + rui2[i][j] - 1;
res = Math.max(res, cnt);
}
}
out.println(res);
}
Recommended Posts