气炸了,昨晚半个小时写了三个题,结果第四个题看不懂题,磨叽大半小时后终于大概理解什么意思了,然后又写不出来,真是操蛋了
problem A. Grasshopper on a Line
题目大意:给定一个坐标n,然后再给一个k,从0开始跳,每次跳的距离不能被k整除,问最多跳几次到n,并输出每次跳的距离,如果有多个任意输出一个即可
思路:对于不能被k整除的n直接输出1即可,对于能被k整除的n,先跳n - 1步,再跳1步即可
数据范围: 1 ≤ n ≤ 100; 2 ≤ k ≤ 100
#include <iostream>
using namespace std;
int main()
{
int T; cin >> T;
while (T --)
{
int n, k; cin >> n >> k;
if (n % k)
{
cout << 1 << endl;
cout << n << endl;
}
else
{
cout << 2 << endl;
cout << n - 1 << " " << 1 << endl;
}
}
return 0;
}
problem B. Comparison String
题目大意:给定一个只包含>和<的字符串,让你构造一个数组,对于i位置上的<,要求si < s(i + 1),对于i位置上的>,要求si > s(i + 1),问构造出的数组最少能有几种不同的元素
例如,对于<<>>而言,可以构造12321符合要求,且只有三个不同元素
思路:找到最长连续的>和<,在两个之间取一个max再加1就是答案
数据范围:1 ≤ n ≤ 100
#include <iostream>
using namespace std;
int main()
{
int T; cin >> T;
while (T --)
{
int n; cin >> n;
string str; cin >> str;
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; )
{
if (str[i] == '>')
{
int cnt3 = 0;
while (i < n && str[i] == '>') i ++, cnt3 ++;
cnt1 = max(cnt1, cnt3);
}
else
{
int cnt4 = 0;
while (i < n && str[i] == '<') i ++, cnt4 ++;
cnt2 = max(cnt2, cnt4);
}
}
cout << max(cnt1, cnt2) + 1 << endl;
}
return 0;
}
problem C. Best Binary String
题目大意:给定字符串s,只包含‘1’, ‘0’, ‘?’,现在把问号替换成‘0’或‘1’,替换后,需要对字符串进行排序使得所有0在1前面,每次操作可以翻转一个子串,问怎么替换可以使操作最小
思路:每次可以翻转一个子串,也就是说我们希望整段一样的更多,可以使用一个flag,遇到‘0’变0,遇到‘1’变1,如果是问号就输出flag
数据范围 1 ≤ |s| ≤ 3e5
#include <iostream>
using namespace std;
int main()
{
int T; cin >> T;
while (T --)
{
string str; cin >> str;
int flag = 0;
for (int i = 0; i < str.size(); i ++)
{
if (str[i] == '0')
{
flag = 0;
cout << (char)str[i];
}
else if (str[i] == '1')
{
flag = 1;
cout << (char)str[i];
}
else cout << (char)(flag + '0');
}
cout << endl;
}
return 0;
}
problem D. Bracket Coloring
不得不吐槽一下根本看不懂题,那个染色操作是真迷。。。
题目大意:给定字符串s,包含’(‘和’)’,把s拆分成一些子序列,使得子序列从左到右排都是合法括号序列,或从右到左排都是合法序列,如果可以请输出每个子序列的编号,否则输出-1
思路:其实只要’(‘的数量等于’)’的数量那么他们从左到右排或者从右到左排一定是美丽的,例如例子中的((())))(可以看作((()))是一个正排合法序列)(是一个反排合法序列,这里可以画图说明,当只在1和4中一个象限的时候输出1,否则输出2,我们可以通过第一个字符的方向选择象限,’(‘说明是1象限,否则是4象限
数据范围:2 ≤ n ≤ 2e5
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int ans[N];
int main()
{
int T; cin >> T;
while(T --)
{
int n; cin >> n;
string s; cin >> s;
int cnt = 0, k = 0, lst = 0;
for(int i = 0; i < n; i ++)
{
if(s[i] == s[0]) cnt ++;
else cnt --;
if(lst + cnt > 0) ans[i] = 1;
else ans[i] = 2;
k = max(k, ans[i]);
lst = cnt;
}
if(cnt != 0)
{
cout << -1 << endl;
continue;
}
cout << k << endl;
for(int i = 0; i < n; i ++) cout << ans[i] << " ";
cout << endl;
}
return 0;
}