题目描述
The student council has a shared document file. Every day, some members of the student council write the sequence TMT (short for Towa Maji Tenshi) in it.
However, one day, the members somehow entered the sequence into the document at the same time, creating a jumbled mess. Therefore, it is Suguru Doujima’s task to figure out whether the document has malfunctioned. Specifically, he is given a string of length n whose characters are all either T or M, and he wants to figure out if it is possible to partition it into some number of disjoint subsequences, all of which are equal to TMT. That is, each character of the string should belong to exactly one of the subsequences.
A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero) characters.
Input
The first line contains an integer t (1≤t≤5000) — the number of test cases.
The first line of each test case contains an integer n (3≤n<105), the number of characters in the string entered in the document. It is guaranteed that n is divisible by 3.
The second line of each test case contains a string of length n consisting of only the characters T and M.
It is guaranteed that the sum of n over all test cases does not exceed 105.
Output
For each test case, print a single line containing YES if the described partition exists, and a single line containing NO otherwise.
样例
Example
Input
5
3
TMT
3
MTT
6
TMTMTT
6
TMTTTT
6
TTMMTT
Output
YES
NO
YES
NO
YES
Note
In the first test case, the string itself is already a sequence equal to TMT.
In the third test case, we may partition the string into the subsequences TMTMTT. Both the bolded and the non-bolded subsequences are equal to TMT.
算法1
题目说白了 就是 给定一个字符串 看能否所有的都能匹配成 TMT 且 要求是子序列(顺序无法改变)
首先 我们要考虑 要匹配成TMT 类似于之前的括号匹配问题 在每一个M 前面 一定有cntt >= cntm
我们先从头 开始遍历 检验是否 在每一个M前面都能满足 cntt >= cntm
然后我们再在 尾部 开始遍历 检验是否 在每一个M前面都能满足 cntt >= cntm
最后我们要检验 T总数量 是否是 M的二倍
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
int n;//TMT
scanf("%d", &n);
string str;
cin >> str;
int len = str.length();
int cntt = 0 , cntm = 0;
bool flog = true;
for(int i = 0 ; i < len ; i ++)
{
if(str[i] == 'T') cntt ++;
else if(str[i] == 'M') cntm ++;
if(cntt < cntm )//cntt >= cntm
{
flog = false;
}
}
cntt = 0 ,cntm = 0;
bool flag = true;
for(int i = len - 1 ; i >= 0 ; i --)
{
if(str[i] == 'T') cntt ++;
else if(str[i] == 'M') cntm ++;
if(cntt < cntm)
{
flag = false;
}
}
if(!flog || !flag || (cntt != cntm * 2))
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
CodeForces - 1278B
You are given two integers a and b. You can perform a sequence of operations: during the first operation you choose one of these numbers and increase it by 1; during the second operation you choose one of these numbers and increase it by 2, and so on. You choose the number of these operations yourself.
For example, if a=1 and b=3, you can perform the following sequence of three operations:
add 1 to a, then a=2 and b=3;
add 2 to b, then a=2 and b=5;
add 3 to a, then a=5 and b=5.
Calculate the minimum number of operations required to make a and b equal.
样例
Input
The first line contains one integer t (1≤t≤100) — the number of test cases.
The only line of each test case contains two integers a and b (1≤a,b≤109).
Output
For each test case print one integer — the minimum numbers of operations required to make a and b equal.
Example
Input
3
1 3
11 11
30 20
Output
3
0
4
每次加的都是 1的等差 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + …
如果直接相加的前缀和为奇数 那么就能把所有 <= 该和的 奇数全部凑出来
如果直接相加的前缀和为偶数 那么就能把所有 <= 该和的 偶数全部凑出来
那么如果abs(b - a) 为奇数 就找>= abs(b -a ) 且 同奇偶的 第一个数
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
typedef pair <int, int> PII;
int main()
{
int t ;
scanf("%d", &t);
while(t --)
{
int a , b;
scanf("%d %d", &a, &b);
if(a == b)
printf("0\n");
else
{
int chazhi = abs(a - b);
int res = 0;
int t = 0;
for(int i = 1 ; i <= 1e5; i ++)
{
res = i * (1 + i) / 2;
if(res >= chazhi && res % 2 == chazhi % 2)
{
t = i;
break;
}
}
printf("%d\n", t);
}
}
return 0;
}
E. Air Conditioners
题目大意： 许多块地方，放置空调， 一块地方只能放置一个空调，每块地方的温度==min()然后计算每块地方的温度
Let’s look at an example. Consider that n=6,k=2, the first air conditioner is placed in cell a1=2 and is set to the temperature t1=14 and the second air conditioner is placed in cell a2=5 and is set to the temperature t2=16. In that case temperatures in cells are:
temperature in cell 1 is: min(14+|2−1|,16+|5−1|)=min(14+1,16+4)=min(15,20)=15;
temperature in cell 2 is: min(14+|2−2|,16+|5−2|)=min(14+0,16+3)=min(14,19)=14;
temperature in cell 3 is: min(14+|2−3|,16+|5−3|)=min(14+1,16+2)=min(15,18)=15;
temperature in cell 4 is: min(14+|2−4|,16+|5−4|)=min(14+2,16+1)=min(16,17)=16;
temperature in cell 5 is: min(14+|2−5|,16+|5−5|)=min(14+3,16+0)=min(17,16)=16;
temperature in cell 6 is: min(14+|2−6|,16+|5−6|)=min(14+4,16+1)=min(18,17)=17.
t[i] = min(t[i], t[i - 1] + 1, t[i + 1] + 1)
可以正着跑一遍 倒着跑一遍 即可得到答案
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
typedef pair <int, int> PII;
int a[maxn], t[maxn];
int main()
{
int q;
scanf("%d", &q);
while(q --)
{
int n, k;
scanf("%d %d", &n, &k);
for(int i = 1 ; i <= k ; i ++)
scanf("%d", &a[i]);
memset(t , INF, sizeof(t));
for(int i = 1 ; i <= k ; i ++)
{
int temp ;
scanf("%d", &temp);
t[a[i]] = temp;
}
for(int i = 1 ; i <= n ; i ++)
t[i] = min(t[i], t[i - 1] + 1);
for(int i = n ; i >= 1 ; i --)
t[i] = min(t[i], t[i + 1] + 1);
for(int i = 1 ; i <= n ; i ++)
printf("%d ",t[i]);
printf("\n");
}
return 0;
}
