第一次打这个比赛，试了下感觉难度比ACM简单，题目质量很好。比赛一般安排在周末，一般都不会有时间冲突，可以专心写题，而且每一轮的时间不一样，照顾各个时区和作息习惯的选手都能参加，这一点也很是不错的。
个人比赛使用的C语言，本地编译器版本是gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0，使用vscode做IDE。
至于rank之类的比较靠后就不提及了，主要说下这些题目的解法。

4个题的分值分配：

• K-Goodness String (5+7)
• L Shaped Plots (8+12)
• Rabbit House (9+15)
• Checksum (10+17+17)

(1) K-Goodness String

Charles defines the goodness score of a string as the number of indices i such that where (1-indexed). For example, the string CABABC has a goodness score of 2 since and .
Charles gave Ada a string S of length N, consisting of uppercase letters and asked her to convert it into a string with a goodness score of K. In one operation, Ada can change any character in the string to any uppercase letter. Could you help Ada find the minimum number of operations required to transform the given string into a string with goodness score equal to K?

问题简述

给定一些字符串，仅包含大写字母。定义得分为字符串中非对称的字符个数，即，其中，为字符串长度。现在需要改变其中一些字符，使得字符串得分等于K，求解最少需要改变的字符个数。

输入

第一行为T，测试的个数。
以下每个测试有2行，前一行为字符串长度N和目标得分K；
后一行是这个字符串S。

输出

输出格式为 Case #x: y，表示第x个测试(x从1编号)需要最少改变y个字符。

数据范围

Memory limit: 1 GB.
.
.

Test Set 1
Time limit: 20 seconds.
.

Test Set 2
Time limit: 40 seconds.
for at most 10 test cases.
For the remaining cases, .

样例输入

2
5 1
ABCAA
4 2
ABAA

样例输出

Case #1: 0
Case #2: 1

分析

求解需要改变的字符个数，也就是求字符串的原始得分和K的差的绝对值。

而计算得分只需要把字符串用一次循环判断一遍字符是否相等，不等的情况+1分即可。

题解代码 (C语言)

#include<stdio.h>
#include<string.h>
int main()
{
    int t=0, n=0, k=0;
    char s[200001];
    scanf("%d", &t);
    for (int i=0; i<t; i++)
    {
        scanf("%d %d", &n, &k);
        scanf("%s", s);
        int len = strlen(s);
        int y = 0;
        for (int j=0; j<(len>>1); j++)
            if (s[j] != s[len-j-1])
                y++;
        y = y-k;
        printf("Case #%d: %d\n", i+1, (y>0?y:-y));
    }
    return 0;
}

(2) L Shaped Plots

Given a grid of R rows and C columns each cell in the grid is either 0 or 1.
A segment is a nonempty sequence of consecutive cells such that all cells are in the same row or the same column. We define the length of a segment as number of cells in the sequence.
A segment is called "good" if all the cells in the segment contain only 1s.
An "L-shape" is defined as an unordered pair of segments, which has all the following properties:

• Each of the segments must be a "good" segment.
• The two segments must be perpendicular to each other.
• The segments must share one cell that is an endpoint of both segments.
• Segments must have length at least 2.
• The length of the longer segment is twice the length of the shorter segment.
• We need to count the number of L-shapes in the grid.

Below you can find two examples of correct L-shapes,

图2-1

and three examples of invalid L-shapes.

图2-2

Note that in the shape on the left, two segments do not share a common endpoint. The next two shapes do not meet the last requirement, as in the middle shape both segments have the same length, and in the last shape the longer segment is longer than twice the length of the shorter one.

问题简述

给定由0、1组成的矩阵为R行C列，定义"线段"为在1行或1列的连续若干个"1"，其中1的个数定义为线段的长度。
定义"L-shapes"由2个互相垂直的线段组成，且满足：两个线段相交于每个线段的一个端点、每个线段的长度至少为2、其中一个线段是另一个长度的2倍。
现在需要统计给定矩阵中"L-shapes"的总个数。

输入

第一行为T，测试的个数。
以下每个测试有行，前一行为R和C两个整数；
接下来的R行，每行有C个数字构成整个矩阵。

输出

输出格式为 Case #x: y，表示第x个测试(x从1编号)的"L-shapes"个数为y。

数据范围

Time limit: 60 seconds.
Memory limit: 1 GB.
.
Grid consists of 0s and 1s only.

Test Set 1
.
.

Test Set 2
and for at most 5 test cases.
For the remaining cases, and .

样例输入

2
4 3
1 0 0
1 0 1
1 0 0
1 1 0
6 4
1 0 0 0
1 0 0 1
1 1 1 1
1 0 1 0
1 0 1 0
1 1 1 0

样例输出

Case #1: 1
Case #2: 9

分析

这题的解决思路是枚举整个矩阵中每个单元格为中心点的情况。

考虑到对于单元格，如果该位置为0，则不可能构成任何"L-shapes"；而该位置为1时，则可能成为若干个"L-shapes"的中心点(即两段线段的交点)，这里可能会有4种情况——以为中心，分别往左上、右上、左下、右下。
而对应每种情况下，长短边也有可能分别在水平或垂直方向。

我们设位置处某一对方向(例如左上)两个方向的线段连续最大长度分别为x, y，以x方向为长边的"L-shapes"个数为，其中-1是因为短边的长度不能为1；对应的，y方向就是。那么，以为中心点的该方向的"L-shapes"个数可求得：

将公式分别代入4种方向，加起来就是以为中心点的所有可能的"L-shapes"总个数：

最后输出的总数就是遍历所有的全部个数的和，时间复杂度为。

注：这里有一个细节，就是如何判断位置处每个方向上的线段连续最大长度。
对此我们采用按照特定方向(如：上→下，左→右)累加的方法，从第一个1开始，每次+1，如遇到0则清零。这个操作的时间复杂度也是。

代码具体处理上的一些点：
一是在计算时，进行了判断是否大于0，因为对于孤立的1点，这个值计算出来是负的，但是并不会导致整个矩阵中的"L-shapes"个数减少。
二是在累加最后的结果的时候，使用了long long int的类型，以便处理特别大的数据规模，输出的时候也要对应使用"%lld"。
三是细节方面进一步加速计算，循环的等变量使用了寄存器变量，除以2的操作改为向右移位运算来加速。

题解代码 (C语言)

#define min(x, y) ((x) < (y) ? (x) : (y))

#include <stdio.h>
int main()
{
    int t = 0, R = 0, C = 0;
    int M[1000][1000], seg[4][1000][1000];
    scanf("%d", &t);
    for (int c = 1; c <= t; c++)
    {
        scanf("%d %d", &R, &C);
        for (register int i = 0; i < R; i++)
            for (register int j = 0; j < C; j++)
                scanf("%d", M[i] + j);

        // --- calculate sum of segments ---
        // left -> right
        for (register int i = 0; i < R; i++)
        {
            int len = 0;
            for (register int j = 0; j < C; seg[0][i][j++] = len)
            {
                if (M[i][j]) len++;
                else len = 0;
            }
        }
        // right -> left
        for (register int i = 0; i < R; i++)
        {
            int len = 0;
            for (register int j = C; j-- > 0; seg[1][i][j] = len)
            {
                if (M[i][j]) len++;
                else len = 0;
            }
        }
        // top -> down
        for (register int j = 0; j < C; j++)
        {
            int len = 0;
            for (register int i = 0; i < R; seg[2][i++][j] = len)
            {
                if (M[i][j]) len++;
                else len = 0;
            }
        }
        // down -> up
        for (register int j = 0; j < C; j++)
        {
            int len = 0;
            for (register int i = R; i-- > 0; seg[3][i][j] = len)
            {
                if (M[i][j]) len++;
                else len = 0;
            }
        }

        // --- calculate F(i,j) and sum up ---
        unsigned long long sum = 0;
        for (register int i = 0; i < R; i++)
            for (register int j = 0; j < C; j++)
                if (M[i][j])
                {
                    for (register int k = 0; k < 4; k++) // k=0,1,2,3; xy=00,01,10,11
                    {
                        int F = min(seg[k >> 1][i][j] >> 1, seg[2 + (k % 2)][i][j]) - 1;
                        F += min(seg[k >> 1][i][j], seg[2 + (k % 2)][i][j] >> 1) - 1;
                        if (F > 0) sum += F;
                    }
                }
        printf("Case #%d: %lld\n", c, sum);
    }
    return 0;
}

(3) Rabbit House

Barbara got really good grades in school last year, so her parents decided to gift her with a pet rabbit. She was so excited that she built a house for the rabbit, which can be seen as a 2D grid with R rows and C columns.
Rabbits love to jump, so Barbara stacked several boxes on several cells of the grid. Each box is a cube with equal dimensions, which match exactly the dimensions of a cell of the grid.
However, Barbara soon realizes that it may be dangerous for the rabbit to make jumps of height greater than 1 box, so she decides to avoid that by making some adjustments to the house. For every pair of adjacent cells, Barbara would like that their absolute difference in height be at most 1 box. Two cells are considered adjacent if they share a common side.
As all the boxes are superglued, Barbara cannot remove any boxes that are there initially, however she can add boxes on top of them. She can add as many boxes as she wants, to as many cells as she wants (which may be zero). Help hew determine what is the minimum total number of boxes to be added so that the rabbit's house is safe.

问题简述

设有一个R行C列的网格，每个格子都有一个给定的高度；现在要求添加一些长宽高都是1的方块，使得所有位置都满足相邻单元格的高度差异最多为1，求最少要放多少个方块。

输入

第一行为T，测试的个数。
以下每个测试有行，前一行为R和C两个整数；
接下来的R行，每行有C个数字，表示网格中每个点的高度。

输出

输出格式为 Case #x: y，表示第x个测试(x从1编号)最少需要添加y个方块。

数据范围

Memory limit: 1 GB.
.
, for all .

Test Set 1
Time limit: 20 seconds.
.

Test Set 2
Time limit: 40 seconds.
.

样例输入

3
1 3
3 4 3
1 3
3 0 0
3 3
0 0 0
0 2 0
0 0 0

样例输出

Case #1: 0
Case #2: 3
Case #3: 4

分析

这个问题的突破口在于对每个点需要满足上下左右4个方向不小于当前位置的高度-1即可。如果小于这个值，就强行设置为当前位置的高度-1，同时统计需要补的方块个数。
那么只要不断遍历整个网格的所有点，对每个点这样处理，直到最后一次遍历了所有网格后发现所有的点都满足这个规则为止。
由于数据规模给的是，最坏的情况的时间复杂度为，在C语言做足够多的优化的情况下，这样的搜索方法可以满足不超时。

注意在遍历的过程中，需要做边界检查，以避免内存地址溢出。还有每个网格的高度最多是，网格大小为，因此最后的结果可能超出int范围，采用long long数据类型。

进一步思考

如果数据规模更大的话，并且遇到更坏的情况，还有一个继续优化时间复杂度的解决思路，就是每次遍历整个网格后，改变一次遍历的方向。包括x轴优先、y轴优先，以及每种情况下的正序和逆序，因此共有4种方向，也就是说整个网格只要遍历4次。而且每次遍历的时候，就只需要沿着遍历的那一个方向做判断即可，无需把4个方向全部处理。这种情况下可以把时间复杂度极限优化到。

这个题目一眼看上去像是需要用找最大值的方法，但是每一步操作都要找一次最大值及其index，这个时间代价太大了，直接操作的话肯定会超时，因此我在处理的时候直接避免了全局找最大值，而直接采用局部操作，效率更快。

题解代码 (C语言)

#include<stdio.h>

int t=0, R=0, C=0;
int G[300][300];

int proc(int g[300][300], int x, int y)
{
    register int s = 0;
    if (x > 0)
    {
        // up
        if (g[x][y] - g[x-1][y] > 1)
        {
            s += g[x][y] - g[x-1][y] - 1;
            g[x-1][y] = g[x][y] - 1;
        }
    }
    if (x < R-1)
    {
        // down
        if (g[x][y] - g[x+1][y] > 1)
        {
            s += g[x][y] - g[x+1][y] - 1;
            g[x+1][y] = g[x][y] - 1;
        }
    }
    if (y > 0)
    {
        // left
        if (g[x][y] - g[x][y-1] > 1)
        {
            s += g[x][y] - g[x][y-1] - 1;
            g[x][y-1] = g[x][y] - 1;
        }
    }
    if (y < C-1)
    {
        // right
        if (g[x][y] - g[x][y+1] > 1)
        {
            s += g[x][y] - g[x][y+1] - 1;
            g[x][y+1] = g[x][y] - 1;
        }
    }
    return s;
}

int main()
{
    scanf("%d", &t);
    for (int i=0; i<t; i++)
    {
        scanf("%d %d", &R, &C);
        for (int x=0; x<R; x++)
            for (int y=0; y<C; y++)
                scanf("%d", G[x]+y);
        register long long s=0;
        register int not_over = 600;
        while (not_over)
        {
            not_over = 0;
            register int add = 0;
            for (register int x=0; x<R; x++)
                for (register int y=0; y<C; y++)
                {
                    add = proc(G, x, y);
                    if (add)
                    {
                        s += add;
                        not_over++;
                    }
                }
        }
        printf("Case #%d: %lld\n", i+1, s);
    }
    return 0;
}

(4) Checksum

Grace and Edsger are constructing a boolean matrix A. The element in -th row and -th column is represented by . They decide to note down the checksum (defined as bitwise XOR of given list of elements) along each row and column. Checksum of -th row is represented as . Checksum of -th column is represented as .
For example, if , , then and .

Once they finished the matrix, Edsger stores the matrix in his computer. However, due to a virus, some of the elements in matrix are replaced with −1 in Edsger's computer. Luckily, Edsger still remembers the checksum values. He would like to restore the matrix, and reaches out to Grace for help. After some investigation, it will take hours for Grace to recover the original value of from the disk. Given the final matrix , cost matrix , and checksums along each row () and column (), can you help Grace decide on the minimum total number of hours needed in order to restore the original matrix ?

问题简述

设一个矩阵的维度为，的元素由0或1组成。每一行、每一列都有对应的奇偶校验值，分别是向量, ，现在A中有一些元素被破坏掉了，用-1表示。对于每个被破坏的元素，恢复它的代价值为，这些数值构成了代价矩阵。求解如何在花费最小的代价的情况下恢复一部分元素，使得剩下的元素可以根据校验值推断出来。

输入

第一行为T，测试的个数。
以下每个测试有(2N+3)行，其中第一行只有一个N，表示矩阵的维度是；
接下来的N行，每行都有N个数字，表示矩阵A中的每个元素；
接下来的N行，每行都有N个数字，表示矩阵B中的每个元素；
接下来一行有N个数字，表示向量R；
接下来一行有N个数字，表示向量C。

输出

输出格式为 Case #x: y，表示第x个测试的最小代价为y。

数据范围

Memory limit: 1 GB.
.
, for all .
, for where , otherwise .
, for all .
, for all .
It is guaranteed that there exist at least one way to replace −1 in A with 0 or 1 such that R and C as satisfied.

Test Set 1
Time limit: 20 seconds.
.

Test Set 2
Time limit: 35 seconds.
.

Test Set 3
Time limit: 35 seconds.
.

样例输入

3
3
1 -1 0
0 1 0
1 1 1
0 1 0
0 0 0
0 0 0
1 1 1
0 0 1
2
-1 -1
-1 -1
1 10
100 1000
1 0
0 1
3
-1 -1 -1
-1 -1 -1
0 0 0
1 1 3
5 1 4
0 0 0
0 0 0
0 0 0

样例输出

Case #1: 0
Case #2: 1
Case #3: 2

分析

这个任务的目标是剩下的元素可以根据校验值推断出来，那么数学描述来看，就是：如果这一行或者列仅有一个元素为-1，那么就可以确定-1被破坏之前的值。直到所有的行、列中唯一的-1都被处理完后，如果整个矩阵已经没有-1，则说明被完全解出来，如果还存在一些行、列的-1个数大于1的，说明还需要恢复更多的元素。

这题中很多的信息是多余的，可以直接无视，比如说R和C向量的具体数值、矩阵A中除了-1之外的元素的具体数值其实都没用。因为你不知道这个-1恢复出来的是多少，所以其实A是无解的，我们只需要利用B中对应的位置求解总代价即可。

先写这么多，等有时间了继续更新。