又是爆炸的一天，炸多了本蒟蒻已经习以为常
但今天比昨天整整高了 40 分！！！！却还是没有 100
今天本蒟蒻本想模仿奆佬的打字速度，结果思路混乱让我无法开始
T1
不是吧怎么是期望 dp ，期望值怎么求来着？
赛后：设 \(F_i\) 为第 i 颗星时的期望，\(F_0 = \dfrac{1}{p_0}\)
可得 \((1-p_i)(F_i+F_{i-1})+1\) 移项 \(F_i=(F_{i-1}*(1-p_i)+1)*\dfrac{1}{p_i}\)
注意逆元
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1000005;
const LL mod=998244353;
int n;
LL x[N],y[N],f[N],ans,tmp;
inline LL Pow(LL x,LL y) {
register LL z=1;
for(;y;y>>=1,x=(x*x)%mod)
if(y&1)z=(z*x)%mod;
return z;
}
int main() {
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%lld%lld",&x[i],&y[i]);
f[0]=y[0]*Pow(x[0],mod-2)%mod;
// ! 1-p[i]
for(int i=1;i<n;i++) {
tmp=f[i-1]*(y[i]-x[i])%mod;
tmp=tmp*Pow(y[i],mod-2)%mod;
++tmp,tmp>=mod?tmp-=mod:1;
f[i]=tmp*y[i]%mod;
f[i]=f[i]*Pow(x[i],mod-2)%mod;
}
for(int i=0;i<n;i++)
ans+=f[i],ans>=mod?ans-=mod:1;
printf("%lld",ans);
}
T2
图论？暴力只有 \(20\ pts\) 预估 40 ，八成是搜索炸了
赛后：线段树
暴力方法
由于 \(i\) 一定能走到 \(i+1,i+2,,,n\) ，可以用线段树维护 \(i\in [i,n]\) 的最小值
然后用搜索一直查询到最优解，可以被链卡成 \(O(n^2)\)
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,T,x[N],mn[N<<2],ans,res;
inline void Up(int rt) { mn[rt]=min(mn[rt<<1],mn[rt<<1|1]); }
void Build(int l,int r,int rt) {
if(l==r) { mn[rt]=x[l]; return; }
register int mid=l+r>>1;
Build(l,mid,rt<<1),Build(mid+1,r,rt<<1|1),Up(rt);
}
void Change(int p,int vl,int l,int r,int rt) {
if(l==r) { mn[rt]=vl; return; }
register int mid=l+r>>1;
if(p<=mid)Change(p,vl,l,mid,rt<<1);
else Change(p,vl,mid+1,r,rt<<1|1); Up(rt);
}
void Query(int ql,int qr,int l,int r,int rt) {
if(ql<=l && r<=qr) {
res=min(res,mn[rt]); return;
} register int mid=l+r>>1;
if(ql<=mid)Query(ql,qr,l,mid,rt<<1);
if(qr>mid)Query(ql,qr,mid+1,r,rt<<1|1);
}
void Dfs(int u) {
res=2100000000,Query(u,n,1,n,1);
if(res==u || u==1)return;
ans=min(ans,res),Dfs(res);
}
int main() {
freopen("island.in","r",stdin);
freopen("island.out","w",stdout);
scanf("%d%d",&n,&T);
for(int i=1;i<=n;i++)scanf("%d",&x[i]);
Build(1,n,1);
for(int opt,x,y;T--;) {
scanf("%d%d",&opt,&x);
if(opt==1) {
scanf("%d",&y);
Change(x,y,1,n,1);
} else {
ans=x;
Dfs(x);
printf("%d\n",ans);
}
}
}
正解
暂时不会
T3
又是回文串？本蒟蒻刚想到 manacher 就不知怎么做了，直接\(O(n^2)\) DP走人
T4
直接上代码？不管，本蒟蒻直接复制 30 走人