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

背景

有史以来发挥最好的一次？

不过最后卡常能力不行所以完全进不了前三，我还是太菜了……

T1

容易发现就是找出现次数最多的字母。

只贴主要代码了，贴上一些板子会很长，有些函数意义也很明显自己脑补一下就好了：

char s[10000010];
int t[27];

void main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	for(int i=1;i<=n;i++)t[s[i]-'a']++;
	int ans=0;
	for(int i=0;i<26;i++)chkmax(ans,t[i]);
	write(ans);
	fcheck(1);return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

T2

枚举分叉点，然后用雷电初始位置到分叉点，分叉点到两个地点的最短路长度之和更新答案，最短路用迪杰斯特拉预处理好，spfa会T飞（亲测……）。

代码如下：

#define maxn 1010
int n,m,a,b,c,d[maxn][maxn];
ll dis1[maxn][maxn],dis2[maxn][maxn],dis3[maxn][maxn];
struct node{
	int x,y;ll z;
	bool operator <(const node &B)const{return z>B.z;}
};
priority_queue<node>q;
int fx[4]={0,1,0,-1};
int fy[4]={1,0,-1,0};
void dij(int sx,int sy,ll dis[maxn][maxn]){
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=1e18;
	q.push((node){sx,sy,d[sx][sy]});dis[sx][sy]=d[sx][sy];
	while(!q.empty()){
		node X=q.top();q.pop();
		int x=X.x,y=X.y;if(dis[x][y]!=X.z)continue;
		for(int k=0;k<4;k++){
			int xx=x+fx[k],yy=y+fy[k];
			if(xx<1||xx>n||yy<1||yy>m)continue;
			if(dis[xx][yy]>dis[x][y]+d[xx][yy]){
				dis[xx][yy]=dis[x][y]+d[xx][yy];
				q.push((node){xx,yy,dis[xx][yy]});
			}
		}
	}
}

void main()
{
	read(n);read(m);read(a);read(b);read(c);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			read(d[i][j]);
		}
	}
	dij(1,a,dis1);dij(n,b,dis2);dij(n,c,dis3);
	ll ans=1e18;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			chkmin(ans,dis1[i][j]+dis2[i][j]+dis3[i][j]-2*d[i][j]);
		}
	}
	write(ans);
	fcheck(1);return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

T3

先考虑如果已经知道了树的形态应该怎么做：类似某个出过两次的NOIP题，对于一个节点 $x$，假如他的父亲 $fa$ 满足 $a[fa]\ge a[x]$，那么在摘它父亲时顺便把自己摘完就好了，否则需要额外摘自己 $a[x]-a[fa]$ 次。

也就是说，对于点 $i$，只有 $j\in [i-k,i-1]$ 且 $a[j]<a[i]$ 的 $j$ 才会使 $i$ 有贡献，贡献为 $a[i]-a[j]$，用两个树状数组维护一下就好了，一个维护区间内 $a[j]<a[i]$ 的 $a[j]$ 之和，一个维护有多少个这样的 $j$。

代码如下：

#define maxn 1000010
int n,k,a[maxn],ans=0;
vector<int> b;
int id[maxn];
struct TREE{
	int tr[maxn];
	void ADD(int x,int y){for(;x<=n;x+=(x&-x))if(y>0)add(tr[x],y);else dec(tr[x],-y);}
	int SUM(int x){int re=0;for(;x;x-=(x&-x))add(re,tr[x]);return re;}
}tr1,tr2;

void main()
{
	read(n);read(k);
	for(int i=1;i<=n;i++)read(a[i]),b.pb(a[i]);
	sort(b.begin(),b.end());
	for(int i=1;i<=n;i++)id[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
	ans=a[1];tr1.ADD(id[1],a[1]);tr2.ADD(id[1],1);
	for(int i=2;i<=n;i++){
		if(i-k-1>0)tr1.ADD(id[i-k-1],-a[i-k-1]),tr2.ADD(id[i-k-1],-1);
		int sum=dec(1ll*tr2.SUM(id[i])*a[i]%mod-tr1.SUM(id[i])),tot=min(i-1,k);
		add(ans,(int)(1ll*sum*INV(tot)%mod));//由于是求期望，所以sum要除以tot才是x的贡献
		tr1.ADD(id[i],a[i]);tr2.ADD(id[i],1);
	}
	write(ans);
	fcheck(1);return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

T4

感觉是很套路的题，当时一眼就看出来了。

设 $f[i]$ 表示从 $i$ 走到 $i+1$ 的期望步数，$s[i]={\sum }_{j=1}^{i}f[j]$，$d$ 为 $i$ 的出度（指额外连的返祖边）。

那么 $i$ 有 $\frac{1}{d+1}$ 的概率直接走到 $i+1$，有 $\frac{1}{d+1}$ 的概率沿返祖边走到某个 $j$，此时需要从 $j$ 走回 $i$ 再走到 $i+1$，于是有：
f i = 1 + 1 d + 1 ( ∑ j s i − 1 − s j − 1 + f i ) 1 d + 1 f i = 1 + 1 d + 1 ( ∑ j s i − 1 − s j − 1 ) f i = d + 1 + ∑ j s i − 1 − s j − 1 f i = 1 + ∑ j s i − 1 − s j − 1 + 1

$$\begin{aligned} f_i&=1+\frac 1 {d+1} \left(\sum_j s_{i-1}-s_{j-1}+f_i\right)\\ \frac 1 {d+1} f_i&=1+\frac 1 {d+1} \left(\sum_j s_{i-1}-s_{j-1}\right)\\ f_i&=d+1+\sum_j s_{i-1}-s_{j-1}\\ f_i&=1+\sum_j s_{i-1}-s_{j-1}+1\\ \end{aligned}$$ fi​d+11​fi​fi​fi​​=1+d+11​(j∑​si−1​−sj−1​+fi​)=1+d+11​(j∑​si−1​−sj−1​)=d+1+j∑​si−1​−sj−1​=1+j∑​si−1​−sj−1​+1​

于是答案就是 $s[n]$。赛时用 $vector$ 存边跑了 $700ms$，换成邻接表就变成了 $200ms$，很奇怪，不是说 $vector$ 访问空间连续会更快些吗……

代码如下：

#define maxn 1000010
int id,n,m;
struct edge{int y,next;}e[maxn];
int first[maxn],len=0;
void buildroad(int x,int y){e[++len]=(edge){y,first[x]};first[x]=len;}
int f[maxn],s[maxn];

void main()
{
	read(id);read(n);read(m);
	for(int i=1,x,y;i<=m;i++)read(x),read(y),buildroad(x,y);
	f[0]=s[0]=0;
	for(int i=1;i<=n;i++){
		f[i]=1;
		for(int j=first[i];j;j=e[j].next){
			add(f[i],dec(s[i-1]-s[e[j].y-1])+1);
		}
		s[i]=add(s[i-1]+f[i]);
	}
	printf("%d",s[n]);
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22