[JAVA] ABC --054 --A & B & C

AtCoder ABC 054 A&B&C AtCoder - 054

Un problème

--Comparez les nombres de A et B --2 <3 <4 <5 <6 <7 <8 <9 <10 <11 <12 <13 <1

• Dessiner si le nombre est le même ――1 est le plus fort, donc si l'un est égal à 1, l'autre gagne ――Si ce n'est ni le même nombre ni 1, le plus grand nombre l'emporte

		int alice = nextInt();
		int bob = nextInt();

		if (alice == bob) {
			out.println("Draw");
		} else if (alice == 1) {
			out.println("Alice");
		} else if (bob == 1) {
			out.println("Bob");
		} else if (alice != bob) {
			out.println(alice > bob ? "Alice" : "Bob");
		}

		out.println("");

Problème B

La description est écrite en ligne dans la source

	private void solveB() {
		int numN = nextInt();
		int numM = nextInt();
		String[] wkA = new String[numN];
		String[] wkB = new String[numM];

		for (int i = 0; i < wkA.length; i++) {
			wkA[i] = next();
		}
		for (int i = 0; i < wkB.length; i++) {
			wkB[i] = next();
		}

		boolean res = chkB(wkA, 0, wkB, 0);
		out.println(res ? "Yes" : "No");
	}


	private boolean chkB(String[] wkA, int currentA, String[] wkB, int aPos) {
		boolean res = false;

		//Impossible de rechercher si wkA a moins de wkB restants
		if (wkA.length - currentA < wkB.length) {
			return false;
		}
		//wkA[]La longueur restante est wkB[]Impossible de rechercher si moins
		if (wkA[currentA].length() - aPos < wkB[0].length()) {
			return false;
		}
		//Tout d'abord, déterminez la position de A
		//Par conséquent, vérifiez où la colonne B actuelle de B apparaît dans la colonne A actuelle de A.
		//Obtenez la valeur sur l'axe horizontal de A
		//* Il est possible que plusieurs axes horizontaux de A puissent être obtenus.
		//Vérifiez où la colonne B actuelle de B apparaît dans la colonne A actuelle de A
		boolean aPosWk = wkA[currentA].startsWith(wkB[0], aPos);
		if (aPosWk) {
			//Lorsque l'axe horizontal de A apparaît, le A actuel+À partir de l'axe horizontal de la colonne 1, currentB dans la colonne B+Vérifiez si 1 apparaît

			for (int i = 0; i < wkB.length; i++) {
				res = wkA[currentA + i].startsWith(wkB[0 + i], aPos);
				if (!res) {
					break;
				}
			}

		}
		//Si l'axe horizontal de A n'apparaît pas, aPos+Rechercher la première colonne
		//Si cet aPos ne correspond pas, aPos+1 et recherchez à nouveau
		if (!res) {
			//B colonne courantB+Si 1 n'apparaît pas, recherchez à nouveau l'axe horizontal de A
			int len = wkA[currentA].indexOf(wkB[0], aPos + 1);
			//Rechercher à nouveau car il y a encore des candidats dans la ligne
			if (len >= 0) {
				res = chkB(wkA, currentA, wkB, len);
			}

		}

		//Si aPos est différent de zéro, définissez le prochain currentId
		if (!res && aPos == 0) {
			//Si l'axe horizontal de A n'apparaît pas, currentA+Rechercher la première ligne
			res = chkB(wkA, currentA + 1, wkB, 0);
		}
		return res;
	}

Problème C

Graphique non orienté Référence: 1 Référence: 2

Pour le moment, l'exemple d'entrée 1 est exprimé comme une matrice adjacente.

Entrée 1

1 2 1 3 2 3

Convertir (mettez True partout où vous le pouvez)

Puisqu'il s'agit d'un graphe orienté, c'est une matrice symétrique.

• Tout d'abord, convertissez l'entrée dans la matrice cible
• Remplacez par vrai là où vous pouvez aller --Générer un booléen [] de même longueur que numN pour mémoriser la destination
• La recherche elle-même est récursive
• Le premier endroit a été visité

	private void solveC() {

		int numN = nextInt();
		int numM = nextInt();

		boolean[][] wk = new boolean[numN][numN];

		for (int i = 0; i < numM; i++) {
			int iA = nextInt();
			int iB = nextInt();
			wk[iA - 1][iB - 1] = true;
			wk[iB - 1][iA - 1] = true;
		}
		boolean[] visited = new boolean[numN];
		visited[0] = true;
		int res = chkSolveC(wk, 0, visited);
		out.println(res);
	}

--Condition de fin de récurrence

• Si vous avez déjà visité, ajoutez +1 et terminez --Conditions pour continuer
• Vous pouvez remonter la matrice adjacente (vrai avec wk [] []) et n'avez pas encore visité (faux avec visité [])

Avec récursif, je voulais ajouter +1 à currentI lors de l'appel de chkSolveC, mais si j'y réfléchis attentivement, je sors le i où je peux aller dans la matrice adjacente et le passe comme argument currentI, donc +1 est inutile.

	private int chkSolveC(boolean[][] wk, int currentI, boolean[] visited) {

		boolean res = true;
		for (int i = 0; i < visited.length; i++) {
			if (!visited[i]) {
				res = false;
			}
		}
		if (res) {
			return 1;
		}

		int resCnt = 0;
		boolean[] wkG = wk[currentI];
		for (int i = 0; i < wkG.length; i++) {
			if (wkG[i] && !visited[i]) {
				visited[i] = true;
				resCnt += chkSolveC(wk, i, visited);
				visited[i] = false;
			}

		}

		return resCnt;
	}