E - DeadLee 题目链接 题目大意： 给n个物品，m个人要拿物品，每个人喜欢的物品有两个x，y；他会随机拿走他喜欢的一个。你可以给他们安排顺序，每个人都必须吃一次。 可不可以保证让他们都有食物吃，有的话问安排完之后的顺序， 题解。 贪心， 如果一个食物需求的个数小于等于现有的个数，那么可以拿这个食物的人最后拿比较好（为了避免那个人拿另一种食物）。 然后如果这些人最后拿，那么另一种食物的需求就会减1，因为保证了这个人，最后拿。并且一定有的拿 然后另一种食物的需求减一可以像之前一样如果需求少于等于现有的个数，这些人就后拿。 代码: #include <algorithm> #i...

Birdwatching 题目链接 题目大意 给一个有向图，和一个点T， 简单点说就是 问跟T相连（x->T）的那些点中，有哪些点是到T必须经过与T相连的那条路。 题解 刚开始的想法：建反边，如果T到那些点的路径中有大于1的就肯定不可以，但是有环这种特殊情况。不知道该怎么判断。 题解：建反边，在直接跟t相连的这些点的集合中如果可以互相到达，那么就不可以。 所以就可以是在这些点的集合中，到达一个点的方式有两次就不可以。但是怎么特判一下环那种的呢。用一个vector，因为只用两次就可以判断出来。 所以直接搜就好了。 #include <algorithm> #include &l...

F - Network Coverage 题目链接 题目大意 有一个环，1~n 代表n个城市，n个城市围成一个环（1与n相连）。每个城市有ai家用户要网。现在有n个供网的在每两个城市之间，bi代表这个供网的最多可以给几家用户供网，每个供网的只能给他旁边两个城市的用户供网，问最后能不能让所有的人有网。 日常不会做 题解 不会做，于是看别人的题解。 为什么我想不到？ 因为我菜？ 给的是一个环，如果是一个链怎么做？肯定是从左边往右边走，每次把左边的都连完，看能不能连右边的，对吧。只能是那一种情况， 现在有个环，也就是左边还有一个可以供，这时，先不管那个，先看成一条链，尽量把第一个的往右边身上连，能连...

城市网络 题目链接 题意 给一棵树，有点权，每次从u->v刚开始自带了一个权值val，然后在路上只要遇见权值比他现有的大的就买下来，权值更新为那个点的权值，问能买几个点。 v是u的祖先。1是根节点 注意 是只要见到比他当前大的就必须买，并不是让找方法买最多的。 题解 买的肯定是递增的。 思路：倍增 dp[i][j]表示从i点往上开始买2^j个能到哪个点。 于是有个新的问题 怎么统计dp[i][0] 也就是i的祖先中离i最近且权值大于i的那个点是谁。 可以用单调栈 然后又有一个问题：因为刚开始给了一个权值，得从比那个权值大的最下面的点开始跳。这个怎么找？ 题解告诉我不用找。。 只用在u下面...

骚区间 题目链接 题意 给一个数组，问有多少个连续子序列l ~ r满足 a[l]是这个区间的次小值a[r]是这个区间的次大值。 题解 刚开始上去没什么想法，但是后来发现 对于一个数， 1、当这个数是左边界时，从他右边比他大的第一个开始到比他大的第二个数之间的数都可能是右边界。 2、当这个数是右边界时，他的左边比他小的第一个数到比他小的第二个数之间都可能是左边界。 但是这两种情况混一下我就不知道该怎么处理了。。。 可能见的题目还是少，比较菜把。 可以用树状数组维护。 树状数组里放的是有多少值当左边界的时候，右边界可能取得到这个位置。。 可能有点绕。。说不清，或许是我理解的不太到位。 设当前位置 ...

迁徙过程中的河流 题目链接 题目大意 有n个人要过河，每个人有过河的时间a[i]，每次船上只能有两个人，只有一艘船，过河的时间按照船上的人的过河时间的最大值算，问最短多长时间可以过河？ 题解 不会做，，不会 dp数组：dp[i] 前i个过河需要的最短时间。 想到了dp，但是不会转移 ，不知道为啥又感觉前后没有关系，就没想dp了。。 转移： 显然每次需要有人回去接人， 一种情况是耗时最短的回去接一个。 还有一种情况是： 比如 现在按耗时排序了，，现在1 2 已经过去了。然后 就可以 1回来 3 4过去2回来接1 。 就这两种情况，这两种情况组合下来可以包含所有情况。 所以代码： #include...

瘦了的牛牛去旅游 题目链接 题目大意 给一个有向图， 有边权。一个路径的密度 = 这条路上的边权和 / 这条路上边的数量。有q次询问 ，每次询问 给两个点，问这两个点路径上的密度最小是多少。 数据范围：点的数量n（50）边的数量m（1000）询问的数量q（1e5） 题解 我做的时候比较捞。。一直没想到dp这种东西。。一看见图就一直在想怎么建图跑个什么东西。。还是菜啊 dp[i][j][k] 表示i到j经过k个边的最小路径长度。 状态转移就很简单了，找一个中间点，然后转移。。。 肯定要先枚举k因为转移k要用到k - 1. 代码： #include <algorithm> #inclu...

J - And And And 题目链接 题目大意 给一棵树，然后算 公式的含义： 任意两个点之间的子路径异或和为0的数量和。 题解 自己做的时候比较呆，啥都看不懂。 公式的意思是先两个for枚举两个点，然后再两个for枚举两个子路径，如果子路径异或和是0 那就答案加一。 题解：先找子路径异或和是0的，然后两边节点乘一下就好。 因为是异或，可以处理一下每个点到根节点的异或。这样的话，如果两个点的值相同，那么这两个点的路径的异或和为0. 1、一个点是另一个儿子的时候，祖先节点的除了这条路上的儿子的数量乘儿子的子节点的数量。 2、两个节点跟lca拐了一下，然后就是 两个子节点的数量乘一下。 然后这...

E - Tree 题目链接 题意 两个人玩游戏，每次有几堆石头，每个人可以选一堆石头，从里面拿走任意个，最后没有石头拿的人输。（这个博弈，经典的nim博弈） 现在有一棵树，有点权，有三种操作， 1 s t 1 ~ s路径上的节点的权值变为ai | t 2 s t 1 ~ s路径上的节点的权值变为ai & t 3 s t 用1 ~ s路径上的节点另加一堆t个石头来玩游戏，问先手的人会不会赢。 博弈跟这棵树没关系，只是用一下树的点权。。。 题解 nim博弈： 每堆石头有a1 a2 a3 …… ak个 那么如果a1 ^ a2 ^ a3 ^ …… ^ ak == 0的话先手胜利。 这样的话题就...

Greater and Greater 题目链接 题目大意 给一个长度为n的数组a （n <= 150000） 一个长度为m的数组b (b <= 4e4) 问a中有多少个连续的子数组s满足 也就是说问有多少个子数组 每一个数字都大于等于b中的每一个数字 题解 大佬说 这种4e4 的数据范围一看就知道是拿bitset之类的搞。。 我补题的时候刚开始的做法： bitset<4e4>bs[1e5] 。 也就是给每一个ai 都开一个bitset 记一下b中那些数字小于等于ai 。 然后再开一个bitset cur从后往前看是否有满足条件的。。。 怎么说呢。。cur[i][j] ...

Happy Triangle 题目链接 题目大意 有三种操作： 插入一个值x 删除一个值x 给一个x 问是否在数组里是否有两个值，可以与x构成三角形。 题解 与x构成三角形可以分为几种情况 x是最大边的时候 数组里比x小的最大的两个的和比x大就可以 x不是最大边的时候 找一个值，存在另一个值与这个值的差小于x 这种情况，这个两个值肯定是相邻的因为这样可以保证差最小， 第一种情况可以用set维护，第二种情况，线段树维护最小值就可以。线段树里维护的是与前一个的差值。 代码： #include <algorithm> #include <cstdio> #include &l...

All with Pairs 题目链接 题目大意 给n个字符串，f(s1,s2) 代表 s1的前缀和s2的后缀相同的最长长度。  求上面的那个式子。 题解 如果算的不是最长长度而是所有的话，就直接先hash一下后缀，在每个前缀里找有多少个后缀与这个前缀相等就可以。 但是这个题要求最大值，并不是所有的，那么怎么去除除了最大值的呢？ 比如 两个字符串 aba 与 aba a 与 a 算一次 ，aba 与 aba 又算一次。 所以得删除掉a算的那次，怎么去掉那次呢？ 先看一下什么情况要删除吧 也就是 算前缀的时候从前往后遍历，如果遇到一个 就把他前面的删掉，也就是 一个前缀k 要把k 的最长的前缀跟...

1 or 2 题目链接 题目大意 给一个无向图，给一个长度为n的a数组 问能不能删除一些边以后能不能让每个点的度数为ai 题解 比赛的时候，因为数据水，用网络流，乱水过去了，后来才知道有反例，不能跑网络流。 正解： 建图方式：拆点，把这个点拆成ai个点，如果有一个边x- - - - -y 就在图中新建两个点代表x，y 就把 x拆的点与x相连 y拆的点与y相连，再把x，y相连。 建完图之后，跑一个带花树板子就好了。 如果是完美匹配，那么就yes，否则是no 为什么这样建图是对的呢？ 因为建完图之后会发现，随便提溜起来一条边，都可以向两边拆点中匹配一条边，并且只能匹配一次，如果一条边只有一边的度数...

Total Eclipse 题目链接 题目大意 给一个无向图，有点权。 每次选一整个连通块，让这个连通块里的点权都减一，问最少操作几步可以让他们都减成0？ 减成0了就不能再减了，也就是这个点就删去了。 题意给的不明确。他没说选的连通块尽可能大。。结果到最后了改了题面说连通块必须选尽可能大的。可是，，选尽可能大的，哪来的最小操作次数。。操作次数不就是一样的吗。。这是出题人的锅  比如这个样例，如果必须选最大的连通块，那么答案是12，如果不用选最大的，答案是8。 但是后来发现这个就算是选尽可能大的连通块，我也不一定会。。 我好菜 题解 减的话，是会先把最小值减成0，然后这个点这里断开，继续选最小的...