【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 x x，假如他的父親 f a fa fa 滿足 a [ f a ] ≥ a [ x ] a[fa]\geq a[x] a[fa]≥a[x]，那么在摘它父親時順便把自己摘完就好了，否則需要額外摘自己 a [ x ] ? a [ f a ] a[x]-a[fa] a[x]?a[fa] 次，

也就是說，對于點 i i i，只有 j ∈ [ i ? k , i ? 1 ] j\in[i-k,i-1] j∈[i?k,i?1] 且 a [ j ] < a [ i ] a[j]<a[i] a[j]<a[i] 的 j j j 才會使 i i i 有貢獻，貢獻為 a [ i ] ? a [ j ] a[i]-a[j] a[i]?a[j]，用兩個樹狀陣列維護一下就好了，一個維護區間內 a [ j ] < a [ i ] a[j]<a[i] a[j]<a[i] 的 a [ j ] a[j] a[j] 之和，一個維護有多少個這樣的 j 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 ] f[i] f[i] 表示從 i i i 走到 i + 1 i+1 i+1 的期望步數， s [ i ] = ∑ j = 1 i f [ j ] s[i]=\sum_{j=1}^i f[j] s[i]=∑j=1i?f[j]， d d d 為 i i i 的出度（指額外連的返祖邊），

那么 i i i 有 1 d + 1 \dfrac 1 {d+1} d+11? 的概率直接走到 i + 1 i+1 i+1，有 1 d + 1 \dfrac 1 {d+1} d+11? 的概率沿返祖邊走到某個 j j j，此時需要從 j j j 走回 i i i 再走到 i + 1 i+1 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 ] s[n] s[n]，賽時用 v e c t o r vector vector 存邊跑了 700 m s 700ms 700ms，換成鄰接表就變成了 200 m s 200ms 200ms，很奇怪，不是說 v e c t o r vector 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;
}