集训Day01模拟赛题目总结

klz

2025-10-10 21:39:30

发布于：上海

12阅读

0回复

0点赞

Day01:

T1 : T75481.礼物

大致题意：小明有 m 元，一共有 n 件物品 , 有 v 和 w 两个属性，一共有 t 次购买方案，
每次要买 q （奇数件）物品，要求购买q件物品中位数最大值。

solve1: 暴力

对于每次购买进行dfs枚举，排列出所有的可能性并找到其中的最大中位数的值。应该能拿 50分

solve2:二分答案（即正解）

因为中位数是具有单调性的，所以能够想到二分答案
对于每次购买去二分可能的中位数（范围在 Vi 中的最小值 ~ 最大值）并检查可行性:

//二分答案 
typedef long long ll;
const int N = 5e5 + 5;
ll n,t,m,maxn,minn=1e9,q;
struct node{
	ll v,w;
}a[N];
bool check(ll x){//二分中位数 
	ll tot = 0 , lowest = (q+1) / 2;
    //子集总价值     最少的个数      
    vector<int> big , val;
    //  big中是比x大的价值的商品的价格    val是所有物品价格
	for(int i=1;i<=n;i++){
        val.push_back(a[i].w);
		if( a[i].v >= x )
			big.push_back(a[i].w);
	}
	if( big.size() < lowest)return false;
    //选择最便宜的价格
    sort(big.begin(),big.end());
    sort(val.begin(),val.end());
    for(int i=0;i<lowest;i++)
        tot += big[i];
    int j = 0 , cnt = 0;
    for(int i=0;i<n && cnt < q - lowest;i++){
        if( big[j] != val[i]){
            tot += val[i];
            cnt ++;
        }
        else if( j < lowest)
            j ++;
    }
    if( cnt < q - lowest)return false;
    if( tot > m)return false;
	return true;
}
int main(){
	cin >> n >> m >> t;
	for(int i=1;i<=n;i++){
		cin >> a[i].v >> a[i].w;
		maxn = max( maxn , a[i].v);
		minn = min( minn , a[i].v);
	}
	while(t--){
		cin >> q;
		ll ans = -1 , l = minn , r = maxn;
		while( l <= r){
			ll mid = ( l + r) / 2;
			if( check(mid) ){;
				l = mid + 1;
				ans = mid;
			}
			else
				r = mid - 1;
		}
		cout << ans << endl;
	}
	return 0;
}

T2 : T75482.秘境

大致题意：题面看似很复杂，但看了样例后简单地就能发现他想要求的就是 1 ~ n 的所有数的开平方并向下取整的和。懂了这个之后，就很简单了，我们可以枚举 1~n 所有的数，并加和所有的sqrt()

solve1:暴力

for(int i=1;i<=n;i++)
    ans += sqrt(i);

但是枚举1 ~ n 时间复杂度为O(n) 而题面的数据中最大n到达了10e18，~~暴力就会直接爆炸(只能拿3个点)~~,那么我们就需要亿点点的数学优化了

solve2:数学优化

我们不难发现，题目想要求的就是对于 i 在 1 ~ n 中求和：

$\sum_{i=1}^n \lfloor\sqrt{i}\rfloor$

这样我们大概会要求一个这样的数列的各项和：

$\begin{matrix} 1,1,1,2,2,2,2,2,3,3,3....., \sqrt{n} \end{matrix}$

那么我们就可以令 $m = \lfloor \sqrt{n} \rfloor$ ，就可以将上式转换成两个不同的式子:

$\sum_{i=1}^n \lfloor\sqrt{i}\rfloor = \sum_{i=1}^{m-1} i^2 + \sum_{i=m^2}^n i$

得到这两个式子之后题目就变得简单了，我们只需要化简一下这两个式子就好了。对于第二个式子，只需要使用~~非常简单的~~求和公式：

$\sum_{i=m^2}^n i = \frac{m(n - m^2 + 1)}{2}$

但是对于第一个式子，我们就需要使用~~非常高级的~~平方和公式了：

$\sum_{i=1}^m i^2 = \frac{m(m+1)(2m+1)}{6}$

想要推导的话就更困难了，但是这里还是稍微论证一下吧

$(n+1)^3 = n^3 + 3n^2 + 3n + 1\\ (n+1)^3 - n^3 = 3n^2 + 3n + 1\\ =3(n^2 + n) + 1\\ 3^3 - 2^3 = 3 \times2\times2 + 3 \times2+1\\ 2^3-1^3 = 3\times1\times1+3\times1+1\\$

*对于所有的 $(i+1)^3 - i^3$ *进行合并可以得到：

$(n+1)^3 - 1^3 = 3(1^2+2^2+... +n^2) + 3(1+2+..+n) + n$

移项一下可以得到：

$1^2 + 2^2+3^2+...+n^3 = ((n+1)^3-1 - 3\times\frac{n(n+1)}{2}-n)\div3 \\ = \frac{2n^3+6n^2+6n-3n^2-3n-2n}{6}\\ =\frac{2n^3+3n^2+n}{6}\\ =\frac{n(n+1)(2n+1)}{6}$

最终可以得到:

$\sum_{i=1}^n \lfloor\sqrt{i}\rfloor = \frac{m(n - m^2 + 1)}{2} + \frac{n(n+1)(2n+1)}{6}$

这样我们就可以O(1)算出答案了

#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
typedef long long ll;
long long n , ans;
ll isqrt(ll x){
	if( x == 0)return 0;
	ll l = 0 , r = 1e10;
	while(l <= r){
		ll mid = (l+r) / 2;
		if( mid * mid <= x){
			l = mid + 1;
		}else
			r = mid - 1;
	}
	return r;//向下取整返回mid-1 
}

ll quick_mi(ll a,ll b){//快速幂 求 a ^ b 
	ll res = 1;
	while( b ){
		if( b & 1)
			(res *= a) %= mod;
		(a *= a) %= mod;
		b >>= 1;
	}
	return res % mod;
}

ll inv(ll x){//乘法逆元 
	return quick_mi(x , mod-2);
}
int main(){
	// m = floor(sqrt(n)) r = [1,m-1]
	// S1 = sum( r * (2r+1) ) 
	//    = sum(2r^2 + r)
	//    = r * (r+1) * (2r+1) / 3 + m * (m+1) / 2
	// [m^2 , n] --> n - m^2 + 1
	// S2 = m * ( n - m^2 + 1) 多出来的 
	
	//对于乘法逆元 a * b === 0 (mod m) 即 ab 互为乘法逆元 
	//则有 b === a ^ -1 (mod m)
	// (c / a) mod m --> a^(mod-2)
	cin >> n;
	ll m = isqrt(n);// m = sqrt(n)
	ll k = (m - 1) % mod;//k = m - 1
	ll b = m % mod;// b = m - 1 + 1
	ll c = (2 * m - 1) % mod;//c = 2m - 1
	ll ans1 = k * b % mod * c % mod * inv(3) % mod;
	ll ans2 = k * b % mod * inv(2) % mod;
	ll S1 = (ans1 + ans2) % mod;
	ll S2 = ( n - m * m + 1) % mod * m % mod;
    ll ans = (S1 + S2 )% mod;
	cout << ans <<endl;
	return 0;
}

T3 : T75480.二分图匹配

*大致题意:有两个字符串S1,S2(只含有A~Z),我们要将他们进行匹配，规则是:对于每个i,j 和 $S1_i和，S2_j$ , $S1_i =S2_j$ 且 $i_1< i_2$ , $j_1<j_2$ 即匹配的每个字符需要相同且每次匹配之后，只能在后面选择字符进行匹配了。

正解思路：

我们可以考虑用动态规划的方法，用二维 $dp_{i,j}$ ,计算在S1字符串的i位置时，匹配成功j次最早的位置。但我们还要考虑S2的字符与S1匹配~~否则复杂度是O(nm)会超时~~，因此我们可以预处理出：t[i]数组，表示字符i在S2中第一次出现的位置和数组 $nxt_{i,j}$ 表示在S2中从第i个字符开始，字符j第一次出现的位置*

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5,M = 1e6 + 5;
int n,m;
//t[] : s2中每个字符第一次出现的位置
//nxt[p][c] 在s2中从位置p(不包括p)开始，字符c首次出现的位置
//dp[i][j] --> 在s1字符串的i位置时，匹配成功j次最早的位置
int dp[N][N],nxt[M][30],t[30];
string s1,s2;

int main(){
	cin >> n >> m;
	cin >> s1 >> s2;
	s1 = ' ' + s1;
	s2 = ' ' + s2;
    
	for(int i=0;i<=26;i++)
        t[i] = m + 1;
    for(int i=m;i>=1;i--){
        for(int c=0;c<=26;c++)
            nxt[i][c] = t[c];//先覆盖在赋值"不包括p"
        t[s2[i] - 'A'] = i;
    }
    for(int c=0;c<=26;c++){
        nxt[0][c] = t[c];
        nxt[m+1][c] = m+1;
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            dp[i][j] = m + 1;
    dp[0][0] = 0;
    for(int i=1;i<=n;i++){
        dp[i][0] = 0;
        for(int j=1;j<=i;j++){
            //以前匹配了j次
            dp[i][j] = dp[i-1][j];
            //以前匹配了j-1次
            //当前字符
            int c = s1[i] - 'A';
            int pre  = dp[i-1][j-1];//上次匹配的最早位置
            int nt = nxt[pre][c];
            dp[i][j] = min( dp[i][j] , nt);//尽可能靠前
        }
    }
    int ans = 0;
    for(int j=1;j<=n;j++)//搜索最大匹配了多少次
        if(dp[n][j] != m + 1)//有值
            ans = j;
    cout << ans << endl;
	return 0;
}

T4 : 三角游戏

大致题意：给你一个正n边形，每个点都有相应权值，要求在这个n边形中选择 $3x$ 个点构成 $x$ 个三角形，对于每个三角形(i,j,k)的得分是a[i] * a[j] * a[k],求能获得的最大分数，且所有三角形不能重叠
题目最难的地方在于如何不重叠三角形，但其实我们只需要将原题转化一下，把这个正n边形看成一个环，我们每次选定3个点，获得的分数并加上将余下的两个(或一个)剩余部分加和或者计算分割成三个区间的最大和。这样我们就得到了一个纯正的动态规划

#include<bits/stdc++.h>
using namespace std;
const int N = 8e2 + 5;
long long t,n,a[N] , dp[N][N];//dpij表示区间[i,j]最大得分 
/*
 选择形成三角形
 在[i,j]中选一个分割点形成三角形
 对于三角形(i,j,k) --> a[i] * a[j] * a[k]
 	[i,j] -- > [i+1,k-1] , [k+1,j-1] --> dp[i+1][k-1] + dp[k+1][j-1] 前提(i+1 <= k-1)( k+1 <= j-1)
 若不选 , 选择一个中间点 k 在 [i,k] 和 [k+1,j] 里找三角形
 	[i,k] [k+1,j] --> dp[i][k] + dp[k+1][j]
 dp[i][j] = max( dp[i][k] + dp[k+1][j] , dp[i+1][k-1] + dp[k+1][j-1] + a[i] * a[j] * a[k])
*/ 
int main(){
	cin >> t;
	while(t --){
		cin >> n;
        memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
			cin >> a[i] , a[n+i] = a[i];
     
		for(int len=3;len<=n*2;len++){
			for(int i=1;i<=n*2-len;i++){
				int j = len + i - 1;
				for(int k=i;k<=j;k++)
					dp[i][j] = max( dp[i][k] + (k+1 <= j ? dp[k+1][j] : 0) , dp[i][j]);
				for(int k=i+1;k<j;k++)
					dp[i][j] = max( dp[i][j] , (i+1 <= k-1 ? dp[i+1][k-1] : 0) + (k+1 <= j-1 ? dp[k+1][j-1] : 0) + a[i] * a[j] * a[k]);
			}
		}
        long long ans = 0;
		for(int i=1;i<=n;i++)
            ans = max( ans , dp[i][i+n-1]);
        cout << ans << endl;
	}
	return 0;
}