0624 B组模拟赛 题解
闲扯
这次几道题都挺有讲头的就一起写了。
T1
首先易证最优解必定是一直往右跳，由于这道题 $N \le 10^5,M\le 10^9$ 直接考虑在 $T_i$ 上 dp，易得 dp 式子：
$$dp_i =\max_{j=0}^{i-1}{dp_j-\left\lceil \dfrac{T_i-T_j}{D}\right\rceil\times A+B_i}$$
然后你就会 $O(n^2)$ 做法了。
考虑 dp 经典操作，把 $i,j$ 分开再考虑如何维护，首先考虑那坨上取整怎么拆（我不会告诉你我赛时这里搞错了痛失 100pts）：
$$ \begin{aligned} \left\lceil\dfrac{T_i-T_j}{D}\right\rceil\times A &=\left\lceil\dfrac{\left\lfloor\frac{T_i}{D}\right\rfloor D+T_i \bmod D-\left\lfloor\frac{T_j}{D}\right\rfloor D-T_j \bmod D}{D}\right\rceil\times A\\ &=\left\lceil\dfrac{\left\lfloor\frac{T_i}{D}\right\rfloor D}{D}-\dfrac{\left\lfloor\frac{T_j}{D}\right\rfloor D}{D}+\dfrac{T_i \bmod D -T_j \bmod D}{D}\right\rceil\times A\\ &=\left\lceil\left\lfloor\frac{T_i}{D}\right\rfloor-\left\lfloor\frac{T_j}{D}\right\rfloor+\dfrac{T_i \bmod D -T_j \bmod D}{D}\right\rceil\times A\\ &=\left(\left\lfloor\frac{T_i}{D}\right\rfloor-\left\lfloor\frac{T_j}{D}\right\rfloor+\left\lceil\dfrac{T_i \bmod D -T_j \bmod D}{D}\right\rceil\right)\times A\\ &=A\left\lfloor\frac{T_i}{D}\right\rfloor-A\left\lfloor\frac{T_j}{D}\right\rfloor+A\left[T_i \bmod D >T_j \bmod D\right] \end{aligned} $$
其中中括号表示若内侧表达式为 true，值为 $1$，反之为 $0$。
然后把这个式子塞回转移方程：
$$ \begin{aligned} dp_i &=\max_{j=0}^{i-1}{dp_j-\left\lceil \dfrac{T_i-T_j}{D}\right\rceil\times A+B_i}\\ &=\max_{j=0}^{i-1}{dp_j-A\left\lfloor\frac{T_i}{D}\right\rfloor+A\left\lfloor\frac{T_j}{D}\right\rfloor-A\left[T_i \bmod D >T_j \bmod D\right]+B_i}\\ &=B_i-A\left\lfloor\frac{T_i}{D}\right\rfloor+\max_{j=0}^{i-1}{dp_j+A\left\lfloor\frac{T_j}{D}\right\rfloor-A\left[T_i \bmod D >T_j \bmod D\right]} \end{aligned} $$
这样只用维护 $\max$ 里面的东西就好了，发现里面的 $A\left[T_i \bmod D >T_j \bmod D\right]$ 很烦人，但是考虑如果按 $T_i \bmod D$ 升序排列后能使这个式子不为 $0$ 的 $j$ 必定是一段连续的前缀，也就是说我们维护一个前缀 $\max$ 后缀 $\max$ 分别代式子即可，这里可以用动态开点线段树/离散化+线段树/离散化+树状数组。
code
我的代码写的很丑，这里贴一下 
的代码。
开两个树状数组分别维护前后缀最大值。
code
//author: _Cyan_
#include<bits/stdc++.h>
#define lowbit(x) (x)&(-x)
#define int long long
using namespace std;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x*f;
}
const int mod=998244353,inf=1e18,N=1e5+5;
int k,m,d,a,n,t[N],b[N],dp[N],s[N],op[N],q[N],h[N],len;
inline void addq(int p,int k){for(;p<=len;p+=lowbit(p)) q[p]=max(q[p],k);}
inline void addh(int p,int k){for(;p;p-=lowbit(p)) h[p]=max(h[p],k);}
inline int askq(int p){int res=-inf; for(;p;p-=lowbit(p)) res=max(q[p],res); return res;}
inline int askh(int p){int res=-inf; for(;p<=len;p+=lowbit(p)) res=max(h[p],res); return res;}
signed main(){
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
k=read(),m=read(),d=read(),a=read(),n=read()+1;
for(int i=2;i<=n;i++) t[i]=read(),b[i]=read();
t[++n]=m;t[1]=k;
for(int i=1;i<=n;i++) op[i]=s[i]=t[i]%d;
sort(s+1,s+n+1);
len=unique(s+1,s+n+1)-s-1;
for(int i=1;i<=n;i++) op[i]=lower_bound(s+1,s+len+1,op[i])-s;
for(int i=1;i<=len;i++) q[i]=h[i]=-inf;
dp[1]=0;
addq(op[1],dp[1]+t[1]/d*a); addh(op[1],dp[1]+t[1]/d*a);
for(int i=2;i<=n;i++){
dp[i]=max(askq(op[i]-1)-t[i]/d*a-a,askh(op[i])-t[i]/d*a)+b[i];
addq(op[i],dp[i]+t[i]/d*a); addh(op[i],dp[i]+t[i]/d*a);
}
cout<<dp[n]<<'\n';
}
T2 题解
首先容易发现长度为 $k$ 的字符串 $P$ 和 $Q$ 能匹配当且仅当：
$$\nexists 1 \le i,j \le k,i \ne j\;s.t.\;P_i=P_j,Q_i \ne Q_j \;or\;P_i \ne P_j,Q_i=Q_j$$
这个自己分情况讨论一下，我不提供证明。
然后这个问题就转化成了维护两字符串内的字符是否一一对应，容易得到 $O(n^2)$ 做法：
$O(n)$ 枚举 $S$ 中子串的开头，然后 $O(n)$ 扫一遍判断有没有一个对多个的情况，统计答案。
发现枚举子串开头很难优化，考虑优化判断的过程，以下的 $S$ 是枚举的子串，$T$ 是整个 $T$。
首先考虑假如 $S$ 中字符 $a$ 与 $T$ 中字符 $b$ 一一对应的话，它们会有什么共同点，容易发现它们的位置是一一相同的，容易想到把位置作为哈希的权值用哈希解决这个问题，但是这难以推到下一个子串，这时候容易想到将每个字符与上一个该字符的距离作为权值来做哈希。
注：我对哈希的定义是 $V=(\sum\limits_{i=1}^{n} val_i\times P^{n-i})\bmod Q$，即以左侧为高位的 $P$ 进制数，其中 $P$ 和 $Q$ 为你喜欢的大质数。
具体来说，假如在当前子串中，第一个字符 $a$ 的位置是 $a_1$，那么它在哈希中的权值就是 $0$，假如第二个字符 $a$ 的位置是 $a_2$ 它在哈希中的权值就是 $a_2-a_1$，以此类推。容易发现这样做 $S$ 和 $T$ 匹配当且仅当哈希值相同（此处不考虑哈希冲突）。
考虑如何维护，假设 $S$ 长这样：
$$\boxed{A_1\dots A_2\dots B_1\dots}B_2$$
其中框出来的是上一个处理的子串，两个 $A$ 分别是第一个、第二个字符 $A$，两个 $B$ 是最后两个。容易发现我们下一步要处理的子串长这样：
$$A_1\boxed{\dots A_2\dots B_1\dots B_2}$$
考虑每个字符的贡献会如何变化，首先 $A_1$ 的贡献不会变，因为它本来就是 $0$，但 $A_2$ 会从原来的 $(A_2-A_1)\times P^{B_2-A_2+1}$ 变成 $0$。
然后中间省略号的字符包括 $B_1$ 的贡献会全部乘以 $P$，这个很常规。
最后 $B_2$ 会对哈希值加上 $B_2-B_1$ 的贡献。
然后直接做就行了，比较板。
code
code
//author:six-floor-slip-liu
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e6+5,inf=1e18,MOD=1e9+7,P=13331;
i64 Q,c,n,m,s[N],t[N];
i64 pren[N],sufn[N];
i64 hsn,hsm;
i64 ksm(i64 a,i64 b){
i64 c=1;
while(b){
if(b&1) (c*=a)%=MOD;
(a*=a)%=MOD;
b>>=1;
}
return c;
}
void del(i64 x,i64 ed){
if(sufn[x]!=0){
hsn=(hsn-(sufn[x]-x)*ksm(P,ed-sufn[x])%MOD+MOD)%MOD;
}
}
void add(i64 i,i64 x){
hsn=hsn*P%MOD;
if(pren[s[x]]>=i){
(hsn+=x-pren[s[x]])%=MOD;
}
sufn[pren[s[x]]]=x;
pren[s[x]]=x;
}
i64 pre[N];
void solve(){
mem(pre,0);mem(pren,0);mem(sufn,0);
hsm=hsn=0;
n=read();m=read();
forup(i,1,n){
s[i]=read();
}
forup(i,1,m){
t[i]=read();
}
if(n<m){
puts("0\n");
return;
}
forup(i,1,m){
add(1,i);
hsm=hsm*P%MOD;
if(pre[t[i]]!=0){
(hsm+=i-pre[t[i]])%=MOD;
}
pre[t[i]]=i;
}
vector<i64> ans;
if(hsm==hsn) ans.push_back(1);
forup(i,1,n-m){
del(i,i+m-1);
add(i+1,i+m);
if(hsn==hsm) ans.push_back(i+1);
}
printf("%lld\n",(i64)ans.size());
for(auto i:ans){
printf("%lld ",i);
}
puts("");
}
signed main(){
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
Q=read();c=read();
while(Q--) solve();
}
T3 题解
这道题想到了做法就爆简单，没想到就爆难。
首先容易想到这道题类似于求出网络流图的所有割并输出方案，然后我赛时因为觉得和网络流有关就直接放弃了。
首先答案的 $K$ 肯定小于等于从 $S$ 到 $T$ 的最短路长度，因为假设 $K$ 大于最短路长度，那么必然存在一个权值 $x$ 使得删掉它对最短路没影响，那么 $S$ 和 $T$ 就连通了。
知道了这个结论考虑如何构造方案，容易发现在网络流分层图中假如删掉了某一层的所有结点和与之相连的边，那么源点 $S$ 和汇点 $T$ 必定不连通，这道题我们可以用一样的思路给图分层，然后就做完了。
code
code
//author:six-floor-slip-liu
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=405,inf=0x3f3f3f3f;
int n,m,s,t,dpt[N],val[N*N],ans=inf;
struct edge{
int v,pos;
};
vector<edge> e[N];
queue<int> q;
void bfs(int x){
mem(dpt,-1);
dpt[x]=0;
q.push(x);
while(q.size()){
int u=q.front();q.pop();
for(auto i:e[u]){
int v=i.v,pos=i.pos;
if(dpt[v]==dpt[u]+1||dpt[v]==dpt[u]){
val[pos]=min(dpt[u]+1,ans);
}else if(dpt[v]==-1){
dpt[v]=min(dpt[u]+1,ans);
val[pos]=min(dpt[u]+1,ans);
q.push(v);
if(v==t) ans=dpt[v];
}
}
}
}
signed main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
n=read();m=read();s=read();t=read();
forup(i,1,m){
int u=read(),v=read();
e[u].push_back(edge{v,i});
e[v].push_back(edge{u,i});
}
bfs(s);
printf("%d\n",ans);
forup(i,1,m){
printf("%d\n",val[i]);
}
}
T4 题解
首先看到异或就想到 01Trie，考虑这个问题在 Trie 上应该如何解决。
注：以下约定 $ls(i)$ 表示 $i$ 在字典树中这一层取 $0$ 连向的结点，$rs(i)$ 表示取 $1$ 连向的结点。
设 $f(i,p)$ 表示考虑 $2^{p+1}\sim2^{60}$ 这些位数全都相等的数中，当前在 $i$ 结点合法的方案数，即只考虑以 $i$ 为根的子树的方案数，易得递归式：
$$ f(i,p)=\begin{cases} f(ls(i),p-1)\cdot f(rs(i),p-1) &x \le 2^p\\ ? &x>2^p \end{cases} $$
其中边界为 $f(i,-1)=2^{cnt_i}$（虽然一般取不到），$cnt_i$ 为值取在 $i$ 节点子树中的叶结点上的数的数量。
式子很好理解，假如在这一层 $x\le 2^p$，说明从左子树随便选一个右子树随便选一个异或起来都大于等于 $x$，这时候就转化成了两个子树中的子问题。
但是假如这一层必定产生分支，我们只用 $f$ 就无法处理了，这时候不妨令 $g(i,j,p,w)$ 表示考虑在 $i$ 的子树中选恰好一个，$j$ 的子树中选恰好一个，$x$ 减去 $p$ 以上位数产生的贡献后还剩下 $w$ 的方案数，这时候就能把上面的递归式补齐了:
$$ f(i,p)=\begin{cases} f(ls(i),p-1)\cdot f(rs(i),p-1) &x \le 2^p\\ g(ls(i),rs(i),p-1,x-2^p)+cnt_i+1 &x>2^p \end{cases} $$
注意要加上只选一个的方案数。
这时候我们考虑如何求 $g(i,j,p,w)$，先上递归式：
$$ g(i,j,p,w)=\begin{cases} g(ls(i),rs(j),p-1,w-2^p)+g(rs(i),ls(j),p-1,w-2^p) &w \And 2^p =1\\ g(rs(i),rs(j),p-1,w)+g(ls(i),ls(j),p-1,w)\\+g(ls(i),rs(j),p-1,w-2^p)+g(rs(i),ls(j),p-1,w-2^p) &w \And 2^p \ne1 \end{cases} $$
他妈的好长。
其中边界为 $g(i,j,p,w)=cnt_i\cdot cnt_j(w \le 0)$。这个很好理解，假如 $w \le 0$ 说明左边随便选一个右边随便选一个都合法，并且由于我们分类讨论的方式必定不会出现 $p=-1,w>0$ 的情况。
然后解释一下递归式，首先假如 $w$ 这一位为 $1$ 说明下面一定要走不一样的两条边不然就不可能构造出合法解，假如不为 $1$ 那么四种情况都能走（但其实这种情况下走两条不一样的边会直接到达边界，为了方便我直接写成这样了）。
总之大体实现就是写两个递归函数互相调用就行了。
另外注意一下我的递归式默认 Trie 是一棵满二叉树，实现时注意判一下结点的存在性。
code
code
//author:six-floor-slip-liu
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=3e5+5,inf=0x3f3f3f3f,mod=998244353;
i64 n,x;
i64 son[N*65][2],cnts;
i64 cnt[N*65];
void Insert(i64 x){
i64 p=0;
fordown(i,60,0){
cnt[p]++;
i64 c=(x>>i)&1;
if(son[p][c]==-1) son[p][c]=++cnts;
p=son[p][c];
}
cnt[p]++;
}
i64 work(i64 u,i64 v,i64 x,i64 p){
if(u==-1||v==-1) return 0;
if(x<=0) return cnt[u]*cnt[v]%mod;
if((x>>p)&1) return (work(son[u][0],son[v][1],x-(1ll<<p),p-1)+work(son[u][1],son[v][0],x-(1ll<<p),p-1))%mod;
else return (work(son[u][0],son[v][1],x-(1ll<<p),p-1)+work(son[u][1],son[v][0],x-(1ll<<p),p-1)+work(son[u][1],son[v][1],x,p-1)+work(son[u][0],son[v][0],x,p-1))%mod;
}
i64 solve(i64 u,i64 x,i64 p){
if(u==-1) return 1;
if(p==-1) return (1ll<<cnt[u])%mod;
if(x>(1ll<<p)) return cnt[u]+1+work(son[u][0],son[u][1],x-(1ll<<p),p-1);
else return solve(son[u][0],x,p-1)*solve(son[u][1],x,p-1)%mod;
}
signed main(){
// freopen("xor.in","r",stdin);
// freopen("xor.out","w",stdout);
mem(son,-1);
n=read();x=read();
forup(i,1,n){
i64 a=read();
Insert(a);
}
printf("%lld",solve(0,x,60)-1);
}