T1 统计数字

算法：排序，STL Map。

C++ 代码 1：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    map<int, int> cnt;

    scanf("%d", &n);
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        cnt[x] ++ ;
    }

    for (auto& [k, v]: cnt)
        printf("%d %d\n", k, v);
    
    return 0;
}

foo.cc: In function 'int main()':
foo.cc:17:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   17 |     for (auto& [k, v]: cnt)
      |                ^

C++ 代码 2：

#include <bits/stdc++.h>
using namespace std;

int n;
int a[200010];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    
    sort (a, a + n);
    for (int i = 0; i < n; i ++ )
	{
        int j = i;
        while (a[j] == a[i] && j < n) j ++ ;
        cout << a[i] << ' ' << j - i << endl;
        i = j - 1;
    }
    
    return 0; 
}

T2 Vigenère 密码

算法：模拟，字符串处理。

C++ 代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string a, b;
    cin >> a >> b;

    string res;
    for (int i = 0; i < b.size(); i ++ )
    {
        char x = tolower(b[i]), y = tolower(a[i % a.size()]);
        char z = (x - 'a' - (y - 'a') + 26) % 26 + 'a';
        if (b[i] < 'a') z = toupper(z);
        res += z;
    }
    
    cout << res << endl;
    
    return 0;
}

T3 生活大爆炸版石头剪刀布

算法：模拟。

C++ 代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 210;

int n, n1, n2;
int a[N], b[N];
int g[5][5] = {
    {0, -1, 1, 1, -1},
    {1, 0, -1, 1, -1},
    {-1, 1, 0, -1, 1},
    {-1, -1, 1, 0, 1},
    {1, 1, -1, -1, 0},
};

int main()
{
    scanf("%d%d%d", &n, &n1, &n2);
    for (int i = 0; i < n1; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < n2; i ++ ) scanf("%d", &b[i]);

    int res1 = 0, res2 = 0;
    for (int i = 0; i < n; i ++ )
    {
        int x = a[i % n1], y = b[i % n2];
        int t = g[x][y];
        if (t > 0) res1 ++ ;
        else if (t < 0) res2 ++ ;
    }

    printf("%d %d\n", res1, res2);
    
    return 0;
}

T4 跳石头

算法：

二分，贪心 $O(NlogL)$

如果长度 $Len$ 可以满足，那么当长度小于 $Len$ 时也可以满足，所以我们可以二分出最大的 $Len$。

剩下的问题是如何判断给定 $Len$ 的情况下，能否最多拿走 $M$ 块石头，使得所有相邻两块石头之间的距离不小于 $Len$。

这一步可以贪心来做。从前往后扫描每个石头：

• 如果当前石头和上一块石头的距离小于 $Len$，则当前石头必须拿走，否则最小距离就会小于 $Len$。
• 如果当前石头和上一块石头的距离大于等于 $Len$，则必然存在一个最优解，使得当前石头可以被拿走。证明：如果存在一个最优解跟我们的贪心解留下的石头不同，那么找出第一个不同的石头，我们把最优解中的留下石头换成贪心解中留下的石头，会发现仍然会得到一组合法方案，通过这种方式，可以逐步将最优解调整成贪心解，且留下的石头数不变，所以贪心解就是一组最优解。

扫描结束后判断拿走的石头数量是否小于等于 $M$。

时间复杂度分析：

总共二分 $O(logL)$ 次，每次贪心的计算是 $O(N)$，因此总时间复杂度是 $O(NlogL)$。

C++ 代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 50010;

int L, n, m;
int w[N];

bool check(int mid)
{
	int res = 0;
	for (int i = 1, last = 0; i <= n; i ++ )
		if (w[i] - last < mid) res ++ ;
		else last = w[i];
	return res <= m;
}

int main()
{
	scanf("%d%d%d", &L, &n, &m);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
	w[++ n] = L;	
	
	int l = 1, r = L;
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	
	printf("%d\n", r);
	return 0;
}