11.24 模拟赛题解
hyfhaha
·
·
个人记录
题解
题解就随便一点了，能看懂就行了
题目皆为原题，非原创，下文会标注原题出处
这次如果大家都不挂分的话应该280或者300以上都没问题，部分分给的很足，出得十分良心。
算是一场信心赛吧，码量都不算大，思维也不算难。
T1 打工job
这是一道十分常规的贪心，搞得我部分分都不知道怎么出了
其实这题就是考验选手有没有轻敌，许多选手刚看到题可能会以为是一个简单模拟或是简单贪心，没有仔细考虑清楚就开始写代码，后果可能会拿不到满分，甚至拿不到高分。
这题虽说是一道常规贪心，却是贪心中一个经典套路，反悔贪心
看到题的第一步肯定是想排序截止时间
正常人当然是想优先完成紧急的工作啦~
在紧急的工作里自然是优先完成报酬高的工作啦~
如果你想到这样贪心的话
枚举1~n项已经排好序的工作
每做一项工作就day++
然后符合条件就做
但是这样就只能拿到一些分
其实错误的原因很简单（如样例2
到后期万一都是高报酬的工作（但由于超时做不了了）
你会不会后悔前期做了哪些低报酬的工作呢？
所以贪心应该有一个后悔操作，把之前赚钱最少的那个工作去掉，换成现在这个更高报酬的工作。实现可以使用优先队列
正确思路就是先按截止日期排序，然后如果一个工作有时间去做，就先做了它（听起来有点怪），然后把它的价值压入一个小根堆。当我们找到一个**没法做**却**价值比当前堆顶高**的工作时，我们就放弃那个最小的工作，用做它的时间去做这个价值更高的工作。
当然这道题我也发现了许多奇奇怪怪的做法，例如树状数组什么的，有兴趣可以研究一下。
原题：luogu [**P2949** [USACO09OPEN]Work Scheduling G](https://www.luogu.com.cn/problemnew/show/P2949)
# T2 购物shop
**题意 **：给你 $n$ 种硬币类型，每种硬币类型 $v_i$ 买家有 $c_i$ 个，卖家有无限个，买家要买一个 $m$ 元的东西（卖家可以找零），买家问你双方之间**交流的硬币个数**（指买家用的硬币数 + 卖家找零的硬币数）最少为多少个？
题意中的金额我们不妨抽象为线段长度
所以题意可以简化成：怎样拼凑成两段线段，且它们的长度之差等于T
你要怎么去拼凑线段，这就有些背包的感觉。所以我们可以分别从hyfhaha和店主不同的角度来考虑最优解
因为hyfhaha的硬币数是有限的，所以可以视为多重背包（这里考到了多重背包的二进制优化），求达到一定钱数所需的最少的硬币数量;店长的硬币数是无限的，所以可以视为完全背包，也是求同种方案最少的硬币数量，再在最后枚举每种付钱和找钱的方案硬币数之和，求个min即可得出答案
但是问题是，我们应该一直找到多少钱的方案才能保证找到合法的最优解呢？我认为这是这道题最关键的部分，以下为证明：
$ \text { 关于这里的 } m x, \text { 我们令它为 } \max _{i=1}^{n} v_{i}^{2}
假设, 在 m+m x 的范围内, 没有（买家付的钱-卖家找的钱等于 m ）的情况, 那么卖家所找的硬币的个数必定大于 v_{\max } \quad\left(\right. 因为 v_{\max }^{2} 显然小于 \left.m x\right) 。设卖家找的钱的序列为 p\left(\forall p_{i}<p_{i+1}\right) 我们作一个前缀数组 s, 使 s_{i}=\sum_{j=1}^{j \leq i} p_{j}, 根据同余的性质,必有两个（或两个以上）的 s_i 是在 mod\ v_{max}意义下是同余的，（因为 s 序列长度大于 v_{max}，而取模后的数最多有 v_{\max } 种 ) ， 那么必然有 s_{i}-s_{j}=k * v_{\max }(i>j) 即这部分的数可以替换成 k 个 v_{\max } .
那么, 既然卖家不用还超过 v_{\max }^{2} 的钱, 那么买家就不用付超过 m+v_{\max }^{2} 的钱, 证必。
那么这题也就没了，主要是两个背包，也算是一道比较不常规的背包题吧，但总体不难。
原题：P2851 [USACO06DEC]The Fewest Coins G
T3 魔法mogic
状压+线段树
这是一道神仙题，想拿满分并不简单，但部分分给的很足，可以考验选手考场时间分配等临场能力
代码实现起来也比较清真，放T3感觉还可以，思维难度不算大，有点考细节
简化题面
给定 m 个长度为 n 的可能含有 ？ 的 01 串，其中 ? 既能代表 0 也能代表 1， q 次操作，每次给定一个区间，求有多少 01 串满足区间内的所有字符串都可以解释成该 01 串，或者单点修改某个字符串。
Solution
子任务 1 :
乱搞
子任务 2 :
考虑 n 只有 10, 因此可以 O\left(2^{n}\right) 去枚举所有可能的串, 然后对于每个询问 O(m) 的逐个判定是否合 法。时间复杂度 O\left(q m 2^{n}\right)。
子任务 3 :
考虑对于一段所有字符串的第 x 个字符, 一共有四种可能：确定为 0 ; 确定为 1 ; 都可以; 都不可以。如
果 0 / 1 都不可以, 则答案为 0, 因为不会有任何一个字符串匹配该区间。如果确定为某个数, 则这一位只
有一种可能; 否则这一位有两种可能。根据乘法原理, 如果有 a 个位置有两种可能, 则本次询问的答案为 2^{a}。
因此对于每个询问, O(n m) 地去遍历区间内所有字符即可。时间复杂度 O(n m q)。
子任务 4 :
考虑 n 只有 30, 可以状压到 int 中。具体的, 维护两个 int，第一个 int 维护对应位是否确定是 0 或 1, 第二个 int 维护如果确定是 0 或 1 了那么具体是 0 还是 1 。
例如, 对于单个字符串, 它所有的为 ？ 的位置, 在第一个 int 中对应位置是 0, 所有为 0 或 1 的 位置, 在第个 int 中对应的位置是 1, 在第二个 int 中对应的位置是自身的值。
考虑 a_{1}, a_{2} 是询问的左端点到某个字符串之前所维护的两个 int , b_{1}, b_{2} 是该字符串的两个 int，现在合并这两个信息。
如果某一位置即不可以是 1, 也不可以是 0, 那么该字符串不为 ? 的位置在 b_{2} 中对应的值应该至少有一 个和 a_{2} 中对应位置的值且 a_{1} 的该位置为 1, 位运算可以表现为 \left(a 1 \& b_{1}\right) \&\left(a_{2} \oplus b_{2}\right) \neq 0, 则该 询问的答案为 0 。
否则这两段信息可以合并：将他们已经确定字符的位置合并起来, 然后将确定位置对应的值合并起来即可。于是 a_{1} 对 b_{1} 取或, a_{2} 对 b_{2} 取或即可。
最终该旬问 0 / 1 都可以的位置的个数即为 a_{1} 中 1 的个数。
时间复杂度 O(m q) 。
子任务 5 :
由于 n 只有 1, 问题变成了求某个区间内的字符是不是全是 0, 全是 1, 全是 ? 或 0 和 1 都有。 可以考虑用线段树非常轻松的维护这样的信息。
时间复杂度 O(q \log m) 。
子任务 6:
世界上没有什么事情是开一棵线段树不能解决的, 如果有, 那就开 30 棵。
时间复杂度 O(n q \log m)。
子任务 7 :
考虑结合子任务 4 和子任务 5 的做法, 发现两个区间的状压信息也可以用子任务 4 的方法合并。因此用线段树维护这两个 int 的状压信息即可。
时间复杂度 O(q \log m)。
原题：P5522 [yLOI2019] 棠梨煎雪
T4 和平peace
一道树上计数题，应该都满熟悉这类题的了
==部 分 分 给 得 特 别 多 ！==
就算你完全不会正解你也可以拿 65 分！
测试点 1-2
暴力枚举两条路径的起始点和终点，然后再判断是否相交。时间复杂度 O(n^4)
测试点 3-4
暴力枚举三条路径的起始点和终点，然后再判断是否相交。时间复杂度 O(n^6)
这两档部分分虽然很水，但在考场上写出来不算简单，所以给了较多的分数
方法1：暴力计算贡献
首先很显然的，用所有的方案减去不合法的方案
所有的方案就是：树上所有长度不超过k的路径条数的m次方
计算不合法的方案要围绕的基准点是什么呢？
不合法的方案路径一定有交点，考虑枚举交点，但路径交点可能有多个，所以可以枚举深度最浅的交点
首先求出f[p]表示经过p且路径两端都在p子树内的长度不超过k的方案数，g[p]表示经过p路径且两端分别在p子树内外，长度不超过k的方案数
那么以p为深度最浅的交点的不合法方案数就为：\displaystyle \sum_{i=0}^{m-1}\binom{m}{i}g[p]^i\times f[p]^{m-i}
也就是选出i个国家放到子树外面，注意不能放m只在外面，不然最浅的交点就不是p了。
这里时间复杂度为 O(nm).
考虑如何计算f和g
对于p的一个儿子q，直接递归q的子树，之前的数据都存在前缀桶里，更新答案后，把新的数据扔到桶里就好了
计算g[p]，其实就是把子树p以外的看成p的另外一棵子树，然后类似上面的过程计算就可以了
国家都只能在p这个节点上，f[p]=1,g[p]=0
此时国家可以走完一整棵树，设\displaystyle cal(x)=\binom{x}{2}+x，表示在x个点中选出2个点满足终点不小于起点
\displaystyle f[p]=cal(size[p])-\sum_{q\in son(p)}cal(size[q])\quad g[p]=(n-size[p])\times size[p]
$g[p]$取的是前面所有能扩展的向后扩展，对$f[p]$求个前缀和，然后再减掉没有到达$p$的就可以了
这样最后总的时间复杂度是$O(n^2+nm)$，代码中直接用快速幂，复杂度多个$\log$（反正也不是正解
# 方法2：简单的转换
~~之前的标算被踩了，本来没有这里的~~
方法$1$之所以慢，关键就在于那个求和式，需要$O(m)$的时间枚举
然后这个式子不就是二项式定理的形式吗？？？
所以$\displaystyle ans=\sum_{i=0}^{m}\binom{m}{i}g[p]^if[p]^{m-i}-g[p]^m=(f[p]+g[p])^m-g[p]^m
这样就可以O(n\log m)计算了，然后就没了
但不妨从容斥的角度直接得到最后的答案
显然这m条路径全部相交的点，肯定是形成一条链（边形成的），这条链的长度为x
设f(x)表示这条链的长度为x的方案数，g(x)表示钦定这条链的长度为x的方案数，那么就有：
$g(0)=f(0)+2\times f(1)+3\times f(2)+...
g(1)=1\times f(1)+2\times f(2)+...
显然不合法的方案数就是\displaystyle f(0)+f(1)+...=g(0)-g(1)
那么只需要求出g(0)和g(1)就行了，因为g(1)肯定是两个相连的节点，直接设为每个节点和其父亲就行了
$g(1)$表示，在树上选出$m$条长度小于等于$k$的链，且至少都经过同两个点
最后要求的东西，其实就是方法$1$求出来的东西了
不知道有没有人能找到更优的求解 $f$和$g$ 数组的算法
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#define ll long long
using namespace std;
const int N=1e6+10;
const ll mod=998244353;
int n,m,k,flag=1,tot,tail;
int fir[N],dep[N],que[N],size[N],s1[N],s2[N],cnt[N];
ll f[N],g[N],pre[N];
struct edge
{
int to;
int nxt;
}e[2*N];
inline void add(int x,int y)
{
e[++tot].to=y; e[tot].nxt=fir[x]; fir[x]=tot;
e[++tot].to=x; e[tot].nxt=fir[y]; fir[y]=tot;
}
inline ll power(ll a,int b)
{
ll res=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1) res=res*a%mod;
return res;
}
inline ll cal(int x)
{
return 1ll*x*(x-1)/2+x;
}
inline void dfs1(int p,int fa)
{
if(p==0) return;
dep[p]=dep[fa]+1,que[++tail]=p;
for(int i=fir[p];i;i=e[i].nxt)
if(e[i].to!=fa) dfs1(e[i].to,p);
}
inline void dfs2(int p,int fa)
{
for(int i=0;i<=k;i++) s1[i]=s2[i]=cnt[i]=0;
dep[p]=tail=0,dfs1(fa,p);
for(int i=1;i<=tail;i++) s1[dep[que[i]]]++;
for(int i=1;i<=k;i++) s1[i]+=s1[i-1];
f[p]=1,g[p]=s1[k];
for(int i=fir[p];i;i=e[i].nxt)
{
int q=e[i].to;
if(q==fa) continue;
tail=0,dfs1(q,p);
for(int j=1;j<=tail;j++)
{
if(dep[que[j]]>k) continue;
cnt[dep[que[j]]]++;
g[p]+=s1[k-dep[que[j]]];
f[p]+=s2[k-dep[que[j]]]+1;
}
for(int j=1;j<=k;j++) s2[j]=s2[j-1]+cnt[j];
}
for(int i=fir[p];i;i=e[i].nxt)
if(e[i].to!=fa) dfs2(e[i].to,p);
}
inline void dfs3(int p,int fa)
{
size[p]=1;
for(int i=fir[p];i;i=e[i].nxt)
{
int q=e[i].to;
if(q==fa) continue;
dfs3(q,p);
size[p]+=size[q];
f[p]-=cal(size[q]);
}
f[p]+=cal(size[p]);
g[p]=1ll*size[p]*(n-size[p]);
}
inline void solve()
{
if(flag)
{
for(int i=1;i<=n;i++)
{
f[i]=min(n-i+1,k+1);
pre[i]=pre[i-1]+f[i]-1;
int last=max(1,i-k);
ll add=1ll*(i-last-1)*(i-last)/2;
g[i]=pre[i-1]-pre[last-1]-add;
}
return;
}
if(k==0)
{
for(int i=1;i<=n;i++) f[i]=1,g[i]=0;
return;
}
if(k==n-1) dfs3(1,0);
else dfs2(1,0);
}
int main()
{
int a,b; ll ans1=0,ans2=0;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
if(a!=b-1) flag=0;
}
solve();
for(int i=1;i<=n;i++)
{
f[i]%=mod,g[i]%=mod;
ans1=(ans1+f[i])%mod;
ans2=(ans2+power(f[i]+g[i],m)-power(g[i],m)+mod)%mod;
}
printf("%lld\n",((power(ans1,m)-ans2)%mod+mod)%mod);
return 0;
}
```
题目都不错的，~~我真良心~~