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


背景

有史以来发挥最好的一次?
【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;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

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

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【LGR-076】洛谷 ⑨ 月月赛 I & Cnoi2020 题解
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏