背景
有史以来发挥最好的一次？
不过最后卡常能力不行所以完全进不了前三，我还是太菜了……
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=1if[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} fid+11fififi=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;
}
