luoguP4137 Rmq Problem / mex

原题传送门>Here<

据说正解是主席树。。然而并不知道用主席树怎么搞。。然后最近在学莫队。。所以就当莫队模板题来做了。。

先对所有询问分块,并一边做一边记录每个数的出现次数,顺便记录当前ans:

如果删除一个数字后区间中没有该数字,则ans=min(ans,该数字);

如果添加数字时该数字第一次在区间中出现且ans==该数字,则ans不停++。

luoguP4450 双亲数

(前言)本文借鉴了dalao的博客,看了这篇文章才终于明白了莫比乌斯反演该怎么打。多谢dalao!!

原题传送门>Here<

网上的的莫比乌斯反演讲稿都讲了很多不明觉厉的公式,搞得我很久都没懂,看了一些题目和dalao的博客以后才发现。。其实有很多公式是不需要的!

实际编程时,很多公式并不需要搞得那么复杂,于是我先写一篇面向OI的学习笔记,以后有时间再更新更奇葩的数学部分。

HDU4825 Xor Sum

原题传送门>here<

这道题比上一道chip factory简单,只要求静态查询,每次只要在trie树中找最大异或和就好了。

代码也十分简单,一遍就过了:

HDU5536 chip factory

原题传送门>Here<

安利一下大佬博客%%%

借鉴了大佬的思路终于做出来了。。之前一直TLE

首先是用trie树求最大异或和的问题。

对于求一组数中两个数的最大异或和的问题,就可以用trie树解决

把每个数按照二进制位从高到低存进trie树里,同时记录有几个数字经过每个点。查找时每位数优先取不一样的数字,若不能取则取一样的数字,这样就可以出解了。

在这道题中,我们先把每个数存进trie树中,每次取出两个数,先从trie树中删除,查询这两个数的和与trie树中的数的最大异或和,查询结束后再把这两个数插入trie树。

这样复杂度是$O(n^2logn)$的。

luoguP3369 【模板】普通平衡树

原题传送门>Here<

这道题我用的是splay,splay的写法各位dalao们都已经讲的很详细了,我就稍微讲讲:

1.查询一个点前驱和后继的时候,用splay比较方便的写法是先将其splay到根,再找左子树的最大值/右子树的最小值;

2.5/6操作查找的数不在splay中时,可以先把它插入,查找后再删除;

3.删除节点的时候一定要清空所有信息!!(我就是因为子节点的父指针没有清空所以TLE和MLE了好久qwq)

luoguP4015 运输问题

原题传送门>Here<

建图:

1.从源点向仓库i建流为a[i],费用为0的边;

2.从仓库i向商店j建流为inf,费用为c[i][j]的边;

3.从商店向汇点建流为b[i],费用为0的边。

对于第一问,跑最小费用最大流即可。

对于第二问,将费用取相反数,再跑一次最小费用最大流,得到的答案再取相反数就可以了。

luoguP4312 [COCI 2009] OTOCI

原题传送门>Here<

LCT裸题,维护一下每个点子树权值,按照题意模拟即可。

注意penguin的时候要先将点access,splay后再修改。

luoguP3203 弹飞绵羊

原题传送门>Here<

(终于不看题解A了一道LCT!!!真开心)

这道题要求动态维护链和查询跳跃次数(即链的长度),容易想到是LCT。

于是用LCT建树,将每个节点连到它跳到的下一个节点,若该节点之后绵羊即被弹飞则连到虚拟点n+1,并维护子树size值,就可以了。

代码如下:(rotate写错调了我一个小时!!!抓狂)

luoguP3355 骑士共存问题

原题传送门>Here<

我们首先观察发现,可以将图中的点分成奇数点和偶数点。也就是说,对于点(x,y),依据(x+y)的奇偶性分成两个点集。这样可以保证每个点所能攻击到的点一定和它在不同的集合中。

1.从源点到每个没有障碍的奇数点建1条流为1的边;

2.从每个没有障碍的奇数点到其可以攻击且没有障碍的偶数点建1条流为inf的边;

3.从每个没有障碍的偶数点到汇点建1条流为1的边。

这样建图以后,每一条从源点到汇点的弧表示有两个点会相互攻击。计算出图的最小割ans,即 使源点到汇点不连通所要花费的最小代价,它的实际意义就是在所有没有障碍的点中至少需要删除多少个才能使得没有点可以相互攻击。

于是答案就是n*n-m-ans.

又因为最小割=最大流,所以建图后跑一边dinic即可。

luoguP3254 圆桌问题

原题传送门>Here<

我果然还是太蒟了。。。这道题都调了两三次才过。

网络流建图:

1.因为每个单位只能有r[i]位代表,所以从源点到每个单位建流为r[i]的边;

2.同一单位代表不能同桌就餐->每桌每单位最多只有一位代表

于是从每个单位到每桌建流为1的边;

3.从每桌到汇点建流为c[i]的边。

这样最大流就是最多可分配的代表人数,如果<总人数则无解

跑完dinic后枚举2中的道路查看流的大小是否为0,为0则表示被选,输出即可。

dinic bfs时必须写h<t!dinic bfs时必须写h<t!dinic bfs时必须写h<t!

(因为写成h<=tTLE了很多次)

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×