xia0ji233's blog

来源于CF1676H2题目，遇到一个求逆序对的问题，咱也不敢问为什么能这么求啊。 求逆序对用途：给一个序列，求出逆序对，$O(log_2n)$ 123456789101112131415161718#include<iostream>#include <vector>using namespace std;int main() { int t; cin>>t; while(t--){ long long n,rez=0; cin>>n; vector<int> a(n),T(n+1); for(int i=0;i<n;i++) cin>>a[i]; for(int i=n-1;i>=0;i--){ for(int x=a[i];x>0;x -= x&-x) rez+=T[x]; for(int x=a[i];x<=n;x+=x ...

树状数组（Fenwick Tree），这次EC Final遇到过的，英文也记一下，也来学一下，刚好半夜刷题刷到了树状数组可以解决的题目！ 简介树状数组和线段树具有相似的功能，但他俩毕竟还有一些区别：树状数组能有的操作，线段树一定有；线段树有的操作，树状数组不一定有。但是树状数组的代码要比线段树短，思维更清晰，速度也更快，在解决一些单点修改的问题时，树状数组是不二之选。 原理下面这张图展示了树状数组的工作原理： 这个结构和线段树有些类似：用一个大节点表示一些小节点的信息，进行查询的时候只需要查询一些大节点而不是所有的小节点。 最上面的八个方块就代表数组 $a$。 他们下面的参差不齐的剩下的方块就代表数组 $a$ 的上级——$c$ 数组。 从图中可以看出：$c_2$ 管理的是 $a_1$,$a_2$；$c_4$ 管理的是 $a_1$,$a_2$,$a_3$,$a_4$；$c_6$ 管理的是 $a_5$,$a_6$；$c_8$ 则管理全部 $8$ 个数。 如果要计算数组 $a$ 的区间和，比如说要算 $a_{51}$~$a_{91}$ 的区间和，可以采用类似倍增的思想： 从 $91$ ...

本场比赛写出一个 1007 也写一篇题解吧！ 1007题目描述 题目分析就是给你 $n$ 层楼，每层楼有一个怪物，杀了怪物需要自己的攻击力超过它的血量，否则不能到达该楼层，一次可以跳 $k$ 以内的层或者下降一层，杀了怪物后这一层不能继续呆了，杀了怪物之后怪物的血量会成为自己的攻击力。 看标程是线段树写的，咱也不会，只能纯模拟啦。 首先可以肯定的一点就是：你跳了之后要把下面的怪物都收拾完，因为题目问你的是：能否解决所有怪物！！而你一次只能下降一层，不能去已经没有怪物的楼层。因此我们主要关注，我们要跳到哪里去，能收拾完下面的怪物。首先可以肯定的是：直接选择能跳的跳是肯定不行的，随便出一组数据便可知。 12316 1 56 1 1 2 1 4 当你贪心地跳到第 $2$ 层之后你就会发现 $6$ 你收拾不了了。而这个数据是有解的，我们跳到第五层从上往下收拾完是能打过 $6$ 的。 那么其实我们就需要判断：我们跳了一个楼层之后是否能收拾下面的怪物，收拾下面的怪物是从上往下收拾，我们还可以沿途吃掉中间的怪物增长攻击力，但是这样的 check 乍一听好像是 O(n) 啊，不可行！但是其 ...

和sigma姐姐vp这场icpc。 D. Journey to Un’Goro这题是构造题，本来有思路了的，但是没敢提交。 题目描述 题目解析就是说给定一个长度，你需要构造一个只有 r 和 b 字符的字符串，在字符串的子串中，如果有奇数个r，这就是个好区间。问你一个这样长度的字符串最多有多少个好区间，并构造出最好的情况，按字典序输出，如果超过100个则输出前100个。 我们思考一下如何去计算最大值，就得先看看怎么去计数，首先暴力计数需要 $n^2$ 就肯定不行。因为是奇数个，所以我们考虑转化成前缀和。那么我们看看，如果只有一个 r 其它全是 b 我们看哪些区间符合条件。这里我们不妨把 r 当成 1，把 b 当成 0。 12b b b b r r r b b b0 0 0 0 1 2 3 3 3 3 可以很容易发现，当前缀和相减之后为奇数时，区间是好区间。那么就是偶数匹配奇数其实，因为偶数减奇数或者奇数减偶数才有可能得到奇数，而前缀和要么是偶数要么是奇数。我们最终得到的结果就是 $num=cnt_{odd}\times cnt_{even}$ 而我们很容易得到 $cn ...

这场打回来一点吧，只是看隔壁div1好像被喷烂了的样子，咱也不懂，也没资格打div1，很多细节没注意到送出去罚时就很难受，本场录屏在B站了， A. Perfect Permutation题目描述 题目分析这题题意看了我有点久，就是构造一串能使得 a[i]/i 为整数比较少的序列，那么 i=1 它可以被任意数整除。但是 i>1 我总能找到不能整除的数，因此这里构造的序列就是，第一个给 n，后面的给 i-1 即可。 标程1234567891011121314151617181920212223#include<bits/stdc++.h>#define maxn 200005using namespace std;int a[maxn],b[maxn];char s[maxn];int n,m;int dp[maxn],sum1[maxn],sum2[maxn];void solve(){ scanf("%d",&n); printf("%d ",n); for(int i=1;i<n; ...

这次的比赛没打，但是自己打估计就是自闭上去的。 A. String Building题目描述 题目分析给你三个门，每个门后可能有🔑，一个钥匙开一个对应的门，问你是否有办法把所有的门打开。很简单，就那到🔑开个门，换新钥匙，看看能开几个门就可以了。 标程1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h>#define maxn 200005using namespace std;int a[maxn],b[maxn];char s[maxn];void solve(){ int a,b[4]; scanf("%d%d%d%d",&a,&b[1],&b[2],&b[3]); int key=a,cnt=0; while(key){ key=b[key]; cnt++; } if(cnt==3){ pu ...

牛客多校碰到毒瘤括号dp题，题解记录一下。 K题目描述 题目分析给定长度为n的括号序列（不保证合法性），求在此基础上生成的长度为m括号序列的方案数。 设 $dp[i][j][k]$表示插入括号的数量为 $i$、使用的原来的序列中的括号数量为 $j$，左括号比右括号多 $k$ 时的方案数。那么最终答案为 $dp[m-nl[n][0]$。那么考虑如何设计状态转移： 首先枚举插入的括号数量，原来的括号序列和左括号比右括号多的数量。如果目前枚举到的括号为左括号，并且使用的原括号的数量$< n$，就可以将该括号放入最终序列中，即为：$$dp[i][j+1][k+1]=(dp[i][j+1][k+1]+dp[i][j][k])%mod$$如果此时枚举到的是一个右括号，并且$k>0$，即左括号的数量大于右括号的数量，并且使用的原括号的数量$<n$，就将该右括号放入最终序列：$$dp[i][j+1][k-1]=(dp[i][j+1][k-1]+dp[i][j][k])%mod$$如果使用的括号数量为 $n$，或当前枚举到右括号，则可以插入左括号：$$dp[i+ ...

练一下线段树专题吧，本篇博客持续更新！ 线段树线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 线段树可以在 $O(\log N)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 线段树维护的信息在很多时候可以认为是满足（幺）半群的性质的信息。 一个幺半群 $M=(S,\circ ,e)$，其中 $\circ$ 为在集合 $S$ 上定义的二元运算符，幺半群具有以下性质： 封闭性：$\forall x\in S$ 和 $\forall y\in S$ 有 $x\circ y\in S$。 结合律：$\forall x,y,z\in S$ 有 $(x\circ y)\circ z=x\circ (y\circ z)$。 存在幺元：即 $\exists e\in S$ 满足 $\forall x \in S$ 有 $e\circ x=x$，$e$ 为左幺元；或 $x\circ e=x$，$e$ 为右幺元。 我们观察到线段树上的信息一般满足这样的性质，一些数域上的加法与乘法自然，考虑二元的 ...

今天掉大分，预估回青名吧。实时录屏 A. Grass Field题目描述： 题目分析给定2×2的草地，一次操作能任意清除三块草地，问最多几次清除所有草地。那就判断草地个数，只有全是草地的时候才要两次，没有草地的时候一次不用，其余情况都是一次。 标程12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>#define maxn 500002using namespace std;int a[maxn];const int mod=1e9+7;int dx[]={1,0,0,-1},dy[]={0,1,-1,0};queue<pair<int,int>>q;//y,xint n,m; void solve(){ int a[4]; scanf("%d %d %d %d",a,a+1,a+2,a+3); int sum=a[1]+a[2]+a[3 ...

好久没打过cf了，今天重温一下，可能手比较生了，打得状态不太好。实时录屏 A. The Third Three Number Problem题目描述： 题目分析题意比较简单，给定一个数，构造三个数使得 a^b+b^c+c^a==n。首先不难想到，奇数一定无法构造，因为奇数异或偶数结果一定为奇数，奇数与奇数以及偶数与偶数异或结果一定为偶数，则我们有以下结论： 若三个数中没有奇数，则相互异或和一定为偶数。 若三个数中只有一个奇数，则异或的结果会产生2个奇数，一个偶数，最终和仍为偶数。 若三个数中有两个奇数，则异或的结果产生2个奇数，一个偶数，最终和也为偶数。 若三个数全是奇数，则异或的结果产生全为偶数，最终结果也是偶数。 不难发现我们最终结果必是偶数。 那么如果不是偶数那么直接输出-1，若是则我们令其中两个数为1，那么最终结果就是 n=1^1+1^x+1^x=2*(1^x)。我们非常容易能解出 x 的值。 标程123456789101112131415161718192021222324252627#include<bits/stdc++.h>#define maxn ...