四糸智乃

编辑于 2023-01-30 19:12 北京

+ 关注

【题解】2023牛客寒假算法基础集训营4 精

预估难度

alt

本场题目难度中等，没有高级算法和大型数据结构。难度最高的题目大概在区域赛铜+银-区间。

缝合题/edu比较多，最近没啥idea，这套题没啥思维含量，尽可能的啥知识点都缝了点进去。

可汗流出题法，全是板子，摆完挂机，没有脑子。纯粹的强大.jpg

出题思路

A/B题：知乎出题大法，思路就是去逛知乎上面有没有一些有趣的数学现象或者问题

A题：三进制为何比二进制更好？ https://www.zhihu.com/question/20194670/answer/862101520

B题：任何一个函数都可以表示成奇函数与偶函数的和成立吗？ https://www.zhihu.com/question/305529279/answer/551645074

E/L题：小学数学出题大法

EL题：原型都是小学数学题。

M题：是条件非常宽松的构造题，要的效果就是咋做都行。一般懒得想签到我就摆一个这玩意上去。

K题：小游戏出题法，打了个暴力发现初始状态下答案都是nm-1,知乎搜了一圈发现没人问这个问题

C/D题是缝合怪出题法，可以量产edu或者练习题。

C/D题本意是想出一个题作为动态规划和图论模型的edu题目。

显然引入最短路模型+动态规划的状态转移图是非常具有edu意义的。

出题的时候我备选用来缝合的素材有数字三角形、背包、区间dp。

数字三角形直接缝有点太简单了，虽然可以再引入其他素材，但是就有点臃肿了。

缝区间dp最大的问题就是不好讲，区间dp大部分人都写记忆化搜索，建图几句话讲不清楚。

引入最短路素材的话就随便缝个强选进去，反映到图论上就是起点终点最短路分层图解静态任意边查询的trick。

当然这个背包缝强选早就出烂了，比如[HEOI2013]EDEN的新背包问题

https://ac.nowcoder.com/acm/problem/20007

其他dp缝强选也都是这么搞搞

G/H也是缝合。

首先走格子抓人这个梗是个老梗，比如WF很早之前就有的一个木乃伊抓人[WF2011]Mummy Madness

随便缝了个迷宫bfs搜索+多查就可以上了。

随便缝的这个LRUD也是个基环树老梗，题号找不到了，大概是一开始n*m的格子上都有一个人，每个格子都是LRUD的方向，问足够长的时间以后还有多少个格子上面有人。

虽然缝的模型中带有基环树，但是基环树的特性在本题并未体现。

实际上这个题的上限有金牌题，只需要再缝个动态基环树的梗上去就好了。

也就是说本题如果带修改，就需要维护动态基环树，然后在上面二分即可。

（但是懒得写，看着就麻烦）

F就是想着随便出个数据“结构”题

要么是线段树，要么是树状数组，反正随便找个二叉树。

随便找了颗树状数组拿lowbit连一连发现大概是个树就直接上了。

I题因为CF之前出过一个一模一样的[CF 576]Points on Plane，所以加了一个不能往某个方向走的限制条件，更好的利用了一下莫队其中一个指针的单调特性。 https://codeforces.com/contest/576/problem/C

K题原本是想直接求从游戏开始到结束的期望，结果暴力打完都是nm-1，然后就这样了。

A、清楚姐姐学信息论

Tag：阅读题、数学

题意：比较两个进制，输出效率更高的进制。

知乎上面e进制的梗

三进制为何比二进制更好？ https://www.zhihu.com/question/20194670/answer/862101520

实际上不知道这个梗读完题直接按照题意模拟也可以过。

读完题就知道是比较 $x^{y}$ 和 $y^{x}$ 哪个大，如果是问高中生的话肯定秒答出来。但是大学生就忘了咋解了。

显然因为x和y都是正整数，所以可以对两式取对数变为 $l n (x^{y})$ 和 $l n (y^{x})$ ，对数函数中幂函数提到外面作为系数，即比较 $y\cdot ln(x)$ 和 $x\cdot ln(y)$ 。

到这里直接写代码计算浮点数其实已经可以通过。

大学生还可以通过构造函数 $f(x)=f(x)=\frac{x}{ln(x)}$ 求导函数 $f'(x)=\frac{ln(x)-1}{(ln(x))^2}$ 的方式求得e进制最优，且在e后进制效率单调递减。而2进制和4进制效率相同，所以3进制最优，2，4进制其次，其他进制越大效率越低。

时间复杂度： $O (1)$

空间复杂度： $O (1)$

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int x,y;
int main()
{
	scanf("%d %d",&x,&y);
	printf("%d\n",x==3||y==3?3:min(x,y));
	return 0;	
}

B、清楚姐姐学构造

Tag：数学

题意：在模系下构造两个数列，一个满足奇函数性质，另一个满足偶函数性质，两个数列的和为任意给定数列。

这个也是一个知乎问题任何一个函数都可以表示成奇函数与偶函数的和成立吗？ https://www.zhihu.com/question/305529279/answer/551645074

和原题的区别在于把函数改成了数列，然后把实数改成了模系数字。

任取一个数列c，设 $c[i]\equiv a[i]+b[i]$ ，设a[i]数列关于 $N / 2$ 对称，b[i]数列关于 $N / 2$ 对称相反。

则 $c[N-i-1]\equiv a[N-i-1]+b[N-i-1]$

两式相加可得 $c[i]+c[N-i-1] \equiv a[i]+b[i]+ a[N-i-1]+b[N-i-1]$ ，根据题意，b[i]数列对称相反消掉，a[i]数列关于 $N / 2$ 对称则 $a[i] \equiv a[N-i-1]$ 。化简得

$c[i]+c[N-i-1] \equiv 2\cdot a[i]$ 即 $a[i] \equiv (c[i]+c[N-i-1])\cdot inv(2)$ 。注意当 $m = 2$ 时无逆需要特殊处理。

相似的，两式相减得 $b[i] \equiv (c[i]-c[N-i-1])\cdot inv(2)$ 。和之前一样， $m = 2$ 时无逆特殊处理即可。

显然除非无逆，不然一定有解，当 $m = 2$ 时实际上只有00,11,01, $3$ 种情况，手动特判即可。

时间复杂度： $O (N)$

空间复杂度： $O (N)$

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n;
long long a[MAXN],b[MAXN],c[MAXN];
long long mod,inv2;
long long pow2(long long a,long long b)
{
	long long res=1;
	a=(a%mod+mod)%mod;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
long long inv(long long x)
{
	return pow2(x,mod-2);
}
void slove()
{
	inv2=inv(2);
	
	for(int i=1;i<=n;++i)
	{
		a[i]=(c[i]+c[n-i+1])*inv2%mod;
		b[i]=(c[i]+mod-c[n-i+1])*inv2%mod;
	}
	printf("Yes\n");
	for(int i=1;i<=n;++i)
	{
		printf("%lld%c",a[i]," \n"[i==n]);
	}
	for(int i=1;i<=n;++i)
	{
		printf("%lld%c",b[i]," \n"[i==n]);
	}
}

bool check()
{
	for(int i=1;i<=n;++i)
	{
		if(c[i]!=c[n-i+1])return false;
	}
	return true;
}
void slove_2()
{
	if(check())
	{
	    printf("Yes\n");
		for(int i=1;i<=n;++i)
		{
			printf("%lld%c",c[i]," \n"[i==n]);
		}
		for(int i=1;i<=n;++i)
		{
			printf("0%c"," \n"[i==n]);
		}
	}
	else
	{
		printf("No\n");
	}
}
int main()
{
	scanf("%d %lld",&n,&mod);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&c[i]);
	}
	if(mod==2)
	{
		slove_2();
	}
	else
	{
		slove();
	}
	return 0;	
}

C、清楚姐姐学01背包(Easy Version)

Tag：01背包，暴力

题意：问每个物品的价值再增加多少，可以保证其必定出现在01背包的答案集合中。

学会01背包以后可以先不放第 $i$ 个物品，求一次01背包，最后再放第 $i$ 个物品的同时模拟的进行状态转移，看看和最优的背包差多少，这样再+1就是答案。

时间复杂度： $O (N^{2} M)$

空间复杂度： $O (N M)$

#ifdef LOCAL_TEST
#include <probconfig.h>
#else
#define FIN
#define FOUT
#endif

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const int MAXM = 5005;
const long long INF = (1LL << 60);
int n, m, w[MAXN];
long long dp[MAXM], v[MAXN];

void update(long long &x, const long long &y, bool type = true)
{
    x = type ? max(x, y) : min(x, y);
}

long long cal(int id)
{
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; ++i)
    {
        if (id == i)
            continue;
        for (int j = m; j >= w[i]; --j)
        {
            update(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    long long limit = dp[m];
    long long ans = INF;
    for (int j = m - w[id]; j >= 0; --j)
    {
        update(ans, max(limit - (dp[j] + v[id]) + 1, 0LL), false);
    }
    return ans;
}

int main()
{
    FIN;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %lld", &w[i], &v[i]);
    }

    for (int i = 1; i <= n; i++)
    {
        printf("%lld\n", cal(i));
    }

    return 0;
}

D、清楚姐姐学01背包(Hard Version)

Tag：01背包，最短路模型

考虑Easy版本，发现不管怎样，都需要先不放第 $i$ 个物品，求一次01背包，即第 $i$ 个物品强制不选，然后求得一个dp数组，如何求这个数组呢。

考虑01背包即能从第 $1$ 个物品到第 $N$ 个物品递推过去，也能从第 $N$ 个物品到第 $1$ 个物品反向递推回来。设 $dp1_{ij}$ 表示背包内已经放了前 $i$ 个物品，背包的容量为 $j$ 时的最优解，设 $dp2_{ij}$ 表示背包内已经放了后 $i$ 个物品背包的容量为 $j$ 时的最优解。

利用 $dp1_{ij}$ 和 $dp2_{(i+1)j}$ 两dp数组相加求和就是去掉第 $i$ 个物品的dp数组。

为什么这里 $d p$ 数组满足可加性，可以借助图论模型去理解。

因为形如 $dp_i=max\{dp_j+val_j,...\}$ 的 $d p$ 方程，本质时 $d a g$ 图最短路，显然对于一条最短路径 $s \to t$ 可以拆分成 $s \to u \to v \to t$ ，假设 $u \to v$ 是一条单边。

那么反过来，如果已知 $s \to u$ 的最短路和 $v \to t$ 的最短路，只要枚举所有 $u \to v$ 的边就可以拼接出 $s \to t$ 的最短路。

这里所谓 $u \to v$ 的边指的是任意一个 $s \to t$ 的边割集。

如果不理解什么是边割集，可以参考：https://oi-wiki.org/graph/concept/#%E5%89%B2

时间复杂度： $O (N M)$

空间复杂度： $O (N M)$

#ifdef LOCAL_TEST
#include <probconfig.h>
#else
#define FIN
#define FOUT
#endif

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const int MAXM = 5005;
const long long INF = (1LL << 60);
int n, m, w[MAXN];
long long dp[MAXN][MAXM], dp2[MAXN][MAXM], v[MAXN];

void update(long long &x, const long long &y, bool type = true)
{
    x = type ? max(x, y) : min(x, y);
}

long long cal(int id)
{
    long long limit = 0;
    for (int i = 0; i <= m; i++)
    {
        update(limit, dp[id - 1][i] + dp2[id][i]);
    }
    long long ans = INF;
    for (int i = 0; i <= m - w[id]; i++)
    {
        long long pick_up = dp[id - 1][i] + dp2[id][i + w[id]] + v[id];
        update(ans, max(limit - pick_up + 1, 0LL), false);
    }
    return ans;
}

int main()
{
    FIN;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %lld", &w[i], &v[i]);
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= m; ++j)
        {
            update(dp[i + 1][j], dp[i][j]);
            if (j + w[i + 1] <= m)
                update(dp[i + 1][j + w[i + 1]], dp[i][j] + v[i + 1]);
        }
    }

    for (int i = n; i; --i)
    {
        for (int j = 0; j <= m; ++j)
        {
            update(dp2[i - 1][j], dp2[i][j]);
            if (j - w[i] >= 0)
                update(dp2[i - 1][j - w[i]], dp2[i][j] + v[i]);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        printf("%lld\n", cal(i));
    }

    return 0;
}

E、清楚姐姐打怪升级

Tag：数学，（二分）

题意：已知 $N$ 只怪物的血量、回血速度，自身的攻击力和攻击间隔，求打死所有怪物的时间。

考虑如果不能一刀秒杀，那么怪物必定会经过至少一次掉血+回血的循环。而最后一次击杀后，怪物立刻死亡肯定不会回血。

所以先把最后一刀减了，然后计算 $\delta=a-v_i$ ，如果 $\delta$ 小于等于 $0$ 就是无解。否则计算总轮数 $s=\left \lceil \frac{h_i}{\delta} \right \rceil + 1$ ， $(s-1)\cdot t+1$ 就是答案。

像这种题，如果你算不清楚，并且题目很明显的不卡时间多个log也能过，请使用二分，请使用二分，请使用二分。

时间复杂度：std: $O (N)$ ，二分： $O(N\cdot logN)$

空间复杂度： $O (N)$

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100005;
long long n,t,a,ans,h[MAXN],v[MAXN];
bool check()
{
    for(int i=1;i<=n;++i)
    {
        if(v[i]>=a&&h[i]>a)return false;
    }
    return true;
}
long long f(const long long &h,const long long &v)
{
    if(h<=a)return 1;
    long long delta=a-v;
    return (h-a+delta-1)/delta+1;
}
int main()
{
    scanf("%lld %lld %lld",&n,&t,&a);
    
    for(int i=1;i<=n;++i)
    {
        scanf("%lld %lld",&h[i],&v[i]);
        v[i]*=t;
    }
    if(!check())
    {
        printf("-1");
        return 0;
    }

    for(int i=1;i<=n;++i)
    {
        ans+=f(h[i],v[i]);
    }
    printf("%lld\n",(ans-1)*t+1);
}

F、清楚姐姐学树状数组

Tag：树状数组，暴力，dfs

题意：给一颗树状数组，建成一颗二叉树，查询若干个节点的前中后序遍历dfn。

首先学完树状数组以后，在注意到树状数组中的两条重要路径 $x \to x+lobit(x)$ 和 $x \to x-lobit(x)$

alt

如图所示，这条重要路径实际上就是树状数组单点修改时经过的路径。

注意到路径中某些部分和题目描述中构造的树边重合，不难发现，当一个节点是左孩子时，其父节点是 $x + l o b i t (x)$ 。

至于为什么，这要从二进制中发现原因，如果一个节点在树状数组中是左孩子，则其二进制形如xxxx010...0，即二进制最低位的1前一位是0。这样再加一个lowbit以后只会进一位。即 $l o g 2 (l o w b i t (x + l o w b i t (x))) = l o g 2 (l o w b i t (x)) + 1$ 。说人话就是 $x + l o w b i t (x)$ 和 $x$ 的lowbit值对2取对数只差1。

按照题意，我们还知道lowbit值对2取对数的几何意义就是二叉树的节点深度，并且我们还知道 $x + l o w b i t (x)$ 和 $x$ 之间再也不存在任何一个值满足这个条件。则可以断定 $x$ 就是 $x + l o w b i t (x)$ 的左子树。这个很好理解，二叉树上深度为 $k$ 的节点左边第一个深度为 $k - 1$ 的节点一定是它的左孩子。

alt

如图所示，这条重要路径实际上就是树状数组求前缀和时经过的路径。

注意到路径中某些部分和题目描述中构造的树边重合，不难发现，当一个节点是右孩子时，其父节点是 $x - l o b i t (x)$ 。

至于为什么，这要从二进制中发现原因，如果一个节点在树状数组中是左孩子，则其二进制形如xxxx110...0，即二进制最低位的1前一位是1。这样去掉最后一个lowbit以后，新数的lowbit反倒会进1。

按照题意，我们还知道lowbit值对2取对数的几何意义就是二叉树的节点深度，并且我们还知道 $x - l o w b i t (x)$ 和 $x$ 之间再也不存在任何一个值满足这个条件。则可以断定 $x$ 就是 $x - l o w b i t (x)$ 的右子树。二叉树上深度为 $k$ 的节点右边第一个深度为 $k - 1$ 的节点一定是它的右孩子。

有了上面的分析，不难写出判断节点是否为左孩子，以及求某节点父节点的代码

bool is_left_child(long long x)
{
    return !(x & (lowbit(x) << 1));
}

long long fa(long long x)
{
    return is_left_child(x) ? x + lowbit(x) : x - lowbit(x);
}

反过来，我们还能扩展一下逆向思维，左孩子是形如xxxx010...0进位的结果，所以可以写出如下代码还原

long long lch(long long x)
{
    return x ^ lowbit(x) ^ (lowbit(x) >> 1);
}

右孩子是形如xxxx110...0去掉末尾的lowbit后的结果，所以可以反推右子树

long long rch(long long x)
{
    return x ^ (lowbit(x) >> 1);
}

有了这几个关系，就可以把题目中的二叉树建出来，但是因为 $N$ 太大建不出来，也不用真的去建，只需要在dfs的时候顺手计算子树尺寸加起来即可。因为长度大小为 $2^{k}$ 的树状数组除根节点外都是全满的，大小实际上就是 $2^{m} - 1$ 可以直接计算。所以dfs模拟前序和后序的过程中跳过整颗的子树部分直接计算答案即可。

至于线段树、树状数组和二进制的关系可以去看一下某篇老古董ppt，zkw统计的力量，但是不用去学zkw线段树，感受一下二进制与二叉树的启发就可以了。不推荐学习，因为还有太多比zkw线段树更值得学习的算法了，普通选手看看就好，厨力选手可以选择拉满。

时间复杂度： $O (l o g N)$

空间复杂度： $O (l o g N)$

#ifdef LOCAL_TEST
#include <probconfig.h>
#else
#define FIN
#define FOUT
#endif

#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int MAXN = 2005;
int k, q;
long long n, x;

long long lowbit(long long x)
{
    return x & -x;
}

long long size(long long x)
{
    return (lowbit(x) << 1) - 1;
}

bool is_left_child(long long x)
{
    return !(x & (lowbit(x) << 1));
}

long long fa(long long x)
{
    return is_left_child(x) ? x + lowbit(x) : x - lowbit(x);
}

long long lch(long long x)
{
    return x ^ lowbit(x) ^ (lowbit(x) >> 1);
}

long long rch(long long x)
{
    return x ^ (lowbit(x) >> 1);
}

long long VLR(long long x)
{
    long long root = n;
    long long ret = 1;
    while (root != x)
    {
        ++ret;
        if (x < root)
        {
            root = lch(root);
        }
        else
        {
            ret += size(lch(root));
            root = rch(root);
        }
    }
    return ret;
}

long long LRD(long long x)
{
    if (x == n)
        return n;
    long long root = x;
    long long ret = size(root);
    while (root != n)
    {
        if (root == rch(fa(root)))
        {
            ret += size(lch(fa(root)));
        }
        root = fa(root);
    }
    return ret;
}

int main()
{
    FIN;
    scanf("%d %d", &k, &q);
    n = (1LL << k);
    while (q--)
    {
        scanf("%lld", &x);
        printf("%lld %lld %lld\n", VLR(x), x, LRD(x));
    }
    return 0;
}

G、清楚姐姐逛街(Easy Version)

Tag：bfs

题意：终点会按照固定方式移动的迷宫搜索问题，多次查询。

其实只用说明白一个事情就可以了，一般的迷宫搜索会有一个 $v i s$ 数组表示是否已经搜索过，这道题最大的问题是如果都放到 $v i s$ 数组里面是一个四维 $80 0^{4}$ 大小的 $v i s$ 数组存不下。考虑是否真的需要存终点，发现是不必要的，因为清楚姐姐的移动方式是固定的，只要时间 $t$ 确定，终点的位置就是确定的。显然智乃移动到任意位置的最短时间都是定值，所以只需要用 $v i s$ 保存智乃的位置即可。接下来就和普通的迷宫搜索问题一样了。

可能会有人有疑问，如果不保存清楚姐姐的位置，那么如果智乃来回走不就会导致智乃在某个位置时，清楚姐姐的位置存在多种可能了。实际上智乃不会来回走，在最短路径下，智乃至多停下来等待一轮（当且仅当 $(x_{s}, y_{s})$ 和 $(x_{t}, y_{t})$ 奇偶性不同时，必定停下来等待一轮）。

时间复杂度： $O (N M Q)$

空间复杂度： $O (N M)$

std懒得写了，引用一下内测同学cstdios的代码。

#include <bits/stdc++.h>
#define int long long 
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
const int INF=805;
const int fx[]={0,0,-1,1};
const int fy[]={1,-1,0,0};
int n,m,sx,sy,qq,dis_[INF][INF];
char Map[INF][INF];
queue < pii >q;
signed main()
{
    memset(dis_,63,sizeof dis_);
    ios::sync_with_stdio(false);
    cin>>n>>m>>sx>>sy>>qq;
    sx++;sy++;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            cin>>Map[i][j];
    q.push({sx,sy});dis_[sx][sy]=0;
    while (q.size()) {
        int x=q.front().fi,y=q.front().se;
        q.pop();
        for (int i=0;i<4;i++) {
            int gx=x+fx[i],gy=y+fy[i];
            if (gx<1 || gy<1 || gx>n || gy>m) continue;
            if (dis_[gx][gy]<=dis_[x][y]+1) continue;
            if (Map[gx][gy]=='#') continue;
            dis_[gx][gy]=dis_[x][y]+1;
            q.push({gx,gy});
        }
    }
     
    while (qq--) {
        int x=0,y=0,fl=0,res=1;
        cin>>x>>y;x++;y++;
        while ("If the world loves me") {
            int lax=x,lay=y;
            if (Map[x][y]=='U' && Map[x-1][y]!='#') x--;
            else if (Map[x][y]=='D' && Map[x+1][y]!='#') x++;
            else if (Map[x][y]=='R' && Map[x][y+1]!='#') y++;
            else if (Map[x][y]=='L' && Map[x][y-1]!='#') y--;
            if (lax==x && lay==y) {
                if (dis_[x][y]>1e9) {
                    fl=-1;
                    break;
                }
            }
            if (dis_[x][y]<=res) {
                fl=max(dis_[x][y],res);
                break;
            }
            res++;
        }
        cout<<fl<<"\n";
    }
    return 0;
}

H、清楚姐姐逛街(Hard Version)

Tag：bfs，倍增法，二分答案

考虑答案是否具有单调性，即如果 $t$ 个时刻可以追上清楚姐姐，那么 $t + 1$ 个时刻能否保持追上清楚姐姐的状态，显然时可以的。因为你可以尾随清楚姐姐粘在她身上。

既然问题具有单调性，显然是可以利用二分答案的思路将求解性问题转化为判断性问题的。这道题的 $c h e c k$ 函数也很好写。

首先使用倍增跳表预处理清楚姐姐在每一个位置移动若干步后的位置，以及智乃从起点到达所有位置的最短距离。

二分答案，如果智乃比清楚姐姐更先到达清楚姐姐在 $t$ 个时刻后移动到的终点，那么显然智乃可以在终点提前等着清楚姐姐相遇，此时为真，否则为假。

此时已经可以用 $O(NM+Q\cdot log(NM)^2)$ 的时间复杂度解决本题。

要注意，当二分里面嵌套倍增一起使用时，可以把二分改为倍增的写法去掉一个log。

（本题如果使用LCT维护动态基环树，则可实现带修操作）

时间复杂度：std: $O(NM+Q\cdot log(NM))$ ，二分套倍增 $O(NM+Q\cdot log(NM)^2)$

空间复杂度： $O(NM\cdot log(NM))$

二分套倍增

#include<bits/stdc++.h>
using namespace std;
const int MAXN=805;
const int LOGN=20;
const int MAXM=MAXN*MAXN;
using P=pair<int,int>;
#define K first
#define V second
P next_p[MAXN][MAXN][LOGN];
int n,m,x_s,y_s,x_t,y_t,q;
char a[MAXN][MAXN];
int dis[MAXN][MAXN];
const int dx[]={-1,0,1,0,0};
const int dy[]={0,1,0,-1,0};
unordered_map<char,int>dir={{'U',0},{'R',1},{'D',2},{'L',3},{'.',4}};
void bfs(int x,int y)
{
	dis[x][y]=0;
	queue<P>q;
	q.push({x,y});
	while(!q.empty())
	{
		auto now=q.front();
		q.pop();
		for(int i=0;i<4;++i)
		{
			if(a[now.K+dx[i]][now.V+dy[i]]!='#'&&dis[now.K+dx[i]][now.V+dy[i]]==-1)
			{
				dis[now.K+dx[i]][now.V+dy[i]]=dis[now.K][now.V]+1;
				q.push({now.K+dx[i],now.V+dy[i]});
			}
		}
	}
}
P get_next(int x,int y,int step)
{
	for(int i=LOGN-1;~i;--i)
	{
		if(step&(1<<i))
		{
			int nx=next_p[x][y][i].K;
			int ny=next_p[x][y][i].V;
			x=nx;
			y=ny;
		}
	}
	return make_pair(x,y);
}
int main()
{
	scanf("%d %d %d %d %d",&n,&m,&x_s,&y_s,&q);
	for(int i=0;i<n;++i)
	{
		scanf("%s",a[i]);
	}
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<m;++j)
		{
			if(a[i][j]!='#')
			{
				int x=i+dx[dir[a[i][j]]];
				int y=j+dy[dir[a[i][j]]];
				next_p[i][j][0]=a[x][y]=='#'?make_pair(i,j):make_pair(x,y);
			}
		}
	}
	for(int k=1;k<LOGN;++k)
	{
		for(int i=0;i<n;++i)
		{
			for(int j=0;j<m;++j)
			{
				if(a[i][j]!='#')
				{
					int x=next_p[i][j][k-1].K;
					int y=next_p[i][j][k-1].V;
					next_p[i][j][k]=make_pair(next_p[x][y][k-1].K,next_p[x][y][k-1].V);
				}
			}
		}
	}
	memset(dis,-1,sizeof(dis));
	bfs(x_s,y_s);
	while(q--)
	{
		scanf("%d %d",&x_t,&y_t);
		
		int l=0;
		int r=MAXM;
		int ans=-1;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			auto qcjj=get_next(x_t,y_t,mid);
			if(~dis[qcjj.K][qcjj.V]&&dis[qcjj.K][qcjj.V]<=mid)
			{
				ans=mid;
				r=mid-1;
			}
			else
			{
				l=mid+1;
			}
		}
		printf("%d\n",ans);
	}
    return 0;
}

单倍增版本

#include<bits/stdc++.h>
using namespace std;
const int MAXN=805;
const int LOGN=20;
const int MAXM=MAXN*MAXN;
using P=pair<int,int>;
#define K first
#define V second
P next_p[MAXN][MAXN][LOGN];
int n,m,x_s,y_s,x_t,y_t,q;
char a[MAXN][MAXN];
int dis[MAXN][MAXN];
const int dx[]={-1,0,1,0,0};
const int dy[]={0,1,0,-1,0};
unordered_map<char,int>dir={{'U',0},{'R',1},{'D',2},{'L',3},{'.',4}};
void bfs(int x,int y)
{
	dis[x][y]=0;
	queue<P>q;
	q.push({x,y});
	while(!q.empty())
	{
		auto now=q.front();
		q.pop();
		for(int i=0;i<4;++i)
		{
			if(a[now.K+dx[i]][now.V+dy[i]]!='#'&&dis[now.K+dx[i]][now.V+dy[i]]==-1)
			{
				dis[now.K+dx[i]][now.V+dy[i]]=dis[now.K][now.V]+1;
				q.push({now.K+dx[i],now.V+dy[i]});
			}
		}
	}
}
int main()
{
	scanf("%d %d %d %d %d",&n,&m,&x_s,&y_s,&q);
	for(int i=0;i<n;++i)
	{
		scanf("%s",a[i]);
	}
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<m;++j)
		{
			if(a[i][j]!='#')
			{
				int x=i+dx[dir[a[i][j]]];
				int y=j+dy[dir[a[i][j]]];
				next_p[i][j][0]=a[x][y]=='#'?make_pair(i,j):make_pair(x,y);
			}
		}
	}
	for(int k=1;k<LOGN;++k)
	{
		for(int i=0;i<n;++i)
		{
			for(int j=0;j<m;++j)
			{
				if(a[i][j]!='#')
				{
					int x=next_p[i][j][k-1].K;
					int y=next_p[i][j][k-1].V;
					next_p[i][j][k]=make_pair(next_p[x][y][k-1].K,next_p[x][y][k-1].V);
				}
			}
		}
	}
	memset(dis,-1,sizeof(dis));
	bfs(x_s,y_s);
	while(q--)
	{
		scanf("%d %d",&x_t,&y_t);
		int ans=0;
		for(int i=LOGN-1;~i;--i)
        {
            auto qcjj=make_pair(next_p[x_t][y_t][i].K,next_p[x_t][y_t][i].V);
            if(dis[qcjj.K][qcjj.V]==-1||dis[qcjj.K][qcjj.V]>ans+(1<<i))
            {
                ans+=1<<i;
                x_t=qcjj.K;
                y_t=qcjj.V;
            }
        }
		printf("%d\n",++ans==(1<<LOGN)?-1:ans);
	}
    return 0;
}

I、清楚姐姐采蘑菇

Tag：莫队、单调性

题意：在二维循环平面上找一条路径经过所有的目标点，要求只能往四个方向中的三个方向移动，路劲长度不超过 $2.01 \times 10^6$ 。

如果不会莫队的话先去学一下。

https://oi-wiki.org/misc/mo-algo/

这个题CF之前有个差不多的，可以先去做一下。

https://codeforces.com/contest/576/problem/C

显然 $2.01 \times 10^6$ 看上去是一个 $O(2\cdot N\sqrt{N}+2\cdot N)$ 的东西，在二维平面上移动可以看成是 $x$ 和 $y$ 两个指针的移动。

显然这道题完美契合莫队的模型，唯一的问题就是禁掉的方向，不过仔细一想，在使用莫队的时候，一个指针在块内横条，另一个指针在整个范围内单调移动。最终使得莫队的时间复杂度为 $O(N\sqrt{N})$ 。所以只要将指针单调移动的方向与题目中禁止的反方向对齐即可。

时间复杂度： $O(N\sqrt{N})$

空间复杂度： $O(N\sqrt{N})$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
using P = pair<int, int>;
#define K first
#define V second
int n, m, x, y, BLOCK;
char X;
vector<P> Data;
vector<char> ans;
void U(){x=x?x-1:n-1,ans.push_back('U');}
void D(){x=(x+1)%n,ans.push_back('D');}
void L(){y=y?y-1:n-1, ans.push_back('L');}
void R(){y=(y+1)%n, ans.push_back('R');}
int main()
{
    scanf("%d %d %c", &n, &m, &X);
    BLOCK = sqrt(n + 0.5);
    for (int i = 0; i < m; ++i)
    {
        P p;
        scanf("%d %d", &p.K, &p.V);
        Data.push_back(move(p));
    }
    sort(Data.begin(), Data.end(), [](const P &A, const P &B)
         {
		if(X=='L'||X=='R')
        {
            if(A.K/BLOCK!=B.K/BLOCK)return A.K/BLOCK<B.K/BLOCK;
            return X=='L'?A.V<B.V:A.V>B.V;
        }
        else
        {
            if(A.V/BLOCK!=B.V/BLOCK)return A.V/BLOCK<B.V/BLOCK;
            return X=='U'?A.K<B.K:A.K>B.K;
        } });
    for (int i = 0; i < m; ++i)
    {
        while (x > Data[i].K && X == 'U')D();
        while (x < Data[i].K && X == 'D')U();
        while (y > Data[i].V && X == 'L')R();
        while (y < Data[i].V && X == 'R')L();
        while (x > Data[i].K)U();
        while (x < Data[i].K)D();
        while (y > Data[i].V)L();
        while (y < Data[i].V)R();
    }
    ans.push_back('\0');
    printf("%s\n", ans.data());
}

J、清楚姐姐学排序

Tag：排序，dfs，bfs

题意：给定一个数组中若干对元素大小关系，求顺序确定的位置和该位置的元素。

由kth_element（快速排序中确定某一个数位置的算法）得到启示，如果一个数字在数组中可以确信的找到 $a$ 个比它大的和 $b$ 个比它小的，且 $a + b = n - 1$ 即它已经和所有元素都进行过比较，那么该元素的位置就可以被确定。

所以只要暴力dfs或者bfs计算是不是有 $a$ 个比它大的和 $b$ 个比它小的即可。

对于C++，因为在搜索的过程中本质为01矩阵的或操作，所以可以使用bitset容器进行优化，复杂度可以优化一个常数到 $O (N M / w)$

这题有更低复杂度的算法。

时间复杂度：暴力: $O (N M)$ ，优化 $O (N M / w)$

空间复杂度： $O (N + M)$

暴力：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, m, ans[MAXN];
vector<int> L[MAXN], G[MAXN];
bool vis[MAXN];
void dfs(int x, vector<int> G[], int &cnt, bool flag = true)
{
    if (vis[x])
        return;
    if (flag)
    {
        cnt++;
        vis[x] = true;
    }
    for (auto i : G[x])
    {
        dfs(i, G, cnt);
    }
}
int calc_kth(int x)
{
    memset(vis, 0, sizeof(vis));
    int cntl = 0, cntg = 0;
    dfs(x, L, cntl, false);
    dfs(x, G, cntg, false);
    return cntl + cntg + 1 == n ? cntl + 1 : 0;
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        L[i].clear();
        G[i].clear();
        memset(ans, -1, sizeof(ans));
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        L[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        ans[calc_kth(i)] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d%c", ans[i], " \n"[i == n]);
    }
    return 0;
}

bitset优化

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, m, ans[MAXN],cnt[MAXN],dg[MAXN],dl[MAXN],rk[MAXN];
vector<int> L[MAXN], G[MAXN];
bool vis[MAXN];
bitset<MAXN>mat[MAXN];

void bfs(vector<int>G[],int d[],bool flag=false)
{
    for (int i = 1; i <= n; ++i)
    {
        mat[i].reset();
    }
    for (int i = 1; i <= n; ++i)
    {
        mat[i].set(i);
    }
    queue<int>q;
    for (int i = 1; i <= n; ++i)
    {
        if(!d[i])q.push(i);
    }
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(auto&i:G[now])
        {
            mat[i]|=mat[now];
            if(!--d[i])q.push(i);
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        flag?rk[i]=mat[i].count():0;
        cnt[i]+=mat[i].count()-1;
    }

}

int main()
{
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v),dg[v]++;
        L[v].push_back(u),dl[u]++;
    }

    bfs(G,dg,true);
    bfs(L,dl);
    memset(ans,-1,sizeof(ans));
    for (int i = 1; i <= n; i++)
    {
        cnt[i]==n-1?ans[rk[i]]=i:0;
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d%c",ans[i] , " \n"[i == n]);
    }
    return 0;
}

K、清楚姐姐玩翻翻乐

题意：给定一个残局，按照最优策略玩翻翻乐，求操作次数期望。

首先能想到翻翻乐游戏中可以进行的操作只有以下三种

1.已知两个相同的，选择两个进行消除。

2.选择一个已知的和一个未知的，有可能会消除。如果未消除，则将未知转化为已知。

3.选择两个未知的，有可能会消除。如果未消除，则将两个未知都转化为已知。

显然最优操作是1的优先度最高。

所以我们先把问题转化成，存在 $k$ 个已知且未配对的图案（配好对就按照1优先进行消除即可），和 $p$ 个未知的图案

至于2和3，得分情况进行讨论。

这里可以使用数学方法或者暴力程序精确计算出对于每一个 $k$ 和 $p$ 的情况下到底谁更优。

大家可以自行计算每一个 $k$ 和 $p$ 的情况下消除的概率，但是实际上它并不是一个解题思路。

对于解题思路而言首先感性的认识到，当 $p$ 足够大的时候，无论2还是3，大概率是消不掉的。最多就是帮你贡献几个图案变为已知。

那显然这种情况下3都优于2，因为操作3可以贡献两个已知，而操作2只能贡献一个已知。

那多大叫做“足够大”呢，这里你可以找一个特例手算一下，如果这个特例满足，那比它更大的话因为操作2和操作3的概率都是单调递减函数。所以比这个特例大的一定满足。

std选了一个 $p = 6$ 的特例打表，对于剩下的相当于只有一种操作，即操作3最优。

对于操作3，再分成如下4种情况进行讨论可以写出 $d p$ 转移方程即可。

1.消除2个。

2.不消除，转化的2个未知且不配对。

2.不消除，但是转化的2个未知有1个配对。

2.不消除，但是转化的2个未知全部配对。

当然，也可以写一个不含任何贪心成分的纯暴力（因为暴力程序的复杂度也是 $O (N^{2} M^{2})$ ，在比赛的时候要么猜结论，要么交暴力）。

时间复杂度： $O (N^{2} M^{2})$

空间复杂度： $O (N^{2} M^{2})$

#ifdef LOCAL_TEST
#include <probconfig.h>
#else
#define FIN
#define FOUT
#endif

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int MAXN = 55;
const int MAXM = 3005;
int N, M, a[MAXN][MAXN], n, k;
long long dp[MAXM][MAXM], inv[MAXM], ans;
unordered_map<int, int> mp;
void init_table()
{
    memset(dp, -1, sizeof(dp));
    inv[1] = 1;
    for (int i = 2; i <= 3000; ++i)
    {
        inv[i] = ((mod - mod / i) * inv[mod % i]) % mod;
    }
    dp[0][0] = 0;
    dp[1][1] = 1 % mod;
    dp[2][0] = 1 % mod;
    dp[2][2] = 5 * inv[2] % mod;
    dp[3][1] = 8 * inv[3] % mod;
    dp[3][3] = 4 % mod;
    dp[4][0] = 3 % mod;
    dp[4][2] = 17 * inv[4] % mod;
    dp[4][4] = 11 * inv[2] % mod;
    dp[5][1] = 23 * inv[5] % mod;
    dp[5][3] = 29 * inv[5] % mod;
    dp[5][5] = 7 % mod;
    dp[6][0] = 5 % mod;
    dp[6][2] = 37 * inv[6] % mod;
    dp[6][4] = 22 * inv[3] % mod;
    dp[6][6] = 17 * inv[2] % mod;
}

long long dfs(int n, int k)
{
    if (~dp[n][k])
        return dp[n][k];

    int m = n - k;
    // m pair

    long long inv_sum = 1LL * inv[n] * inv[n - 1] * 2 % mod;
    long long p1 = 1LL * k * (k - 1) * inv[2] % mod * inv_sum % mod; // kk      -2
    long long p2 = 1LL * k * m * inv_sum % mod;                      // km      -1
    long long p3 = 1LL * (m - 2) * m * inv[2] % mod * inv_sum % mod; // mm       0
    long long p4 = 1LL * m * inv[2] % mod * inv_sum % mod;           // mm      -1

    dp[n][k] = 0;

    if (p1)
    {
        dp[n][k] += (dfs(n - 2, k - 2) + 2) * p1 % mod;
    }
    if (p2)
    {
        dp[n][k] += (dfs(n - 2, k) + 1) * p2 % mod;
    }
    if (p3)
    {
        dp[n][k] += (dfs(n - 2, k + 2)) * p3 % mod;
    }
    if (p4)
    {
        dp[n][k] += (dfs(n - 2, k)) * p4 % mod;
    }
    dp[n][k]++;
    dp[n][k] %= mod;
    return dp[n][k];
}
int main()
{
    init_table();
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= M; ++j)
        {
            scanf("%d", &a[i][j]);
            if (a[i][j])
                mp[a[i][j]]++;
        }
    }
    n = N * M;
    for (auto &[i, j] : mp)
    {
        if (j == 1)
            --n, ++k;
        else
            n -= 2, ++ans;
    }
    printf("%lld\n", (ans + dfs(n, k)) % mod);
}

L、清楚姐姐的三角形I

题意：解三元一次方程组，并且要求解是正整数且能组成三角形。

解三元一次方程组，三个方程三个未知数，6年级小朋友都知道是唯一解。

然后简单判断一下是不是正整数，能不能组成三角形即可。

时间复杂度： $O (1)$

空间复杂度： $O (1)$

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

int va,vb,vc,a,b,c;
int T;
bool check(int a,int b,int c)
{
    if(a<=0||b<=0||c<=0)return false;
    vector<int>arr={a,b,c};
    sort(arr.begin(),arr.end());
    return arr[0]+arr[1]>arr[2];
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d %d",&va,&vb,&vc);
        a=vb+vc-va;
        b=va+vc-vb;
        c=va+vb-vc;
        if((a&1)||(b&1)||(c&1))
        {
            printf("No\n");
        }
        else{
            a/=2;
            b/=2;
            c/=2;
            if(check(a,b,c))
            {
                printf("yes\n%d %d %d\n",a,b,c);
            }
            else
            {
                printf("No\n");
            }
        }
    }
}

M、清楚姐姐的三角形II

题意：构造一个长度大小为 $N$ 的数组，任意相邻三项不能组成三角形。

随便做，样例的斐波那契数列是骗人的，最简单的比如1 1 2循环即可。

时间复杂度： $O (N)$

空间复杂度： $O (1)$

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

int n;
int a[]={1,1,2};

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        printf("%d%c",a[i%3]," \n"[i==n-1]);
    }
}

2024最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(0) 回帖

加载中...

话题同步到我的动态回帖

【题解】2023牛客寒假算法基础集训营4 精

预估难度

出题思路

A、清楚姐姐学信息论

B、清楚姐姐学构造

C、清楚姐姐学01背包(Easy Version)

D、清楚姐姐学01背包(Hard Version)

E、清楚姐姐打怪升级

F、清楚姐姐学树状数组

G、清楚姐姐逛街(Easy Version)

H、清楚姐姐逛街(Hard Version)

I、清楚姐姐采蘑菇

J、清楚姐姐学排序

K、清楚姐姐玩翻翻乐

L、清楚姐姐的三角形I

M、清楚姐姐的三角形II

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐