noone___'s blog
0%

01801202-AGC007

发表于 更新于 分类于
AGC007

C

一条直线上有 $N$ 个球， $N+1$ 个洞，每个球与相邻的洞距离 $d_i \ (1\leq i\leq N\times 2)$ 。随机选择一个球并向随机方向推，若洞中有球则继续滚，无球掉入。求每个球移动距离的期望

这个阴间题有一下结论：第一个球滚入洞中后，新的距离序列的期望值仍是一个等差数列

  • 题解的证明：

    共 $2\times n$ 中可能，对于第 $i$ 段，考虑能对其期望长度做出贡献的行为

    • 原第 $i$ 段距离被滚过，重新编号后原第 $i+2$ 段成为现第 $i$ 段
    • 原第 $i+1$ 段被滚过，原第 $i,i+2,i+3$ 段成为第 $i$ 段

  • 口胡找规律的证明

    https://pic.imgdb.cn/item/6171fecf2ab3f51d91664313.png

    $4$ 个距离的期望分别是 $\frac{8\times d+5\times x}{6} \quad \frac{8\times d+15\times x}{6} \quad \frac{8\times d+25\times x}{6} \quad \frac{8\times d+35\times x}{6}$

    然后手推一推找规律得：$d’_1=d+\frac{2\times d+5\times x}{2\times n},x’=x+\frac{4\times x}{2\times n}$

    最后对于期望距离是 $d+\frac{2\times n-1}{2\times x}$ ，即，数列的中位数

$\therefore O(n)$ 递推数列即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n;
double d,k,ans,n2;

int main(){
    scanf("%d%lf%lf",&n,&d,&k);
    n2=n<<1;
    for(rei i=n;i;--i){
        ans+=d+k*(n2-1)/2;
        d+=(2*d+5*k)/n2;
        k+=4*k/n2;
        n2-=2;
    }
    printf("%.10lf\n",ans);
    getchar(),getchar();
    return 0;
}

D

数列上有 $n$ 只位于 $x_i$ 熊，到达该熊位置后 $T$ 秒会在该熊的位置生成一个金币，从 $0$ 开始走，每走以一单位长度需要 $1$ 秒，求收集所有金币并到出口的最短时间

经典C比D难

显然有 $dp$ 式子：

考虑优化这个 $O(n^2)$ 的式子

首先注意 $\sum a_i-a_j=lenth$ ，所以提出这个式子并在结果中加上数列总长

其次处理 $\max$ :对于 $(a_i-a_{j+1})$ 的大小分类讨论，其大小随 $a_i$ 单增，维护队列，当 $(a_i-a_{j+1})\leq \frac{T}{2}$ 留在队列中，队首转移时所有弹出的 $j$ 满足 $(a_i-a_{j+1})>T$ ，记录最小值即可

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
const int N=2e5+100;
ll n,T,x[N],f[N],ans,k=1e18;
ll head=1,tail=1,sta[N];

int main(){
    memset(f,0x3f,sizeof f);
    scanf("%d%lld%d",&n,&ans,&T);
    for(rei i=1;i<=n;++i) scanf("%d",&x[i]);
    f[0]=0;
    for(rei i=1;i<=n;++i){
        while(head<=tail && (x[i]-x[ sta[head] ]+1)>(T>>1)){
            k=min(k,f[ sta[head] ]-2*x[ sta[head]+1 ]);
            ++head;
        }
        f[i]=min(f[i],min(f[ sta[head] ]+T,k+2*x[i]));
        sta[++tail]=i;
    }
    ans+=f[n];
    printf("%lld\n",ans);
    getchar(),getchar();
    return 0;
}const int N=2e5+100;
ll n,T,x[N],f[N],ans,k=1e18;
ll head=1,tail=1,sta[N];

int main(){
    memset(f,0x3f,sizeof f);
    scanf("%d%lld%d",&n,&ans,&T);
    for(rei i=1;i<=n;++i) scanf("%d",&x[i]);
    f[0]=0;
    for(rei i=1;i<=n;++i){
        while(head<=tail && (x[i]-x[ sta[head] ]+1)>(T>>1)){
            k=min(k,f[ sta[head] ]-2*x[ sta[head]+1 ]);
            ++head;
        }
        f[i]=min(f[i],min(f[ sta[head] ]+T,k+2*x[i]));
        sta[++tail]=i;
    }
    ans+=f[n];
    printf("%lld\n",ans);
    getchar(),getchar();
    return 0;
}

E

给定一个严格二叉树，每条边有边权，找到一条 $\text{Euler}$ 环游路径(从根出发并回到根，期间每条边的两个方向恰被经过一次)，设该路径经过的叶节点按顺序依次为 $l_1,l_2,….$ ,最小化 $\max\{dis(l_1,l_2),dis(l_2,l_3),…,dis(l_{n-1},l_n)\}$

最小化最大值，自然想到二分答案，转化为判定性问题

二分答案为 $mid$ ，设二元组 $(a,b)_x$ 表示 $x$ 子树下第一次走的代价为 $a$ ,在最后一次走的代价为 $b$ ，中间过程都 $\leq mid$

可以得到暴力做法：枚举当前点左右儿子的二元组 $(a,b)_{ls},(c,d)_{rs}$ ，左儿子边权为 $x$ ，右儿子边权 $y$ ，若满足 $b+c+x+y\leq mid$ ，则能得到一个新二元组 $(a+x,d+y)_x$

考虑优化：

对于两个有序对 $(a,b),(c,d)$ 若 $a\leq d 或 b\leq c$ ，即前者偏序与后者，显然前者优于后者

那么只保留优等情况后， $a,b$ 是反向单调的，即， $ad$

对于 $(a,b) 和 (c,d)$ 的合并，假设固定 $b$ ，那么需要找 $c$ 满足 $d\leq v-b$

显然希望剩下的 $d$ 尽可能小，有反向单调性可知，需要找尽可能大的 $c$

可以按照单增的顺序枚举 $b$ ，所需的 $c$ 的上界则单减，双指针扫即可

再考虑顶点 $i$ 的所有状态，注意到两子节点可交换，即要同时插入 $(l,r) , (r,l)$

这里并不需要再次排序，由枚举的单调性可知内部有序，只需进行一次有序表合并

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
const int N=14e4+100,M=5e5;
int n,fa[N],lc[N],rc[N];
ll depth[N];
PLL g[M],h[M],tmp[M];
vector <PLL> f[N];

inline void link(int x,int fa){ (lc[fa] ? rc[fa] : lc[fa])=x;}

inline bool valid(ll v){
    for(rei x=n;x;--x){
        f[x].clear(); rei l=lc[x],r=rc[x];
        if(!(l || r)){ f[x].emplace_back(depth[x],depth[x]); continue;}
        rei L=f[l].size(),R=f[r].size(),cg,ch,i,j;
        ll lim=v+2*depth[x];
        for(cg=ch=j=i=0;i<L;++i){
            for(;j<R && f[l][i].first+f[r][j].second>lim;++j);
            if(j==R) break;
            g[cg++]=mk(f[l][i].second,f[r][j].first);
            h[ch++]=mk(f[r][j].first,f[l][i].second);
        }
        reverse(g,g+cg),j=merge(g,g+cg,h,h+ch,tmp)-tmp;
        if(!j) return false;
        for(f[x].emplace_back(*tmp),i=1;i<j;++i)
            if(tmp[i].second<f[x].back().second) f[x].emplace_back(tmp[i]);
    }
    return true;
}

signed main(){
    ll l=0,r=0,mid;
    scanf("%d",&n);
    for(rei i=2;i<=n;++i)
        scanf("%d%lld",&fa[i],&depth[i]),link(i,fa[i]),r+=depth[i],depth[i]+=depth[ fa[i] ];
    for(;l<r;valid(mid=(l+r)/2) ? r=mid : l=mid+1);
    printf("%lld\n",l);
    getchar(),getchar();
    return 0;
}

F

给定初始串 $S_0$ 与目标串 $T$ ，第 $i$ 步将 $S_i$ 变为 $S_{i+1}$ ，其中：

求最少几次操作可以变为目标串

考虑到 $T$ 中的每个字符来源于 $S_0$ ，有对应关系的边不会相交，且一个字符对应一个区间

可以采取的最优策略是：先尽量右移，移动到需要覆盖的左边界处后向下到底线，再横向覆盖，让路径尽量靠右

再考虑最优补数：从后往前考虑每个 $T$ 中须要匹配的左端点，让路径尽量靠右，若当前层数无法完成，则加一层

具体地，用队列维护上一条路径所有右侧转折点，其横纵坐标单增

当 $S_i\rightarrow T_j$ ，末端弹出所有横坐标在 $j$ 后面的所有转折点

答案是所有转折点纵坐标的最大值 $+1$

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
const int N=1e6+100;
char s[N],t[N];
int n,pre[N],p[255],ans,ql,qr;
struct Data{int i,j;}q[N];

int main(){
    scanf("%d%s%s",&n,s+1,t+1); bool flag=1;
    for(rei i=1;i<=n;++i) if(s[i]!=t[i]) flag=0;
    if(flag) return puts("0"),0;
    for(rei i=1;i<=n;++i) pre[i]=p[ s[i] ],p[ s[i] ]=i;
    rei ql=1,qr=0;
    for(rei i=n,las=n+1,c=0;i;--i){
        if(t[i]==t[i-1]) continue;
        while(p[ t[i] ]>min(las,i)) p[ t[i] ]=pre[ p[ t[i] ] ];
        if(!p[ t[i] ]) return puts("-1"),0;
        rei u=p[ t[i] ],v=i;
        while(ql<=qr && v<q[ql].i-c+1) ++ql;
        if(las!=u && u<v) q[++qr]=((Data){u+c,1-c});
        if(ql<=qr) ans=max(ans,q[ql].j+c);
        ++c;las=u;
    }
    printf("%d\n",ans+1);
    getchar(),getchar();
    return 0;
}