DYM Blog

Thinking will not overcome fear but action will.

USACO/Stringsobits

USACO/Stringsobits

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacostringsobits/ 给定排好序的N(N<=31)位二进制数,输出第i小的，长度为N，且1的位数的个数小于等于L的那个二进制数。 解法：递归的输出字符,ans[n][l]表示长度为n，1的位数小于等于L的二进制数的个数，则ans[n][l] = dfs(n-1 , l)+dfs...

Posted by dym on May 20, 2014

USACO/Factorials

USACO/Factorials

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacofactorials/ 求阶乘最后的非零位，n<=4220 解法：直接模拟，每次乘法后保留后四位数 #include<iostream> #include<algorithm> #include<fstream> using namespace ...

Posted by dym on May 20, 2014

USTC/Shaping Regions

USTC/Shaping Regions

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/ustcshaping-regions/ n个不同颜色的不透明长方形放置在一张长方形的白纸上，各个长方形的边和白纸的边平行放置，以白纸的左下角为坐标原点，问从上向下俯视能够看到的各种颜色的面积。 解法：枚举每一层，递归的用上一层对当前所枚举的层进行切割，对切割后剩下的矩形继续向上重复此操作，当到达最...

Posted by dym on May 18, 2014

USACO/Stamps

USACO/Stamps

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacostamps/ 知道一个 N 枚邮票的面值集合（如，{1 分，3 分}）和一个上限 K —— 表示信封上能够贴 K 张邮票。计算从 1 到 M 的最大连续可贴出的邮资，输出M。 解法：动态规划，另ans[i]表示贴出i所需的最少邮票数，则有： ans[i] = min(ans[i - cn...

Posted by dym on May 17, 2014

USACO/Contact

USACO/Contact

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacocontact/ 寻找长度在A到B之间（包含A和B本身）的重复得最多的比特序列 (1 <= A <= B <= 12)。输出规定个数的出现频率最多的序列。 例输入： 2 4 10 0101001001000100011110110000101001100111100001...

Posted by dym on May 17, 2014

USACO/Humble Numbers

USACO/Humble Numbers

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacohumble-numbers/ 寻找第n个丑数，丑数集合中每个数从小到大排列，每个丑数都是给定素数集合中的数的乘积，第N个“丑数”就是在能由素数集合中的数相乘得来的第n小的数。 解法：模拟,维护每一个素数所需乘的最小值 #include<iostream> #include&...

Posted by dym on May 14, 2014

USACO/Score Inflation

USACO/Score Inflation

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacoscore-inflation/ 完全背包。动态规划的方程是dp[w] = Max( dp[w-o[i].wei]+o[i].val) , dp[w])，方程的形式和0-1背包是相同的，但是容量的循环的顺序不同。 #include<iostream> #include<...

Posted by dym on March 15, 2014

USACO/Agri-Net

USACO/Agri-Net

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacoagri-net/ 裸的最小生成树，prim。 #include<iostream> #include<algorithm> #include<fstream> #include<stdio.h> using namespace std; ...

Posted by dym on March 13, 2014

USACO/Fractions to Decimals

USACO/Fractions to Decimals

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacofractions-to-decimals/ 将分数转换为小数，如果是有限小数，则直接输出结果，若果是循环小数，则找到循环节并用括号括起来表示后面的循环部分。规则如下： 1/3 = 0.(3) 22/5 = 4.4 1/7 = 0.(142857) 2/2 = 1.0 3/8 = 0.37...

Posted by dym on March 12, 2014

USACO/Bessie Come Home

USACO/Bessie Come Home

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacobessie-come-home/ 给定一些点，标号为A-Z、a-z，给定点之间的距离，求从Z到所有其他的大写字母代表的点的最短路径中的最小值。 解法：Dijkstra，注意处理重复边 #include<iostream> #include<algorithm> ...

Posted by dym on March 12, 2014

FEATURED TAGS
-算法 -技术 -数学
ABOUT ME

不忘初心，方得始终!

✉️ 1121477757@qq.com

FRIENDS