模拟赛游记 #5

cjdst

2025-08-22 15:31:35

发布于：广东

76阅读

0回复

0点赞

本来以为会保龄的，没想到一分没挂，感觉好像阳寿少了一点了（（（

T1

题面：给定一个数组 $A$ ，你需要生成一个序列 $B$ ，使 $B$ 包含 $A$ 所有的非空子集。用序列 $B$ 生成一个新的序列 $C$ ，使 $C$ 的每一项都与 $B$ 的一项的最大值一一对应。求 $C$ 的所有众数中的最大值

老师说这题是个人都做得出来。

显然， $A$ 中的最大值至少会占 $C$ 中的一半。所以直接输出 $A$ 的最大值即可。

#include <iostream>
#include <cstdio>
#include <algorithm> 
using namespace std;
int a[100005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	cout << *max_element(a + 1, a + n + 1);
	
	return 0;
}

时间复杂度： $O(n)$ 。

个人感觉 T3 比 T2 简单，先开的题也是 T3，所以我先讲 T3。

T3

由于题意非常重要，所以直接放题面。

题面：有 $2N$ 张卡牌从左到右依次放在桌子上，编号为 $1,2,...,2N$ ，卡牌 $i$ 上写有整数 $A_i$ 。对于 $x=1,2,3,4,5,...,N$ ，存在恰好两张卡牌上写的整数为 $x$ 。

24老师吃饱了没事干，因此决定用这些卡牌玩一个游戏；该游戏的流程如下：

依次考虑卡牌 $1,2,3,...,2N$ ：

24老师决定是否拿起这张卡牌：如果他决定拿起，那么依次进行以下的步骤；如果他决定不拿起该卡牌（跳过该卡牌），则跳过以下的步骤；
如果24老师的手中持有一张写有 $A_i$ 的卡牌，那么该卡牌和卡牌 $i$ 同时消失，他获得 $V_{A_i}$ 分；
如果24老师左手中有一张卡牌，那么他将其丢弃；
如果24老师右手中有一张卡牌，那么他将其转移到左手；
如果卡牌 $i$ 没有在步骤 2 中消失，那么他将其放在右手中。

通过上面的流程，每次得到的分数之和即为24老师的最终得分。

请求出24老师能获得的最大得分。

显然被丢掉的牌没有用，所以我们应使所有选中的牌都被消除，问题的关键在于如何选择可以使得分最大。

注意到步骤 3，我们发现即使右手的牌被消除，左手的牌依旧会丢掉。所以当一张牌被拿起，并且没有被消除时，最多只能再拿一张其他牌。

注意到这题是一个很染色的题目，而且染色有一个很简便的转换成区间问题的做法，所以考虑将本题转化成区间问题。

染色转化成区间问题后变为没有重复元素的区间的分数和的最大值，这题则转化成区间中可以与一个区间有交集，但不能包含那个区间的分数和的最大值。例如下图中，

区间 $1,4$ 、 $1,2$ 都是合法的选择方案，但是 $3,4$ 就不能选。

对此，我使用了一个特别猎奇的做法：

定义 $l_i$ 为第 $i$ 张牌前面写上的整数与 $A_i$ 相同的卡牌的下标，定义 $dp[i][j]$ 为插入了尾下标为 $i$ 的区间后， $i$ 是否与前面的一个区间有交集，的得分最大值。则有如下状态转移方程：

$dp[i][0]=(\max_{j=1}^{j\lt l_i}\max\{dp[j][0],dp[j][1]\})+V_{A_i}\\ dp[i][1]=(\max_{j\lt i∧l_j\lt l_i} dp[j][0])+V_{A_i}$

按照这个转移方程写的初始代码如下：

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[1000005], b[500005];
int lst[500005];
int l[1000005];
int dp[1000005][2];
int n;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n * 2; i++){
		cin >> a[i];
		l[i] = lst[a[i]];
		lst[a[i]] = i;
	}
	for(int i = 1; i <= n; i++) cin >> b[i];
	for(int i = 1; i <= n * 2; i++){
		if(!l[i]) continue;
		for(int j = 1; j < i; j++){
			if(j > l[i]) continue;
			dp[i][0] = max(dp[i][0], max(dp[j][0], dp[j][1]) + b[a[i]]);
		}
		for(int j = 1; j < i; j++){
			if(l[j] > l[i]) continue;
			dp[i][1] = max(dp[i][1], dp[j][0] + b[a[i]]);
		}
	}
	int ans = 0;
	for(int i = 1; i <= 2 * n; i++){
		ans = max(ans, max(dp[i][0], dp[i][1]));
	}
	cout << ans;
	
	return 0;
}

时间复杂度： $O(n^2)$ 。

注意到最大值都是以 $1$ 开始的，所以可以使用树状数组优化，分别维护 $\max\{dp[j][0],dp[j][1]\}$ ， $dp[j][1](1\le l_j\le i)$ 的最大值。

//全网最诡异代码 
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
/*呃呃呃懒得写了（（（ 
class Segtree{
	vector <int> tr, left, right;
	void build(int u, int l, int r){
		left[i] = l, right[u] = r;
		if(l == r) return;
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
	}
	void modify(int u, int idx, int val){
		
	}
	int query
	public:
	
	Segtree(){}
	void init(int n){
		tr.resize(n << 2 | 1, 0);
		left.resize(n << 2 | 1, 0);
		right.resize(n << 2 | 1, 0);
		build(1, 1, n);
	}
}t1, t2;*/
class FenwickTree{
	vector <int> tr;
	int n;
	
	public:
	
	FenwickTree(){}
	void init(int n){
		this -> n = n;
		tr.resize(n, 0);
	}
	void modify(int idx, int val){
		for(int i = idx; i <= n; i += (i & (-i))) tr[i] = max(tr[i], val);
	}
	int query(int idx){
		int ans = 0;
		for(int i = idx; i; i -= (i & (-i))) ans = max(ans, tr[i]);
		return ans;
	}
}dp01, dp0;
int a[1000005], b[500005];
int lst[500005];
int l[1000005];
int dp[1000005][2];
int n;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	dp01.init(n * 2 + 5);
	dp0.init(n * 2 + 5);
	for(int i = 1; i <= n * 2; i++){
		cin >> a[i];
		l[i] = lst[a[i]];
		lst[a[i]] = i;
	}
	for(int i = 1; i <= n; i++) cin >> b[i];
	for(int i = 1; i <= n * 2; i++){
		if(!l[i]) continue;
		dp[i][0] = dp01.query(l[i] - 1) + b[a[i]];
		dp[i][1] = dp0.query(l[i] - 1) + b[a[i]];
		dp01.modify(i, max(dp[i][0], dp[i][1]));
		dp0.modify(l[i], dp[i][0]);
	}
	int ans = 0;
	for(int i = 1; i <= 2 * n; i++){
		ans = max(ans, max(dp[i][0], dp[i][1]));
	}
	cout << ans;
	
	return 0;
}

时间复杂度： $O(n\log n)$ 。

T2

题意解析：给定一个 $N$ 个节点 $M$ 条边的图，你可以进行一次操作，给任意 $u,v$ 两个点连一条长度为 $L$ 的边。求有多少种方案可以使 $S\rarr T$ 的最短路长度 $\le K$ 。

我们可以跑两遍 Dij 求出 $S\to i,i\to T$ 的最短路 $dis1[i],dis2[i]$ ，然后二分求出有多少个满足 $dis1[i]+dis2[i]+L\le K$ 即可。特判 $dis1[T]\le K$ 的情况，此时应输出 $\frac{N(N-1)}{2}$ 。~~这么简单的做法这个贵物甚至想了一个多小时~~

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>
#define int long long
#define pii pair <int, int>
using namespace std;
vector <pii> v[200005]; 
pii dis1[200005], dis2[200005];
bool vis[200005];
int n, m, s, t, l, k;
void dijkstra(int idx, pii *dis){
	for(int i = 1; i <= n; i++){
		vis[i] = 0;
		dis[i].first = 0x3f3f3f3f3f3f3f3fll;
	}
	priority_queue <pii, vector <pii>, greater <pii>> q;
	q.push({0, idx});
	dis[idx].first = 0;
	while(!q.empty()){
		auto head = q.top();
		q.pop();
		if(vis[head.second]) continue;
		vis[head.second] = 1;
		for(auto it:v[head.second]){
			if(dis[it.first].first > head.first + it.second){
				dis[it.first].first = head.first + it.second;
				q.push({dis[it.first].first, it.first});
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> s >> t >> l >> k;
	for(int i = 1; i <= m; i++){
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back({y, z});
		v[y].push_back({x, z});
	}
	dijkstra(s, dis1);
	if(dis1[t].first <= k){
		cout << n * (n - 1) / 2;
		return 0;
	}
	dijkstra(t, dis2);
	for(int i = 1; i <= n; i++){
		dis1[i].second = i;
	}
	for(int i = 1; i <= n; i++){
		dis2[i].second = i;
    }
	sort(dis1 + 1, dis1 + n + 1);
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(dis2[i].first > (k - l)) continue;
		int idx = upper_bound(dis1, dis1 + n + 1, make_pair(k - l - dis2[i].first, 0x3f3f3f3fll)) - dis1 - 1;
		ans += idx;
	}
	for(int i = 1; i <= n; i++){
		if(dis1[i].first + dis2[dis1[i].second].first + l <= k){
			ans--;
		}
	}
	cout << ans;
	
	return 0;
}