Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###nameTypewriter ###descirptionOne day, Jerry found a strange typewriter. This typewriter has 2 input modes: pay p coins to append an arbitrary single letter to the back, or q coins to copy a substring that has already been outputted and paste it in the back.Jerry now wants to write a letter to Tom. The letter is a string S which contains only lowercase Latin letters. But as Jerry is not very wealt ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 二分图的最小顶点覆盖定义：假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。 方法：最小顶点覆盖等于二分图的最大匹配。 我们用二分图来构造最小顶点覆盖。 二分图的最大独立集定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。 方法：最大独立集=所有顶点数-最小顶点覆盖。 二分图的最大团定义：对于一般图来说，团是一个顶点集合，且由该顶点集合诱导的子图是一个完全图，简单说，就是选出一些顶点，这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。对于二分图来说，我们默认为左边的所有点之间都有边，右边的所有顶点之间都有边。那么，实际上，我们是要在左边找到一个顶点子集X，在右边找到一个顶点子集Y，使得X中每个顶点和Y中每个顶点之间都有边。 方法：二分图的最大团=补图的最 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 先bb一堆dij算法很简单，就是通过不断的松弛离源最近的点，说白了，就是一个bfs变种,或者叫做启发式搜索？启发函数就是当前的距离。搜索过程中松弛点 A*算法也不难，本质上就是启发式搜索，核心就在启发函数f+g上面，其中f为当前走过的路径长度，g为估值函数，估计下还有多远到终点 在一般的A*搜索中，可以解决迷宫问题，用曼哈顿距离来作为g函数，可以跑的飞快 我们可以根据dij算法求出的信息来计算第k短路。 我们对原图的反向图，求出以待求终点为起点的最短路数组，以此作为A*的启发函数的评估函数，可以证明，在此启发函数作为指引的情况下， 我们首先会得到一条从原图起点到终点的路线，如果我们此时不让算法停止，忽略此次结果，那么我们得到的第二个路线是什么呢？ 其实就是第二短路。 dijkstradijkstra算法，用于解决单源最短路问题，是一种每一次通过贪心的选择距离源点最近的点来松弛其他点来得到解 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###namePath ###descirptionYears later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her.After doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly n houses, and some of them are connected with direct ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###nameVacation ###descirptionTom and Jerry are going on a vacation. They are now driving on a one-way road and several cars are in front of them. To be more specific, there are n cars in front of them. The ith car has a length of $l_i$, the head of it is $s_i$ from the stop-line, and its maximum velocity is $v_i$. The car Tom and Jerry are driving is $l_0$ in length, and $s_0$ from the stop-line, w ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###nameOperation ###descirptionThere is an integer sequence a of length n and there are two kinds of operations:0 l r: select some numbers from $a_l…a_r$ so that their xor sum is maximum, and print the maximum value. 1 x: append x to the end of the sequence and let n=n+1. ###inputThere are multiple test cases. The first line of input contains an integer T(T≤10), indicating the number of test ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###nameBlank ###descriptionThere are N blanks arranged in a row. The blanks are numbered 1,2,…,N from left to right.Tom is filling each blank with one number in {0,1,2,3}. According to his thought, the following M conditions must all be satisfied. The ith condition is:There are exactly $x_i$ different numbers among blanks $∈[l_i,r_i]$.In how many ways can the blanks be filled to satisfy all the cond ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111#include<bits/stdc++.h>using namespace std;#define rep(i,j,k) for(int i=j;i<=(k);++i)#define per(i,j,k) for(int i=j;i>=(k);--i)#define repe(i,u) for(int i=head[u];i ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###namepath ###descripptionYou have a directed weighted graph with n vertexes and m edges. The value of a path is the sum of the weight of the edges you passed. Note that you can pass any edge any times and every time you pass it you will gain the weight. Now there are q queries that you need to answer. Each of the queries is about the k-th minimum value of all the paths. ###inputThe input consists ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475// tree 节点0不准使用int head[maxn];// pointint to[maxn*2],nex[maxn*2],tot;// edgeinline void _addedge(int u,int v){to[++tot]=v,nex[tot]=head[u],head[u]=tot;}inline void addedge(int u,int v){_addedge(u,v),_addedge(v,u);}void deltree(int rt,int fat ...