(AtCoder Beginner Contest 312)

(AtCoder Beginner Contest 312)

A - Chord

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;


void solve(){
    string s;cin>>s;
    string a[7]={"ACE","BDF","CEG","DFA","EGB","FAC","GBD"};
    for(int i=0;i<7;++i){
        if(s==a[i]){
            cout<<"Yes";return ;
        }
    }
    cout<<"No";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //init();
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

B - TaK Code

思路：维护黑色的前缀和，枚举每个点，满足左上角和右下角的3、4个宽度的黑色个数都为9则输出

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;

int g[105][105];
void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            char c;cin>>c;
            if(c=='#')g[i][j]=1;
            g[i][j]+=(g[i-1][j]+g[i][j-1]-g[i-1][j-1]);
        }
    for(int i=1;i+8<=n;++i)
        for(int j=1;j+8<=m;++j){
            int x1=i+2,y1=j+2,a1,a2,b1,b2;
            a1=g[x1][y1]-g[i-1][y1]-g[x1][j-1]+g[i-1][j-1];
            x1=i+3,y1=j+3;
            a2=g[x1][y1]-g[i-1][y1]-g[x1][j-1]+g[i-1][j-1];
            x1=i+5,y1=j+5;
            int x2=i+8,y2=j+8;
            b1=g[x2][y2]-g[x1-1][y2]-g[x2][y1-1]+g[x1-1][y1-1];
            x1=i+6,y1=j+6;
            b2=g[x2][y2]-g[x1-1][y2]-g[x2][y1-1]+g[x1-1][y1-1];
            //if(i==1&&j==10)cout<<a1<<' '<<a2<<' '<<b1<<' '<<b2<<'\n';
            if(a1==a2&&a2==b1&&b1==b2&&b2==9){
                cout<<i<<' '<<j<<'\n';
            }
        }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //init();
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C - Invisible Hand

思路：对a、b排序，二分x，比较a中小于等于x的个数和b中大于等于x的个数，找出最小的x

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;


void solve(){
    int n,m;cin>>n>>m;
    vector<int>a(n),b(m);
    for(int i=0;i<n;++i)cin>>a[i];
    for(int i=0;i<m;++i)cin>>b[i];
    sort(a.begin(),a.end()),sort(b.begin(),b.end());
    int l=1,r=1e9+1,ans;
    auto check=[&](int x){
        int p1= upper_bound(a.begin(),a.end(),x)-a.begin();
        int p2= lower_bound(b.begin(),b.end(),x)-b.begin();
        p2=b.size()-p2;
        return p1>=p2;
    };
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //init();
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

D - Count Bracket Sequences

思路：对于 ‘（ ’计一分，‘ ）’计-1分；

dp[i][j]表示前i个字符的情况，且第i个字符选定后，当前的分值为j的情况数

枚举到i时，最多有i分，再枚举0~i分的情况；

那么当s[i]='('时，dp[i][j]=dp[i-1][j-1]

当s[i]=')'时，dp[i][j]=dp[i-1][j+1]

当s[i]='?'时，s[i]可以是'('和')'，则dp[i][j]=dp[i][j+1]+dp[i][j-1]

最后的答案即为dp[n][0]

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

int dp[N][N];
void solve(){
    string s;
    cin>>s;int n=s.size();
    s.insert(0," ");
    dp[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=i;++j){
            if(s[i]=='(')dp[i][j]=dp[i-1][j-1]%mod;
            else if(s[i]==')')dp[i][j]=dp[i-1][j+1]%mod;
            else{
                dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%mod;
            }
        }
    }
    cout<<dp[n][0];
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //init();
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

E - Tangency of Cuboids

F - Cans and Openers