DYM Blog

Thinking will not overcome fear but action will.

USACO/Cow Tours

USACO/Cow Tours

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacocow-tours/ 给定至少两个牧场，每个牧场由若干连通的牧区组成，给定牧区之间的连通关系和各自的坐标，问找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。（直径就是牧场中最远的两个牧区的距离）。输出在所有牧场中最小的可能的直径。 解法：首先通过给定的连通...

Posted by dym on March 12, 2014

USACO/Overfencing

USACO/Overfencing

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacooverfencing/ 给定一个迷宫，求从迷宫中任意一点出发到达出口的最短路径中最长的一条路径长度（迷宫有两个出口）。 解法：使用bfs从两个出口分别进行一次搜索和标记（即每一格记录一个步数），然后对比两次结果，每一点都取两次结果的最小值。最后输出所有点到出口的距离中的最大值。 #in...

Posted by dym on March 11, 2014

USACO/The Tamworth Two

USACO/The Tamworth Two

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacothe-tamworth-two/ 给定一个矩阵表示一张图，”.”表示通路，”“表示障碍物，农夫和牛分别从一点向同一方向出发行走，每一分钟，要么在前方没有障碍的情况下向前走一步，要么在前方有障碍的情况下顺时针旋转90度（不走）。问经过多少时间相遇或回答不能相遇。 解法：直接模拟行走过程，若...

Posted by dym on March 11, 2014

One Idea for Architecture Recovery

One Idea for Architecture Recovery

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/one-idea-for-architecture-recovery/ Def:a module is defined as a conceptual and arbitrary large collection of consecutive source code fragments with a...

Posted by dym on March 10, 2014

USACO/Controlling Companies

USACO/Controlling Companies

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacocontrolling-companies/ 有一些公司之间存在控制关系，若A有B的50%以上的股份，称A控制B，控制关系定义如下： 1.一个公司控制自己 2.如果A控制B，B控制C，则A控制C 3.如果A控制k个公司，这k个公司所占B公司的股份和若大于50%，则A控制B 给定公司间的股份...

Posted by dym on March 9, 2014

USACO/Longest Prefix

USACO/Longest Prefix

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacolongest-prefix/ 给定一个字符串集合A和一个字符串S，求使用给定集合A中的字符串所能组成的S的最长前缀是多长 解法：首先用给定集合A组成一棵trie，用来进行匹配，然后使用动态规划。dp[i]表示从S串第i个位置开始使用A中的元素所能组成的最长前缀，则dp[0]则为所求。每当...

Posted by dym on March 9, 2014

USACO/Money Systems

USACO/Money Systems

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacomoney-systems/ 求将整数N用给定的v个数进行划分的种类数，划分中的数可以重复。 解法：动态规划 cnt[i][j]表示将i拆分的数中最大为j的种类数，要么没有j,即为cnt[i][j - 1];要么至少有一个j，则为cnt[i-j][j];所以 动态规划在转移方程为：cnt[...

Posted by dym on March 6, 2014

USACO/Zero Sum

USACO/Zero Sum

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacozero-sum/ 给定N，在顺序排列的1～N之间随意插入“+”，“-”，“ ”，使得所构成的表达式计算之和为0，输出所有的解。N<=9 解法：先生成运算符的全排列，然后排序，再将表达式转为运算式计算，若结果为0则输出 #include<iostream> #inclu...

Posted by dym on March 5, 2014

USACO/Cow Pedigrees

USACO/Cow Pedigrees

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacocow-pedigrees/ 二叉树总共有N个节点(3 <= N < 200)。有如下性质:每一个节点的度是0或2。树的高度等于K(1 < K <100)。高度是从根到最远的那个叶子所需要经过的结点数;叶子是指没有孩子的节点。求有多少不同的结构，输出结果是数的结构数...

Posted by dym on March 5, 2014

USACO/Party Lamps

USACO/Party Lamps

本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacoparty-lamps/ 1~N 共N盏灯，有四个按钮， 按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。 按钮2：当按下此按钮，将改变所有奇数号的灯。 按钮3：当按下此按钮，将改变所有偶数号的灯。 按钮4：当按下此按钮，将改变所有序号是3*K+1(K&g...

Posted by dym on February 22, 2014

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

不忘初心，方得始终!

✉️ 1121477757@qq.com

FRIENDS