题面：有n只牛，把牛都放到郊外吃花，每次带回一头牛，来回时长是2*ti,每头牛吃花的速度是di，问怎么带才能吃最少的花。 思路：像这种题一般都往贪心去想，贪心有一个这样的理解就是，两个对比来贪。假如有两头牛，一个是a，一个是b，假如把a带回去，花费是 ，把b带回去就是因为排序可以通过比较函数排，我们知道两头牛之间怎么去算花费，所以在比较函数里面把花费算出来，把小的排在前面就好了。 代码： #include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include...

A 小A买彩票 前言：开始以为这是一道可以通过计算算出来的题，后来想想不对，看到n这么小，应该就是概率dp了，在这道题上也可以看作暴力。思路：dp[i][j]表示前i张彩票，中奖总金额为j的概率的次数。转移方程： ，其中k是1~4的数。为什么是这样？我们可以理解为，之后能抽到的总奖金j，是从之前的总奖金加上新的彩票得到的，新的彩票金额只有1到4，所以转移就是理所当然的了。处理完dp后，统计大于等于n*3的次数总和sum，我们把一共的情况记为tot,tot就等于4^n。答案就是：sum/tot。为什么tot是4^n？因为每次都往外延伸4种情况，可以理解为一颗树一样，对于每次结果都可以往外再...

前言： 这个题就是完全背包的裸题，只要把题目完全读懂就好了，难度不高。 思路： 首先我们知道，题目的意思是说能不能用更少种类的钱来表示这个货币系统，换言之就是，有的钱它可能可以通过小面额的钱来组成，那这种钱就不需要存在这个货币系统了，比如：2 5 9这个9就可以通过2+2+5来组成，所以9这个面额就可以不需要了；但是2无法组成5，所以5这个面额是需要的。所以题意就是在说：哪些面额的钱不能通过小面额的钱来组成因此就很简单了，那只需要先排个序，从小面额开始跑完全背包，如果之后发现这个面额是可以通过小面额的钱组成的就跳过，统计一下答案就好了。 完全背包不用教了吧，大家百度一下完全背包就能理解了。 代...

前言：快期末了时间越来越少了，补题也不能做那么多了，这次B题只过了40个大概就不写了吧，只写了比较简单的剩余4个题（其实C、D没见过这种题还真的不是那么简单） A 收集纸片 这是小白月赛里面的题，我打过那场小白月赛，我当时用的方法是旅行商问题的DP，也就是先处理好两点间的距离dis[i][j]，然后dp[i][j]表示终点为i时，此时已经经过点的状态为j，（状态因为是二进制数，1表示已经经过，0表示还未经过）花费的距离是多少。三重循环，第一重循环是：枚举状态，然后枚举起点，最后枚举终点。dp转移方程为： 因为n只有10，其实用next_permutation枚举所有的情况也可以。 代码...

感想：这个题跟很早以前入门贪心的题看电影很类似，但是那个题是给定了开始时间和结束时间，所以按照结束时间贪心就好了，这个题给出的是持续时间和结束时间，但是依然是一个贪心。 思路：如果按照工作时间排序，尽量做时间短的不一定就是最优解，因为可能时间短的都截止的晚，导致你截止时间早的就完不成了。所以首先肯定是先要按照结束时间排序，因为前面的工作要先干完才能干后面的，这很容易想到。然后，贪心肯定是能干就干，先把已经干了活的总时间和加起来。但是会遇到这样一个问题，就是之后某一个活就不够时间干了。因此可以发现，在保证干活数一定的情况下，尽量让这个总时间小一点比较好。因此可以得到思路：先对结束时间从小到大排序...

感想：真的不会做这种题，虽然已经想到了异或和这种题要按位求贡献，但是偶数还有区间这个问题想不出来怎么解决。后来看了别人的题解，想了好久才终于想明白怎么一回事了。 思路：首先，一般异或和这种题都是按位求贡献这个方向是没错的。此时要算一个区间内的异或和的这一位是否有贡献（也就是区间异或和的这一位是否为1）可以通过异或前缀和来O(1)得到。什么意思呢？首先我们先求一个异或前缀和，假设是sum数组，那么如果知道这个区间内异或和的这一位是否为1，只需要看sum[l-1]^sum[r]是不是1就好了。为什么？假如sum[l-1]这一段前缀和是这一位是1，sum[r]这一位是0，那么说明在l到r这一段异或和...

123

每日一题终于来了一个简单的题了！！！ 思路：首先这是一个排列，也就是说每个数只出现一次。我们把要找到的数的位置记为pos，对于pos右边，从pos+1到n扫一遍，同时用map存下来一个值：从pos+1到i这段区间里面比b大和比b小的差值的个数（比如2 3 4这里面差值是-3，2 5 6的差值是1，也就是说比b大就++，小就--，然后mp[count]++）。左边也同理存一下。 有什么用呢？我们只需要扫一下左边（或者右边）的map存放值，跟另一边的负存放值，答案加上这两个存放值的个数就好了。比如：对于左边的mapl[3]，那么我们需要找到右边有多少个mapr[-3]，然后答案就需要加上mapl[...

感想：看到这个题目一开始没什么想法，因为不知道怎么才能每个点都走得到。后来发现本来是只能走图上的奇数位置点，如果你走一个奇环，就能改变奇偶了，从而可以走偶数个点了。 思路：根据上面说的，如果一个图里存在一个奇环，就能够走完所有的点。但是这个图不一定是连通的，可能有很多个连通分量，所以这些连通分量之间都需要一条边连起来。奇环也同样连一条边就好了。因此：ans=连通分量个数-1+是否存在奇环(是=0，不是=1)。 代码： #include<cstdio> #include<iostream> #include<cmath> #include<algorit...

我横竖睡不着，仔细看了半夜，才从字缝里看出字来，满本都写着四个字是‘区间DP’！ 为什么是区间DP呢？因为是中序遍历啊！中序遍历有一个很大的特点就是，根在中间，二叉树的左右子树节点在根的左右对应。 那么我们只需要枚举根就好了，枚举根是不是就很像区间DP。对于一个区间，我们枚举分割点就相当于枚举根，然后一步步转移就好了，同时也要记录下每个区间的根是什么，也就是最优值是多少。 既然是DP，那也写一个转移方程吧（感觉题目已经给了诶） 因为dfs其实更好写，所以用dfs更方便。 #include<cstdio> #include<iostream> #include<c...

这是我第一次接触bitset的题，说实话我一开始真的不会做，后面发现是bitset优化dp才知道原来可以这样做。 首先，这个题目是一个状压DP，dp[i]这个i表示前1到i个数的累加和能出现的状态有多少，这个我们可以用状压去记录，比如0号位是1表示0可以出现，1号位是1表示1可以出现。 所以每个数需要2位，总的空间复杂度是 ，不会爆。 每个dp[i]可以从dp[i-1]那转移，转移只需要用到<<和|运算就好了，因为加一个数就等于左移多少位，每种合法的数加这个数就等于整体左移这么多位，然后用或运算存下来新的可行情况就好了。所以转移方程为： 然后呢，怎么存下来这个状态就需要用到bit...

感想：有一说一这次的小白月赛还真的挺舒服的了，代码量小，而且大部分题如果做过类似的题其实很容易就想出来怎么做了，除了B感觉是一个组合数学不是那么好想（数学太差啦），感觉这套题对小白而言是一套挺有意思的题，喜欢这套题。 A AOE还是单体？三分的模板题，用三分枚举使用多少次第二个技能，然后输出最后的最优值即可。 代码： #include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<vector> #include<cstrin...

4