专栏文章

2025寒假专场10

ccompaq
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqe3k74
此快照首次捕获于
2025/12/04 03:18
3 个月前
此快照最后确认于
2025/12/04 03:18
3 个月前
查看原文
空闲连续天
入门，模拟
CPP
#include<bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e3 + 10;

int n, m;
int f[N];
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char c;
			cin >> c;
			if (c == 'o') f[j]++;
		}
	}
	int res = 0, maxn = 0;
	for (int i = 1; i <= m; i++) {
		if (f[i] == n) res++;
		else {
			maxn = max(maxn, res);
			res = 0;
		}
	}
	maxn = max(maxn, res);
	cout << maxn;
	return 0;
}
二维码
入门，模拟
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100 + 10;

int n, m, res;
char g[N][N];
bool check(int x, int y, int u) {
	bool f = true;
	if (u == 1) {
		for(int i = x; i <= x + 2; i++) {
			for(int j = y; j <= y + 2; j++) {
				if (g[i][j] != '#') {
					f = false;
					break;
				}
			}
			if (!f) break;
		}
		for (int i = 0; i <= 3; i++) {
			if (g[x + i][y + 3] != '.' || g[x + 3][y + i] != '.') {
				f = false;
				break;
			}
		}
	}
	else{
		for(int i = x - 2; i <= x; i++) {
			for(int j = y - 2; j <= y; j++) {
				if(g[i][j] != '#') {
					f = false;
					break;
				}
			}
			if (!f) break;
		}
		for (int i = 0; i <= 3; i++) {
			if (g[x - i][y - 3] != '.' || g[x - 3][y - i] != '.') {
				f = false;
				break;
			}
		}
	}
	return f;
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) 
			cin >> g[i][j];
		
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!check(i, j, 1)) continue;
			int x = i + 8, y = j + 8;
			if (x <= n && y <= m) {
				if (check(x, y, 2)) {
					cout << i << ' ' << j << endl;
				}
			}
		}
	}
	return 0;
}
买家卖家
当价格dd越高时, 可能的商贩数量xx就会越多, 而顾客数量yy就会越少; 发现这个单调性后我们就可以考虑用二分来实现;
如果对于价格mid,mid, x<yx < y, 那我们就增大价格midmid直到x>=yx>=y;
CPP
#include<bits/stdc++.h>
#define int long long

using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int s[N], b[N];
bool check(int u) {
	int numb = 0, nums = 0;
	for (int i = 1; i <= n; i++) 
		if (s[i] <= u) nums++;
	
	for (int i = 1; i <= m; i++) 
		if (b[i] >= u) numb++;
	
	if (nums >= numb) return true;
	
	return false;
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> s[i];
	for (int i = 1; i <= m; i++) cin >> b[i];
	int l = 0, r = 1e9+10;
	while (l < r) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << endl;
	return 0;
}
合法字符串
典型的括号类的 dpdp 。 dpi,jdp_{i, j}表示前ii个字符，左括号数量 - 右括号数量= jj的方案数，答案为dpn,0 dp_{n, 0}。
  • 若si==′(′s_i == '(' , 则 dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i - 1][j - 1]
  • 若si==′)′s_i == ')', 则$ dp[i][j] = dp[i - 1][j + 1]
。若si==′?′s_i == '?'，则分别加上是 (的方案和 )的方案即可, 即 dp[i][j]=dp[i−1][j−1]+dp[i−1][j+1]dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e3 + 10, mod = 998244353;

int n, m , res;
int dp[N][N];

signed main() {
	string s;
	cin >> s;
	n = s.size();
	s = ' ' + s;
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= i; j++) {
			if (s[i] == '(' && j) dp[i][j] = dp[i - 1][j - 1];
			else if (s[i] == ')') dp[i][j] = dp[i - 1][j + 1];
			else if(s[i] =='?') {
				dp[i][j] = dp[i - 1][j + 1];
				if (j) (dp[i][j] += dp[i - 1][j - 1]) %= mod;
			}
		}
	}
	cout << dp[n][0];
	return 0;
}
罐头开起来
设拉环罐头为a, 普通罐头为b, 开罐器为c;
解题的关键就在于b; 如果b的数量确定了, 那c的数量也就确定, b和c的数量都知道了, 那a的数量也确定了；
所以根据这个思路我们可以遍历b的数量, 然后用二分找出c的数量, 最后用m减去a和b就得到了c的数量; 为了方便运算我们可以先把a,b,c从大到小排序之后求前缀和, 这样就省去了求和的过程, 也方便c的二分答案; 注意在二分找c的数量时, b和c加起来的数量不能大于m就行;
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
int n, m;
ll a[N], b[N], c[N];
int cnta, cntb, cntc;

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		int x;  ll y;
		scanf("%d%lld", &x, &y);
		if(x == 0) a[++cnta] = y;
		if(x == 1) b[++cntb] = y;
		if(x == 2) c[++cntc] = y;
	}
	sort(a + 1, a + cnta + 1); reverse(a + 1, a + cnta + 1);
	sort(b + 1, b + cntb + 1); reverse(b + 1, b + cntb + 1);
	sort(c + 1, c + cntc + 1); reverse(c + 1, c + cntc + 1);
	
	for(int i = 1; i <= cnta; i++) a[i] += a[i - 1];
	for(int i = 1; i <= cntb; i++) b[i] += b[i - 1];
	for(int i = 1; i <= cntc; i++) c[i] += c[i - 1];
	
	ll ans = 0;
	for(int i = 0; i <= cntb; i++){ // 枚举b的数量 
		ll res = b[i];
		if(i > c[cntc]) break;
		int num = lower_bound(c + 1, c + cntc + 1, i) - c;
		if(i == 0) num = 0;
		if(i + num > m) break;
		res += a[min(cnta, m - i - num)];
		ans = max(ans, res);
	}
	printf("%lld\n", ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...