Educational Codeforces Round 64 部分题解

2023-12-05 08:42:58

不更了不更了

CF1156D 0-1-Tree

有一棵树，边权都是0或1。定义点对$x,y(x\neq y)$合法当且仅当树上$x$到$y$的路径权值是一段0接一段1。求合法点对数量。

直接点分治

我是傻逼居然还写了50min。。。

有一个排列，求满足$l\leq r,p_l+p_r=\max_{i=l}^rp_i$的数对$l,r$数量。

枚举最大值的位置，那么$l,r$有一个初步的范围就是这个最大值左边第一个大于它的位置+1和右边第一个大于它的位置-1，可以用单调栈处理。

然后在小的那一边中枚举$p$，在另一边查找是否有合法的。

考虑将序列建树的过程：将序列最大值拿出来，左右的序列分别建树作为两个儿子。

暴力枚举的次数实际上是$\sum \min(siz[ls],siz[rs])$，即启发式合并的复杂度。

有一堆卡，等概率随机拿出来一个，如果这不是第一次拿则将这张牌的大小与上一张牌大小比较，如果这张牌更大则重复这个过程，更小则你输了，相等则你赢了。最后没有牌你就输了。求获胜概率。

如果赢了那么拿出来的牌是一个递增的序列，最后一个数重复两次。

设$f[i][j]$表示抽了$i$张卡且没有重复，最后一张大小是$j$的概率。直接dp就行了。

有一种辣鸡语言

这个语言的变量名最多4个字符，命名规则是第一个字符是字母，其他字符是字母或者数字。

这个语言的语句只有两种，每一种占一行

赋值形如<lvalue>=<rvalue>，如yyb=juju
还是赋值形如<lvalue>=<arg1><op><arg2>，其中<op>是一种运算符，有四种，分别是$,#,&,^。如yyb=ak$ioi

比如这是一种合法的程序：

c=aa#bb

d12=c

res=c^d12

tmp=aa$c

一个程序的返回值被定义为程序结束时变量res的值

你可以认为这个程序初始所有变量都有一个随机的值。而运算符<op>所代表的运算是不确定的。定义两个程序是等效的，当且仅当对于每一种相同初始值以及计算规则，这两个程序的返回值相等。

现在萌新写了个程序，你想帮他压行，即写一个与萌新的程序等效的程序，使得你写的程序行数最小。

输出最小行数以及你写的程序。

先来看看有哪些东西可以被压掉

1可以通过实现solve(x,n)表示计算变量x在n语句以前的值来实现不计算没有用的

2可以通过哈希在solve的时候判掉

那么就是一个简单的大模拟了