昨晚 CF A-E 题解

userId_undefined

复仇者_帅童

CSP-J一等奖出题人

2025-08-22 23:42:37

发布于：广东

35阅读
0回复
0点赞

A

题意解析：给定一个长度为 nn 的字符串 SS。有 mm 次操作，每次会往字符串最前面或最后面添加一个字符。请你输出最后的字符串。

显然双端队列 deque 可以完美解决这个问题。

#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
void solve(){
	int n, m;
	cin >> n;
	string s1, s2, s3;
	cin >> s1 >> m >> s2 >> s3;
	deque <char> q;
	for(char c:s1) q.push_back(c);
	for(int i = 0; i < s3.size(); i++){
		if(s3[i] == 'D') q.push_back(s2[i]);
		else q.push_front(s2[i]); 
	}
	while(!q.empty()){
		cout << q.front();
		q.pop_front();
	}
	cout << '\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度：O(t×(n+m))O(t\times (n+m))。

B

题意解析：给定一个正整数 nn，求出所有的正整数 xx，使得存在一个正整数 yy 满足 yy 为在 xx 的十进制位末尾添加一些 00 得到的结果，且 x+y=nx+y=n。

显然，yy 一定为 10k×x10^k\times x，其中 kk 为正整数。所以问题转化成了求出所有的 x,kx,k，使得 (10k+1)×x=n(10^k+1)\times x=n。显然答案就位所有的正整数 x=n10k+1x=\frac{n}{10^k+1}。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
void solve(){
	int n;
	cin >> n;
	vector <int> ans;
	for(int i = 10; i <= n; i *= 10){
		if(n % (i + 1) == 0) ans.push_back(n / (i + 1));
	}
	cout << ans.size() << '\n';
	if(ans.empty()) return;
	reverse(ans.begin(), ans.end());
	for(int i:ans) cout << i << ' ';
	cout << '\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度：O(tlog⁡n)O(t\log n)。

C1

题意解析：
有一个潘子涵前来买瓜。
潘子涵：这瓜多少钱一斤？
卖家：我们这有很多种瓜，每种瓜都有 (105)3(10^5)^3 个，第 ii 种瓜质量 3i3^i 斤，售价 3i+1+i×3i−13^{i+1}+i\times 3^{i-1} 元。
潘子涵：Whatsup，你这瓜皮子是瓜粒子做的还是金子是金子做的？
卖家：你要不要吧。
潘子涵：我刚刚 AK 了 IOI，不差钱。但是我有一个要求：

  • 我恰好要买 nn 斤瓜，多一斤少一斤都不行。
  • 我希望我买的瓜的数量最小。

卖家：我不会啊，你自己挑吧。
潘子涵：我也不会啊。
卖家：你都 AK IOI 了你还不会？还有你这不是两个要求吗？
假如你是潘子涵，你会如何挑选？请你输出潘子涵所花费的最小金币数。

如果你不选择买第 ii 种瓜，就得买至少 3j3^j 个第 i−ji-j 种瓜。显然这样是不优的。

所以我们有这样的贪心：如果能买大的瓜，就直接买。
预处理出 3i3^i 的值，就能直接过了。显然同一种瓜最多只能买 22 个，使用 while 也可以通过。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int ksm[100005];
int len;
void solve(){
	int n;
	cin >> n;
	int ans = 0;
	for(int i = len - 1; i >= 0; i--){
		while(n >= ksm[i]){
			n -= ksm[i];
			ans += ksm[i + 1] + i * ksm[i - 1];
		}
	}
	cout << ans << '\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	ksm[0] = 1;
	for(int i = 1;; i++){
		ksm[i] = ksm[i - 1] * 3;
		len = i;
		if(ksm[i] > 1e10) break;
	}
	int t;
	cin >> t;
	while(t--) solve();
	
	return 0;
}

时间复杂度：O(tlog⁡n)O(t\log n)。

C2

题意解析：
有一个潘子涵前来买瓜。
卖家：怎么又是你？
潘子涵：那咋了。老规矩。
卖家：好的，来几斤？
潘子涵：nn 斤……等等，我经过二分答案，发现我能提不超过 kk 个瓜。所以你只要给我装不超过 kk 个瓜就行了。如果不能装，给我 11 元。
卖家：尼姆（指一种博弈）。
假如你是卖家，请你算出他最少付的钱数。如果不能装，输出 -1。

首先按照上面的贪心，算出最少得瓜数。然后推式子，看看如果 11 个第 ii 种瓜被 33 个第 i−1i-1 种瓜代替会产生什么样的结果：

3×(3i+(i−1)×3i−2)=3i+1+(i−1)×3i−13\times (3^i+(i-1)\times 3^{i-2})\\ = 3^{i+1}+(i-1)\times 3^{i-1}

我们发现，会少 3i−13^{i-1} 元钱。而这样会多买 22 个瓜。
所以我们先将 ii 较大的瓜代替，逐个计算。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int ksm[100005];
int cur[100005];
int len;
void solve(){
	int n, m;
	cin >> n >> m;
	int ans = 0;
	for(int i = len - 1; i >= 0; i--){
		while(n >= ksm[i]){
			n -= ksm[i], m--, cur[i]++;
			ans += ksm[i + 1] + i * ksm[i - 1];
		}
	}
	if(m < 0){
		cout << "-1\n";
		for(int i = 0; i <= len; i++){
			cur[i] = 0;
		}
		return;
	}
	for(int i = len - 1; i; i--){
		if(m < 2) break;
		else if(m < cur[i] * 2){
			ans -= (m / 2) * ksm[i - 1];
			break;
		}else{
			m -= cur[i] * 2;
			cur[i - 1] += cur[i] * 3;
			ans -= cur[i] * ksm[i - 1];
			cur[i] = 0;
		}
	}
	cout << ans << '\n';
	for(int i = 0; i <= len; i++){
		cur[i] = 0;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	ksm[0] = 1;
	for(int i = 1;; i++){
		ksm[i] = ksm[i - 1] * 3;
		len = i;
		if(ksm[i] > 1e10) break;
	}
	int t;
	cin >> t;
	while(t--) solve();
	
	return 0;
}

时间复杂度：O(tlog⁡n)O(t\log n)。

D

题意解析：有一个无限长的数，它为所有正整数逐个拼接起来的结果。它张这个样子：1234567891011121314151617181920...1234567891011121314151617181920...。求这个总左往右数前 nn 位的和。

绝世糖题。二分出前 nn 位是由多少个自然数拼接而来的（再加下一个自然数的一部分），然后拿个数位 DP 的板子就秒了。

#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
using namespace std;
int dp[25], pow[25], digits[25], now[25];
int dfs(int n, int dgt, bool f, bool lim){//预制代码 
	if(n == 0){
		if(f) f = 0;
		return 0;
	}
	if(!lim && !f && dp[n] != -1) return dp[n];
	int ans = 0;
	int lst = (lim ? digits[n] : 9);
	for(int i = 0; i <= lst; i++){
		if(f && i == 0){
			ans += dfs(n - 1, dgt, 1, (lim && i == lst));
		}else if(i == dgt && lim && i == lst){
			ans += now[n - 1] + 1 + dfs(n - 1, dgt, 0, 1);
		}else if(i == dgt){
			ans += pow[n - 1] + dfs(n - 1, dgt, 0, 0);
		}else{
			ans += dfs(n - 1, dgt, 0, (lim && i == lst));
		}
	}
	if(!lim && !f) dp[n] = ans;
	return ans;
}
int solve2(int n, int dgt){
	memset(dp, -1, sizeof(dp));
	int len = 0;
	while(n){
		len++;
		digits[len] = n % 10;
		n /= 10;
		now[len] = now[len - 1] + digits[len] * pow[len - 1];
	}
	return dfs(len, dgt, 1, 1);
}
int get_len(int val){
	int ans = 0;
	for(int i = 1; i <= val; i *= 10){
		ans += (val - i + 1); 
	}
	return ans;
}
void solve(){
	int n;
	cin >> n;
	int l = 1, r = n;
	while(l <= r){
		int mid = l + r >> 1;
		if(get_len(mid) <= n) l = mid + 1;
		else r = mid - 1;
	}
	int ans = 0;
	for(int i = 1; i <= 9; i++){
		ans += i * solve2(r, i);
	}
	int lst = r + 1, lstlen = n - get_len(r);
	int tmp = 0;
	while(lst){
		tmp = tmp * 10 + lst % 10;
		lst /= 10;
	}
	for(int i = 1, j = 1; i <= lstlen; i++, j *= 10){
		ans += tmp / j % 10;
	}
	cout << ans << '\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	pow[0] = 1;
	for(int i = 1; i <= 18; i++) pow[i] = pow[i - 1] * 10;
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度：O(tlog⁡2n)O(t\log^2 n)。

E

题意解析：给定两个长度分别为 n,mn,m 的数组 A,BA,B，你需要回答 qq 次询问，每次询问给出三个数 x,y,z(z≤x+y)x,y,z(z\le x+y)，你需要在 A,BA,B 分别选择最多 x,yx,y 个数，并且选的数总数量必须为 zz。求你选的这些数的和的最大值。

首先肯定得排序，因为每次选肯定得选最大的。然后再做一个前缀和，方便求 [1,k][1,k] 的区间的和。

此时这两个数组有了一个性质：均为单调递增，但是它们的增量单调不增。

我们需要发挥我们惊人的注意力，发现：当 AA 数组选的数的数量越来越大时，选数的和会先上升后下降！
证明：
假设选了 AA 数组前 ii 个数。则我们就得选 BB 数组前 z−iz-i 个数。
由于两个数组增量单调不增，所以 ii 越大，AA 数组选的数的和的增加量越来越小，而 BB 数组的减小量却越来越大！当这两个值的差大于 00 时，和上升；等于 00 时，和不变；小于 00 时，和下降。

所以我们只需要求这个单峰函数的最大值就行了。显然可以三分。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int a[200005], b[200005];
void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= m; i++) cin >> b[i];
	sort(a + 1, a + n + 1, greater <int>());
	sort(b + 1, b + m + 1, greater <int>());
	for(int i = 1; i <= n; i++) a[i] += a[i - 1];
	for(int i = 1; i <= m; i++) b[i] += b[i - 1];
	while(q--){
		int x, y, z;
		cin >> x >> y >> z;
		int l = max(0ll, z - y), r = min(z, x);
		while(l <= r){
			int lmid = l + (r - l) / 3;
			int rmid = r - (r - l) / 3;
			if(a[lmid] + b[z - lmid] < a[rmid] + b[z - rmid]){
				l = lmid + 1;
			}else{
				r = rmid - 1;
			}
		}
		cout << a[l] + b[z - l] << '\n';
	}
	for(int i = 1; i <= n; i++) a[i] = 0;
	for(int i = 1; i <= m; i++) b[i] = 0;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度：O(nlog⁡n+mlog⁡m+qlog⁡(n+m))O(n\log n+m\log m+q\log (n+m))。

userId_undefined
去预览
0/2000

全部评论 5

热门讨论