AtCoder ABC 129 A&B&C&D AtCoder - 129
Je l'ai fait fondre en B pendant plus de 50 minutes et j'ai presque pleuré en chemin
E et F seront mis à jour plus tard ce mois-ci pour voir la solution!
A - Airplane
J'ai été confus par l'exemple d'entrée, mais si vous le lisez normalement, vous pouvez voir que ce qui suit est demandé. .. ..
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
Je ne pouvais pas comprendre pourquoi l'exemple d'entrée 2 était ainsi, alors je l'ai beaucoup fondu. .. .. Raison? Pour une raison quelconque, vous devez trier ce que vous avez tapé! Parce que j'ai pensé. Je laisse une sorte dans le commentaire pour l'auto-discipline. .. ..
La solution est la suivante
--Déplacez i à 1 --N-1 et obtenez la plus petite différence entre le total jusqu'à 0-i et le total jusqu'à i + 1 --N-1.
Donc, dans la production réelle, j'ai utilisé la somme cumulative (je ne pouvais pas comprendre l'exemple d'entrée 2 et je pensais que ce n'était pas une recherche complète, non?), Mais c'était exagéré. ..
private void solveB() {
int n = nextInt();
int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();
//Je mettrai trié... int[] wk = IntStream.range(0, n).map(i -> nextInt()).sorted().toArray();
int[] rui = new int[n];
//0-Effectuer la somme cumulée de N
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 à n de 1 pour trouver réellement la valeur numérique de T candidat-Déplacer vers 1
*N'allez pas au tout début ou à la fin pour vous diviser en deux groupes
* (rui[n - 1] - rui[i]) -> i+Somme de 1 à N
* rui[i] ->Somme de 0 à 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);
}
«Je pense que vous pouvez écrire plus joliment dans sum1 et sum2, mais je ne l'ai pas proposé.
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
――Comme le nom du problème l'indique, un DP vraiment typique
n + 3 au lieu de n + 1, vous n'avez pas besoin de juger ʻi + 2 <= n ou ʻi + 1 <= n.Je n'ai pas tout fini (je ne peux pas du tout résoudre le problème du score élevé!), Mais les concours suivants sont utiles.
AtCoder - Concours Éducatif DP / Concours Résumé DP AtCoder - Typical DP Contest article de drken: Super introduction à la planification dynamique! Explications des problèmes A à E du concours DP éducatif et problèmes similaires article de drken: Explication et problèmes similaires des problèmes F à J dans le concours Education DP
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
«Je pense que c'était un problème de somme cumulative assez typique.
--Image de prendre des sommes cumulées verticalement et horizontalement et de les superposer à la fin ――Combien de carrés pouvez-vous éclairer verticalement? À côté de combien de carrés éclairez-vous? Première fabrication
Je pense que c'est lent à écrire du code parce que j'écris en commentant pendant le concours
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];
/*
*Créer une somme cumulée pour W
*/
for (int i = 0; i < h; i++) {
int cnt = 0;
/*
*L'exemple d'entrée 1 ressemble à ce qui suit(Cote à cote)
* 012012
* 123450
* 123401
* 010123
*/
for (int j = 0; j < w; j++) {
if (wk[i][j] == '.') {
cnt++;
} else {
cnt = 0;
}
rui1[i][j] = cnt;
}
/*
*Lisser les résultats accumulés(Cote à cote)
* 012012
* 123450
* 123401
* 010123
*À
* 022022
* 555550
* 444401
* 010333
*Conversion en
*/
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];
/*
*Créer une somme cumulée pour H
*/
for (int j = 0; j < w; j++) {
int cnt = 0;
/*
*L'exemple d'entrée 1 ressemble à ce qui suit(Verticalement)
* 011011
* 122120
* 233201
* 040312
*/
for (int i = 0; i < h; i++) {
if (wk[i][j] == '.') {
cnt++;
} else {
cnt = 0;
}
rui2[i][j] = cnt;
}
/*
*Lisser les résultats accumulés(Verticalement)
* 011011
* 122120
* 233201
* 040312
*À
* 043021
* 243320
* 243302
* 040312
*Conversion en
*/
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];
}
}
}
/*
*Puisqu'il est cumulatif, lécher tout
*Cependant, la partie centrale où le haut, le bas, la gauche et la droite se chevauchent-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