这道题的边连起来的话是个基环树森林的样子(i往a[i]连边)，先考虑如果是个树怎么做，设f[i][0/1]表示节点i不选和选可投放的最大节点数量，则（因为一定要有至少一个子节点不选以限制当前节点）。可以先连的有向边，拓扑排序找出每个基环树里面的环，然后断掉环上的一条边来实现这个过程（在这之前重新建一个的有向边的图以方便dp转移）。然后假设断掉的边是，就没有用到p可以限制a[p]的这个条件，强制不选p以限制a[p]，再进行一次树形dp，那么，并用来更新答案即可。总的答案即为各个基环树的答案之和 #include <bits/stdc++.h> using namespace std;...

基环树直径的板子。但是dfs会爆栈...所以最后改成了bfs。还是一个很考验码力的板子。首先基环树的直径显然有两种情况，在不进入环的情况下在一个子树内，这直接dp求就好了。第二种是一个子树中的链+环上一段+另外一个子树中的链。按这两种情况分类讨论即可。对于这种情况，可以在先求第一种情况的同时把子树中的以子树的根为起点的最长链求出来，然后拓扑排序找出环，处理出环上的前缀和，断环成链，在上面跑一下单调队列就可以求出第二种情况下的了。然后这道题里这些步骤最好都是用bfs实现，dfs可能会爆栈...各种细节也要注意好...复杂度是的。 #include <bits/stdc++.h> us...

真正意义上的线性基...在关于向量加法和标量乘法的线性空间中的线性基。题目的意思就是要构造一个价格最低的基底。对于同个线性空间它的基底的位数不会变，那么要费用最低，可以按费用排序然后依次加入线性基判定是否可行。关于证明，设该线性空间中的向量为，线性基中的向量为，若存在满足，，而A_k是费用最低的一个向量，显然可以对于任意一个，使得，那么就相当于用代替成为线性基中的一个元素，线性基的位数不变，可表出的向量不变。而总费用更低。所以这么贪心是正确的。 #include <bits/stdc++.h> using namespace std; #define ll long long co...

首先有个显然的结论：图中所有环的xor和都可以取到（考虑从1走过去绕一圈回来，那么过去那段路的xor和就抵消了），dfs处理出所有的环（这个可以通过记录in_edge然后利用返祖边找环，在搜索树上维护前缀和即可），扔进线性基中，然后随便选一条1到n的路径，在线性基取max即可。考虑证明正确性：如果从1到n有多条路径，那么显然路径处于多个环上，假设现在有两条路，1->2->4,1->3->4,如果选了1->2->4，但是1->3->4更优，那么在线性基中就会选出1-2-3-4这个环，然后xor上后就变成了取了1->3->4这条路径，所以...

做法：线性基+贪心先手必胜。 游戏的结论是所有数的和不为则先手胜。因为自己可以取一次来修改局面，对手也可以取一次来修改局面，那么现在的目标就变成了取走最少的石头堆，让剩下的石头没有一个非空子集的和为。而线性基刚好满足这一性质。所以问题就变成了构造一个线性基，使其包含的石子数最多。这个将石子降序插入线性基即可。这是强行两个结论拼起来的题... #include <bits/stdc++.h> using namespace std; #define ll long long const int N = 100010; ll ans = 0, a[N]; struct lb { int...

Solution 很容易就能一眼并查集吧...提供一个简便且好写的方法，利用了哈希的思想。但是太大了。顺理成章想到离散化 这是对的 但是离散化好麻烦啊 所以我们拿一个大质数来一下吧 比如某神奇的八位质数？ #include <bits/stdc++.h> using namespace std ; #define N 2000100 const int mod = 1000007 ; int T , n ; int f[ 2 * N ] ; int a[ N ] , b[ N ] ; int find( int x ) { if( f[ x ] == x ) return x ; ...

因为太菜所以只会的做法 就是那种要用二分的，并不会clj那种不带log的做法 首先数的值域为1e9肯定要离散化一下 因为数最多有40000个所以开40000个vector，存一下每个数出现的位置 预处理出每个以块的端点为左右端点的区间的众数，这种区间一共有O(block^2)个，所以可以用O(n*block)的时间复杂度来预处理 可以发现的一点是，每个区间的众数，要么是散块里面的数，要么是中间所有整块的区间众数（因为散块中出现的那些数增加了中间的整块中第二大第三大的这些区间众数的出现次数，他们就有可能篡位了） 那么我们可以在离散化之后，将每个数出现的位置存到一个vector里面，在处理散块中的...

题目地址 https://www.luogu.org/problem/P1850 题解 这题的转移其实挺好想的但是方程特别长...真的特别长...首先设表示当前在第个位置，申请了次，当前这次申请了/没申请，为当前被安排的课室位置，为可申请的课室位置，为申请通过的概率，表示到的最短路。 直接一遍求出来就好了。那么对于，分类上一次申请了和上一次没有申请两种情况来转移，上一次没申请了就直接转移，上一次申请了就分别讨论申请通过的情况和没通过的情况，然后加起来即可。 对于，共四种情况需要组合，并且因为两次申请互相独立，所以需要乘法原理乘起来（我第一次就是写成了加法然后挂掉了）。  #include &l...

该题解同步于我的博客与我的牛客博客 A 对于，直接开个桶统计即可。入门题目。 代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41153707&scrollToDetail=1 B 对于，直接按题目模拟就好。每次两个指针扫一下就是的了。整个加起来是的复杂度。可以结合代码理解。 代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41153710 C 对于直接copy代码然后完善一下头文件什么的就行了。考虑这个是在干什...

该题解同步于我的博客 A 对于，直接开个桶统计即可。入门题目。 代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41153707&scrollToDetail=1 B 对于，直接按题目模拟就好。每次两个指针扫一下就是的了。整个加起来是的复杂度。可以结合代码理解。 代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41153710 C 对于直接copy代码然后完善一下头文件什么的就行了。考虑这个是在干什么，其实就是求...

题目描述 Two arrays u and v each with m distinct elements are called equivalent if and only if RMQ(u,l,r)=RMQ(v,l,r) for all 1≤l≤r≤m1≤l≤r≤m where RMQ(w,l,r) denotes the index of the minimum element among wl,wl+1,…,wr. Since the array contains distinct elements, the definition of minimum is unambiguous. ...

Description   现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。 但是不希望改变过多的数，也不希望改变的幅度太大。 Input   第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。n<=35000,保证所有数列是随机的 Output   第一行一个整数表示最少需要改变多少个数。 第二行一个整数，表示在改变的数最少的情况下，每个数改变 的绝对值之和的最小值。 Sample Input 4 5 2 3 5 Sample Output 1 4 Solution 神仙题目。 第一问考虑能保留下来多少，两个位置\(i,j(i&...

Description 给出A，B，考虑所有满足l<=a<=A，l<=b<=B，且不存在n>1使得n^2同时整除a和b的有序数 对(a，b)，求其lcm(a，b)之和。答案模2^30。 Input 第一行一个整数T表示数据组数。接下来T行每行两个整数A，B表示一组数据。 T ≤ 2000,A,B ≤ 4 × 10^6 Output 对每组数据输出一行一个整数表示答案模2^30的值 Sample Input 5 2 2 4 6 3 4 5 1 23333 33333 Sample Output 7 148 48 15 451085813 Solution 设\(f(...

题目链接 题目链接 题解 细心模拟题。最主要就是要细心，并且注释不要嫌多&码风要好，心态要好。思路没捋清晰之前不要动手写代码。 对于\(ERR\)，用栈来存放当前的数据。然后用个\(vis\)来判断字母重复。 输入用\(getline\)来输入会方便一点 然后对于并列，在栈空的时候进入新循环即可 对于嵌套，注意是否能展开。在嵌套层数的时候需要注意是否有展开（这个只能特判一下，类似栈，同时注意在\(E\)的时候把对应的删了) 最主要还是不能急啊，一开始心急打了一遍，结果死活调不出来:(。 #include <bits/stdc++.h> using namespace std...