专栏文章

基础算法补题

封封禁用户
个人记录参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqa3fv3
此快照首次捕获于
2025/12/04 01:26
3 个月前
此快照最后确认于
2025/12/04 01:26
3 个月前
查看原文
四道题，总分四百，赛时一共拿了30 + 0 + 0 + 0 = 30分

第一题

第一题的话是一道签到题，就是一道纯递归的题，但是由于那恶心的范围，导致使用递归TLE了.赛后发现只需要加一个记忆化搜索就行了(其实赛时也想到了，但是不会写)
这是数据范围 1≤N≤106,1≤ai,bi,ci≤300 1 \le N \le 10^6, 1 \le a_i, b_i, c_i \le 300(但凡是个人都知道递归过不了) 非常神奇，赛后提交居然过不了了只有 50pts
CPP
#define _CRT_SECURE_NO_WARNINGS 1 //这行是我用的VS2022不支持scanf加的
#include <bits/stdc++.h>
using namespace std;
long long N, mod = 1e9 + 7;
bool vis[309][309][309];
long long ans[309][309][309];

long long f(long long a, long long b, long long c) {
	if (a <= 0 || b <= 0 || c <= 0) return 1;
	if (vis[a][b][c] == 1) //记录f(a, b, c)有没有被计算过
		return ans[a][b][c]; //记录过直接返回
	ans[a][b][c] = (f(a - 1, b, c) + f(a, b - 1, c) + f(a, b, c - 1)) % mod; //需要计算f(a, b, c)
	vis[a][b][c] = 1; //标记f(a, b, c)计算过
	return ans[a][b][c];
}

int main() {
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	while (N--) {
		long long a, b, c; cin >> a >> b >> c;
		cout << f(a, b, c) % mod << endl;
	}
	return 0;
}

第二题

这道题我赛时的话是暴力，枚举每一条路和每一个盔甲是否满足条件即可。
它的部分分(20pts)是0≤ki,j 0 \le k_{i,j},也就是它只会对盔甲加生命值，这时候只需要枚举最小生命值的盔甲即可

正解：

使用二分法。
设res=0res = 0, 模拟盔甲受到ki,jk_{i, j}的收益， 当积累到resres时，最小的绝对值一定是res+1res + 1就是盔甲的最小生命值。二分查找合法盔甲即可。
核心代码
CPP
void solve() {
	sort(h.begin(), h.end()); // 二分的条件:单调 -> 对盔甲进行升序排列
	long long i = 1;
	while (i <= t) {
		long long res = 0, ans = 0;
		while (m[i]--) {
			long long tmp; cin >> tmp;
			res += tmp; // res累加k_{i, j}
			ans = min(ans, res);
		}
		ans = abs(ans) + 1; // |ans| + 1 是盔甲最小的生命值
		long long pl = lower_bound(h.begin(), h.end(), ans) - h.begin();
		if (h[pl] != *h.end()) // 只要不是最后一个 -> 有解
			cout << h[pl] << endl;
		else 
			cout << "-1" << endl;
		++i;
	}
}

第三题

赛时的时候是想用DFSDFS做的，但是死活调不出来。它的正解我确实没想出来，主要是因为它的EE不知道怎么求。

正解：

题目给了一个例子：111111111111的EE值是123321123321，这个EE值是怎么算出来的呢？
首先看第22个11，它的左边有一个11,距离为∣2−1∣+1=2|2 - 1| + 1 = 2, 虽然右边有四个11，但是以第二个为中心，左边只扩展了一个，所以右边也只能扩展一个，所以距离也是22.
我们再来构造一个奇数的序列：0000000000的EE值是1232112321，这是我们发现一个规律：当序列为偶数时，中间有22个最大数；奇数时只有一个。也就是说我们的EE值是可以直接构造出来的。比如111000011111111000011111，它的EE值可以分为三个部分构造。
E={3个1121中间的4个01221最后的5个112321E = \begin{cases} 3个1 & 121 \\ 中间的4个0 & 1221\\ 最后的5个1 & 12321 \end{cases}
所以这个序列的EE值为121122112321121122112321。这样我们就可以在O(n)O(n)的复杂度里构造出来EE值，而是O(n2)O(n^2)的复杂度。
思路：根据不同连续子串的长度分类讨论构造出EE值，最后加一个前缀和预处理即可。
CPP
#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll n, m, pre[1000009];
vector<ll> sum;
string s;

void init() {
	cin >> n >> m >> s;
	s = "s" + s; // 下标从1开始
	return;
}

void ini() {
	ll i = 1, cnt0 = 0, cnt1 = 0; // cnt0 -> 连续0的子串, cnt1 -> 连续1的子串
	sum.push_back(0); // 下标从1开始
	while (i <= n) {
		if (s[i] == '0')
			cnt0++; // 连续0的数量
		else 
			cnt1++; // 连续1的数量
		// 连续的一段结束
		if (i != 1 && s[i] != s[i - 1])	{
			ll j = 1;
			// 构造
			if (s[i] == '0') {
				while (j < (cnt1 + 1) / 2) sum.push_back(j), ++j;
				if (cnt1 % 2 == 0 && cnt1 != 0) sum.push_back(j);
				while (j) sum.push_back(j), --j;
				cnt1 = 0;
			}
			else {
				while (j < (cnt0 + 1) / 2) sum.push_back(j), ++j;
				if (cnt0 % 2 == 0 && cnt0 != 0) sum.push_back(j);
				while (j) sum.push_back(j), --j;
				cnt0 = 0;
			}
		}
		// 到达末尾结束
		if (i == n) {
			ll j = 1;
			// 构造
			if (s[i] == '0') {
				while (j < (cnt0 + 1) / 2) sum.push_back(j), ++j;
				if (cnt0 % 2 == 0 && cnt0 != 0) sum.push_back(j);
				while (j) sum.push_back(j), --j;
				cnt0 = 0;
			}
			else {
				while (j < (cnt1 + 1) / 2) sum.push_back(j), ++j;
				if (cnt1 % 2 == 0 && cnt1 != 0) sum.push_back(j);
				while (j) sum.push_back(j), --j;
				cnt1 = 0;
			}
		}
		++i;
	}
	i = 1;
	// 前缀和
	while (i <= n) {
		if (s[i] == '1') sum[i] = sum[i] * sum[i] * sum[i] % mod;
		else sum[i] = sum[i] * sum[i] % mod;
		pre[i] = (sum[i] + pre[i - 1]) % mod;
		++i;
	}
	return;
}

void solve() {
	init();
	ini();
	while (m--) {
		ll l, r; cin >> l >> r;
		// 相减的时侯	取余先 + mod % mod
		cout << (pre[r] - pre[l - 1] + mod) % mod << endl;
	}
	return;
}

int main() {
	solve();
	return 0;
}

第四题

赛时的话我是想暴力枚举每个区间和再排序。但是由于时间不够了，没敲完。 结束之后，看了正解，它的思路的话是：直接寻找一个数值等于所有子区间的区间和，从小到大排序后的第kk个数值。也就是说直接二分查找出这第kk个数值，看能不能合法。
例如：枚举sumsum表示某一个区间的和，当它正好是第kk个的时候 我们可以二分查找sumsum。然后再用双指针优化
sum={有k个比sum大sum可减小有k个比sum下sum可增大sum = \begin{cases} 有k个比sum大 & sum可减小\\ 有k个比sum下 & sum可增大\\ \end{cases}
CPP
#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, ans, a[200009];

void init() {
	cin >> n >> k;
	ll i = 1;
	while (i <= n) cin >> a[i++];
	return;
}

bool check(ll mid) {
	ll i = 1, j = 1, tmp = 0, cnt = 0; // cnt -> mid大于等于的区间个数 <-> 区间和 <= mid的区间个数
	while (i <= n && j <= n) { // 双指针
		tmp += a[j];
		while (tmp > mid) tmp -= a[i++]; // tmp记录的区间和 <= mid
		cnt += (j - i + 1);
		++j;
	}
	if (cnt >= k) return 1;
	else return 0;
}

void solve() {
	init();
	ll l = 0, r = 1e14; // A_min = 0, A_max*N = 1e14
	while (l <= r) {
		ll mid = l + r >> 1;
		if (check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	cout << ans;
	return;
}
	
int main() {
	solve();
	return 0;
}

评论

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

正在加载评论...