USACO 2020 Февраль Бронза Q2. Злой ученый

Проблема: http://usaco.org/index.php?page=viewproblem2&cpid=1012

Решение:

По сути, этот алгоритм просто принимает две входные строки как массивы символов и выполняет итерацию по ним обеим одновременно. Мы продолжаем использовать переменную (flip), чтобы отслеживать количество подстрок в двух массивах, которые не равны друг другу. Кроме того, мы также используем переменную (equal), чтобы отслеживать, эквивалентны ли текущие подстроки друг другу. Если текущие символы в одной и той же позиции не эквивалентны, мы устанавливаем equalfalse. Если символ сразу после него также не эквивалентен, equal по-прежнему будет ложным, поскольку они являются частью одной и той же подстроки. Мы увеличиваем flip, когда для equal снова устанавливается значение true, потому что это происходит только тогда, когда «неравная» подстрока заканчивается и текущие символы равны. Если мы перебираем массив, а equal по-прежнему имеет значение false, это означает, что в конце массивов есть подстрока/символ, которые не равны и не были добавлены в наш ответ, flip, поэтому мы пишем дополнительный оператор «if» вне нашего цикла for, чтобы учесть это.

import java.io.*;
import java.util.*;
public class MadScientist {
public static void main(String[] args) throws IOException {
  // TODO Auto-generated method stub
  Kattio io = new Kattio("breedflip");
  
  // Take in input
  int N = io.nextInt();
  char[] a = io.next().toCharArray();
  char[] b = io.next().toCharArray();
  
  // 'flip' is the variable that stores our answer
  int flip = 0;
  // 'equal' keeps track of whether or not the current character/substring of 'b' equals 'a'
  boolean equal = true;
  
  // iterate through both arrays simultaneously
  for (int i = 0; i < N; i++)
  {
   // if the current character of a does not equal the current character of 'b', we 
   // set 'equal' to false
   if (a[i] != b[i]) equal = false;
   
   // if the current character of 'a' equals the current character of 'b'
   // and 'equal' is false, then we increment 'flip' and reset 'equal' to true
   if (a[i] == b[i] && !equal) 
   {
    flip++;
    equal = true;
   }
  }
  
  // if we finish iterating through the array and 'equal' still has the value false,
  // then that means that the last substring of 'b' does not equal the corresponding portion of
  // 'a' so we do this if statement to account for that edge case since the arrays were traversed
  // through before we incremented flip again
  if (!equal) flip++;
  io.println(flip); // output answer
  
  
  io.close();
}
 static class Kattio extends PrintWriter {
  private BufferedReader r;
  private StringTokenizer st;
 
  // standard input
  public Kattio() { this(System.in, System.out); }
  public Kattio(InputStream i, OutputStream o) {
   super(o);
   r = new BufferedReader(new InputStreamReader(i));
  }
  // USACO-style file input
  public Kattio(String problemName) throws IOException {
   super(new FileWriter(problemName + ".out"));
   r = new BufferedReader(new FileReader(problemName + ".in"));
  }
 
  // returns null if no more input
  public String next() {
   try {
    while (st == null || !st.hasMoreTokens())
     st = new StringTokenizer(r.readLine());
    return st.nextToken();
   } catch (Exception e) { }
   return null;
  }
 
  public int nextInt() { return Integer.parseInt(next()); }
  public double nextDouble() { return Double.parseDouble(next()); }
  public long nextLong() { return Long.parseLong(next()); }
 }
}

Надеюсь, эта редакция помогла вам! Если это так, мы будем очень благодарны, если вы нажмете кнопку хлопка в этой статье. Если необходимы какие-либо разъяснения или у вас есть какие-либо предложения по улучшению, не стесняйтесь оставлять комментарии ниже.