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

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

巴特西

GDKOI 2021 Day2 TG 总结

T1

T2

暴力方法

正解

T3

T4

最新文章

热门文章