透過執行子字串的異或運算，在 K 步內最大化二進位制字串的值

#include <stdio.h>
#include <string.h>
#include <stdlib.h> // Added for dynamic memory allocation

// Function to add 'n' zeros to the beginning of a string
void addNZero(char *substr, int n) {
   int i;

   // Shift existing characters to the right to make space for zeros
   for (i = strlen(substr); i >= 0; i--) {
      substr[i + n] = substr[i];
   }

   // Add 'n' zeros at the beginning
   for (i = 0; i < n; i++) {
      substr[i] = '0';
   }
}

// Function to perform XOR of two strings
void getXOR(char *temp1, char *temp2, char *result) {
   int len1 = strlen(temp1);
   int len2 = strlen(temp2);
   int len = len1 > len2 ? len1 : len2; // Maximum length
   int i;

   // Make both strings of equal length by adding leading zeros
   if (len1 > len2) {
      addNZero(temp2, len1 - len2);
   } else if (len2 > len1) {
      addNZero(temp1, len2 - len1);
   }

   // Compute XOR
   for (i = 0; i < len; i++) {
      if (temp1[i] == temp2[i]) {
         result[i] = '0';
      } else {
         result[i] = '1';
      }
   }

   // Null-terminate the result string
   result[len] = '\0';
}

// Function to find the maximum value of a binary string after K XOR operations
void findMaxValue(char *bin_str, int K) {
   int len = strlen(bin_str);
   int leftZero = -1, cnt0 = 0, cnt1 = 0;
   char *rightStr, *temp, *maxRes, *temp1, *temp2;
   int size;

   // Calculate the number of 0's and 1's in the binary string
   for (int p = 0; p < len; p++) {
      if (bin_str[p] == '1') {
         cnt1++;
      } else {
         if (leftZero == -1) {
            leftZero = p;
         }
         cnt0++;
      }
   }

   // Case 1 - When the string contains all 1's
   if (cnt1 == len) {
      char one[] = "1";
      getXOR(bin_str, one, bin_str);
      return;
   }

   // Case 2 - When the string contains all zeros
   if (cnt0 == len) {
      printf("0\n");
      return;
   }

   // Take the substring starting from the leftmost '0' to maximize it
   rightStr = bin_str + leftZero;
   size = len - leftZero;
   temp = rightStr;
   maxRes = (char *)malloc((len + 1) * sizeof(char)); // Allocate memory for maxRes
   temp1 = (char *)malloc((len + 1) * sizeof(char));   // Allocate memory for temp1
   temp2 = (char *)malloc((len + 1) * sizeof(char));   // Allocate memory for temp2

   // Initialize memory to avoid undefined behavior
   memset(maxRes, 0, (len + 1) * sizeof(char));
   memset(temp1, 0, (len + 1) * sizeof(char));
   memset(temp2, 0, (len + 1) * sizeof(char));

   // Choosing the second string
   for (int q = 0; q < len; q++) {
      if (q < size) {
         temp1[q] = bin_str[q];
      } else {
         // If temp1 gives the maximum XOR result, choose it as the second string
         char res[len + 1];
         getXOR(temp, temp1, res);
         if (strcmp(res, maxRes) > 0) {
            strcpy(maxRes, res);
            strcpy(temp2, temp1);
         }

         // Update temp1 string
         for (int i = 0; i < size - 1; i++) {
            temp1[i] = temp1[i + 1];
         }
         temp1[size - 1] = bin_str[q];
      }
   }

   // Handling the last case
   char res[len + 1];
   getXOR(temp1, temp, res);
   if (strcmp(res, maxRes) > 0) {
      strcpy(maxRes, res);
      strcpy(temp2, rightStr);
   }

   // Take the XOR of the original string and the second string
   getXOR(bin_str, temp2, bin_str);

   // Remove leading zeros
   leftZero = -1;
   for (int p = 0; p < len; p++) {
      if (bin_str[p] != '0') {
         leftZero = p;
         break;
      }
   }
   if (leftZero == -1) {
      printf("0\n");
   } else {
      printf("%s\n", bin_str + leftZero);
   }

   // Free dynamically allocated memory
   free(maxRes);
   free(temp1);
   free(temp2);
}

int main() {
   char bin_str[] = "1101";
   int K = 1;
   printf("The maximum value of the string after performing 1 XOR operations is - ");
   findMaxValue(bin_str, K);
   return 0;
}

輸出

The maximum value of the string after performing 1 XOR operations is - 1111