(AtCoder Beginner Contest 312)
#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; }
思路:维护黑色的前缀和,枚举每个点,满足左上角和右下角的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; }
思路:对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; }
思路:对于 ‘( ’计一分,‘ )’计-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; }
- Beginner AtCoder Contest 312beginner atcoder contest 312 contest atcoder programming 312 contest 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