AtCoder Beginner Contest 312（A~D）

A

//语法题也要更仔细嘞，要不然也会wa

#include <bits/stdc++.h>
// #pragma GCC optimize(3,"Ofast","inline")
// #pragma GCC optimize(2)
using namespace std;
typedef long long LL;
#define int LL
typedef pair<int, int> PII;
const int N = 1e6 + 10;void solve()
{string s;cin >> s;if(s=="ACE"||s=="BDF"||s=="CEG"||s=="DFA"||s=="EGB"||s=="FAC"||s=="GBD") cout << "Yes" << endl;else cout << "No" << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;// cin >> t;while(t -- ) solve(); system("pause");    return 0;
}

B

题意就是从一块大棋盘中抠出一块9*9指定的图案。数据范围不大，没有什么新奇的想法，直接遍历判断的。坐标的转换比较绕人//下次还是从1开始存吧

#include <bits/stdc++.h>
// #pragma GCC optimize(3,"Ofast","inline")
// #pragma GCC optimize(2)
using namespace std;
typedef long long LL;
#define int LL
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
char g[110][110];bool check(int x, int y)
{//左上角3*3的黑色for(int i = 0; i < 3; i ++ )for(int j = 0; j < 3; j ++ ){if(g[x+i][y+j] != '#') return false;}//右下角3*3的黑色for(int i = x + 8; i >= x + 6; i --)for(int j = y + 8; j >= y + 6; j -- )if(g[i][j] != '#') return false;//黑色周围的白色for(int i = 0; i < 4; i ++ ){if(g[x+3][y+i] != '.') return false;if(g[x+i][y + 3] !='.') return false; if(g[x+5][y+8-i] != '.') return false;if(g[x+8-i][y + 5] !='.') return false;}return true;
}void solve()
{    cin >> n >> m;for(int i = 0; i < n; i ++ ){for(int j = 0; j < m; j ++ ) cin >> g[i][j];}for(int i = 0; i < n - 8; i ++ )for(int j = 0; j < m - 8; j ++ ){if(check(i, j)){cout << i + 1<< ' ' << j + 1<< endl;}            }}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;// cin >> t;while(t -- ) solve(); system("pause");    return 0;
}

C

思路：裸二分题，直接二分答案即可。
二分的时间复杂度是logn，check是n，nlogn能过。也可以给两个数组排序，对于每个mid在数组里二分查找坐标，但是排序的时间复杂度是nlogn，其实是一样的。

#include <bits/stdc++.h>
// #pragma GCC optimize(3,"Ofast","inline")
// #pragma GCC optimize(2)
using namespace std;
typedef long long LL;
#define int LL
typedef pair<int, int> PII;
const int N = 2e6 + 10;
int a[N], b[N];
int n, m;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 cnt2 <= cnt1;
}void solve()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int j = 1; j <= m; j ++ ) cin >> b[j];int l = 0, r = 1e9 + 1, mid;//注意右边界不能是1e9，a和b的范围是1e9,但是实际出价的范围可以比1e9多while(l < r){mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout << l << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;// cin >> t;while(t -- ) solve(); system("pause");    return 0;
}

D

dp题，f[i,j]表示前 i 个字符，剩余左括号数为 j 的方案数

#include <bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
using namespace std;
typedef long long LL;
#define int LL
const int N = 3010, mod = 998244353;
int f[N][N];void solve()
{ string s;cin >> s;s = '0' + s;f[0][0] = 1;for(int i = 1; i < s.size(); i ++ )for(int j = 0; j <= i; j ++ ){if(s[i] == '(') //如果第i位是左括号，那么情况与上一位 左括号数-1的情况相同f[i][j] = f[i - 1][j - 1];else if(s[i] == ')') //如果这位是右括号，情况与上一位 剩余左括号数+1情况相同f[i][j] = f[i - 1][j + 1];else //如果这一位是？,那么相当于可以是左括号也可以是右括号，情况为上面两种的和f[i][j] = (f[i - 1][j + 1] + f[i - 1][j - 1])%mod;}//遍历到最后一个字符串，并且左右括号恰好匹配（无剩余左括号）cout << f[s.size() - 1][0] << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;// cin >> t;while(t -- ) solve(); system("pause");    return 0;
}