【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;
}

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;
}

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;
}

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$，於是有：
$$\begin{array}{rl}{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{array}$$

於是答案就是 $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;
}