AtCoder Beginner Contest 312

AtCoder Beginner Contest 312

B

思路

枚举,判断,写起来麻烦点

代码

这里参考jly的写法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int  n,m;
    cin>>n>>m;
    
    vector<string> S(n);
    for (int i = 0; i < N; i++) {
        std::cin >> S[i];
    }
    
    for (int i = 0; i + 8 < n; i++) {
        for (int j = 0; j + 8 < m; j++) {
            int  f = 1;
            for (int x = 0; x < 4; x++) {
                for (int y = 0; y < 4; y++) {
                    if (S[i + x][j + y] != (x == 3 || y == 3 ? '.' : '#')) {
                        f = 0;
                    }
                    if (S[i + 8 - x][j + 8 - y] != (x == 3 || y == 3 ? '.' : '#')) {
                        f = 0;
                    }
                }
            }
            if (f) {
                cout << i + 1 << " " << j + 1 << "\n";
            }
        }
    }
    
    return 0;
}

C

思路

排序加二分

题目问的是求一个最小的X.满足愿意以X及X以上买的人数,大于等于愿意以X及X以下的人数

我们设a为存储卖家的数组

​ b为储存买家的数组,将a.b 从小到大排序

首先我们要考虑下如何判断一个数x是否符合条件.

• 看在 a数组中有多少个数 小于等于x,这里我们可以用 upper_bound 得到数组中严格大于x的下标即我们所要求的数量
• 看在 b数组中有多少个数 大于等于x,这里我们可以用 lower_bound 得到数组中大于等于x的下标,在用数组大小减去下标,就得到有多少数符合条件

那么如何判断最小呢

对于这类区间中取最小值或者最大值的问题,我们一般采用二分,对X采用二分,每次循环中进行两次二分,$\mathrm{时}\mathrm{间}\mathrm{复}\mathrm{杂}\mathrm{度}O(log(A)\ast log(N\ast M)),A\mathrm{为}\mathrm{最}\mathrm{大}\mathrm{取}\mathrm{值}时间复杂度O(log(A)\; *log(N*M)\; ),A为最大取值$

这里取值范围是1到1e9,所以我们将范围设置为1到1e10,(设为1e9的话,如果买家都是1e9的话,那么数值应该是1e9+1)

代码

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 200010;
vector<long long> a;
vector<long long> b;
int n,m;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=n;i++) 
	{
		 int x;
		 cin>>x;
		 a.push_back(x);
	}
	for(int i = 1;i<=m;i++) 
	{
		 int x;
		 cin>>x;
		 b.push_back(x);
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	
	long long l = 1;
	long long  r =1e10;
	while(l<r)
	{
		// cout<<l<<" "<<r<<" ";
		 long long mid = l + r >>1;
		// cout<<mid<<endl;
		 int x = upper_bound(a.begin(),a.end(),mid) - a.begin();
		 int y = lower_bound(b.begin(),b.end(),mid) - b.begin();
		 //cout<<x<<" "<<y<<endl;
		 //y = m - y;
		 if( y <= x) r = mid;
		 else l = mid+1; 
	}
	cout<<l<<"\n";
}

D

思路

DP,括号匹配,需要了解以下两个性质

• 前i个字符中,左括号的数量必须大于等于右括号
• 最后左括号的数量要等于右括号的数量

因此我们这里思考下状态的表示

/*dp[i][j] 为前i字符中有j个左括号的数量,当时我们可以发现这样的表示是有局限的,比如 ))((,就符合条件表示但不是我们所要求的   
所以我们要加上前面写的第一个性质 左括号必须大于等于右括号.
那么我们的就不会有错误情况加入了. */                                              

接下来考虑如何转移

/*当括号为"("时,我们可以直接转移,dp[i][j] = dp[i-1][j-1]
  当括号为")"时,我们可以需要判断 (加上后左括号需要继续大于右括号) if(j >= i - j) dp[i][j] = dp[i-1][j]
  为"?" 有两种情况,为"(" 按"("的情况处理
                 为")" 按")"的情况处理
                 
   最后需要判断字符数量,如果为奇数就为0,因为不和性质,偶数就输出dp[n][n/2];              
*/

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 998244353, N = 3010;
int dp[N][N];

int main()
{
         ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
         string str;
         cin>>str;
         int n = str.size();
        // cout<<n<<endl;
         str =' '+str;
         //cout<<str<<endl;
         dp[0][0] = 1;
         for(int i = 1;i<=n;i++)
         {
         	for(int j = 1;j<=i;j++)
         	{
         		if( str[i]==')' )
         		{
         			if(j>=i-j) dp[i][j]=dp[i-1][j];
         			dp[i][j]%=mod;
         		}
         		else if(str[i]=='(')
         		{
         			dp[i][j] = dp[i-1][j-1];
         			dp[i][j]%=mod;
         		}
         		else
         		{
         			dp[i][j] = dp[i-1][j-1];
         			if(j>=i-j)
         			{
         				dp[i][j] = (dp[i][j] + dp[i-1][j]);
         				dp[i][j]%=mod;
         			}
         		}
         	}
         }
         
         cout<<(n%2 ? 0 : dp[n][n/2])<<"\n";
         return 0; 	
 }

F

思路

排序,贪心

求 0 到 n的A罐头感前缀和

求0 到 n 的B罐头后缀和

然后枚举用多少个A罐头,与前后缀之和作比较,求最大值

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> a;
vector<ll> b;
vector<ll> c;
int n,m;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
	{
		 int t,x;
		 cin>>t>>x;
		 if(t==0) a.push_back(x);
		 else if(t==1) b.push_back(x);
		 else c.push_back(x);
	}
	
	vector<ll> op(n+1);
    vector<ll> xq(n+1);
	
	sort(a.begin(),a.end(),greater<>());
	sort(b.begin(),b.end());
	sort(c.begin(),c.end());
	求前缀值
	for(int i = 0;i<n;i++) 
	{
		 if(i<a.size()) op[i+1] = op[i]+a[i];
		 else
		 {
		 	op[i+1] = op[i];
		 }
	}
	//求后缀值
	int r = 0;
	for(int i = 0;i<n;i++)
	{
		if(b.empty()) xq[i+1] = xq[i];
		else if(r==0)
		{
			if(!c.empty()){
				r+=c.back();
				c.pop_back();
			}
			xq[i+1] = xq[i];
		}
		else
		{
			 r--;
			 xq[i+1] = xq[i]+b.back();
			 b.pop_back();
		}
	}
	    ll ans = 0;
	 	for(int i = 0;i<=m;i++) ans = max(ans,op[i]+xq[m-i]);
		cout<<ans;
		return 0;
}