codeforces round #829 (div. 2)_白也_y的博客-爱代码爱编程
比赛地址
A.Technical Support
题意:
给定一个包含 Q 和 A 的字符串,Q 表示询问,A 表示回答,多个 A 可以回答同一个Q ,问最后是否有 Q 没有回答
思路:
遍历字符串,若出现 Q 则 res ++, 若出现 A 则考虑 res:
- 若 res > 0,说明前面还有 Q 没有被回答,则 res –
- 若 res = 0,说明前面的 Q 都被回答了,当前的 A 是补充回答其中某一个 Q,res = 0
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
#define div() cout << "-----------------------------" << endl
#define deb(n) cout<< #n << " = " << n <<endl
typedef pair<int, int> PII;
typedef pair<string, int> PSI;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
int n, m;
int a[N];
void oper()
{
cin >> n;
string s;
cin >> s;
int res = 0;
for (int i = 0; i < n; i ++)
{
if (s[i] == 'Q') res ++;
else if (s[i] == 'A' && res > 0) res --;
else res = 0;
}
if (res) cout << "NO" << endl;
else cout << "YES" << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) oper();
return 0;
}
B.Kevin and Permutation
题意:
求 1 ~ n 的全排列,使得所有连续两项之差的绝对值的最小值最大,
即
使
得
min
i
=
1
n
−
1
∣
p
i
+
1
−
p
i
∣
最
大
即使得 \min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert 最大
即使得i=1minn−1∣pi+1−pi∣最大
思路:
构造:x, 1, x + 1, 2, x + 2 … … 其中 x = n / 2 + 1
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
#define div() cout << "-----------------------------" << endl
#define deb(n) cout<< #n << " = " << n <<endl
typedef pair<int, int> PII;
typedef pair<string, int> PSI;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
int n, m;
int a[N];
void oper()
{
int n;
cin >> n;
int d = n / 2;
int a[N];
a[1] = 1 + d;
a[2] = 1;
for (int i = 3; i <= n; i ++) a[i] = a[i - 2] + 1;
for (int i = 1; i <= n; i ++) cout << a[i] << ' ';
cout << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) oper();
return 0;
}