题意：先交换任意两个，然后只能交换相邻两个，问最少操作次数和方案。 思路：由于冒泡排序有个定理就是逆序数的个数等于最少的交换相邻元素的次数，问题就转换为了交换两个数并且使得整个数组逆序数个数最少，我们枚举交换哪两个数，用树状数组处理b[i][j],f[i][j]，i之前大于a[j]的个数，i之后小于a[j]的次数，我们交换两个数逆序数就转变为原序列-原来他俩对数组造成的影响+他俩对新序列造成的影响再加1，为什么加1？证明：当a[i]>aj那么交换了就减去了2，多减了1我们加回来，反之小于的话，交换完他俩就能贡献一个逆序数，所以也要加。 #include<iostream> ...

题意：求一长度为y乘积为x的方案数，允许出现负数。 解题思路：我们先处理正数的，把x分解质因数，然后枚举每个质因数的次数，考虑把他们放进y个位置的方案数，就好比是将d个相同球放进y个位置，位置可以为空，为空就不好做，我们往每个位置都放一个球，问题就转变为将d+y个球放进y个位置，且位置不空，用隔板法很好做。由于乘法原理，将每个质因数的方案数乘起来，然后就是负数的情况，负数情况=(C(2,y)+C(4,y)±–+C(k,y))和正数加在一起就是2的y-1次。 代码： #include<iostream> #include<cstring> using namespace...

题意：如图 思路：单调栈维护某个点的前驱节点有多少个，设置f[i]，定义为跳到i这个位置最少跳的次数。然后我们考虑一下什么时候可以跳 1：两边比中间都大，并且左边比右边大 2:两边比中间大，并且右边比左边大 3:两边比中间小，并且右边比左边大 4:两边比中间小，并且左边比右边大。维护四个单调栈。 #include<iostream> #include<cstring> #include<queue> #include<algorithm> #include<cstdio> using namespace std; typedef l...

题意：给你n个火柴 让你凑成a-b=c的形式，不包括前导0，问总共有多少个方案数（mod上m）。 思路：真的想不出来，太妙了，先把a-b=c变形成a=b+c,然后从低位往高位枚举每位填的数，dp状态定义成f[i][f1][f2][flow] （只剩下i根火柴，b是否填完，c是否填完，是否有进位的方案数），终止条件就是b和c都填完了，看看是否有进位。很妙，每次火柴数量减去要填的数量，a的数字可以算出来，是（flow+i+j）%10。 代码： #include<iostream> #include<cstring> using namespace std; typedef...

纪念一下自己上绿了。 下面是题目： 题意：当一个数满足大于他相邻的数的时候，可以在他这建房子，我们每次操作可以将某个数减1，问最少操作多少次可以满足（1～（n+1）/2)。 思路： 一开始想的是定义状态是f[i][j]表示考虑前i个建立j个房子的最小操作数，后来发现好像不够，因为我们很难判断出第i个第i-1第i-2个数之间的关系，那么我们还是加一维吧，表示第i个数是否建立房子，并且只考虑前i个，不考虑i+1个，那么初始化的时候把所有建房子的数量为0的方案数的步数变为0，f[1][1][1]也变成0，状态转移方程： 第i个数不建立房子的方程很好说， f[i][j][0]=min(f[i-1]...

iven an extremely large non-negative integer nn, you are asked to count the number of pairs (i,j)(i,j) of integers satisfying the following conditions: 0\leq j\leq i\leq n0≤j≤i≤n; ii & n=in=i; and ii & j=0j=0. Here & represents the bitwise AND operator. For simplicity, the binary repre...

分手了不太开心QAQ，写篇博客吧。这题是区间dp的问题，题意就是给你无限个1145141919，有t次询问，询问的n小于等于5000，问是否存在这样的前缀使得你操作无限次加、乘和括号，没啥思路，看了大佬的代码，发现是有规律的？我这种菜鸡来打表都不会，那当且仅当前缀长度小于等于13，那就区间dp好了，dp[l][r][val] 代表l到r之间val这个值是不是合法，预处理的时候记得粘连在一起的部分也要算，例如“1145”，那么dp[1][4][1145]=true。 贴上代码OVO： #include<stdio.h> #include<string.h> #inclu...

Elven Postman Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 3784 Accepted Submission(s): 2268 Problem Description Elves are very peculiar creatures. As we all know, they can live for a very long time and their magical prowess are not somethi...

题意很简单：求前n项的和 并且第i项是i-1的平方倍%m。 思路：由于n很大，那么我们可以找循环节，但貌似循环节不一定从第一个位置开始，那么可以找出现两次和出现三次的pos，出现次数用map记录，然后一个一个算就行了。 代码： #include<iostream> #include<set> #include<map> using namespace std; const int N=300010; //const int mod=10000; typedef long long ll; ll sum[N]; //int n,m; ll n,x,m; //...

题意很简单：求平面所有点最大的曼哈顿距离。 ｜xi - xj | + | yi - yj | 的最大值。 思路 ： 假设 xi > xj ，那么yi 和 yj 有两种情况， yi大于yj的时候 即 ( xi - yi ) - ( xj - yj) 的最大值，反之 (xi + yi) - (xj + yj)的最大值，我们记录这两个值就行了。最后取max。 #include<iostream> #include<cstring> #include<algorithm> #include<vector> #define x first #def...

题目大致意思: 总共有n种邮票，每选一张邮票，邮票的价格会加一，邮票的初始值是1，最后问拿完n种邮票的期望价格。 思路： 发表一下看这个题题解的感想：这个题太仙了，概率dp的套路司空见惯就是把数组定义成已经考虑前i个—到n的期望。那么我们先开一个数组来记录，f[]记录从已经选了i个从第i种开始选到第n种的期望步数，那么转移就来了，只有两种情况，第一种是选到了之前选了邮票，第二种选了之前没选的邮票， f[i]=(i/n)(f[i]+1)+((n-1)/n) (f[i+1]+1),为什么要在每个里面加一呢，代表走出第i种决策的一步。f数组还是比较好想的，但是我们最后要求的是期望花费呀，秉承着要求什...

题意：给你一个序列，从左往右一次选择数字，奇数次选的符号为正，反之符号为负，问最后的最大值是多少，qwq这是简单版本的，然后难的版本多了一个修改，该修改是交换两个数的位置。 解题思路：如果是简单版本那么可以用dp来做，数组定义为考虑前i个 且轮到第i个的时候是奇数还是偶数次，难的版本有大佬说可以用线段树做，然而我并不会，然后看最优解在途中的表示，是先波峰再波谷 这样循环往复，然后画图发现竟然这个策略与(i>=1 && i<=n)zigema max(a[i]-a[i-1],0)等价，那么修改就很好办了，减去l和r对答案的贡献，再加上新的l和r对答案的贡献，当l=r+...

题意：有一棵树，主人公要从1开始走，逃生，问逃生的期望步数，在1这个点 不可能死也不可能逃生，在别的点有ei的概率逃生，ki的概率死亡并且回到1这个点。 思路： 真的是难推啊，我们定义f数组为在i这个点逃生的期望步数，由于是无向图，我们先从叶子结点考虑， f[i]=0e[i]+ k[i]f[1] + (1-ei-ki)(f[fa[i]]+1) 对于普通节点 f[i]=0e[i]+k[i]f[1]+(1-ei-ki)/m(f[fa[i]]+1)+zigma((1-ei-ki)/m*(f[child[i]]) 其中m代表i这个点的度数。 把child带进去 求出f的相应式子，将f变为Af[1]+B...

题意：给定含有WL的序列，最多能将k的L变成W，问最大的分值，当有连续的W的时候后面的W加二，第一个W加1。 解题思路： 一开始想的是dp，dp复杂度过不去啊。。后来想着把所有夹在两个W之间得区间都排序，就没继续往下面想了，看了题解，发现贪心策略跟我差不多，策略：尽量往贴近W的位置修改L，因为这样对答案的贡献都是+2，在这个基础上如果往两个W之间填满了W答案会多增加1，那么我们要让1加的尽量多，我们把所有两个W之间的区间从大到小排序就行了，感言：还是太年轻啊。。。 AC代码： #include<iostream> #include<cstring> #include&...