GDKOI 2021 Day2 TG 总结
发布日期:2021-06-21 02:54:34 浏览次数:6 分类:技术文章

本文共 2070 字,大约阅读时间需要 6 分钟。

又是爆炸的一天,炸多了本蒟蒻已经习以为常

但今天比昨天整整高了 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
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
=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
=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
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 走人

转载地址:https://blog.csdn.net/KonjakuLAF/article/details/115714470 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:凸包学习小记
下一篇:矩阵乘法优化递推

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月26日 09时16分01秒