xtayex / gitalk Goto Github PK
View Code? Open in Web Editor NEWgitalk
gitalk
https://xtayex.github.io/2019/02/17/HDU2639-Bone-Collector-II/#more
Bone Collector II 这道题与Bone Collector的不同之处在于,这道题求的是第k优解,而非最优解。那应该怎么做呢? 首先,01背包的核心方程式dp[j] = max(dp[j] , dp[j - w[i]] + v[i]) ,也就是说,每一个新状态都是由dp[j]或dp[j - w[i]] + v[i]转移来的。我们首先用一个
题目链接:序列统计 首先,L与R实际上是没太大意义的,因为我们需要的只是L和R之间含有多少个数,即R-L+1个数。其次,要注意一点,在一个序列中,数字是可以重复的。以样例中的2 4 5为例,符合要求的序列有{4},{5},{4,5},{4,4},{5,5}。事实上,问题可以转化为“有R-L+1个不同的盒子,若要将i(1<=i<=n)个相同的小球放进这些盒子里(某
https://xtayex.github.io/2019/02/17/POJ1384-Piggy-Bank/
Piggy Bank 完全背包的经典问题,只要把状态转移方程的max改为min,同时将dp[0]设为0,其余则设为INF即可( 因为要求是否能装满 )
https://xtayex.github.io/2019/02/17/URAL-1244-Gentlemen/#more
URAL - 1244 Gentlemen 一道01背包的题目,只不过这一次不是用01背包来求最大值或最小值,而是将背包填满。这只需要将数组dp[]的dp[0]设为0,将其他设为 -∞即可(原因:这是为什么呢?可以这样理解:初始化的 F 数组事实上就是在没有任何物品可以放 入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为 0 的背包可以在什 么也不装且价值为 0
https://xtayex.github.io/2019/01/28/HDOJ5446-Unknown-Treasure/#more
题目链接:Unknown Treasure 这道题求得实际上是C(n,m)%M,M=p1·p2·p3···pk。又因为pi都是素数,故可用卢卡斯定理。但这里不可以直接用Lucas,因为Lucas的使用条件是“C(n,m)很大,但p不太大,同时p为素数”,而这里的M可能会很大。故我们可以先求C(n,m)%p1,C(n,m)%p2,C(n,m)%pk,然后再利用**剩余定理得到最终答案。 代码如下:
https://xtayex.github.io/2019/02/17/POJ3624-Charm-Bracelet/
Charm Bracelet 一道01背包模板题,套模板即可。
https://xtayex.github.io/2018/12/11/%E4%BB%A3%E7%A0%81%E5%88%86%E4%BA%AB/
这是POJ1002 #include #include #include #include using namespace std;char a[1010],b[1010];char rsl[2000];void rev(char str[]){ int len=strlen(str); for(int i=0;i<len/2;i++){ int tmp=st
hehehehhe
https://xtayex.github.io/2019/01/26/POJ1328-Radar-Installation-%E8%B4%AA%E5%BF%83/#more
思路:以岛屿为圆心作半径为d的圆,则每个可以被覆盖的岛屿(即y<=d)都可以在x轴上形成一个或两个交点。也就是说,每个岛屿在画圆后都在x轴上形成一个长度大于或等于0的区间。这些区间即为安装雷达的地方。接下来要做的就是将这些区间的相交区间(即交集)找出来并计数。相交区间的数目即为雷达的数目。
https://xtayex.github.io/2019/02/22/HDU1969-Pie/
Pie 二分答案的经典题。所谓二分答案,即在整个可能的答案空间内进行二分操作,每次都检验一下mid,并根据检验结果调整lef和rig的值。
https://xtayex.github.io/2019/01/26/HDOJ1002-A+B-Problem/#more
大数相加,方法就是用字符串存数字,然后模拟手算的方法计算。虽是水题,但有些细节还是要注意。
https://xtayex.github.io/2019/02/11/HDU4054-Hexadecimal-View/
Hexadecimal View 此题没有考查任何一个算法知识点,只是一道用来练代码熟悉度的题目
https://xtayex.github.io/2019/01/26/POJ2159-Ancient-Cipher/#more
题目链接:Ancient Cipher
https://xtayex.github.io/2019/01/28/%E5%BF%AB%E9%80%9F%E4%B9%98%E7%AE%97%E6%B3%95/#more
原理与快速幂相似,利用二进制将两个数的乘法运算转化为加法运算。具体代码如下:
https://xtayex.github.io/2019/02/11/HDU4054-Hexadecimal-View/
Hexadecimal View 此题没有考查任何一个算法知识点,只是一道用来练代码熟悉度的题目
https://xtayex.github.io/2019/02/22/POJ-3734-Block/
Block 这是冬训的一道关于矩阵快速幂的题目,但我硬是想不出递推式,于是只好硬推公式(同时部分参考题解)
https://xtayex.github.io/2019/02/22/POJ2063-Investment/
Investment 其实就是做若干次的完全背包,每做一次都更新一下钱的总数。需要注意的是,因为钱的总数可能会很大,所以需要进行缩小,以免MLE。缩小方法是,因为每一种证券的价钱都是1000的倍数,故我们可以将它们的价钱都缩小为原来的1/1000(而利息不变)。
https://xtayex.github.io/2019/01/25/code-highlight-test/
123456789#include <iostream>#include <cstdio>#include <cstring>using namespace std;int main(){ cout<<"hello world!"<<endl; return 0;}
https://xtayex.github.io/2019/02/18/HDU3466-Proud-Merchant/
Proud Merchant 这道题最难搞的地方在于如何处理“小于qi时不能买”这一要求。苦思冥想许久,依然不知如何解决,于是只好去看题解…… 这道题的做法是首先将“商人”按照q-p排序,然后再进行01背包。为什么是按照q-p排序呢?假设有两件物品A,B,他们对应的p,q分别是p1,q1和p2,q2。如果这两件东西都要买,那么,如果先买A,就至少需要
https://xtayex.github.io/2018/12/10/%E7%AC%AC%E4%B8%80%E7%AF%87%E5%8D%9A%E5%AE%A2/
这是我的第一篇博客 #include <stdio.h>int main(){ printf(“hello,world\n”); return 0;}
https://xtayex.github.io/2019/02/13/HDOJ1171-Big-Event-in-HDU/#more
HDOJ1171一道多重背包的题目,我做的时候写了三个版本的代码(第一个版本的TLE了)
https://xtayex.github.io/2019/01/26/POJ1328-Radar-Installation-%E8%B4%AA%E5%BF%83/#more
思路:以岛屿为圆心作半径为d的圆,则每个可以被覆盖的岛屿(即y<=d)都可以在x轴上形成一个或两个交点。也就是说,每个岛屿在画圆后都在x轴上形成一个长度大于或等于0的区间。这些区间即为安装雷达的地方。接下来要做的就是将这些区间的相交区间(即交集)找出来并计数。相交区间的数目即为雷达的数目。
https://xtayex.github.io/2019/01/25/long-article-test/
曝林青霞与秦汉领证结婚 1月25日,网络疯传林青霞嫁给秦汉,传两人已低调领证,但有港媒报道,据和林青霞相交40年以上的密友表示“不可能”。 林青霞去年屡传和邢李婚变,但她始终没承认,而目前单身的秦汉曾和青霞有过一段情,近日疯传林青霞现身秦汉豪宅,又传林青霞和秦汉两人已低调领证,消息一出震惊网友。但据和林青霞相交40年以上的密友表示“不可能”。曝林青霞与秦汉领证结婚 1月25日,网络疯传林青霞嫁给秦
Saving BeansProblem Description123Although winter is far away, squirrels have to work day and night to save beans. They need plenty of food to get through those long cold days. After some time the squ
https://xtayex.github.io/2019/02/01/拓展欧几里得算法/#more
普通的欧几里得算法 这大概是最为人熟知的数论算法了吧,作用是求出gcd(a,b),代码如下:
https://xtayex.github.io/2019/01/26/HDOJ-2612-Find-A-Way-BFS/
这是一道稍微有点特殊的题,特殊之处在于它需要使用2次广搜。刚开始做的时候思路是把所有肯德基的位置记录下来,然后以每一个肯德基的位置为终点来bfs。。。。。。然后就TLE了OTZ。。。。。。后来发现只需要只需要用两次bfs,把整个地图走遍,如果走到的地方是肯德基,就记录此时的步数,然后两个最小值相加乘以11就行了。代码如下: 123456789101112131415161
https://xtayex.github.io/2019/02/18/HDU1864-%E6%9C%80%E5%A4%A7%E6%8A%A5%E9%94%80%E9%A2%9D/#more
最大报销额 这道题有两个需要注意的地方:一是题目说的“每项”其实是“每类”,也就是A类,B类和C类,而不是每个物品……(这题目表述有问题啊!);二是在计算时要将所有的数据扩大100倍然后再转为int,计算出最后结果后再缩小为原来的倍率,否则无法用钱数来做背包(浮点数无法作为数组下标)。
https://xtayex.github.io/2019/01/26/POJ2159-Ancient-Cipher/#more
题目链接:Ancient Cipher
https://xtayex.github.io/2019/02/17/HDOJ2602-Bone-Collector/#more
Bone Collector 一道01背包模板题,套模板即可
https://xtayex.github.io/2019/02/17/HDU1171-Big-Event-in-HDU/#more
Big Event in HDU 这道题是让我们将设备根据价值尽可能地平均分成两半,其实就是把设备的价值总和平分成两个部分,然后以此为背包,将这个背包尽可能填满。因为这里的“体积”和“价值”都是设备的价值,所以其实就是求价值的最大值。题目还要求输出时,大的在前面,小的在后面,这可以利用整除的特性做到,因为一个整数a整除2得到的结果一定是小于或等于a/2(非整除)的。 代码如
https://xtayex.github.io/2019/01/26/UVa101-The-Blocks-Problem/#more
题目链接:Uva101也可以在这看:Vjudge
https://xtayex.github.io/2019/02/17/HDU2955-Robberies/#more
Robberies 依然是01背包,但这次的有点特殊。特殊之处在于,背包的总体积是可以获得的钱的最大值( 如果是以概率为背包也不能枚举啊23333 ),然后用动态规划求得获得该钱数被抓的最大概率( 如果在最大概率的情况下都不会被抓,那就肯定不会被抓 )。 代码如下:1234567891011121314151617181920212223242526272829303132
卢卡斯定理 卢卡斯定理主要是用来求组合数取模,即C(n,m)%p。其适用范围是:组合数很大,但p又不是很大且p是素数的情况(10^6+3也算是“不很大”) 。卢卡斯定理可以表达为:
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.