AtCoder ABC 023 A&B&C AtCoder - 023
private void solveA() {
int x = nextInt();
int res = 0;
while (x != 0) {
res += x % 10;
x /= 10;
}
out.println(res);
}
«Puisque l'ordre de la combinaison de« a »,« c »et« b »n'est pas pris en considération», il s'agit en fait de ** solution de mensonge **. .. .. Un correctif sera bientôt disponible.
b '' et comporte toujours +2 caractères, donc ce sera toujours un nombre impair. --Faux pour les nombres pairs -Le centre est b '', et la gauche et la droite sont l'un des suivants
- 'a' xxx 'c'
- 'c' xxx 'a'
- 'b' xxx 'b' private void solveB() {
int numN = nextInt();
String s = next();
if ((numN & 1) == 0) {
out.println(-1);
return;
}
int max = numN / 2;
int res = 0;
for (int i = 0; i < max; i++) {
char down = s.charAt((numN - 1) - (max + 1) - i);
char up = s.charAt((max + 1) + i);
if ((down == 'a' && up == 'c') || (down == 'c' && up == 'a') || (down == 'b' && up == 'b')) {
res = i + 1;
} else {
out.println(-1);
return;
}
}
out.println(res);
}
AtCoder Beginner Contest 023 Explication P.12 ~
-Je n'écrirai qu'un supplément sur [Ajustement fin \ Rechercher où le bonbon a été placé]
| col no\row no | 1 | 2 | 3 | ||
|---|---|---|---|---|---|
| nombre de cols\nombre de lignes | 2 | 1 | 2 | ||
| 1 | 1 | 〇 | |||
| 2 | 2 | 〇 | 〇 | ||
| 3 | 2 | 〇 | 〇 |
--Lorsque k = 3 -A la position $ (col no, row no) = (2,2) $, vous pouvez obtenir 3 bonbons sans aucun problème.
Si l'endroit où vous mettez les bonbons est $ col count + row count = K $, vous comptez les endroits qui ne devraient pas être comptés.
| col no\row no | 1 | 2 | 3 | ||
|---|---|---|---|---|---|
| nombre de cols\nombre de lignes | 2 | 1 | 2 | ||
| 1 | 1 | 〇 | |||
| 2 | 2 | 〇 | 〇 | ||
| 3 | 2 | 〇 | 〇 |
--Lorsque k = 3 -A la position $ (col no, row no) = (3,3) $, vous pouvez obtenir 3 bonbons sans aucun problème. --Cependant, $ (nombre de colonnes, nombre de lignes) = (2,2) $, donc le total est de 4
--Si l'endroit où vous placez le bonbon est $ col count + row count = K + 1 $, le bonbon est compté deux fois. ―― +1 parce que j'ai compté les bonbons que j'ai mis deux fois
private void solveC() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
int n = nextInt();
int[] rI = new int[n];
int[] cI = new int[n];
int[] rP = new int[r + 1];
int[] cP = new int[c + 1];
for (int i = 0; i < n; i++) {
int tmpR = nextInt() - 1;
int tmpC = nextInt() - 1;
rI[i] = tmpR;
cI[i] = tmpC;
//Nombre de bonbons pour chaque ligne de r
rP[tmpR]++;
//Nombre de bonbons pour chaque colonne de c
cP[tmpC]++;
}
/*
*Agréger le nombre de bonbons pour chaque rangée
*Si ce numéro est pour chaque ligne
* [1, 2, 2, 0]
*Comptez comme suit
* 0=1
* 1=1
* 2=2
* 3=0
*La taille du rPCount est N+1 c'est parce qu'il n'y a plus de bonbons
*/
int[] rPCount = new int[n + 1];
for (int i = 0; i < r; i++) {
rPCount[rP[i]]++;
}
//Traitez chaque colonne de la même manière que la ligne
int[] cPCount = new int[n + 1];
for (int i = 0; i < c; i++) {
cPCount[cP[i]]++;
}
long res = 0;
/*
*Calculez grossièrement la combinaison
*Pour l'exemple d'entrée 1,
*Lorsque le nombre de bonbons dans la ligne est 0, le nombre de bonbons dans le col doit être 3
*pour cette raison,[Nombre de lignes où r candy vaut 0]×[Le nombre de lignes où le bonbon de c est 3]Calculer
*De même, lorsque le nombre de bonbons dans la rangée est de 1, le nombre de bonbons dans col doit être de 2.
* [Nombre de lignes où r bonbons vaut 1]×[Le nombre de lignes où le bonbon de c est 2]Calculer
*Cela donne une combinaison approximative
*/
for (int i = 0; i <= k; i++) {
res += rPCount[i] * cPCount[k - i];
}
/*
*tordre
*Rechercher où le bonbon a été placé
*/
for (int i = 0; i < n; i++) {
long sum = rP[rI[i]] + cP[cI[i]];
if (sum == k) {
/*
*Le fait que la somme soit égale à K compte les objets qui ne doivent pas être comptés dans le calcul de combinaison approximative.
*Par conséquent, cette position est exclue du décompte
*/
res--;
} else if (sum == k + 1) {
/*
*Le total est K+1 est hors de portée du comptage au moment du calcul de la combinaison grossière
*Par conséquent, cette position compte
*/
res++;
}
}
out.println(res);
}
private void solveC3() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
int n = nextInt();
// int[][] masu = new int[r][c];
Map<Integer, Set<Integer>> wk = new HashMap<Integer, Set<Integer>>();
int[] rP = new int[r];
int[] cP = new int[c];
for (int i = 0; i < n; i++) {
int tmpR = nextInt() - 1;
int tmpC = nextInt() - 1;
// masu[tmpR][tmpC] = 1;
Set<Integer> tmpSet = new HashSet<Integer>();
tmpSet.add(tmpC);
wk.merge(tmpR, tmpSet, (oldV, newV) -> {
oldV.addAll(newV);
return oldV;
});
rP[tmpR]++;
cP[tmpC]++;
}
long res = 0;
Set<Integer> defSet = new HashSet<Integer>();
for (int i = 0; i < rP.length; i++) {
for (int j = 0; j < cP.length; j++) {
int val = wk.getOrDefault(i, defSet).contains(j) ? 1 : 0;
// int val = wk.getOrDefault(i, new HashSet<Integer>()).contains(j) ? 1 : 0;
if (rP[i] + cP[j] - val == k) {
res++;
}
}
}
out.println(res);
}
/**
* MLE
*/
private void solveC2() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
int n = nextInt();
int[][] masu = new int[r][c];
int[] rP = new int[r];
int[] cP = new int[c];
for (int i = 0; i < n; i++) {
int tmpR = nextInt();
int tmpC = nextInt();
masu[tmpR - 1][tmpC - 1] = 1;
rP[tmpR - 1]++;
cP[tmpC - 1]++;
}
long res = 0;
for (int i = 0; i < rP.length; i++) {
for (int j = 0; j < cP.length; j++) {
if (rP[i] + cP[j] - masu[i][j] == k) {
res++;
}
}
}
out.println(res);
}
Recommended Posts