AtCoder ABC 021 A&B&C AtCoder - 021 ** 201905/15 postscript ** Im Kommentarbereich finden Sie eine Lösung für Problem A.
――Wenn Sie dasselbe mehrmals verwenden können, können Sie wahrscheinlich alle 1 verwenden. .. .. AC
private void solveA() {
int n = nextInt();
out.println(n);
IntStream.range(0, n).forEach(i -> out.println(1));
}
** 201905/15 Nachtrag ** Im Kommentarbereich befindet sich ein Code in einer sauberen Schleife
――Sieht es ohne Vereinfachung so aus?
private void solveA2() {
int n = nextInt();
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++) {
for (int l = 0; l <= n; l++) {
if (i * 1 + j * 2 + k * 4 + l * 8 == n) {
out.println(i + j + k + l);
for (int l2 = 0; l2 < i; l2++) {
out.println(1);
}
for (int j2 = 0; j2 < j; j2++) {
out.println(2);
}
for (int k2 = 0; k2 < k; k2++) {
out.println(4);
}
for (int l2 = 0; l2 < l; l2++) {
out.println(8);
}
return;
}
}
}
}
}
}
――Wenn die Route die folgenden Bedingungen erfüllt, gibt es zumindest keinen zusätzlichen Umweg
Auskommentieren ist ein Überbleibsel des ersten Gedankens
private void solveB() {
int n = nextInt();
int a = nextInt();
int b = nextInt();
int k = nextInt();
int[] wk = IntStream.range(0, k).map(i -> nextInt()).toArray();
Map<Integer, Long> tmp = Arrays.stream(wk).mapToObj(i -> new Integer(i))
.collect(Collectors.groupingBy(s -> s, Collectors.counting()));
boolean res = tmp.entrySet().stream()
.allMatch(entry -> !entry.getKey().equals(a) && !entry.getKey().equals(b) && entry.getValue() < 2);
out.println(res ? "YES" : "NO");
// for (Entry<Integer, Long> entry : tmp.entrySet()) {
// if (entry.getKey().equals(a) || entry.getKey().equals(b) || entry.getValue() > 1) {
// out.println("NO");
// return;
// }
// }
// out.println("YES");
}
Ich kann es mir nicht leisten, Stream zu verwenden, also alle For-Anweisungen ...
Referenz: Zusammenfassung der Lösungen für das Problem der kürzesten Route DP-Geschichte Für Sie, die die Dyxtra-Methode nicht verstanden haben Programmierwettbewerb Challenge Book S.87 ~ Bedeutung und topologische Sortierung des gerichteten Nicht-Schaltungsgraphen (DAG)
Obwohl es im Kommentar des Codes über den Übergang geschrieben ist, wird es extrahiert
** 1: Berechnung der Mindestkosten **
| Startpunkt\Endpunkt | Stadt 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| Stadt 1 | 0 | 1 | 1 | 2 | 3 | 3 | 4 | |
| 2 | 1 | 0 | 2 | 1 | 2 | 2 | 3 | |
| 3 | 1 | 2 | 0 | 1 | 2 | 2 | 3 | |
| 4 | 2 | 1 | 1 | 0 | 1 | 1 | 2 | |
| 5 | 3 | 2 | 2 | 1 | 0 | 2 | 1 | |
| 6 | 3 | 2 | 2 | 1 | 2 | 0 | 1 | |
| 7 | 4 | 3 | 3 | 2 | 1 | 1 | 0 |
** 2: Mindestkosten und topologische Art der Bewegung vom Startpunkt zum Endpunkt von der eingegebenen Seite **
| Startpunkt\Endpunkt | Stadt 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| Stadt 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | |
| 2 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
| 3 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
** 3: Fassen Sie basierend auf dem Ergebnis der topologischen Sortierung zusammen, wie viele Wegpunkte es für jede Kosten gibt (und in der Reihenfolge der Kosten. TreeMap wird für die Bestellung verwendet) vom Startpunkt bis zum Endpunkt. **
| Kosten | 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|---|
| Stadt durchzugehen | 1 | 2,3 | 4 | 5,6 | 7 |
** 4: Berechnet in DP (in der Reihenfolge der Kosten) **
private void solveC() {
int n = nextInt();
int a = nextInt() - 1;
int b = nextInt() - 1;
int m = nextInt();
final int CONST_INF = 999999999;
int[][] graph = new int[n][n];
for (int i = 0; i < graph.length; i++) {
Arrays.fill(graph[i], CONST_INF);
graph[i][i] = 0;
}
Edge[] edge = new Edge[m];
for (int j = 0; j < m; j++) {
int from = nextInt() - 1;
int to = nextInt() - 1;
graph[from][to] = 1;
graph[to][from] = 1;
Edge wkEdge = new Edge();
if (from > to) {
wkEdge.from = to;
wkEdge.to = from;
wkEdge.cost = 1;
} else {
wkEdge.from = from;
wkEdge.to = to;
wkEdge.cost = 1;
}
edge[j] = wkEdge;
}
/*
*Berechnungsergebnis der Worshall Floyd-Methode
* [0, 1, 1, 2, 3, 3, 4]
* [1, 0, 2, 1, 2, 2, 3]
* [1, 2, 0, 1, 2, 2, 3]
* [2, 1, 1, 0, 1, 1, 2]
* [3, 2, 2, 1, 0, 2, 1]
* [3, 2, 2, 1, 2, 0, 1]
* [4, 3, 3, 2, 1, 1, 0]
*/
getMinByWarshall(graph, n);
/*
*Kürzeste Route DAG
*Nach der topologischen Sortierung
* [0, 1, 1, 0, 0, 0, 0]
* [0, 0, 0, 1, 0, 0, 0]
* [0, 0, 0, 1, 0, 0, 0]
* [0, 0, 0, 0, 1, 1, 0]
* [0, 0, 0, 0, 0, 0, 1]
* [0, 0, 0, 0, 0, 0, 1]
* [0, 0, 0, 0, 0, 0, 0]
*/
int[][] dag = new int[n][n];
for (int i = 0; i < m; i++) {
int x = edge[i].from;
int y = edge[i].to;
if (graph[a][x] == graph[a][y] + 1) {
dag[y][x] = 1;
}
if (graph[a][x] == graph[a][y] - 1) {
dag[x][y] = 1;
}
}
/*
*Karte der kürzesten Entfernung
*Punkt a(a=0)Karte nach Entfernung von
* {0=[0], 1=[1, 2], 2=[3], 3=[4, 5], 4=[6]}
*/
Map<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>();
for (int i = 0; i < n; i++) {
int d = graph[a][i];
if (map.containsKey(d)) {
List<Integer> list = map.get(d);
list.add(i);
map.put(d, list);
} else {
List<Integer> list = new ArrayList<Integer>();
list.add(i);
map.put(d, list);
}
}
long CONST_MOD = (long) Math.pow(10, 9) + 7;
long[] minStep = new long[n];
minStep[a] = 1;
/*
*Drehen Sie die Bewegungskosten von Punkt a nach Punkt b
*/
for (List<Integer> towns : map.values()) {
for (Integer town : towns) {
for (int k = 0; k < n; k++) {
/*
*Wenn es möglich ist, von Punkt: Stadt zu Punkt zu gehen: k (1 am Tag)=）
* minStep[k]Zu minStep[town]Plus die Anzahl der Züge von(Kann sich zu Punkt k bewegen)
*/
if (dag[town][k] == 1) {
minStep[k] = (minStep[k] + minStep[town]) % CONST_MOD;
}
}
}
}
System.out.println(minStep[b]);
}
private static class Edge {
private int from;
private int to;
private int cost;
}
private void getMinByWarshall(int[][] edge, int vertex) {
for (int k = 0; k < vertex; k++) {
for (int i = 0; i < vertex; i++) {
for (int j = 0; j < vertex; j++) {
edge[i][j] = Integer.min(edge[i][j], edge[i][k] + edge[k][j]);
}
}
}
}
Nach dem Erstellen der ** Karte mit der kürzesten Entfernung ** verwendet der letzte DP die Karte.
for (List<Integer> towns : map.values()) {
for (Integer town : towns) {
for (int k = 0; k < n; k++) {
/*
*Wenn es möglich ist, von Punkt: Stadt zu Punkt zu gehen: k (1 am Tag)=）
* minStep[k]Zu minStep[town]Plus die Anzahl der Züge von(Kann sich zu Punkt k bewegen)
*/
if (dag[town][k] == 1) {
minStep[k] = (minStep[k] + minStep[town]) % CONST_MOD;
}
}
}
}
Wenn ich jedoch in die Karte schaue, die auf Eingabebeispiel 1 und Eingabebeispiel 2 basiert, habe ich das Gefühl, dass sie wie unten gezeigt repariert werden kann (Reparatur? Code). Wenn Sie sich in allen Städten drehen, brauchen Sie doch keine Karte, oder? Warum also nicht alles von Anfang an drehen? ?? ?? Wann. Zusammenfassend lässt sich sagen, dass genaue Werte nur dann ausgegeben werden, wenn die DP auf der Grundlage der Karte erfolgt.
7
4 7
7
1 5
1 6
6 7
1 2
2 3
3 4
1 7
for (int town = 0; town < n; town++) {
for (int k = 0; k < n; k++) {
if (dag[town][k] == 1) {
minStep[k] = (minStep[k] + minStep[town]) % CONST_MOD;
}
}
}
Recommended Posts