AtCoder ABC 021 A&B&C AtCoder - 021 ** 201905/15 postscript ** Il existe une solution au problème A dans la section commentaires
――Si vous pouvez utiliser le même plusieurs fois, je pense que vous pouvez utiliser tous les 1. .. .. AC
private void solveA() {
int n = nextInt();
out.println(n);
IntStream.range(0, n).forEach(i -> out.println(1));
}
** PostScript 201905/15 ** Il y a un code dans une boucle propre dans la section commentaire
―― Est-ce que ça ressemble à ça sans simplification?
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;
}
}
}
}
}
}
――Si l'itinéraire remplit les conditions suivantes, au moins il n'y a pas de détour supplémentaire
Le commentaire est un vestige de la première pensée pour
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");
}
Je n'ai pas les moyens d'utiliser Stream, donc toutes les déclarations For ...
référence: Résumé des solutions au problème de l'itinéraire le plus court Histoire de DP Pour vous qui ne comprenez pas la méthode Dyxtra Concours de programmation Challenge Book P.87 ~ Signification et tri topologique du graphe non-circuit dirigé (DAG)
Bien qu'il soit écrit dans le commentaire du code sur la transition, il est extrait
--Utilisez la méthode Worshall Floyd
** 1: Calcul du coût minimum **
| point de départ\point final | Ville 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| Ville 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: Coût minimum et tri topologique du mouvement du point de départ au point final du côté saisi **
| point de départ\point final | Ville 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| Ville 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: Résumez le nombre de waypoints pour chaque coût (et par ordre de coût. TreeMap est utilisé pour le classement) du point de départ au point final en fonction du résultat du tri topologique **
| Coût | 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|---|
| Ville à traverser | 1 | 2,3 | 4 | 5,6 | 7 |
** 4: Calculé en DP (par ordre de coût) **
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;
}
/*
*Résultat du calcul de la méthode Worshall Floyd
* [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);
/*
*DAG de l'itinéraire le plus court
*Après avoir effectué un tri topologique
* [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;
}
}
/*
*Carte de la distance la plus courte
*Pointez un(a=0)Carte par distance de
* {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;
/*
*Faire pivoter le coût du mouvement du point a au point b
*/
for (List<Integer> towns : map.values()) {
for (Integer town : towns) {
for (int k = 0; k < n; k++) {
/*
*S'il est possible d'aller d'un point: de la ville au point: k (1 au dag)=）
* minStep[k]À minStep[town]Plus le nombre de coups de(Peut se déplacer au point k)
*/
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]);
}
}
}
}
Après avoir fait la ** carte de la distance la plus courte **, le dernier DP utilise la carte.
--Code correspondant
for (List<Integer> towns : map.values()) {
for (Integer town : towns) {
for (int k = 0; k < n; k++) {
/*
*S'il est possible d'aller d'un point: de la ville au point: k (1 au dag)=）
* minStep[k]À minStep[town]Plus le nombre de coups de(Peut se déplacer au point k)
*/
if (dag[town][k] == 1) {
minStep[k] = (minStep[k] + minStep[town]) % CONST_MOD;
}
}
}
}
Cependant, si vous regardez à l'intérieur de la carte basée sur l'exemple d'entrée 1 et l'exemple d'entrée 2, vous aurez l'impression que vous pouvez la réparer comme indiqué ci-dessous (réparer? Code). Après tout, si vous tournez dans toutes les villes, vous n'avez pas besoin de carte, non? Alors, pourquoi ne pas tout retourner depuis le début? ?? ?? Quand. En conclusion, des valeurs précises ne sortiront que si DP est effectué sur la base de Map.
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