正文

题目1

题目链接
题目大意：
小明有a个1元硬币，b个2元硬币；
小明想要购买一个商品，并且不想找零；
现在小明想知道自己无法给到最低价格是多少；

比如说1个1元硬币，1个2元硬币，最低价格就是4元；
比如说0个1元硬币，1个2元硬币，最低价格就是1元；（不能找零）

输入：
第一行，整数? 表示t个样例 ? (1≤?≤1e4)
每个样例一行，整数 ?? and ?? (0≤??,??≤1e8)

输出：
每个样例一行，输出最低价格；

Examples
input
5
1 1
4 0
0 2
0 0
2314 2374

output
4
5
1
1
7063

题目解析：
如果有1元硬币，那么必然可以给到a+2*b价格内的所有整数；
如果没有1元硬币，那么1元就无法给到；

class Solution {
    static const int N = 201010;
    int a[N];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int x, y;
            cin >> x >> y;
            cout << (x > 0 ? x+1+2*y : 1) << endl;
        }
    }
}
ac;

题目2

题目链接
题目大意：
小明有n种糖果，每种糖果分别有a[i]颗；
现在小明开始吃糖果，并且每次只吃剩下糖果数量最多的那种，如果有多种则可以任意选择一种数量最多的糖果；

小明想知道最终，能不能吃完所有糖果，并且满足没有连续2天吃到一样的糖果；

输入：
第一行，整数? 表示t个样例 ? (1≤?≤1e4)
每个样例两行，第一行整数 ? (1≤?≤2⋅1e5)
第二行是n个整数?? (1≤??≤1e9)

输出：
每个样例一行，如果可以输出YES，如果不行则输出NO；

Examples
input
4
aabbcc
aaab
aaa
abba

output
0
2
1
2

题目解析：
因为题目限定了每次只吃数量最多的糖果，那么可以将数组排序，这样方便后续抉择；
我们唯一能选的，就是当出现两种糖果一样多情况，我们要如何吃；
容易知道，假如有两个糖果一样多，只要交替吃就行了；
那么问题就变成，最多和次最多的两个糖果，能不能顺利达到数量一致的情况；
容易知道相差超过1就无法达到，因为需要连续两天吃一样的最多数量的糖果。

class Solution {
    static const int N = 201010;
    int a[N];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
            }
            sort(a, a + n);
            bool ans = 0;
            if (n == 1) {
                ans = a[0] <= 1;
            }
            else {
                ans = (a[n - 1] - a[n - 2]) <= 1;
            }
            cout << (ans ? "YES" : "NO") << endl;
        }
    }
}
ac;

题目3

题目链接
题目大意：
字符串s可以成为偶字符串，如果字符串满足：
1、字符串的长度为偶数；
2、所有奇数位的字符?[?]，满足?[?]=?[?+1]；

比如说“aa”、“aabb”、“aabbcc”就是偶字符串，但是“aaa”、“aaab”、“abba”就不是偶字符串；
现在想知道，最少移除掉字符串s中多少个字符，可以使得字符串s变成偶字符串；

输入：
第一行，整数? 表示t个样例 ? (1≤?≤1e4)
每个样例一行，字符串 ? (1≤|?|≤2⋅105),

输出：
每个样例一行，输出最少移除的字符串；

Examples
input
4
aabbcc
aaab
aaa
abba

output
0
2
1
2

题目解析：

dp[i] 表示前i个字符，能找到的最长even字符串；
那么对于第i个字符，我们有两个选择：
取第i个字符，那么找到最近一个和第i个字符相近的位置k，我们有dp[i]=max(dp[i], dp[k-1] + 2)；
不取第i个字符，那么有dp[i]=max(dp[i], dp[i - 1])；

class Solution {
    static const int N = 201010;
    char str[N];
    int dp[N];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> (str + 1);
            int n = strlen(str + 1);
            int pos[26] = {0};
            for (int i = 1; i <= n; ++i) {
                dp[i] = dp[i - 1];
                int index = str[i] - 'a';
                if (pos[index]) { //
                    dp[i] = max(dp[i], dp[pos[index] - 1] + 2);
                }
                pos[index] = i;
            }
            cout << n - dp[n] << endl;
        }
    }
}
ac;

题目4

题目链接
题目大意：
给出n个整数的数组a，其中数组的元素绝对值满足 abs(a[i]) <= 2；
现在可以移除数组前面x个元素和后面y的个元素，求剩下的元素乘积尽可能的大；

输入：
第一行，整数? 表示t个样例 ? (1≤?≤1e4)
每个样例两行，第一行是整数? (1≤?≤2⋅1e5)
接下来是n个整数?1,?2,…,?? (|??|≤2)；

输出：
每个样例一行，包括整数x和y，x和y分别表示：移除数组前面x个元素和后面y的个元素；
允许移除所有的元素，这样乘积为1；
如果有多个答案，输出任意一个；

Examples
input
5
4
1 2 -1 2
3
1 1 -2
5
2 0 -2 2 -1
3
-2 -1 -1
3
-1 -2 -2

output

0 2
3 0
2 0
0 1
1 0

题目解析：
题目的要求是乘积尽可能大，那么数字0首先被排除，因为0乘以任意数字都0，而移除所有元素的乘积结果都是1；
那么按照0，将数组切分成若干段，题目变成了在某一个子区间[left, right]中，寻找乘积最大的子区间；
假如区间[left, right]没有负数，或者有偶数个负数，那么这个区间所有数字的乘积就是最大的；
假如区间[left, right]有奇数个负数，那么肯定是去掉最左边的负数（假如位置是posLeft），或者去掉最右边的负数（假如位置是posRight）；
这样就可以得到区间[left, right]的最大乘积；

由于乘积会比较大，这里只需要统计2和-2的数量即可，这个结果越大，则乘积越大。

class Solution {
    static const int N = 201010;
    int a[N];
    int ansTotal, ansLeft, ansRight;
    int pos[N], k;
    
    void find(int left, int right) {
        int total = 0, posLeft = 0, posRight = right;
        int cntTotal = 0, cntLeft = 0, cntRight = 0;
        for (int i = left; i <= right; ++i) {
            if (a[i] < 0) {
                ++total;
            }
            if (abs(a[i]) == 2) {
                ++cntTotal;
            }
            if (a[i] < 0 && !posLeft) {
                posLeft = i;
            }
            if (a[i] < 0) {
                posRight = i;
            }
        }
        for (int i = left; i <= posLeft; ++i) {
            if (abs(a[i]) == 2) {
                ++cntLeft;
            }
        }
        for (int i = posRight; i <= right; ++i) {
            if (abs(a[i]) == 2) {
                ++cntRight;
            }
        }
        if (total % 2 == 0) {
            if (cntTotal > ansTotal) {
                ansTotal = cntTotal;
                ansLeft = left;
                ansRight = right;
            }
        }
        else {
            if (cntLeft < cntRight) {
                cntTotal -= cntLeft;
                if (cntTotal > ansTotal) {
                    ansTotal = cntTotal;
                    ansLeft = posLeft + 1;
                    ansRight = right;
                }
            }
            else {
                cntTotal -= cntRight;
                if (cntTotal > ansTotal) {
                    ansTotal = cntTotal;
                    ansLeft = left;
                    ansRight = posRight - 1;
                }
            }
        }
    }

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            
            for (int i = 1; i <= n; ++i) {
                scanf("%d", &a[i]);
            }
            
            k = 0;
            pos[k++]= 0;
            for (int i = 1; i <= n; ++i) {
                if (a[i] == 0) { //
                    pos[k++] = i;
                }
            }
            pos[k++] = n + 1;
            ansTotal = 0;
            ansLeft = 1;
            ansRight = 0;
            for (int i = 1; i < k; ++i) {
                int l = pos[i - 1];
                int r = pos[i]; // (l, r)
                find(l + 1, r - 1);
            }
            cout << ansLeft - 1 << " " << (n - ansRight) << endl;
        }
    }
}
ac;

题目5

题目链接
题目大意：
给出一个n x n的矩阵，矩阵由数字0和1组成；
现在可以对矩阵进行下列操作：
1、将数组的每一行向上移动；
2、将数组的每一行向下移动；
2、将数组的每一列向左移动；
2、将数组的每一列向右移动；
这个操作是没有代价的，可以进行任意次；
然后还可以对矩阵中任何一个数字进行异或（XOR）操作，这个操作的代价是1；

现在想要把整个矩阵变成单元矩阵，问最小的代价是多少；
（单元矩阵是一个对角线为非零元素，其它元素为零的方形矩阵）

输入：
第一行，整数? 表示t个样例 ? (1≤?≤1e4)
每个样例两行，第一行是整数? (1≤?≤2000)
接下来是n x n的01矩阵；

输出：
每个样例一行，输出最小的代价。

Examples
input
4

3
010
011
100

5
00010
00001
10000
01000
00100

2
10
10

4
1111
1011
1111
1111
output
1
0
2
11

题目解析：
题目的要求是构造单元矩阵的代价最小，那么需要尽可能利用无代价的4个位移操作；
以简单的3阶矩阵来分析，对于矩阵
010
001
010
我们可以拼接4个矩阵，得到
010 010
001 001
010 010
----------
010 010
001 001
010 010

以左移一列为例，结果就是图中左上角的2-4列，如下：
0 100
0 010
0 100

按照这个思路，其实就是在4个n x n矩阵拼出来的大矩阵中，找到一个n x n子矩阵，并且斜对角线的1尽可能多；
那么就直接从每一行的第一列开始向右下角遍历，保持长度为n的斜对角线，存在尽可能多的1；
但是直接拼接4个矩阵去模拟，整体实现复杂度比较高；对于第i行第j列的元素a[i][j]，右下角其实就是a[i+1][j+1]，其中：
j是从1到n，因为每行的遍历都是从最左开始；
i可能会存在大于n的情况，此时可以对n取模，保证数组不越界；

假设对角线上最多的1数量为maxSize，矩阵中所有1的数量是totalSize；
那么答案就是ans=(total - maxSize) + (n - maxSize) 。

class Solution {
    static const int N = 3010;
    char a[N][N];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            
            for (int i = 1; i <= n; ++i) {
                cin >> (a[i] + 1);
            }
            
            int total = 0, maxSize = 0;
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    total += ('1' == a[i][j]);
                }
                // 从a[i][1]开始，向右下角遍历
                int tmpSize = 0;
                for (int k = 0; k < n; ++k) {
                    int x = (i - 1 + k) % n + 1;
                    int y = 1 + k;
//                    cout << x << " " << y << endl;
                    if (a[x][y] == '1') {
                        ++tmpSize;
                    }
                }
                maxSize = max(maxSize, tmpSize);
            }
            cout << (total - maxSize) + (n - maxSize) << endl;
        }
    }
}
ac;

题目6

题目链接
题目大意：
给出由+和-组成的字符串，我们称字符串为平衡的字符串，假如+和-的字符是相同的；
现在可以对字符串执行操作，每次将两个相邻的-号合并为+号；
假如若干次操作之后，字符串变成了平衡的字符串，那么这个字符串可以称之为特殊的字符串；

现在给出长度为n的字符串，问字符串中有多少子串是特殊的；

输入：
第一行，整数? 表示t个样例 (1≤?≤500)
每个样例两行，第一行是整数 ? (1≤?≤3000)
第二行是字符串；

输出：
输出满足要求的子串数量；

Examples
input
5
3
+-+
5
-+---
4
----
7
--+---+
6
+++---
output
2
4
2
7
4

题目解析：
这是easy难度，题目给出来的范围比较小；
那么可以使用最暴力的办法，O(N*N)的复杂度，枚举所有字符串的子串；
再分别计算这个子串是否符合要求；
判断一个字符串是否是特殊的，可以遍历整个字符串中+和-的数量（假如总数是x和y）；
如果x==y，或者x<y并且(y-x)%3==0 && (y-x)%3 < z，则子串满足要求。
统计x或者y是一个比较快的过程，用countx[i][j]表示区间[i, j]内的+数量，那么countx[i][j]可以由countx[i][j-1]来快速计算；y的计算同理；

class Solution {
    static const int N = 3010;
    char str[N];
    int a[N];
    int dp[N]; // dp[i] 前i个字符，以i结尾，并且x==y的子串数量
    int countx[N][N], county[N][N];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            cin >> (str + 1);
            // 如果x==y，或者x<y并且`(y-x)%3==0
            
            int ans = 0;
            for (int i = 1; i <= n; ++i) {
                for (int j = i; j <= n; ++j) {
                    if (str[j] == '+') {
                        countx[i][j] = countx[i][j - 1] + 1;
                        county[i][j] = county[i][j - 1];
                    }
                    else {
                        countx[i][j] = countx[i][j - 1];
                        county[i][j] = county[i][j - 1] + 1;
                    }
                    if (countx[i][j] == county[i][j] || ((countx[i][j] < county[i][j] && (county[i][j] - countx[i][j]) % 3 == 0))) {
                        ++ans;
                    }
                }
            }
            cout << ans << endl;
        }
    }
}
ac;

题目7

题目链接
题目大意：
给出由+和-组成的字符串，我们称字符串为平衡的字符串，假如+和-的字符是相同的；
现在可以对字符串执行操作，每次将两个相邻的-号合并为+号；假如若干次操作之后，字符串变成了平衡的字符串，那么这个字符串可以称之为特殊的字符串；

现在给出长度为n的字符串，问字符串中有多少子串是特殊的；

输入：
第一行，整数? 表示t个样例
每个样例两行，第一行是整数?
第二行是字符串；

输出：
输出满足要求的子串数量；

Examples
input
5
3
+-+
5
-+---
4
----
7
--+---+
6
+++---
output
2
4
2
7
4

题目解析：
这是hard难度，题目给出来的范围比较大，O(N*N)的复杂度枚举所有字符串的子串的方式已经不适用；
首先需要对我们已经采用的方法进行简化，countx和county其实可以简化为countx-county的方式，并且由二维简化为一维：
我们用sum[i]表示前i个字符相加的结果，字符+表示-1，字符-表示+1；
那么子串[i, j]可以用sum[j] - sum[i - 1]的方式快速得到结果，(sum[j] - sum[i - 1])%3==0 && sum[j] >= sum[i - 1] 表示有解；

从左到右遍历字符串，对于第j个字符，首先得到sum[j]，然后遍历i∈[1, j-1]判断 (sum[j] - sum[i - 1])%3==0 && sum[j] >= sum[i - 1] 的数量；
这个遍历过程存在较多重复计算，我们只在乎i∈[1, j-1]这个区间中sum[i]的值，而对i的位置并不关心，并且sum[i]的值最多也只有2n+1种可能（取值范围是[-n, n]）；
那么如果我们把sum[i]的结果直接存到[-n, n] 这个区间上，我们就可以直接获取遍历这个区间的值即可。
以n=4为例，sum[i]的结果可能有[-4,-3,-2,-1,0,1,2,3,4]，如果sum[j]=3，那么我们只需要取sum[i]=3/0/-3的值；如果sum[j]=2，那么我们只需要取sum[i]=-1/-4的值；
由于我们只在乎%3的结果，我们可以用cnt[0,1,2]来表示sum[i]%3的值和，这样从数组中取值就不需要遍历，可以很快取到某个余数的值；

但是这里还有一个条件是sum[j] >= sum[i - 1]，sum[j]=0的时候，sum[i]=3这种情况是不允许的，所以cnt的值是需要维护的，维护方式就是：
当我们sum[j]变小的时候，cnt作为累加和，要退掉之前累加的值；
比如说sum[j]=2的时候，cnt累加了[-4, 2]的区间；sum[j+1]=1的时候，cnt累加了[-4, 1]的区间；也就是cnt需要退掉sum[j]=2的值；

由于sum[i]的取值范围是[-n, n] 我们可以将sum[i]+n，这样取值范围变成[0, 2n]，好处是可以用数组来表示，并且不影响我们对结果的结算，因为 (sum[j] - sum[i - 1])等于 (sum[j] + n）-（sum[i-1] + n），sum[j] >= sum[i-1] 等于 sum[j] + n >= sum[i-1] + n；

class Solution {
    static const int N = 200010;
    char str[N];
    int sum[N * 2];
    int cnt[3];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            cin >> (str + 1);
            lld ans = 0;
            int preCount = n;
            memset(cnt, 0, sizeof(cnt));
            memset(sum, 0, sizeof(sum));
            sum[preCount] = 1;
            cnt[preCount % 3] = 1;
            for (int i = 1; i <= n; ++i) {
                int curCount = preCount + (str[i] == '-' ? 1 : -1);
                int index = curCount % 3;
                if (curCount < preCount) {
                    cnt[preCount % 3] -= sum[preCount];
                }
                else {
                    cnt[curCount % 3] += sum[curCount];
                }
                ans += cnt[index % 3];
                cnt[curCount % 3]++;
                sum[curCount]++;
                preCount = curCount;
            }
            cout << ans << endl;
        }
    }
}
ac;

总结

趁着假日闲暇时光以及工作间隙，把1660CF的7个题目都AC了。
有一丝成就感，毕竟已经是退役接近十年的选手；也有一丝挫败感，在毕业多年之后，水平已经变成只能在DIV3达成AK成就。
在最应该学习的时候，没有努力学习，那么未来即使有机会也很难超越自己。当年不擅长做的数论题，现在依旧不会做。
这让我逐渐明白一个道理：面对困难和挑战，人在当下的选择，往往会影响后续一辈子。
不是说生活一定要迎难而上，一定要吃得苦中苦方为人上人，而是思考和确定自己的目标、选择、动力，然后再努力前行。