题目链接 https://codeforces.com/problemset/problem/664/B 解题思路 由于每一个？只能取1-n，那么我们对于每一个？首先赋值为前面符号对应的+1或者-1，那么接下来就只需要在扫一边所有的数对这个答案进行调整就行了 AC代码 #include<bits/stdc++.h> using namespace std; const int N=1e6+10; int num[N],n,f=1,pos,val; char ch; int main() { while(cin>>ch) { if(c...

题目链接 https://codeforces.com/problemset/problem/556/D 解题思路 贪心+点匹配区间问题 点匹配区间问题例题及讲解不想多说了，感觉挺板子的。特别注意输出是“Yes”/“No”，而不是“YES”/“NO”！！！ AC代码 #include<bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std; const int N=2e5+5; typedef pair<ll,int> pli; priori...

题目链接 https://vjudge.net/problem/POJ-3614 题目大意 有C头奶牛晒日光浴，第i头奶牛需要minSPF[i]至maxSPF[i]之间的日光强度。现在有L个防晒霜，第i个防晒霜可以使日光强度控制在SPF[i]，可以供cover[i]头奶牛使用，求最多能满足多少头奶牛。 解题思路 贪心，<stron>。</stron> 因为同时有上限和下限约束着防晒霜的使用，所以贪心策略不一样。需要先去掉一个约束再执行贪心策略，所以从小打到枚举每一种防晒霜，对于每一种防晒霜，我们需要先找出所有spf下限小于它 的牛，然后再贪心选出可以使用防晒霜的spf上...

题目链接 https://codeforces.com/problemset/problem/558/C 解题思路 大佬都说这叫暴力，但是这技巧性也太足了吧……整体思路：暴力枚举每个数能到达的数，并记录下到达该数的步数，最后找到每个数都能到达且步数之和最小的数输出。 详细思路：找最后的答案没必要再暴力统计，我们可以同cnt[i]记录开始的n个数中能到达数值为i的个数；同时用step[i]记录所有开始的n个数到达数值为i的步数之和。 最后输出的答案最大也就是开始n个数中的最大值。（证明我真不会，就是种感觉吧……乱蒙）（这是大佬的解释，但是我没看懂：最大的交点最多是输入的最大值mx，因为如果要去往...

题目链接 https://ac.nowcoder.com/acm/problem/20532 解题思路 整体思路：考虑每两个节点之间的最短距离就是求这两个点的 LCA ，那么三个点我们可以先两两一组找到 LCA。我们可以发现三个点的 LCA 要么是完全一样，要么是有两个（两个相同，一个不同），如果是有两种 LCA 那么此时我们要选择不同的那一个这样才能使路径最短，因为可以保证有一条路径不会重复两遍。这个的粗略证明应该比较简单，自己手画画就行。肯定要找祖先作为集合地点，之后总结一下什么情况下用哪个祖先，整理一下得到上面的结论。 具体实现 代码1是通过ST表+欧拉序实现的，因为当时只会这个方法求L...

题目链接 https://www.acwing.com/problem/content/description/111/ 题解链接 https://www.acwing.com/solution/content/15458/写的太好了，提醒一下，第一个代码会TLE，其他两个均可以AC我下面附上的两个代码是可以AC的。 AC代码 //非归并排序+倍增 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=5e5+10; int n,m,T; ll k,tmp[N],a[N]; ...

题目链接 https://www.luogu.com.cn/problem/P1083 解题思路 第一种方法，也是我用的方法，因为另一种没想到。线段树，维护区间最小值，比较简单，就是代码冗长 不会戳这里第二种才是好方法，差分数组+二分这道题就是我点差分数组才找到的，说来惭愧我并没用差分数组。将二分请求出错是第几次，check函数的话，从第一次请求到二分的这次请求循环，用差分数组记录，再循环1 ~ n求和，并比较与房间个数的大小关系，比房间多说明不可行，否则可行。 AC代码 //线段树 维护最小值 区间修改 区间查询 //提醒用scanf，printf否则可能超时 #include<bit...

题目链接 https://www.luogu.com.cn/problem/P3128 解题思路 树上差分 LCA知道树上差分在什么情况下使用，树上路径，树上两点等。 AC代码 #include<bits/stdc++.h> using namespace std; const int N=5e4+10; const int INF=0x3f3f3f3f; vector<int> e[N]; int n,k,a,b,ans=-INF,Time; int sum[N],path[N<<1],st[N<<1][20],pos[N<<...

题目链接 https://www.luogu.com.cn/problem/P3379 解题思路 ST表 + 欧拉序 。通过欧拉序会发现根结点总在中间，而根结点是该段序列深度最小的点。因此两个点的LCA，就是在该序列上两个点第一次出现的区间内深度最小的那个点。 细节见代码，主要是注意下标含义。 AC代码 #include<bits/stdc++.h> using namespace std; const int N=5e5+100; int n,m,rt,Time,a,b; int path[N<<1],pos[N<<1][20],dp[N],in[N]...

前言 废物POJ，QDUOJ都比它强！！！废物POJ！万能头用不了还说的过去，妈的，你告诉我还卡二维vector？？？非得用个vector<vector<int> > v(N)？？？debug 3h？？？wdnmd哦，唯一的一个优点就是快。</int> 题目链接 http://poj.org/problem?id=3321 解题思路 首先，客观的说（不带主观色彩），这个题数据是不是过于水？通过AC代码，发现输入的a，b两个节点一定是a位于靠近根的位置，b位于远离根的位置，居然不用判断是不是经过父亲节点。其次，POJ垃圾！不想讲这个题，直接挂个类似的题吧。 求...

题目链接 https://codeforces.com/problemset/problem/426/D 解题思路 首先应当得出点结论： 数据规模小。 如果01矩阵中所有0的连通块以及1的连通块都是矩阵的话，那么其实可以确定01矩阵的每一行与下一行的关系，要么这两行的元素全部相等，要么就全部相反。 ** 当 n<=k 时，可以枚举第一列的01状态，其他各行都根据第一列**的状态进行变换操作以保证所有01连通块都为矩阵。同时注意，枚举的是第一列的状态，因为是行数小于等于k，k又小于等于10，2^10是可行的，但是列数最多为100，2^100是不可行的。当然，这只是其中一个很片面的原因，望...

题目链接 https://codeforces.com/problemset/problem/424/C 解题思路 前置知识：A^0=AA^A=0异或具有结合律 直接暴力超时；第一眼以为整除分块，拉倒吧，整除分块是加法；打了个表，看列还是有规律的；所以我当时的想法是统计1 ~ n每个数个数的奇偶，之后再遍历一遍，若是奇数个就异或一下，若是偶数个continue，但是没找到快速统计个数的方法。 正确思路：还是看列，列的变化是具有周期性的；我们先统计前缀，什么前缀？sum[i]表示1 ~ i的异或，即1 ^ 2 ^ …… ^ i；再计算每一列的周期数，如果周期为奇数个，就需要用答案异或一下前缀，若...

题目链接 https://codeforces.com/problemset/problem/426/C 解题思路 先用前缀和求出每段区间的价值和；暴力枚举区间，枚举到的区间要与剩余部分的元素进行交换；交换规则：枚举到的区间从小到大排序，未枚举到的部分从大到小排序，用枚举到的区间中小的换未枚举到部分中大的，最多交换k次，若接下来的交换已经无法使枚举到的区间的价值和增加，也要break。 具体实现看代码 AC代码 //未用优先队列 139ms #include<bits/stdc++.h> #define ll long long using namespace std; cons...

解题思路 正常思路：枚举1 ~ n，统计每个数的每个质因子的个数，但是时间复杂度为为O(n根号n)。正确思路：既然枚举数求质因子不行，那我们就枚举质因子求每个数含有此质因子的个数。 看似好像两个思路就是两层循环在内在外的关系，其实正确思路的时间复杂度为O(nlogn) n！的每一个质因子都不会超过n，我们可以先筛选出1 ~ n的每个质数p，然后考虑阶乘n！中一共包含多少个质因子。n!中质因子p的个数就等于1 ~ n每个数包含质因子p的个数之和。在1 ~ n中，p的倍数，即至少包含1个质因子p的显然有floor(n/p)个。而p^2的倍数，即至少包含2个质因子p的有floor(n/p^2)个。不...