题目1

题目链接
题目大意：
给出一个字符串（由26个大写字母组成），询问这个字符串中，是否相同的字母都连在一起。

输入：
第一行整数t，表示有t个样例（1≤?≤1000）
每个样例两行，第一行是整数n，表示字符串长度 (1≤?≤50)
第二行是字符串
输出：
如果满足要求，则输出YES；
如果不满足要求，则输出NO；

Examples
input
5
3
ABA
11
DDBBCCCBBEZ
7
FFGZZZY
1
Z
2
AB

output
NO
NO
YES
YES
YES

题目解析：
用一个数组记录已经出现的字符串，从左到右枚举字符串；
对于第i个字符，如果和第i-1个字符不相同，则判断是否出现过：
已出现过则不满足要求；
未出现则标识该字符已出现。

class Solution {
    static const int N = 100010;
public:
    int n, m;
    string str;
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> n;
            cin >> str;
            int a[256] = {0}, ok = 1;
            a[str[0]] = 1;
            for (int i = 1; i < n; ++i) {
                if (str[i] == str[i-1]) {
                    continue;;
                }
                else {
                    if (a[str[i]]) {
                        ok = 0;
                    }
                    else {
                        a[str[i]] = 1;
                    }
                }
            }
            if (ok) {
                cout << "YES" << endl;
            }
            else {
                cout << "NO" << endl;
            }
        }
    }
}
ac;

题目2

题目链接
题目大意：
给出一个数字n，求出[1,n]的区间中，有多少整数是可以满足，所有数字都是相同的。

输入：
第一行是整数t，表示有t个样例(1≤?≤1e4).
每个样例一行，第一行是整数n(1≤?≤1e9).
输出：
每个样例一行，输出1到n的整数中，有多少个由相同数字组成的数。

Examples
input
6
1
2
3
4
5
100

output
1
2
3
4
5
18

题目解析：
如果直接遍历数字1到n，可以算出来有多少个整数满足要求。
因为n比较比较大，这种做法会超时。
注意到满足要求的数字应该不多，我们可以直接满足要求的数字：
先看一位数的有多少个数字；
再看二位数的有多少个数字；
...
直到枚举出来的数字，比n还要大。

class Solution {
    static const int N = 100010;
public:
    int n, m;
    string str;
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> n;
            int ans = 0;
            int current = 1, cnt = 1;
            while (current * cnt <= n) {
                ++ans;
                ++cnt;
                if (cnt > 9) {
                    current = current * 10 + 1;
                    cnt = 1;
                }
            }
            cout << ans << endl;
        }
    }
}
ac;

题目3

题目链接
题目大意：
给出一个数字n，构造n * n的矩阵，要求：
相邻的数字，绝对值之差要大于1；
每个数字可以和上下左右，四个方向的数字相邻；
矩阵中的数字是1~n * n，没有重复；

输入：
第一行是整数t，表示有t个样例 (1≤?≤100).
每个样例第一行是整数? (1≤?≤100).
输出：
如果有解，则输出n行，每行n个整数；
如果无解则输出-1；

Examples
input
3
1
2
3

output
1
-1
2 9 7
4 6 3
1 8 5

题目解析：
1只有一个解，2无解；
从3开始，可以采用间隔的方式先填充数字；
1 0 2
0 3 0
4 0 5
如上，先从上到下，从左到右填充；
最后补齐
1 5 2
6 3 7
4 8 5
因为我们都是间隔着填充，相邻的数字只差，肯定大于1，满足要求。

class Solution {
    static const int N = 100010;
public:
    int n, m;
    int a[101][101];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> n;
            if (n == 1) {
                cout << 1 << endl;
            }
            else if (n == 2) {
                cout << -1 << endl;
            }
            else {
                int cnt = 1, x = 0, y = 0;
                while (cnt <= n*n) {
                    a[x][y] = cnt;
                    ++cnt;
                    y += 2;
                    if (y >= n) {
                        x += 1;
                        y -= n;
                    }
                    if (x >= n) {
                        x = 0;
                        y = 1;
                    }
                }
                for (int i = 0; i < n; ++i) {
                    for (int j = 0; j < n; ++j) {
                        cout << a[i][j] << " ";
                    }
                    cout << endl;
                }
            }
        }
    }
}
ac;

题目4

题目链接
题目大意：
给出n个数字的数组，问数组中存在多少个(i, j)的组合，满足i<j 且 a[j]-a[i]=j-i；

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

输出：
输出满足要求的组合数量。

Examples
input
4
6
3 5 1 4 6 6
3
1 2 3
4
1 3 3 4
6
1 6 3 4 5 6

output
1
3
3
10

题目解析：
将题目要求的 a[j]-a[i]=j-i 换一下位置，得到 (a[j] - j)= (a[i] - i)；
那么将所有的数字，减去当前的位置，然后排序，即可知道每一组数字的数量；
每一组数字假设有k个，那么就有k*(k-1)/2的可能。

class Solution {
    static const int N = 200010;
public:
    int n, m;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> n;
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
                a[i] -= i;
            }
            a[n] = 0;
            sort(a, a + n);
            lld ans = 0, cnt = 1;
            for (int i = 1; i<= n; ++i) {
                if (a[i] != a[i - 1]) {
                    ans += cnt * (cnt - 1) / 2;
                    cnt = 1;
                }
                else {
                    ++cnt;
                }
            }
            cout << ans << endl;
        }
    }
}
ac;

题目5

题目链接
题目大意：
给出长度为n的字符串，'*'表示绵羊， '.'表示空地；
每次可以把绵羊移动到相邻的空地，问需要移动多少次，才能将所有的绵羊赶在一起。

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

输出：
最小的移动次数。

Examples
input

 5
 6
 **.*..
 5
 *****
 3
 .*.
 3
 ...
 10
 *.*...*.**

output
1
0
0
0
9

题目解析：
方法1：
暴力，假设羊最终集中在区间[left, right]上面，枚举left的位置，再用贪心从左到右匹配羊的位置。

方法2：
动态规划
dpLeft[i]表示，前i个位置中的所有羊，都集中在位置i左边；
dpRight[i]表示，[i, n]的位置中所有羊，都集中在位置i的右边；
这样只要得到结果之后，只要枚举每一个位置即可。

数据范围较大，没用long long 错了2次。

class Solution {
    static const int N = 1000010;
public:
    int n, m;
    string str;
    pair<lld, lld> dpLeft[N], dpRight[N]; // first 是最小代价，second的当前绵羊数量
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> n;
            cin >> str;
            dpLeft[0] = make_pair(0, 0);
            for (int i = 1; i <= n; ++i) {
                char c = str[i - 1];
                if (c == '*') {
                    dpLeft[i].first = dpLeft[i-1].first;
                    dpLeft[i].second = dpLeft[i-1].second + 1;
                }
                else {
                    dpLeft[i].first = dpLeft[i-1].first + dpLeft[i-1].second;
                    dpLeft[i].second = dpLeft[i-1].second;
                }
            }
            dpRight[n+1] = make_pair(0, 0);
            for (int i = n; i > 0; --i) {
                char c = str[i - 1];
                if (c == '*') {
                    dpRight[i].first = dpRight[i+1].first;
                    dpRight[i].second = dpRight[i+1].second + 1;
                }
                else {
                    dpRight[i].first = dpRight[i+1].first+dpRight[i+1].second;
                    dpRight[i].second = dpRight[i+1].second;
                }
            }
            lld ans = dpRight[1].first;
            for (int i = 0; i <= n; ++i) {
                ans = min(ans, dpLeft[i].first + dpRight[i + 1].first);
            }
            cout << ans << endl;
        }
    }
}
ac;