#include <bits/stdc++.h>
using namespace std;
const int N = 400010;
int a[N];
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= k; i++) cin >> a[i];
sort(a + 1, a + 1 + k);//从小到大进行排序
int sum = 0;//获救数量
int num = 0;//标记猫的位置
for (int i = k; i >= 1; i--)
{
if (num < a[i])//猫还没有跑到当前遍历到的老鼠的位置，代表该老鼠可以获救
{
sum++;
num += n - a[i];//更新老鼠获救之后猫的位置
}
}
cout << sum << endl;
}
return 0;
}
//题意问最多能能有几只老鼠获救，肯定最靠近门的老鼠最先获救，对数组按照从小到大的顺序排完序之后倒序考虑获救情况，用num标记猫当前位置，
用sum标记获救老鼠的数量，如果猫的位置(num)还没有到老鼠的位置（<a[i]），就代表这只老鼠可以获救。
K - Missing Bigram
#include <bits/stdc++.h>
using namespace std;
int t;
int n;
int main()
{
cin >> t;
while (t--)
{
char op[110][5];
cin >> n;
for (int i = 1; i <= n - 2; i++)
{
scanf("%s", op[i]);//依次读入字符串
}
int sum = 2;//统计一共输出了多少个字符，最后与n进行比较
cout << op[1][0];
cout << op[1][1];//第一个串不做处理直接输出
for (int i = 2; i <= n - 2;)
{
if (op[i][0] != op[i - 1][1])//如果不相等代表中间某一个被删除了，就把被删除那个补上
{
cout << op[i][0];
op[i - 1][0] = op[i - 1][1];//把删除的那个补上，补到前一个位置
op[i - 1][1] = op[i][0];
sum++;//输出一个加一次
}
else
{
cout << op[i][1];//如果前后相等就输出后一个的第二个值（因为前一个的后一个值与后一个的前一个值是同一个）
sum++;
i++;//相等就往后挪一位
}
}
if (sum < n)//如果输出的字符个数小于n，就在最后补上一个（最后一个字符串可以任补）
{
cout << op[n - 2][1];
}
cout << endl;
}
return 0;
}
//题意是给定一个字符串，拆成两两一组，然后删掉其中一组复原字符串，用循环去看前后两个字符串连接的那一部分是否相等，相等就可以看作中间没有被删除
然后输出没重复的那一部分，如不相同就补上前面删掉的那一组，然后继续循环
L - Chess Tournament
#include <bits/stdc++.h>
using namespace std;
char g[55][55];
int st[55];//判断2类型是否符合2的条件
int main()
{
int t;
cin >> t;
while (t--)
{
memset(st, 0, sizeof st);//将数组重置为0
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j) g[i][j] = 'X';
else g[i][j] = '.';
}
}//将字符数组初始化，对角线位置初始为X
string s;
cin >> s;
int num = 0;//统计2类型的数量
int sum = 0;//统计1类型的数量
bool flag = 0;//标记是否存在
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '1') sum++;
else num++;
}
if (num == 0)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j) g[i][j] = 'X';
else g[i][j] = '=';
}
}
}//不存在2类型的话除了对角线之外全是=
else
{
if (num == 1 || num == 2)flag = 1;//分析会得到当2类型的为1或者2一定不会存在，其他情况都是存在的
else
{
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '1')
{
for (int j = 0; j < n; j++)
{
if(i != j)
g[i][j] = g[j][i] = '=';
}
}
}//先把1类型的处理好，当1类型的处理为=时方便考虑2类型
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '2')//处理2类型
{
for (int j = 0; j < n; j++)
{
if (g[i][j] == '+' && !st[i])
{
st[i] = 1;
}//2类型的那一行，某个位置为+，代表符合2类型，就把第i行标记一下
else if (g[i][j] == '.' && !st[i])
{
g[i][j] = '+';
g[j][i] = '-';
st[i] = 1;
}//2类型不满足2的条件，就把第i行第j个更新为+，同时更新第j行第i列和标记数组
else if (g[i][j] == '.' && st[i])
{
g[i][j] = '-';
g[j][i] = '+';
}//满足2的条件但是之前没有遍历到的点更新为-
}
}
}
}
}
if (!flag)//flag = 0代表存在
{
puts("YES");
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << g[i][j];
}
cout << endl;
}
}
else//不存在直接输出NO
{
puts("NO");
}
}
}
//判断存不存在只需要看2类型的数量，如果存在，就先把1类型的处理完（处理成等号便于处理2类型），然后接着处理2类型，分满足2的条件没遍历到的，不满足2
的条件的，刚满足2条件的三种情况进行讨论。