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

AtCoder ABC 054 A&B&C AtCoder - 054

Ein Problem

--Vergleichen Sie die Zahlen von A und B.

• 2 <3 <4 <5 <6 <7 <8 <9 <10 <11 <12 <13 <1
• Zeichnen Sie, wenn die Nummer gleich ist ――1 ist am stärksten. Wenn einer der beiden 1 ist, gewinnt der andere ――Wenn es weder die gleiche noch die gleiche Zahl ist, gewinnt die größere Zahl

		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("");

B Problem

Die Beschreibung wird in der Quelle inline geschrieben

	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;

		//Kann nicht suchen, wenn wkA weniger als wkB übrig hat
		if (wkA.length - currentA < wkB.length) {
			return false;
		}
		//wkA[]Die verbleibende Länge beträgt wkB[]Kann nicht suchen, wenn weniger
		if (wkA[currentA].length() - aPos < wkB[0].length()) {
			return false;
		}
		//Bestimmen Sie zunächst die Position von A.
		//Überprüfen Sie daher, wo die aktuelle B-Spalte von B in der aktuellen A-Spalte von A angezeigt wird.
		//Holen Sie sich den Wert auf der horizontalen Achse von A.
		//* Es besteht die Möglichkeit, dass mehrere horizontale Achsen von A erhalten werden können.
		//Überprüfen Sie, wo die aktuelle B-Spalte von B in der aktuellen A-Spalte von A angezeigt wird
		boolean aPosWk = wkA[currentA].startsWith(wkB[0], aPos);
		if (aPosWk) {
			//Wenn die horizontale Achse von A erscheint, wird Strom A.+Von der horizontalen Achse von Spalte 1 ist currentB in Spalte B.+Überprüfen Sie, ob 1 angezeigt wird

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

		}
		//Wenn die horizontale Achse von A nicht angezeigt wird, wird aPos+Suchen Sie die erste Spalte
		//Wenn dieses aPos nicht übereinstimmt, aPos+1 und erneut suchen
		if (!res) {
			//B SpaltenstromB+Wenn 1 nicht angezeigt wird, suchen Sie die horizontale Achse von A erneut
			int len = wkA[currentA].indexOf(wkB[0], aPos + 1);
			//Suchen Sie erneut, da sich noch Kandidaten in der Zeile befinden
			if (len >= 0) {
				res = chkB(wkA, currentA, wkB, len);
			}

		}

		//Wenn aPos nicht Null ist, setzen Sie die nächste aktuelle ID
		if (!res && aPos == 0) {
			//Wenn die horizontale Achse von A nicht angezeigt wird, wird currentA+Suchen Sie die erste Zeile
			res = chkB(wkA, currentA + 1, wkB, 0);
		}
		return res;
	}

C Problem

Ungerichtete Grafik Referenz: 1 Referenz: 2

Das Eingabebeispiel 1 wird vorerst als benachbarte Matrix ausgedrückt.

Eingabe 1

1 2 1 3 2 3

Konvertieren (setzen Sie True, wo immer Sie können)

Da es sich um einen gerichteten Graphen handelt, handelt es sich um eine symmetrische Matrix.

• Konvertieren Sie zuerst die Eingabe in die Zielmatrix
• Ersetzen Sie wahr, wohin Sie gehen können --Erstellen Sie einen Booleschen Wert [] mit der gleichen Länge wie numN, um das Ziel zu speichern
• Die Suche selbst ist rekursiv

	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);
	}

	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;
	}