blowhail

题解

/ 注册

全部文章 / 题解（共43篇）

毒瘤xor

思路：计算每一位上的0和1的个数，如果0多，就让这一位为1，如果1多，就让这一位为0。因为要求较小的解，所以0和1个数相等的时候为0. #include <cstdio> #include <iostream> #include <algorithm> #inc...

2020-07-08

0 496

珂朵莉的数列

思路：求区间内逆序对个数，可以找出逆序对之后求它对整个区间的贡献。例如 j，k是一个逆序对，那么它对整个区间的贡献应该是(j-0)*(n-k+1)，因此，用树状数组枚举k，找出（1~k-1）范围内大于a[k]的数的坐标和就行了。 #include <cstdio> #include ...

2020-07-08

0 621

借教室

题目大意：有n天可以租教室，给出每天可以租用的教室数量，有m次询问，找出最小值判断能不能完成租借。思路：线段树求区间最小值。 #include <cstdio> #include <iostream> #include <algorithm> #include ...

2020-07-07

0 571

小A买彩票

题意：用3元买一张彩票，等概率获得1,2,3,4元奖品，求买n张不亏本的概率。思路：dp[j][i]表示买了i张获得的钱，转移方程就是： dp[j][i]=dp[j-1][i-1]+dp[j-2][i-1]+dp[j-3][i-1]+dp[j-4][i-1]; #include <cstdio...

2020-06-29

0 513

Forsaken喜欢数论

题意：求前n个数的最小质因子的和。思路：素数筛的时候求一下和即可。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <s...

2020-06-29

0 524

小仙女过生日啦

思路：如果是凸多边形的时候，就是三角剖分问题了，状态转移方程就是dp[i][j]=min( dp[i][j] , max( triangle(a[i],a[j],a[k]) , max( dp[i][k] , dp[k][j] ) ) );其中（i<k<j） triangle()计算的是...

2020-06-20

0 874

字符串

思路：使用尺取法，简单来说就是先固定左边，右边逐次遍历，如果满足条件了，再将左边缩短，以此来寻找最短的满足条件的字符串。 #include <cstdio> #include <iostream> #include <algorithm> #include <...

2020-06-19

1 690

背包

思路：我们分为奇数和偶数的情况。如果是奇数，相当于在左右两边各取m/2个数，如果是偶数，左边取m/2-1个，右边取m/2个。因此，我们先枚举出每一个可能是中位数的数左右两边要取的数的和。首先先对物品按照价值进行排序，然后利用优先队列维护已存物品的体积，如果放的数量超过了要取的数，就去掉占用体积最大的...

2020-06-16

2 726

失衡天平

思路：我们拿到一个新的武器之后，有三种状态：①放到天平左边②放到天平右边③不要这个武器那么状态转移方程就为：dp[i][j]=max( dp[i-1][j] , max( dp[i-1][j+va[i]] , dp[i-1][abs(j-va[i])] )+va[i] );(dp[i][j]表示前...

2020-06-10

0 707

扑克牌

思路：二分的思想，枚举可能的套数 x ，判断的时候，只需要计算有x套时需要多少个joker，如果joker比手中的jioker大或者比套数x大（说明至少有一套不止有一个joker）就不成立，否则都成立。 #include <cstdio> #include <iostream>...

2020-06-09

0 562