cy41的博客

这篇文章用的bfs，昨天还看到一个大神的数论推导，太强了：https://blog.csdn.net/v5zsq/article/details/52097459 这一道题由于没有给出杯子的具体量度，只是给出了最大容量，故每次两个杯子之间的状态为两种：        1. s1全部倒入s2中；(s1现在的液体和s2中已有的液体之和小于等于s2的容积)        2.s1倒入s2中，s1中...

小数背包，最开始我想着把小数转化为整数，乘它个10000再算，发现不对QAQ，上网搜了一下；把总钱数作为背包容量太强了； 由于是累乘背包，将所有概率转化为了不被捉的概率； 一定记得一家银行都不抢的时候被捉到的概率为0；dp[0]=1||dp[0][0]=1; #include<cstdio> #include<iostream> #include<algori...

我看到网上好多都是将物品的价值，背包容量扩大一百倍全部转化为int再最后输出时转化为double输出，所以我想可不可以直接用总支票数作为背包容量，显然是可以的。 每一张支票的重量为1，权值即是报销额度，可以通过计算，直接筛除不符合条件的支票； 由于有一个最大的总报销额，所以1.   dp[j-1]+val[i]<=Q（最大报销额）,则 dp[j]=max(dp[j],dp[j-1]+va...

原来（1,1）与（n，m）都是不可达的，因为题目说他俩可以以不同的速度走，所以必须保证只有一次相遇，我一开始觉得（n，m）是可达的，比如a从（n-1，m）来，b从（n，m-1）来，然后b再向上去往（1，m），但是由于他俩行走速度可以不同，那么就可能会发生一种情况：a在来的过程中，还没有到（n，m）的时候，b已经经过（n，m）的点，他俩就会在m这一列的某个点处相遇了就会发生多个点相遇的地方，故最后确...

因为给定的序列的数是0~n-1不重复的，所以可以边读入数字，边单点更新sum[k] 线段树表示的是:sum[k]对于[l,r]的数字出现的次数和,(即l<=x<=r,x出现的次数;) 题目要求逆序数，即对于i<j,a[i]>a[j]的数的个数和，要求第一次的话是，对于输入的数字x，求他的前面比他大的数字的个数和，再单点为x更新sum[k]++；   求出最开始的序列...

首先求出线性基,并且进一步尽可能的使的p[i]除了第i位是1以外,取余全0,尽量使得除了主对角线其余元素都为0; 之后判断线性基的秩,若秩!=元素个数,说明元素之间异或会出现0的情况,那么需要将k-1，因为此时剩余的非零向量间是无法异或出0的情况的，0是最小的异或值; 假设秩为x,那么向量间相互异或的可能情况有1<<x种,若k>=(1<<x)，则说明不可异或出,否...

题目链接：HDU - 6609 题意：多组输入，给定一个n，m，再给一个长度为n的序列，对于所有的你可以选择一些下标范围在范围内的数字变为0，使得前缀和小于等于m，问对于每个i需要改变的最小次数。i与i-1是独立的两个问题。注意嗷，这个题行末有空格 权值线段树，对于每个数字我们肯定是贪心的减掉较大的数字肯定会使得答案更小，那么问题转化成了对于第i个位置，假设前面的数字已经有序了，从i-1开始向...

有向图，从某一点出发到其他所有点的最小权值总和。 过程： 选入边集，找到除rot节点外，每一个点的所有入边中权值最小的，用in[]记录这个最小权值，用pre[]记录该最小入边的前驱；（若图中存在孤立节点的话，不存在最小树形图） 找有向环，用id[]记录节点所属环的编号。 将有向环缩点，并更新与之有直连边的权值。 以环的数量为下一次查找的点数建新图，继续重复上述过程直到没有环或者判定出不存在最小树...