myee

分类

个人(1) 题解(15)

/ 注册

全部文章（共15篇）

牛客练习赛105 F

引言首杀，我的首杀……qwq 原来差点就 F 一血了……我 19:08:01 就提交了……8 min 就打完了…… 结果 F 题让我发现我一直的异或卷积板子是假的……而且在平时只有一次卷积时可以证明不可能出锅……因为我最后一步的乘法打成加法了，然后平时这一位只可能是 000，0+0=0×00+0=...

2022-11-04

13 699

牛客练习赛104 F

Update on 2022.10.22：出题人已经修改数据并重测了。 Update on 2022.10.21：实践检验表明数据确实锅了，对 k=1k=1k=1 的数据请输出 000！完蛋了交了 101101101 发要被封号了。不管了，先胡一下这个过不去的做法，供后人观赏。倒开人...

2022-10-21

7 919

牛客挑战赛64 D

大家好这里是赛时调不出代码的小丑 myee。这里我给出 T4 一个理论线性但肯定没人会去写的垃圾做法。当然，如果你懒了，可以和我一样带只 log⁡\loglog，反正也能过。首先容斥，贡献为 ∑l=1n∑r=l+1n[f(l,r)=al∨f(l,r)=ar]l≤i≤rai=∑l=1n∑r=l+...

2022-10-14

4 482

牛客小白赛54 E

大家都知道 KMPAM 吧？对这题，考虑一个 dp 套 dp。内层为你目前在 KMP 自动机上的位置，外层为到当前点已经匹配了多少个。顺着 KMPAM 转移边的方向转移即可。 p.s. KMPAM 就是 KMP 匹配的过程写成自动机的形式，使得可以 O(1)O(1)O(1) 转移。上代码~ ...

2022-08-13

1 359

牛客挑战赛59 D

放一个常数巨大不能通过的做法。首先子序列信息显然可以动态 dp。然后有插入操作，于是显然得用平衡树来维护区间信息。打的 WBLT，然后结果实测不加平衡措施还更快？？？（除掉 S=0 外，均有数据随机） struct Info{ullt O,R,Z,OR,RZ,ORZ;__always_inli...

2022-04-15

4 391

牛客练习赛97 G

预处理枚举答案位置，然后用卷积得到询问答案。 ∑ifi(xi)(m−xn−i)=∑ifix!(m−x)!i!(n−i)!(x−i)!(m−x−n+i)!=x!(m−x)!∑ifii!(n−i)!(x−i)!(m−x−n+i)!=x!(m−x)!∑ifii!(n−i)!1(x−i)!(m−x−n+i)...

2022-03-11

4 478

牛客练习赛97 F

LCT 板子，不多说了。复杂度是可以均摊的。 typedef std::pair<ullt,uint>Pair; struct LCT { struct node { Pair val,max;node*son[2],*fath;bol tag; ...

2022-03-10

4 467

牛客练习赛97 E

一个结论是一段区间可行当且仅当其总石子个数是偶数且最多者不超过总数一半。笛卡尔树上启发式合并即可。（听说数据水，乱搞也能过。） // 笛卡尔树毁我青春 // 隐式构建.jpg ullt S[100005]; uint Cnt[2][100005]; uint A[100005]; struct ...

2022-03-10

6 585

牛客练习赛97 D

直接树形 dp，记录当根节点颜色假如已经被确定时的两种方案对应方案数即可。 std::vector<uint>Way[1000005]; modint x,y; modint Kind[1000005][2]; voi dfs(uint p,uint f) { Kind[p][0...

2022-03-10

11 452

牛客练习赛97 C

反悔贪心即可。 llt A[100005],P[100005];uint Op[100005]; int main() { uint n,m;scanf("%u%u",&n,&m); for(uint i=0;i<n;i++)scanf("%lld",A+i),...

2022-03-10

7 543