前言
强身健体带来的好处太多了，肉体的强壮也会增加灵魂的韧性。
第一题
题目： Happy Birthday, Polycarp!
题意：
给定一个整数n，询问所有小于等于n的相同数的数量。相同数：如果某个正整数每一位的数字都相同，则称之为相同数。例如：1，2，3，11，555。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
接下来第二行到第n+1行是n个样例，每个样例是一个正整数。
输出格式
对每个样例输出一个整数。
数据范围
1 ≤ t ≤ 104
1 ≤ n ≤ 109
输入样例：
6
18
1
9
100500
33
1000000000输出样例：
10
1
9
45
12
81思路：
- 很容易注意到每增加一位，相同数增加9个，所以我们可以先计算n的位数，然后单独判断n最高位有多少个相同数。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<vector>
using namespace std;
const int N = 4e5 + 10;
#define ll long long
int main()
{
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
//k与n的位数相同，且仅由1组成。m表示n的位数。
ll k = 1,m=0,c=n;
while (c)c/=10,k =1+k*10,m++;
ll sum = (m - 1) * 9;
//cout << "??" << sum <<" " <<k<< endl;
k /= 10;
//特判n最高位有多少相同数。
for (ll i = 1; i <= 9; ++i)if (k * i <= n)sum++;
cout << sum << endl;
}
return 0;
}
第二题
题目：Make Them Odd
题意：
给我们一个长度为n的数列，我们每次可以选择数列中任意个值相同的偶数，使其依次除2，询问最少要多少次操作才可以使得数列中全部为奇数。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例共有两行，第一行是一个整数n，表示数列中整数的个数。
每个样例第二行是n个整数。
输出格式
对于每个样例，输出一个整数，表示操作数。
数据范围
1 ≤ t ≤ 104
1 ≤ n ≤ 2 × 105
对于每个样例，一定是由n个1~n的不同的数组成的。
所有样例的n总和不超过2 × 105。
输入样例：
4
6
40 6 40 3 20 1
1
1024
4
2 4 8 16
3
3 1 7输出样例：
4
10
4
0思路：
- 因为我们每次操作都可以选择任意个相同的数，为了使得操作尽量的少，我们需要使得所选择的数尽量的多。那么显然我们需要从大的数字开始除，在除的过程中每次有其他数可以加入时，就将其直接加入，然后依次遍历，保证所以数都是奇数即可。
- 问题在于如果直接去找其它数，会超时。
- 考虑用
map记录所除过的数，这样我们就不用去找其他数，只需要遍历一次整个数组就可以。从大数开始，不断除到为奇数，并记录过程中的数，遍历数组时，已经记录过的数直接跳过。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<vector>
using namespace std;
const int N = 2e5 + 10;
#define ll long long
int a[N];
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
//将数列升序排序
sort(a + 1, a + n + 1);
//p用来记录是否被除过
unordered_map<int, int>p;
ll sum = 0;
for (int i = n; i >= 1; --i)
{
//如果已经被除过，那么直接跳过
if (p[a[i]])continue;
p[a[i]] = 1;
//否则一直除到变为奇数为止
while (!(a[i] & 1))
{
a[i] /= 2;
p[a[i]] = 1;
sum++;
}
}
cout << sum << endl;
}
return 0;
}
第三题
题目： As Simple as One and Two
题意：
给定一个字符串，我们可以任意的去除字符串中的某些字符，使得字符串中不会出现 one 和 two ，询问最少需要去除几个字符，并给出这些字符的位置。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例有一行，仅由小写英文字母组成的字符串。
输出格式
对于每个样例，输出两行。
第一行是一个整数x，表示最少删除的字符数。
第二行是x个整数，依次用空格隔开，表示删除的字符的位置。
如果x为零，第二行输出空行。
数据范围
1 ≤ t ≤ 104
单个字符串的长度不会超过1.5×105
所有样例的总长度不会超过1.5×106。
输入样例：
4
onetwone
testme
oneoneone
twotwo输出样例：
2
6 3
0
3
4 1 7
2
1 4
思路：
- 如果字符串中出现
one和two这样的子串，那么分别去掉n和w是最好的选择，因为形如oonee这样的组合我们无论去掉o还是e都会形成新的one，two同理。 - 对于
one我们直接去掉n就可以，但是对于two，需要注意是否会有twone这样的存在，这时我们只需要去掉o即可去掉一个two和一个one。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<vector>
using namespace std;
const int N = 2e5 + 10;
#define ll long long
int a[N];
int main()
{
int t;
cin >> t;
while (t--)
{
//s存输入的字符串，c存需要去掉的字符的位置
string s;
cin >> s;
vector<int>c;
int m = s.size();
for (int i = 0; i < m; ++i)
{
//对于one直接去掉n
if (i + 2 < m && s[i] == 'o' && s[i + 1] == 'n' && s[i + 2] == 'e')
{
c.push_back(i + 1);
s[i + 1] = '1';
}
//对于two需要特判twone这样的情况
else if (i+2<m && (s[i] == 't' && s[i + 1] == 'w' && s[i + 2] == 'o'))
{
//存在twone，去掉o，否则去掉w
if (i + 4 < m && s[i + 3] == 'n' && s[i + 4] == 'e')
{
c.push_back(i + 2);
s[i + 2] = '1';
}
else
{
c.push_back(i + 1);
s[i + 1] = '1';
}
}
}
cout << c.size() << endl;
for (int i = 0; i < c.size(); ++i)cout << c[i]+1 << " ";
cout << endl;
}
return 0;
}
第四题
题目： Let’s Play the Words?
题意：
有一个游戏，规则是大家自由的用0和1创造字符串，条件是所创造字符串的第一个字符必须和上一个人的最后一个字符相同。
Polycarp有一组字符串，他希望通过尽量少的反转其中某些字符串，使得自己的这组字符串可以满足上述条件。
但是Polycarp有两个条件：
1.反转后的字符串不能与其他字符串相同。
2.最后这组字符串只要能通过某种顺序符合游戏规则即可。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例第一行是一个整数n，表示有n个字符串。
每个样例的第2到n+1行是n行字符串，表示Polycarp的这组字符。
输出格式
对于每个样例，如果可以通过调整使得Polycarp的字符串数组符合游戏规则，答案有两行，第一行输出最少需要反转的字符串的个数，第二行输出反转字符串的位置。如果个数为0，第二行输出空行。
如果不能，输出-1。
数据范围
1 ≤ t ≤ 104
1 ≤ n ≤ 2×105
对于每个样例，字符串长度之和不会超过4×106。
对于所有样例，所有字符串个数不会超过2×105，所有字符串长度之和不会超过4×106。
所有字符串均唯一。
输入样例：
4
4
0001
1000
0011
0111
3
010
101
0
2
00000
00001
4
01
001
0001
00001输出样例：
1
3
-1
0
2
1 2 思路：
- 首先我们可以考虑这个题的本质，因为只要求后一个字符串的第一个字符和上一个字符串的最后一个字符相同，所以实际上我们只需要考虑每个字符串的开头和结尾两个字符即可。
- 这样问题就简化为了判断00,01,10,11这四种字符的数量。
- 什么时候无解？显然是所有的字符串都由00和11组成时。需要注意如果仅由00或者11组成，也是有解的。
- 所有的00可以组合在一起视为一个00，所有的11同理可以视为一个11，那么只要有一个01或者10就可以有解。而所有的01和10又可以任意的组合在一起。
- 每个01可以和一个10组合，那么我们直接输出01和10差值的一半即可，这就是最少需要反转的字符串数量。
- 因为要输出所反转字符串的位置，所以需要单独记录反转后不会依旧唯一的01和10的位置。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int N = 2e5 + 10;
#define ll long long
char s[N][3];
int main()
{
int t;
cin >> t;
while (t--)
{
//一共只有4种：00 01 10 11
//其中01和10可以任意配对
//所有的00可以视为1个00，所有的11可以视为1个11
//那么只剩下01和10，找到两者差值的一半，输出反转不影响
int n;
cin >> n;
string c;
//y记录出现过的字符串，用来记录哪些字符串可以反转。
unordered_map<string, int>y;
//u标记的位置标示该字符串不可以反转
int u[N]={0};
//a[1]到a[4]记录00 01 10 11的数量
int a[5] = {0};//00 01 10 11
//p和q记录可以反转的01和10的位置
vector<int>p, q;//01 10
for (int i = 1; i <= n; ++i)
{
cin >> c;
//仅保留每个字符串的开头和结尾两个字符
s[i][0] = c[0], s[i][1] = c[c.size() - 1];
//如果该字符串出现过，标记该字符串的位置
if (y[c])
{
u[y[c]] = u[i] = 1;
}
//否则将字符串和其反转后的字符串均标记一次
else
{
y[c] = i;
reverse(c.begin(), c.end());
y[c] = i;
}
}
//统计四种字符串的位置，记录可以反转的01和10的位置
for (int i = 1; i <= n; ++i)
{
if (s[i][0] == s[i][1])
{
if (s[i][0] == '0')a[1] ++;
else a[4] ++;
}
else
{
if (s[i][0] == '0')
{
a[2] ++;
if(u[i] == 0)p.push_back(i);
}
else if (s[i][0] == '1')
{
a[3]++;
if(u[i] == 0)q.push_back(i);
}
}
}
由00和11组成
if (a[1] + a[4] == n && a[1] && a[4])
{
cout << -1 << endl;
continue;
}
//cout <<" ? ? " << a[1] << " " << a[2] << " " << a[3] << " "<<a[4] << endl;
int m = abs(a[2] - a[3]);
m /= 2;
//仅由00或者11组成，或者01和10数量相同
if (m==0||a[1]==n||a[4]==n)cout << 0 << endl << endl;
//m是需要反转的字符串数量，根据01和10谁的数量多，决定反转哪个
else if (a[2] > a[3])
{
//如果允许反转的字符串数量少于需要反转的数量，那么输出-1，否则直接m个01字符串的位置
if (m > p.size())cout << -1 << endl;
else
{
cout << m << endl;
for (int i = 0; i < m; ++i)cout << p[i] << " ";
cout << endl;
}
}
else
{
//如果允许反转的字符串数量少于需要反转的数量，那么输出-1，否则直接m个10字符串的位置
if (m > q.size())cout << -1 << endl;
else
{
cout << m << endl;
for (int i = 0; i < m; ++i)cout << q[i] << " ";
cout << endl;
}
}
}
return 0;
}
