【LGR-076】洛谷 ⑨ 月月赛 I & Cnoi2020

呃呃呃本来想打的然后因为数学物理考试咕咕咕了...

说实话都是纸老虎仔细想想就切掉了....

P6832 [Cnoi2020]子弦

可以冲sam吗?.....1e7不太能啊

答案显然就是每个最短的串的出现次数

即统计a~z出现次数

code:


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e7 + 8;
char s[MAXN];
int cnt[50], ans;
int main() {
	scanf("%s", s);
	int n = strlen(s);
	for(int i = 0; i < n; ++i) {
		cnt[s[i] - 'a']++;
	}
	for(int i = 0; i < 26; ++i)ans = max(ans, cnt[i]);
	printf("%d\n", ans);
	return 0;
}

P6833 [Cnoi2020]雷雨

一开始就发现了正解然后心里暗示自己是错误的/cy

显然可以做三遍最短路:第一遍是从最上层任意一个点出发到剩下所有点的,第二遍是从红魔馆,第三遍是迷途竹林

然后枚举中间点三者求和即可

复杂度 $O(nmlog(nm))$ 因为点数和边数同阶所以dijkstra可过

spfa???老哥这是网格图啊

code:

咕咕咕

P6834 [Cnoi2020]梦原

纸老虎1

先想想给出一个树的形态咋做吧....

显然一定每次选极大连通块??

然后如果是链上好像就是积木大赛???

差分数组所有正值加起来???

啊啊啊这好像树上是一样的....

然后树形态不固定好像也会了....

因为显然一个值会在1/k个区间出现啊,他的贡献就是value*1/k

用一个二维数点,求区间比一个数大的数的和/数的出现次数

离线+树状数组即可

注意特判 $k>i$ 此时概率为 $\frac 1 {i-1}$

讲述写代码的时候一个sb错误:树状数组的add和取模优化的add重了QAQ

code:


#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int P=998244353;
const int MAXN=1e6+7;
int n,k;
ll fac[MAXN],ifac[MAXN],inv[MAXN];
struct rec {
	int x,id;
	bool operator<(const rec &w) const {
		return x<w.x;
	}
} a[MAXN];

inline void add(ll &x,ll y) {
	x+=y;
	if(x>=P)x-=P;
}
const int MAXT=2e6+7;
struct BIT {
#define lowbit(x) (x&-x)
	ll tr[MAXT];
	inline ll qry(int x) {
		ll ret=0;
		if(x==0)return 0;
		for(; x; x-=lowbit(x)) {
			add(ret,tr[x]);
		}
		return ret;
	}
	inline void mdf(int x,ll V) {
		for(; x<=n; x+=lowbit(x))add(tr[x],V);
	}
} tr1,tr2;

inline ll ksm(ll x,ll y) {
	ll ans=1;
	while(y) {
		if(y&1)ans=ans*x%P;
		x=x*x%P;
		y>>=1;
	}
	return ans;
}

inline void init() {
	fac[0]=1;
	for(int i=1; i<=k; ++i)fac[i]=1ll*fac[i-1]*i%P;
	ifac[k]=ksm(fac[k],P-2);
	ifac[0]=ifac[1]=1;
	for(int i=k-1; i>=2; --i)ifac[i]=1ll*ifac[i+1]*(i+1)%P;
	for(int i=1; i<=k; ++i) {
		inv[i]=1ll*fac[i-1]*ifac[i]%P;
	}
	return ;
}

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE],*p1=buf,*pend=buf;
	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x=0;
		char s=nc();
		for(; !isdigit(s); s=nc());
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		return x;
	}
}
using namespace fastIO;

signed main() {
//	freopen("test.in","r",stdin);
	n=read();
	k=read();
	for(int i=1; i<=n; ++i) {
		a[i].x=read();
		a[i].id=i;
	}
	sort(a+1,a+n+1);
	init();
	ll ans=0;
	for(int i=1; i<=n; ++i) {
		if(a[i].id==1) {
			add(ans,a[i].x);
			tr1.mdf(a[i].id,a[i].x);
			tr2.mdf(a[i].id,1);
			continue;
		}
		int L=max(1ll,a[i].id-k);
		int sum=tr1.qry(a[i].id-1)-tr1.qry(L-1);
		int num=tr2.qry(a[i].id-1)-tr2.qry(L-1);
		add(ans,1ll*(num*a[i].x%P-sum+P)%P*inv[a[i].id-L]%P);
		tr1.mdf(a[i].id,a[i].x);
		tr2.mdf(a[i].id,1);
		//一个统计个数一个统计sum
	}
	printf("%lld\n",ans);
	return 0;
}

/*

5 4
1 2 3 4 5

*/

P6835 [Cnoi2020]线形生物

哇偶!

我: $f_i$ 表示点i走到n的期望值

ljh:太棒了你可以高斯消元!

我:QAQ!

ljh随手在黑板上写了几个式子,然后切掉了!

我:!!!!

$f_i$ 表示从 $i$ 走到 $i+1$ 的期望步数

由期望的线性性质我们可以得到答案就是求个和

怎么求 $f_i$ ?

sum表示f数组前缀和

f_i=\frac 1 {in[i]}*(\sum_{v!=i+1}(sum_{i-1}-sum_{v-1}+f_i+1)+1)

然后我们随便化简一下

$in[i]==1$

f_i=1

$in[i]!=1$

f_i=\sum_{v!=i+1}(sum_{i-1}-sum_{v-1}+1)+1

做完了

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P=998244353;
const int MAXN=1e6+7;
int id,n,m;
ll f[MAXN],sum[MAXN];

int home[MAXN],nxt[MAXN],to[MAXN],ccnt,in[MAXN];

inline void ct(int x,int y) {
	ccnt++;
	nxt[ccnt]=home[x];
	home[x]=ccnt;
	to[ccnt]=y;
}

inline void add(ll &x,ll y) {
	x+=y;
	if(x>=P)x-=P;
}

int main() {
	scanf("%d%d%d",&n,&n,&m);
	for(int i=1,x,y; i<=m; ++i) {
		scanf("%d%d",&x,&y);
		ct(x,y);
		in[x]++;
	}
	for(int i=1; i<=n; ++i) {
		in[i]++;
	}
	//dp！
	ll ans=0;
	for(int u=1; u<=n; ++u) {
		f[u]=1;
		sum[u]=sum[u-1];
		if(in[u]==1) { //只有一步QAQ
			add(ans,1);
			add(sum[u],f[u]);
			continue;
		}
		for(int i=home[u]; i; i=nxt[i]) {
			int v=to[i];
			add(f[u],(sum[u]-sum[v-1]+1+P)%P);
		}
		add(sum[u],f[u]);
		add(ans,f[u]);
	}
	printf("%lld\n",ans);
	return 0;
}

夏晓光(loveJY)的博客

【LGR-076】洛谷 ⑨ 月月赛 I & Cnoi2020

20zr提高组十连测day4