四糸智乃

04-29 09:43 已编辑深信服_算法工程师

关注

【题解】牛客练习赛124_PLUS

尝试出小白月赛的又一次失败

来内测的同学都觉得这套题难，但是我不知道难在哪里。尤其是A题。。。我不知道它为什么难，但是内测来10个人有8个都觉得难。

A、智乃的gcd构造

如果你看WA和TLE的代码，你可以看到各路神仙思路，我不明白在算什么奇怪的式子，但我觉得很多写法和思考的难度已经远大于正解了，感觉是脑补了另一个更hard的问题在做。

其实是诈骗题，对于 $|a+b|\geq x$ 和 $|a-b|\geq y$ 这两个条件，当 $a$ 的值非常小， $b$ 的值非常大时就同时满足了。

所以并不是所有输入的变量都需要用到，只需要 $z$ 就可以了。

直接输出 $z$ 和 $inf/z*z$ 即可。

#include <bits/stdc++.h>
using namespace std;
const long long INF = 5e18;
int n;
int main()
{
    long long x, y, z;
    cin >> x >> y >> z;
    cout << z<<" " << INF / z * z << endl;
}

B、智乃的Chino语言随机数生成器(easy version)

这个题就是介绍了一种模拟的语言，告诉你一个随机数生成器，让你取反后输出。

最简单的方法是

3
rand 0
test 0 1 0
return 0

easy可以帮你测试hard的代码，然后顺带提示，可以利用test功能取反。

C、智乃的k线段区间

经典扫描线算法，如图所示

我们先预处理出所有“包含K条线段”的最小区间。这一步预处理过程我们可以借助std::priority_queue或者std::multiset很方便的做到，或者排序后直接二分，总之只要读进来之后按照右端点排序，取最近的第 $K$ 个左端点坐标即可。

在上图中，这个已处理的部分我们用红色区间表示。

现在想，有一条扫描线从左往右扫描红色区间。

假设扫描到第一个红色区间的右端点，我们叫它 $now_r$ ，对应的左端点叫 $now_l$ 、那么很显然，包含该红色部分的区间数目为 $(now_l)\times(M-now_r+1)$ 。接下来当扫描线继续向右扫描，推进到下一个红色区间的时候，假设下一个红色区间的左右端点分别为 $now_l'$ 和 $now_r'$ 。显然因为右侧的区间没有统计过，所以右边仍然是 $(M-now_r+1)$ ，但是对于左边，从 $now_l$ 到 $now_l'$ 的区间都已经被统计过了，所以不要再重复统计，所以移动时的增量为 $(now_l'-now_l)\times(M-now_r'+1)$ 。当然这么写还不够，实际处理的时候还要保证 $now_l$ 的值始终单调不降，即取前缀max。

#include <bits/stdc++.h>
using i64 = long long;
const i64 INF = (i64)9e18;
const i64 mod = 1e9 + 7;

...
//-----------------------------------------
using namespace std;
const int MAXN = 100005;
using i64 = long long;
class L {
  private:
    multiset<i64> s;
    int _k;

  public:
    L(int k) : _k(k) {}
    void push(i64 val) {
        s.insert(val);
        while (s.size() > _k) {
            s.erase(s.begin());
        }
    }
    i64 get() const {
        if (s.size() < _k) {
            return -1;
        }
        return *s.begin();
    }
};

map<i64, vec_t<i64, 1>> v;
int main() {
    int n, k;
    i64 m;
    read(n, m, k);
    L s(k);
    for (int i = 1; i <= n; ++i) {
        i64 l, r;
        read(l, r);
        v[r].push_back(l);
    }
    i64 nowl = 1;
    i64 ans = 0;
    for (const auto& it : v) {
        for (const auto& i : it.second) {
            s.push(i);
        }
        if (s.get() != -1 && s.get() >= nowl) {
            ans += (m - it.first + 1) * (s.get() - nowl + 1);
            nowl = s.get() + 1;
        }
    }
    println(ans);
    return 0;
}

D、智乃的原始部落

这个题我也没想明白为什么难，可能没看到数据范围，本来是想贪心，发现贪不了一点，打了暴力找了几天规律放弃了，然后把数据范围改成暴力能过的范围。本来是放到了C题的地方，然后被内测同学吐槽后改为了D题

当然，暴力也没有那么的暴力，还是需要一些贪心技巧的。

首先这个问题有一个IO方言，叫《子集mex》，感兴趣可以自行了解一下。

对于两块金条，假设长度分别为 $a,b$ ，我们可以找零表示的最大可以表示的数字为 $s$ 。我们可以用一个三元组 $(a,b,s)$ 来表示一个当且状态。定义 $f(a,b,s)$ 表示当前长度分别为 $a,b$ ，最大可以表示的数字为 $s$ 的最小代价。初始状态为 $f(l_a,l_b,0)$ 。

我们思考这样一个问题，当满足如下约束条件时

$\left\{\begin{matrix}a'\geq a\\b' \geq b \\s' \leq s \end{matrix} \right.$

必定存在 $f(a',b',s')\leq f(a,b,s)$ 成立。所以每次dfs的时候贪心的取 $s$ 准没错，除非金条剩余部分已经满足条件，需要直接加到 $s$ 中。

思考时间复杂度，发现最坏情况就是按照 $1,2,4,8,16,...$ 倍增，所以最多递归 $log(max(n,m))$ 次，每次dfs要么切 $a$ 要么切 $b$ ，复杂度为 $O(2^{log(max(n,m))})=O(max(n,m))$ ，所以暴力即可通过本题。

#include <bits/stdc++.h>

using namespace std;

...

const long long INF = 1e18;

int main() {
    int n, m, a, b, flag = 1;
    using i64 = long long;
    i64 ans = INF;
    read(n, m, a, b);
    vec_t<int, 1> ta, tb;
    std::function<void(int, int, int, i64, int)> dfs = [&](int now, int n, int m,
    i64 sum, int option) {
        if (sum > ans || !flag) {
            return;
        }
        if (n == 0 && m == 0) {
            if (option) {
                flag = 0;
            } else {
                ans = min(ans, sum);
            }
            return;
        }
        if (n && n <= now + 1) {
            if (option & flag)ta.push_back(n);
            dfs(now + n, 0, m, sum, option);
            if (option & flag)ta.pop_back();
        }
        if (m && m <= now + 1) {
            if (option & flag)tb.push_back(m);
            dfs(now + m, n, 0, sum, option);
            if (option & flag)tb.pop_back();
        }
        if (n && n > now + 1) {
            if (option & flag)ta.push_back(now + 1);
            dfs(now << 1 | 1, n - now - 1, m, sum + a, option);
            if (option & flag)ta.pop_back();
        }
        if (m && m > now + 1) {
            if (option & flag)tb.push_back(now + 1);
            dfs(now << 1 | 1, n, m - now - 1, sum + b, option);
            if (option & flag)tb.pop_back();
        }
    };
    dfs(0, n, m, 0, 0);
    dfs(0, n, m, 0, 1);
    println(ans, (int) ta.size() - 1, (int) tb.size() - 1);
    for (int i = 0; i < ta.size(); ++i) {
        printf("%d%c", ta[i], " \n"[i + 1 == ta.size()]);
    }
    for (int i = 0; i < tb.size(); ++i) {
        printf("%d%c", tb[i], " \n"[i + 1 == tb.size()]);
    }
    return 0;
}

E、智乃的括号匹配

本来是道小白赛题，中间那个符号本来是个异或。

发现改成乘号的话有点意思，但其实也没那么难。

首先先说一下，假设没有负数，那么直接区间dp，同时这个区间dp隐含了一个贪心。

就是区间DP以外的部分，默认它的值是0，因为一定会被枚举到。

现在现在有负数，你不能默认它是 $0$ 。

从结果考虑，当所有的括号全部匹配后，剩余部分一定是

形如 $)))))...)(...(((($ 的结构、

所以可以枚举断点，然后在匹配区间外，断点左侧全部为')'，右侧全部为'('。

你可以把所有的dp全部耦合在一起写一个大DP，但我强烈不推荐这样写。

你就写一个 $n^3$ 的dp表示括号完整匹配，然后单独写两个 $n^2$ 的线性dp合并。参考std代码。

#include <bits/stdc++.h>
using i64 = long long;
 
using namespace std;
const int MAXN = 1005;
const i64 INF = 1LL << 60;
i64 dp[MAXN][MAXN], c[MAXN][2], v[MAXN];  //0:'(',1:')'
bool vis[MAXN][MAXN];
i64 dp2[MAXN], dp3[MAXN];
char s[MAXN];
i64 val(int l, int r)
{
    if (l > r)
        return 0;
    if (((r - l) & 1) == 0)
        return -INF;
    if (vis[l][r])
        return dp[l][r];
    vis[l][r] = true;
    dp[l][r] = val(l + 1, r - 1) + c[l][0] + c[r][1] + (v[l] * v[r]);
    for (int i = l + 1; i < r; i += 2)
    {
        dp[l][r] = max(dp[l][r], val(l, i) + val(i + 1, r));
    }
    return dp[l][r];
}
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lld",&v[i]);
    }
    for (int i = 1; i <= n; ++i)
    {
        int op = s[i] == '(';
        scanf("%lld",&c[i][op]);
        c[i][op] *= -1;
    }
    for (int i = 1; i <= n; ++i)
    {
        dp2[i] = dp3[i] = -INF;
    }
    
    for (int i = 1; i <= n; ++i)
    {
        dp2[i] = max(dp2[i], dp2[i - 1] + c[i][1]);
        for (int j = i - 1; j >= 1; j -= 2)
        {
            dp2[i] = max(dp2[i], dp2[j - 1] + val(j, i));
        }
    }
    for (int i = n; i; --i)
    {
        dp3[i] = max(dp3[i], dp3[i + 1] + c[i][0]);
        for (int j = i + 1; j <= n; j += 2)
        {
            dp3[i] = max(dp3[i], dp3[j + 1] + val(i, j));
        }
    }
    i64 ans = -INF;
    for (int i = 1; i <= n + 1; ++i)
    {
        ans = max(ans, dp2[i - 1] + dp3[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

F、智乃的Chino语言随机数生成器(hard version)

这个题原本是一个面试题，如果你去搜“不均匀分布随机数产生均匀分布随机数”，会搜到很多内容。

方法一：

01不等概率生成01等概率-CSDN博客

借助这个算法，我们无论输入的 $p$ 是多少，都能够获得01等概率随机数。接下来把生成的01随机数利用模拟位运算集中到一起。

利用chino语言，构造一个高精度比较大小的方法，就可以得到精度极高的任意概率随机数生成器。

这个是std使用的方案。

#include <bits/stdc++.h>
using namespace std;

const int MAXN=3005;
struct node
{
	int op,x,y,z;
	node(int _op=0,int _x=0,int _y=0,int _z=0):op(_op),x(_x),y(_y),z(_z){}
};
/*
0 rand
1 test
2 if
3 return
*/
vector<node>a;
int p,q;
int main() 
{
	map<int,string>mp={{0,"rand"},{1,"test"},{2,"if"},{3,"return"}};
	scanf("%d %d",&p,&q);
	int x=round(q*10.24);
	const int ONE=1000000;
	const int ZERO=999999;
	const int RAND=0;
	const int TEST=1;
	const int IF=2;
	const int RETURN=3;
	a.emplace_back(TEST,ONE,ONE,ONE);
	for(int i=0;i<10;++i)
	{
		if(x&(1<<i))
		{
			a.emplace_back(TEST,100009-i,100009-i,100009-i);
		}
	}
	for(int i=0;i<100;++i)
	{
		a.emplace_back(RAND,i,0,0);
	}
	for(int i=0;i<50;++i)
	{
		a.emplace_back(TEST,100+i,i*2,i*2+1);
		a.emplace_back(TEST,100+i,100+i,ZERO);
		for(int j=9;j;--j)
		{
			a.emplace_back(IF,100+i);
			a.emplace_back(TEST,200000+j,200000+j-1,ONE);
		}
		a.emplace_back(IF,100+i);
		a.emplace_back(TEST,200000,i*2,ONE);
	}
	for(int i=0;i<10;++i)
	{
		a.emplace_back(TEST,300000+i,200000+i,100000+i);
		a.emplace_back(TEST,300000+i,300000+i,ZERO);
		a.emplace_back(IF,300000+i);
		a.emplace_back(RETURN,200000+i);
	}
	a.emplace_back(RETURN,ONE);
	printf("%d\n",(int)a.size());
	for(auto &i:a)
	{
		printf("%s",mp[i.op].c_str());
		if(i.op==0||i.op==2||i.op==3)
		{
			printf(" %d\n",i.x);
		}
		else
		{
			printf(" %d %d %d\n",i.x,i.y,i.z);
		}
	}
    return 0;
}

方法二：

类似线段树/01字典树上二分，但是这个二分是不均匀的，需要记录当前返回0/1的概率和来决定接下来生成的数字是否返回，是否继续递归，是否需要取反。

这个的话大部分选手都是这样写的，可以参考一下通过代码。

G 队友被抓，边笑边刷

首先从题目中可以提取出几个可能影响答案的因素。

果酱的位置，打野的剩余复活时间，果酱转线的剩余时间，当前的时刻，果酱与打野的经济差

考虑DP，由于经济差巨大，所以无法成为前置维度，所以假设DP状态为

$DP[当前的时刻][果酱转线的剩余时间][打野的剩余复活时间][果酱的位置] = 果酱与打野的经济差$ 。

由于果酱一定会选择最大化经济差，所以可以保证对于4维确定的情况下，能获得最优答案。

此时时间复杂度为 $O(2nmk)$ ，一定会超时。

考虑优化掉一维，对于当前时刻，无法优化。

假设优化转线剩余时间，那么剩余状态为 $DP[当前的时刻][打野的剩余复活时间][果酱的位置] = 果酱与打野的经济差$ ，由于已经知道转线所需时间，且由于在转线过程中，打野所获得的经济可以提前预处理出来，所以时间复杂度可以优化为 $O(2nk)$ 。

假设优化复活时间，那么剩余状态为 $DP[当前的时刻][果酱转线的剩余时间][果酱的位置] = 果酱与打野的经济差$ ，通过优化打野死亡情况下，果酱的最优选择，可以将时间复杂度优化为 $O(2nm)$ 。由于打野死亡过程中，可能涉及多次转线的情况，所以该写法会有一点复杂，在内测过程中也确实有人这样实现，最终被Hack掉。

经过分析，可以优化掉转线剩余时间，来写出来一个比较好实现的代码。

剩下的就全是代码细节了。

代码如下

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 10,M = 1e2 + 10;
i64 dp[N][M][2],e[N];
int a[N],b[N],c[N],d[N];
i64 ask(int l,int r){
	if(l > r)return 0;
	return e[r] - e[l - 1];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	int n,m,k;
	cin >> n >> k >> m;//k转线 M复活
	memset(dp,0xcf,sizeof dp);
	dp[0][0][0] = 0;
	for(int i = 1;i <= n; i ++)
		cin >> a[i];
	for(int i = 1; i <= n; i ++)
		cin >> b[i];
	for(int i = 1;i <= n; i ++)
		cin >> c[i];
	for(int i = 1;i <= n; i ++)
		cin >> d[i];
    for(int i = 1; i<= n; i ++)
		e[i] = e[i - 1] + c[i];

	for(int i = 0; i <= n ;i ++){
		if(i >= 1){
			// 打野死了
			for(int j = 1;j < m; j ++){
				// 上路 吃经济
				dp[i][j][0] = max(dp[i][j][0],dp[i - 1][j + 1][0] + a[i]);
				// 下路没经济
				dp[i][j][1] = max(dp[i][j][1],dp[i - 1][j + 1][1]);
			}
			// 抓人
			if(d[i] == 1){
				//上路
				dp[i][0][0] = max(dp[i][0][0],dp[i - 1][0][0] + a[i] - c[i]);
				dp[i][0][0] = max(dp[i][0][0],dp[i - 1][1][0] + a[i] - c[i]);
				// 可以改d[i]
				// 代表在下路的受益 即将打野抓人经济与被反蹲经济区分开
				dp[i][m][1] = max(dp[i][m][1],dp[i - 1][0][1] + b[i]);
				dp[i][m][1] = max(dp[i][m][1],dp[i - 1][1][1] + b[i]);
			}else{
				dp[i][0][0] = max(dp[i][0][0],dp[i - 1][0][0] + a[i] - c[i]);
				dp[i][0][0] = max(dp[i][0][0],dp[i - 1][1][0] + a[i] - c[i]);
				dp[i][0][1] = max(dp[i][0][1],dp[i - 1][0][1] - c[i]);
				dp[i][0][1] = max(dp[i][0][1],dp[i - 1][1][1] - c[i]);
			}
		}
		// 转线
		if(i + k - 1 <= n){
			assert(k >= 1);
			for(int j = 0 ;j <= m;j ++){
				int x = i + k - 1,y = max(j - k + 1,0),l = i + max(j,1),r = x;
				dp[x][y][0] = max(dp[x][y][0],dp[i][j][1] - ask(l,r));
				dp[x][y][1] = max(dp[x][y][1],dp[i][j][0] - ask(l,r));
			}
		}
	}
	i64 ans = -1e18;
	for(int i = 0 ;i < 2; i ++)
		for(int j = 0 ;j <= m; j ++)
			ans = max(ans,dp[n][j][i]);
	if(ans > 0){
		cout <<"YYLX!\n";
		cout << ans <<"\n";
	}else cout <<"G!\n";
}