AtCoder Beginner Contest 复盘合集
2023.12.6 ABC312 VP(OI赛制)
这次的ABC相对比较难:红橙黄黄蓝绿绿,Ex(蓝)
A:
#include <bits/stdc++.h>
using namespace std;
vector<string> v;
signed main(){
v.push_back("ACE");
v.push_back("BDF");
v.push_back("CEG");
v.push_back("DFA");
v.push_back("EGB");
v.push_back("FAC");
v.push_back("GBD");
string s;
cin>>s;
for(auto it:v){
if(it==s){
cout<<"Yes\n";
return 0;
}
}cout<<"No\n";
return 0;
}
B:稍微麻烦一点。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 225;
int n,m;
string s[N];
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 false;
}
}for(int i = x;i <= x+3;++i){
if(s[i][y+3] != '.') return false;
}for(int i = y;i <= y+3;++i){
if(s[x+3][i] != '.') return false;
}
for(int i = x+6;i<= x+8;i++){
for(int j = y+6;j<= y+8;j++){
if(s[i][j] != '#') return false;
}
}
for(int i = x+5;i <= x+8;i++){
if(s[i][y+5] != '.') return false;
}
for(int i = y+5;i <= y+8;i++){
if(s[x+5][i] != '.') return false;
}return true;
}
signed main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> s[i];
s[i] = ' '+s[i];
}
for(int i = 1;i <= n-8;i++){
for(int j = 1;j <= m-8;j++){
if(check(i,j)){
cout<<i<<" "<<j<<endl;
}
}
}
return 0;
}
C:很水,直接Sort一遍即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5+5;
struct node{
int x,id;
}a[N];
bool cmp(node a,node b){
return a.x<b.x;
}
signed main(){
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> a[i].x;
a[i].id=0;
}for(int i = n+1;i <= n+m;i++){
cin >> a[i].x;
a[i].x++;
a[i].id=1;
}n = n + m;
sort(a+1,a+1+n,cmp);
int cnt1=m,cnt2=0;
for(int i = 1;i <= n;i++){
if(a[i].id){
cnt1--;
}else{
cnt2++;
}if(cnt1 <= cnt2){
cout<<a[i].x;
exit(0);
}
}
return 0;
}
D:稍微思考,可以得出一个DP,准确来说不太像DP
#include <bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
string s;
int dp[3005][3005];
signed main(){
cin >>s;
int n=s.size();
s=' '+s;
dp[0][0]=1;
for(int i = 1;i <= n;i++){
if(s[i] == '('){
for(int j = n;j >= 0;j--){
dp[i][j+1] = dp[i-1][j] % mod;
}
}else if(s[i] == ')'){
for(int j=1;j <= n;j++){
dp[i][j-1] = dp[i-1][j] % mod;
}
}else{
for(int j=1;j <= n;j++){
dp[i][j-1] += dp[i-1][j] % mod;
}for(int j = n;j >= 0;j--){
dp[i][j+1] += dp[i-1][j] % mod;
}
}
}cout<<dp[n][0] % mod <<endl;
return 0;
}
我非常的弱智,\(n <= 3000\) 赛时写成1000。因为OI赛制,所以很弱智的挂分。
赛时因为无脑写压维被卡,换成二维即可过掉。
E:其实我一开始也是认为要维护每一个面,也就是每一个坐标,然后进行前缀和或者差分,但是觉得很复杂。后面突然间想到,其实暴力即可。为什么?因为如果你 \(n\) 个输入都直接遍历他的每一个 \(x,y,z\) 都是没有问题的。理论上会达到 \(n * 100^3\) 肯定会TLE。但是题目中有一个条件 每一个长方体的题解没有相交。意味着我们最多只会遍历 \(100^3\) 。非常nice。然后存到一个三维的数组当中后:
我们可以通过六个面来看周围是不是其他长方体,但是我们发现如果你往 \((x+1,y,z)\) 和 \((x-1,y,z)\) 是等价的。这是啥意思呢?因为你的 \(x-1\) 可以由 \(x-1\) 来判断它的 \(x+1\)(也就是 \(x\))来解决。
于是呢我们就可以通过三个if来判断。我真聪明。
然后再用一个set维护即可。
时间充裕:$O(100^3\times \log n) $ 非常轻松水了一道蓝。。
准确来说这应该是绿吧。
const int N = 1e5+5;
const int M = 105;
int n;
int a[M][M][M];
set<int> st[N];
void solve(){
cin >> n;
for(int i = 1;i <= n;i++){
int x1,y1,z1,x2,y2,z2;
cin >> x1 >> y1>> z1>>x2>>y2>>z2;
for(int x = x1+1;x<=x2;x++){
for(int y = y1+1;y<=y2;y++){
for(int z = z1+1;z<=z2;z++){
a[x][y][z] = i;
}
}
}
}
for(int x = 1;x <= 100;x++){
for(int y = 1;y <= 100;y++){
for(int z = 1;z <= 100;z++){
if(a[x][y][z] == 0) continue;
if(a[x+1][y][z] != a[x][y][z] && a[x+1][y][z]) st[a[x][y][z]].insert(a[x+1][y][z]),st[a[x+1][y][z]].insert(a[x][y][z]);
if(a[x][y+1][z] != a[x][y][z] && a[x][y+1][z]) st[a[x][y][z]].insert(a[x][y+1][z]),st[a[x][y+1][z]].insert(a[x][y][z]);
if(a[x][y][z+1] != a[x][y][z] && a[x][y][z+1]) st[a[x][y][z]].insert(a[x][y][z+1]),st[a[x][y][z+1]].insert(a[x][y][z]);
}
}
}
for(int i = 1;i <= n;i++){
cout<<st[i].size()<<endl;
}
}
F:赛后发现巨水。可以说是思考10s,码量2min,调1.5h
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int N = 2E5+5;
int a[N],b[N],c[N];
int f[N],g[N];
bool cmp(int a,int b){
return a > b;
}
signed main() {
cin >> n >> m;
for(int i = 1;i <= n;i++){
int t,x;
cin >> t >> x;
if(t==0) a[++a[0]] = x;//先分类
else if(t==1) b[++b[0]] = x;
else c[++c[0]] = x;
}
sort(a+1,a+1+a[0],cmp);//排序
sort(b+1,b+1+b[0],cmp);
sort(c+1,c+1+c[0],cmp);
for(int i = 1;i <= a[0];i++){//前缀和a
f[i] = f[i-1] + a[i];
}
int res=0,ci=0;
int cnt=0;
for(int i = 1;i <= b[0];i++){//g[i]记录当取i个b或c时的最大收获。
//res为ci个c能够开多少个b
while(res < i && ci < c[0]) res += c[++ci];
if(res<i) break;
g[ci+i-1] = max(g[ci+i-1],cnt);
cnt+=b[i];
g[ci+i]=cnt;
}
for(int i =1;i <= m;i++){
f[i] = max(f[i],f[i-1]);
}
int ans=0;
for(int i = 0;i <= m;i++){
ans=max(ans,g[i]+f[m-i]);
}
cout<<ans;
return 0;
}
甚至还请了何竺凌来帮我调。。。
最后发现的问题是在:
for(int i =1;i <= m;i++){
f[i] = max(f[i],f[i-1]);
}
整体思路是算t=0的部分的答案,和t=1,t=2的答案,然后最后组合在一起即可。
但是会发现如果需要选6个,但是只有2个可以选,那么会出现中间是空的,无法组合 ,这样,我们只需要把f数组渲染一遍即可。
总结:
这次其实F挺水的。大概是正常的D。赛时没切F主要是时间不够,而且一直认F是很难的。所以没搞F。然后D耽误了一点时间,总体来说发挥不太好。(OI赛制嘛,一般来说正常AT我都是罚时吃饱。。
- Beginner AtCoder Contestcontest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 315 beginner atcoder contest 310