又是求异或和的和的常见套路——按位计算，即计算二进制中每一位的贡献。 需要注意的是，题目要求的不仅要区间长度在[L,R],而且区间长度必须是偶数（因为这个debug了好久qwq） 我们先来简化下题目。 我们假设只考虑一个二进制位x，并且区间长度也可以为奇数，那么这个怎么做呢？ 很简单，我们为了方便处理，先做个前缀和，表示，前i个数字中，二进制第x位为1的数字的个数。 然后，我们就来统计答案，为了好计算，我们肯定要先固定区间的一个端点，于是，我们先枚举左端点l,那么，明显的，对答案有贡献的只有第x位为1的个数是奇数的区间，每个这样的区间都会产生贡献的贡献，那么，我们统计有几个这样的区间就行了。 ...

直接复制以前写的代码，还带注释，真棒！ 咳咳。 这道题，我们算从A到D点的最短距离，那么明显的，我们考虑三分。 我们先三分出从A点到AB中的某个点X，作为出发点，然后，再三分出从X到CD的某个点Y，再从Y直接到D，这样，我们就可以求出最小的值了。 我们来看看，我们这样三分是否完备。 我们走的最短路线一共有四种情况，即是否走两条传送带。 如果我们不走AB传送带，那么，其实就相当于一开始我们从A点走到A点，再开始走 不走CD传送带，也就是相当于直接从X走到D点（两点之间线段最短，且速度相同，所以不走CD传送带的话，直接走到D是最短的） 所以，我们发现，我们这样三分是完全可行的！做一遍就行了！ (代...

Ps:数据范围: 一道比较套路的题了 因为对于一个数a[i],我们其实只需要知道它与b的大小关系就行了，并不需要知道其准确的值，所以，我们可以将每个点变为它对它所在的所有区间的中，这个数添加进区间后，会对b到中位数的位置的变化的贡献是多少： 如果a[i]>b,那么，它会使得b的位置向左移一位，所以，贡献就是-1 如果a[i]=b,没有影响，贡献为0 如果a[i]<b,那么，他会使得b的位置向右移动一位，所以贡献就是1 当然，你也可以这么理解： 因为一个点是中位数(区间长度为奇数且无重复)当前仅当小于这个数的数字的个数==大于这个数的数字的个数。 那么，我们只需要知道，小于b的数的个...

#我的一日对象#

我们用字典树，从高位到低位进行排序，使用中有类似于基排的思路。 残留问题在于，空间方面，需要我们使用vector或类似的动态扩充的来做。不过，不想去想了，先给个代码： #include<bits/stdc++.h> using namespace std; const int N=1e5+1,M=256,mod=255; struct node{ int a[M],tot; }t[N<<2]; int cnt,sav[5]; inline void insert(int x){ int now=0; for(int i=1;i<=4;++i){ sav[i]=(x...

ThinkofBlank 我要对象

呜呜来晚了。。。 题目大意： 你只能两步两步的走,问你最少添加多少条边才可以使得你能遍历完整个图 题解: 我们每次只能两步两步地走，那么如果，我们走一条边再回去，这是毫无意义的。 如果，我们一个图中没有无向边环，（也即是图的形状类似于树），那么，很明显的，一个点到另外一个点走的步数的奇偶性就确定了，而且，必然无法走通，我们就必须考虑添边。 那么要添几条边呢？ 我们分析下，我们现在添加一条边后，就必然产生了一个无向边环，那么我们讨论下这个环的奇偶性即可。 如果这个环是偶环，那么，我们走一遍环后，步数奇偶性不变，原来不能到达的点现在还是不能到达，没用。 如果这个环是奇环，那么，我们走一遍环后，步数...

一个简单的贪心做法（已通过@7QQQQQQQ大佬的hack数据） 我们设maxe[i]表示i-n的元素的最大值。 那么，我们假设，当前栈顶的元素比maxe[i+1]大（最近入栈的是第i个元素），那么，不难发现，如果我们当前元素不出栈的话，之后如果有元素入栈，那么最后出栈的字典序一定会小于当前元素出栈的字典序。于是按照这个策略模拟即可~ 代码: #include<bits/stdc++.h> using namespace std; const int N=1e6+2; int a[N],maxe[N],sta[N],top; int main(){ int n; scanf("%d...

把之前的补过来/xk 最近,做了好多图论,其中大部分都跟tarjan有关,而又有好多无向图。。。orz 我们都知道,tarjan会把能互达的若干点合并为一个点,然而,在无向图中,所有点都可互达(图联通),故,整个图就会缩成一个点...然鹅,我们把图画出来,又是另外的样子...明明就只有一个环,却把所有点都缩进去了,很是恼火... 一开始遇到了,想了半小时,算了,放弃.直到最近水P2783的时候,突然恍然大悟,下面来介绍下我的做法(不知道有没有大佬跟我一样。。。) 首先,我们想,如果我们的无向图不是无向图而是有向图该多好啊。。。于是,我便打算只建一条边,然鹅这个想法很快就被淘汰了,因为,只建一条...

还是来写点有意思的题目的题解吧/x C.Rabbit的工作(1) 这题很明显是个dp题，因为n很小，我们直接乱搞就行了，不用考虑优化什么的。。。 我们设dp[i][j]表示前i天，我们一共工作了j天所耗费的最小疲惫度 那么对于第i天来说，我们有如下情况： 如果第i天为0，直接从i-1那里将值继承过来就行了，即dp[i][j]=dp[i-1][j] 如果第i天为1，那么就有两个情况： 1.第i天不上课，那么和上面的一样，dp[i][j]=dp[i-1][j] 2.第i天上课，但是，我们无法保证连续性啊，难道我们还要多加一维0/1表示第i是否上课吗？ 不用，我们直接乱搞,我们直接枚举我们从哪天开始...

嗯。。。表达式计算的又一道类模板 做这类题，其实就相当于在搞一个大模拟的题目。 我们需要注意的是：因为有多余的括号出现，所以我们最好在一开始把多余的括号去掉，防止中途计算出现问题。 其次，就是需要注意计算的顺序，对于此题，我们应该先算括号，再算乘方，然后按出现顺序算乘除，最后再按出现顺序算加减。 我的代码非常长，因为全程大模拟/xk 不过，其中有很多地方只是稍微改了一点点，应该可读/xk 代码: #include<bits/stdc++.h> using namespace std; const int N=31; inline int calc(string x){//计算表达式...

逆序对模板题/x(怎么又是模板题啊) 题目大意： 给你一个长度为n的序列，求逆序对数 直接上归并排序。。。才怪。。。 作为一个热衷于权值线段树的菜鸡，当然直接上权值线段树辣！ 只需要实现insert()添加一个数和find()查询值的范围属于查询区间的数字的个数 这两个基本函数就行。 代码: #include<bits/stdc++.h> using namespace std; const int N=1e5+1; int W[N<<2]; inline void insert(int now,int l,int r,int x){ ++W[now]; if(l==r...

题目大意： 给你三个数A,B,P,求 快速幂模板题/xk 但是，我们注意到，P的值很大，可以达到,所以，我们不能直接打快速幂，我们需要搞个龟速乘进去。 代码： #include<bits/stdc++.h> using namespace std; inline unsigned long long ksc(unsigned long long x,unsigned long long y,unsigned long long p){ unsigned long long ans=0; while(y){ if(y&1){ ans=(ans+x)%p; } x=(x+x)%...

一.闲话 做题历程：点开题目->发现做过->点击提交->AC (/x) 二.题解 明显的一道bitset的题目/x bitset是个高级的黑科技，支持各种操作，其中最有用处的，就是bitset支持位运算。 我曾经尝试模拟了一下，貌似挺简单的，就是开个int数组，值就是当前状态状压后的值，进位就是把值传个下一个下标，直接模拟即可。 如果使用long long模拟的话，可以做到单次操作，不过不知道bitset还有没有其它玄学操作。。。 来看这道题。 我们把一个bitset看做一个支持位运算的bool数组 那么，我们设s[i]表示我们是否可以做到和为i 如果，我们求出来了之前的所有...