视频题解

A

易知每个数组只会挑选最大的或最小的，即一段前缀或后缀。将两个数组分别排序，直接枚举即可。

#include <bits/stdc++.h>
using namespace std;
int n, a[100005], b[100005];

long long calc(int x, int y)
{
    long long ret = -1e18;
    for (int i = 0; i <= x; i++)
    {
        long long t = 1;
        for (int j = 1; j < 1 + i; j++)
            t *= a[j];
        for (int j = n; j > n - (x - i); j--)
            t *= a[j];
        for (int k = 0; k <= y; k++)
        {
            long long t2 = t;
            for (int j = 1; j < 1 + k; j++)
                t2 *= b[j];
            for (int j = n; j > n - (y - k); j--)
                t2 *= b[j];
            ret = max(ret, t2);
        }
    }
    return ret;
}

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);

    long long ans = -1e18;
    for (int i = 1; i <= 5; i++)
    {
        if (i <= n && 6 - i <= n)
            ans = max(ans, calc(i, 6 - i));
    }

    cout << ans << endl;

    return 0;
}

B

首先题目保证了 $max(r_i​−l_i​)≤min(x_i​−y_i​)$ ，那么如果某个圈包含了某个奖品，则该圈一定包含了这个奖品的中点。

这样一来，我们就可以在输入 $l_i​,r_i​$ 的时候，标记其中点 (mp[(l+r)/2]++)，再做一遍前缀和（方便过会儿使用），最后查询时 $[x_i​,y_i​]$ 这个区间的和就是答案。

注意有可能会出现中点的位置是个小数这种情况，所以我们不妨把所有坐标都 *2（不要忘记数组大小也要开两倍），以避免上述情况的发生。

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m;
int mp[N];
int main()
{
	cin>>n>>m;
	int l,r;
	for (int i=1;i<=n;i++)
	{
		cin>>l>>r;
		mp[l+r]++;//标记中点
	}
	for (int i=1;i<N;i++)
	{
		mp[i]+=mp[i-1];//前缀和预处理
	}
	for (int i=1;i<=m;i++)
	{
		cin>>l>>r;
		l*=2;
		r*=2;
		cout<<mp[r]-mp[l-1]<<endl;
	}
	return 0;
}

C

显然，$f_1​=a$。

对于 $f_i​$，有两种转移方法：

• 加法： $f_i​=f_j​+f_{j−i}​+b$，其中 $j∈[1,i)$。
• 乘法： $f_i​=f_j​+f_k​+c$，其中 $j≥2,k≥2$ 且 $j×k=i$。

所以状态转移方程为： $f_i​=min(​f_j​+f_{i−j}​+b,​f_j​+f_k​+c)$

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

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,b,c,dp[3005];
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> a >> b >> c;
	memset(dp,0x3f,sizeof dp);
	dp[1]=a;
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++) 
			dp[i]=min(dp[i],dp[j]+dp[i-j]+b);//加法
		for(int j=2;j*j<=i;j++) if(i%j==0){
			dp[i]=min(dp[i],dp[j]+dp[i/j]+c);//乘法 
		}
	}
	for(int i=1;i<=n;i++) cout << dp[i] << " ";
	return 0;
}

D

$40pts:$

循环枚举即可

或使用搜索，dfs、bfs均可。

因为搜索的结果都是稳定数，复杂度 $O(n)$。

$100pts:$

答案满足单调性，可以进行二分。

在二分时，需要检查当前 $<=x$ 的稳定数有多少个，使用数位dp: $dp[pos][pre][lim]:$ 当前从高位开始准备进行第 $pos$ 位，上一位的数字是 $pre$，$lim$ 表示当前位是否受上一位限制，否的话当前位可以任选。

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
int d[20], tot;
ll dp[20][11][2];

ll dfs(int pos, int pre, int lim)
{
    if (!pos)
        return 1;
    if (dp[pos][pre][lim] != -1)
        return dp[pos][pre][lim];
    int up = lim ? d[pos] : 9;
    ll res = 0;
    for (int i = 0; i <= up; ++i)
    {
        if (pre == 10)
        {
            if (i == 0)
                res += dfs(pos - 1, 10, lim && (i == up));
            else
                res += dfs(pos - 1, i, lim && (i == up));
        }
        else
        {
            if (abs(i - pre) <= 2)
                res += dfs(pos - 1, i, lim && (i == up));
        }
    }
    return dp[pos][pre][lim] = res;
}

ll calc(ll x)
{
    tot = 0;
    while (x)
    {
        d[++tot] = x % 10;
        x /= 10;
    }
    memset(dp, -1, sizeof(dp));
    return dfs(tot, 10, 1) - 1;
}

ll find(int n)
{
    ll l = 1, r = 1e18, mid, ans;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (calc(mid) >= n)
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return ans;
}

int main()
{
    int n;
    cin >> n;
    cout << find(n) << endl;
    return 0;
}