AT_abc301 复盘
A
一眼水，只需要遍历一遍数组，记录哪一个胜利场数先打到 \((n + 1) / 2\) 就好了。
AC code：
// LUOGU_RID: 139221441
#include <bits/stdc++.h>
using namespace std;
int n, c1, c2;
string s;
int main(){
cin >> n >> s;
for (int i = 0; i < n; i++){
if (s[i] == 'T') c1++;
else c2++;
if (c1 >= (n + 1) / 2) return cout << "T", 0;
if (c2 >= (n + 1) / 2) return cout << "A", 0;
}
return 0;
}
B
依旧很水，只需要看当前与下一个数之间的趋势，然后输出就好。
注意边界，如果输出一个区间包含前面但不含后面的话，最后一个数要单独输出。
AC code：
// LUOGU_RID: 139221974
#include <bits/stdc++.h>
using namespace std;
int n;
int a[105];
int main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i < n; i++){
if (a[i] < a[i + 1]){
for (int j = a[i]; j < a[i + 1]; j++) cout << j << " ";
}
else {
for (int j = a[i]; j > a[i + 1]; j--) cout << j << " ";
}
}
cout << a[n] << endl;
return 0;
}
C
依旧是字符串，先记录下每一个字母的出现情况和两个字符串中 @ 的数量。之后遍历一遍字母，如果缺失（两个字符串字母出现次数不同）的字母是 atcoder 中的一个，那么记录需要的 @ 的数量。
最后判断所需 @ 符是否超过字符串已有的，或者两个字符串剩的 @ 符不同。
AC code：
// LUOGU_RID: 139224230
#include <bits/stdc++.h>
using namespace std;
string s, t;
int cnts, cntt;
int ms[30], mt[30];
int main(){
cin >> s >> t;
for (int i = 0; i < s.size(); i++){
if (s[i] == '@') cnts++;
if (t[i] == '@') cntt++;
if (s[i] != '@') ms[s[i] - 'a']++;
if (t[i] != '@') mt[t[i] - 'a']++;
}
for (char i = 'a'; i <= 'z'; i++){
if (ms[i - 'a'] != mt[i - 'a']){
if (i == 'a' || i == 't' || i == 'c' || i == 'o' || i == 'd' || i == 'e' || i == 'r'){
if (ms[i - 'a'] < mt[i - 'a']) cnts -= (mt[i - 'a'] - ms[i - 'a']);
else cntt -= (ms[i - 'a'] - mt[i - 'a']);
}
else return cout << "No", 0;
}
}
if (cnts < 0 || cntt < 0 || cnts - cntt != 0) return cout << "No", 0;
cout << "Yes";
return 0;
}
D
算是比较水的 D，只要先记录初始的数，特判一下是否大于 \(n\)。然后从高位到低位去看每一个 ? 是否能变成 \(1\)，如果能，就加上这个数二进制还原回来的数，否则跳过。
注意：不开 long long 见祖宗。
AC code：
// LUOGU_RID: 139228615
#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
int n, sum, cnt = 1;
int a[65];
signed main(){
cin >> s >> n;
for (int i = s.size() - 1; i >= 0; i--) a[i] = cnt, cnt *= 2;
for (int i = 0; i < s.size(); i++) sum += (s[i] == '1') ? a[i] : 0;
if (sum > n) return cout << -1, 0;
for (int i = 0; i < s.size(); i++){
if (s[i] == '?' && sum + a[i] <= n) sum += a[i];
}
cout << sum << endl;
return 0;
}
E
跟我们出的题很像，直接状压dp + 最短路就行，只不过这里不需要最短路，直接 BFS。
考虑状压dp，设置状态为：走到第 \(i\) 个猴子的位置且状态为 \(j\)，如果 \(j\) 的第 \(k\) 位为 \(1\) 则走到了第 \(k\) 个点，值为当前状态所花时间的最小值。basecase：设起点为 0 号猴子，终点为 \(cnt+1\) 号猴子，则 basecase 为 \(dp_{0,1<<cnt}=0\)。answer：当 \(dp_{cnt + 1,j} \le t\) 时，\(j\) 中包含 \(1\) 的个数的最大值。
坑点不多，注意在装完终点后，真正猴子的数量为 \(cnt-1\)。
AC code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int h, w, t, sx, sy, ex, ey;
vector<pair<int, int>> v;
string s[305];
signed main(){
cin >> h >> w >> t;
for (int i = 0; i < h; i++){
cin >> s[i];
for (int j = 0; j < w; j++){
if (s[i][j] == 'S') sx = i, sy = j;
else if (s[i][j] == 'G') ex = i, ey = j;
else if (s[i][j] == 'o') v.push_back({i, j});
}
}
return 0;
}
AT_abc312 复盘
A
一眼过去直接 \(if\) 秒了
AC code:
#include <bits/stdc++.h>
using namespace std;
string s;
int main(){
cin >> s;
if (s == "ACE" || s == "BDF" || s == "CEG" || s == "DFA" || s == "EGB" || s == "FAC" || s == "GBD") cout << "Yes";
else cout <<" No";
return 0;
}
B
直接暴力枚举左上角的点，然后去判断整一个矩阵是否满足要求。
注意边界。
AC code：
#include <bits/stdc++.h>
using namespace std;
int n, m;
string s[105];
bool check(int x, int y){
for (int i = x; i <= x + 2; i++){
for (int j = y; j <= y + 2; j++){
if (s[i][j] == '.') return 0;
}
}
for (int i = x; i <= x + 3; i++){
if (s[i][y + 3] == '#') return 0;
}
for (int i = y; i <= y + 3; i++){
if (s[x + 3][i] == '#') return 0;
}
for (int i = x + 6; i <= x + 8; i++){
for (int j = y + 6; j <= y + 8; j++){
if (s[i][j] == '.') return 0;
}
}
for (int i = x + 5; i <= x + 8; i++){
if (s[i][y + 5] == '#') return 0;
}
for (int i = y + 5; i <= y + 8; i++){
if (s[x + 5][i] == '#') return 0;
}
return 1;
}
int main(){
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> s[i];
for (int i = 0; i <= n - 9; i++){
for (int j = 0; j <= m - 9; j++){
if (check(i, j)) cout << i + 1 << " " << j + 1 << endl;
}
}
return 0;
}
C
一眼二分答案，直接二分最低的价格就好了，\(check\) 里面就写满足卖家的数量和买家的数量是否满足条件。
注意：二分的有边界要设为 \(10^{9} + 1\)，不然可能取不到极限 1e9。
AC code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[200005], b[200005];
bool check(int mid){
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; i++){
if (a[i] <= mid) cnt1++;
}
for (int i = 1; i <= m; i++){
if (b[i] >= mid) cnt2++;
}
return cnt1 >= cnt2;
}
signed main(){
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
int l = 1, r = 1e9 + 1;
while (l < r){
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}
D
根据题面很容易想到用递归，由小的可以推出来大的，显然可以推出一个递推或者说 \(dp\) 式子。
不难想到可以用 \(dp_{i,j}\) 表示第 \(i\) 个数前面有 \(j\) 个右括号，其中最后答案为 \(dp_{n, n/2}\)。
转移方程就是分类讨论，? 和 ( 和 )，其中 ? 为左括号和右括号之和再模上 \(998244353\)。转移方程不难，只要想到当前情况是由这一个带右括号，或者不带右括号转移过来的就行了。
注意：在计算右括号部分的时候记得特判一下前面有没有右括号，不然会 RE。
AC code：
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
string s;
int dp[3005][3005];
int main(){
cin >> s;
s = ' ' + s;
int len = s.size() - 1;
if (len % 2 == 1) return cout << "0", 0;
dp[0][0] = 1;
for (int i = 1; i <= len; i++){
for (int j = 0; j * 2 <= i; j++){
if (s[i] == '?') dp[i][j] = ((j ? dp[i - 1][j - 1] : 0) + dp[i - 1][j]) % mod;
else if (s[i] == '(') dp[i][j] = dp[i - 1][j];
else dp[i][j] = j ? dp[i - 1][j - 1] : 0;
}
}
cout << dp[len][len / 2];
return 0;
}
F
二分答案。很容易想到直接三层枚举（实际为两层），仔细一想，其实第二层枚举拉环罐头的具有单调性，开罐器越多，拉环罐头开得越多，我们可以枚举普通罐头，然后拉环罐头和开罐器总和一定，之后二分拉环罐头的个数，求出最大值。在这之前很容易想到贪心一下，给权值从大到小排序。
WA code：
#include <bits/stdc++.h>
using namespace std;
int n, m, t, x, ans;
int sa[200005], sb[200005], sc[200005];
vector<int> a, b, c;
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> t >> x;
if (t == 0) a.push_back(x);
if (t == 1) b.push_back(x);
if (t == 2) c.push_back(x);
}
sort(a.begin(), a.end(), greater<int>());
sort(b.begin(), b.end(), greater<int>());
sort(c.begin(), c.end(), greater<int>());
for (int i = 0; i < a.size(); i++) sa[i + 1] = sa[i] + a[i];
for (int i = 0; i < b.size(); i++) sb[i + 1] = sb[i] + b[i];
for (int i = 0; i < c.size(); i++) sc[i + 1] = sc[i] + c[i];
for (int i = 0; i <= a.size() && i <= m; i++){
int l = 0, r = n - i;
while (l + 1 < r){
int mid = l + r >> 1;
if (sc[n - i - mid] >= mid) l = mid;
else r = mid - 1;
}
ans = max(ans, sa[i] + sb[l]);
}
cout << ans << endl;
return 0;
}