usaco专题
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)
思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
usaco 1.3 Calf Flac（暴搜）
思路是暴搜。 需要注意的地方是输入的方法，以及输出时的换行。 代码： /*ID: who jayLANG: C++TASK: calfflac*/#include<stdio.h>#include<string.h>#include<math.h>int main(){freopen("calfflac.in","r",stdin);freopen("calfflac.ou
usaco 1.3 Barn Repair（贪心）
思路：用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序，选取最大的M-1个作为间隙，其余地方用木板盖住。 做法： 1.若，板（M） 的数目大于或等于 牛棚中有牛的数目（C），则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则，先对 牛牛们的门牌号排序，然后 用一个数组 blank[ ] 记录两门牌号之间的距离，然后 用数组 an
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)
到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
usaco 1.2 Palindromic Squares（进制转化）
考察进制转化 注意一些细节就可以了 直接上代码： /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi
usaco 1.2 Name That Number（数字字母转化）
巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码： /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (
usaco 1.2 Milking Cows（类hash表）
第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时！！ 第一种思路：我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较 1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end ) 2 反之 这个
usaco 1.2 Transformations（模拟）
我的做法就是一个一个情况枚举出来 注意计算公式： （ 变换后的矩阵记为C） 顺时针旋转90°：C[i] [j]=A[n-j-1] [i] （旋转180°和270° 可以多转几个九十度来推） 对称：C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<
usaco 1.1 Broken Necklace（DP）
直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于： 如果 str[i] = 'r' , rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' , bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w', bl[i]=b
USACO Section 3.1 Humble Numbers
题意： 已知一个集合S 由S的任意子集作为因子 可构造出一个数字 求 这些构造出的数字中第k大的数字是多少 思路： 拿到这题就被“数字不是很多而且比较连续暴力枚举就好”这个思路迷惑了 果断TLE… 跪了一次后想到通过bfs构造可取 这时用了queue维护bfs 用priority_queue维护答案（大顶堆 内部最多k个数字） 用set判重复（5*2=2*5） 写
USACO Section 2.3 Fractions to Decimals
题意： 已知分子分母 求 该数字的小数形式 要求如果是循环小数用（）表示出循环节 思路： 不循环小数容易处理 循环小数需要找出哪里是循环节 想象笔算除法的方法可以知道 当被除数的状态再次出现 则表示进入循环 用此方法即可 记录状态时候数组开的大点（我还用了map来映射该状态对应的位置） 因为循环节不一定什么时候出现… 我不会算… 注意： USACO对空格
USACO Section 2.3 Cow Pedigrees
题意： N个节点 深度为K 的正则二叉树 求 树有几种形态 思路： 一开始以为是数学题… 看了byvoid的题解才知道是dp… 每棵树由根节点、左子树、右子树构成 由此得状态转移 树=左子树*右子树 节点数和深度是影响答案的属性 所以令dp[i][j]表示i个节点深度在j以内的树的形态数 深度在j以内的树又两个深度在j-1以内的树和一个根节点构成 设左子树k个节
USACO Section 2.3 Longest Prefix
题意： 给你一大堆小字符串 和 一个大字符串 求 使用小字符串能拼出的大字符串的前缀最长是多少 思路： 由于数据不大 所以可以尝试扫描大字符串 每到一个位置用小字符串拼一下看看能拼多长 拼的最远距离就是答案 我用trie树来存小字符串集合 扫描大字符串时 如果该位置是可以向后延伸的（即之前能拼到这个位置） 那么我用一个标记在trie树上爬 每次发现一个小字符串结
USACO Section 1.5 Checker Challenge
题意： N皇后问题 输出 字典序最小的3种解法 和 解的数量 思路： dfs去放皇后判断和前面的皇后是否冲突 题目时间卡的超级很近！！ 简单的搜索一定跪 能剪的地方要拼命剪枝！！ 列举我的剪枝： 1.直接按字典序搜索 最先搜到的3个解保证字典序最小 直接输出 2.通过上几行皇后的放法 求出现在这行有几个位置能放皇后 之后进行搜索（这是关键！！ 千万不要先搜位置
USACO Section 1.5 Prime Palindromes
题意： 输入a和b 求 a和b之间所有既是素数同时又有回文性质的数 从小到大输出 思路： 如果枚举a到b之间所有的数再判断素数和回文那么复杂度会比O(n)还大 本题O(n)都会跪 因此思路转到能否 先得到所有素数再判断回文 或者 先得到所有回文的数在判断素数 本题我的做法是后者 说下原因 本题b最大为10^8 因此构造回文的数字可以枚举1~10000中的数字再对数字翻折
USACO Section 1.4 Packing Rectangles
题意： 已知4个矩形的l和w 矩形可以旋转和平移 用一块最小面积的新的矩形覆盖4个矩形 求最小的面积 以及新矩形的l和w 思路： 题目已经给出6种摆放方式 按它的方式摆即可 我们要枚举4个矩形是否旋转（只转90度）过 然后枚举每种摆放方式中矩形的编号 代码中的枚举方法是二进制枚举旋转 全排列枚举编号 最后计算所有情况中的答案 第6种摆放方式比较难想 大致思路就是
USACO Mother's Milk
题意 ：有3个杯子，问当a杯子为空时，c杯子能够装多少种体积的水 思路 ：倒水问题，有广搜，对于当前，接下来有6种状态：a到给b，a到给c ,c到给b,c到给a,b到给a, b到给c。每一种状态又有两种情况：能装满和不能装满。这里还要注意一点就是必须判断重复，即防止a倒给b，然后b再倒给a这种情况的发生！ 这里还有一个节省代码的技巧：因为情况很多，一开始我使用6个if，结果代码写的老长，十分不
USACO Training 4.2.3 Job Processing 工序安排 题解与分析
Job Processing 工序安排 IOI'96 描述 一家工厂的流水线正在生产一种产品，这需要两种操作：操作A和操作B。每个操作只有一些机器能够完成。 上图显示了按照下述方式工作的流水线的组织形式。A型机器从输入库接受工件，对其施加操作A，得到的中间产品存放在缓冲库。B型机器从缓冲库接受中间产品，对其施加操作B，得到的最终产品存放在输出库。所有的机器平行并且独立地工作，每个库的容量
USACO Training 3.3.3 Camelot 亚瑟王的宫殿 题解与分析
Camelot亚瑟王的宫殿 IOI 98 描述 很久以前，亚瑟王和他的骑士习惯每年元旦去庆祝他们的友谊。为了纪念上述事件，我们把这些是看作是一个有一人玩的棋盘游戏。有一个国王和若干个骑士被放置在一个由许多方格组成的棋盘上，没有两个骑士在同一个方格内。 这个例子是标准的8*8棋盘 国王可以移动到任何一个相邻的方格，从下图中黑子位置
USACO 2014 February Contest, Silver
题目地址： click here 第一次 做USACO的 silver。 感觉不出 铜银区难度的差距。。。 结果 CHN 2016 Tian Yanfei667 ****tttttt ********** *t**ttt*** 1，Auto-Complete View problem 给你 w个任意顺序的字符串，然后 n个询问， 问在这w个字典序排
![网课：第四章二分、三分、01分数规划---[USACO 2010 Feb S]Chocolate Eating](https://img-blog.csdnimg.cn/direct/f464f0f2a32d4479ae638bb9cb25e468.png)
网课：第四章二分、三分、01分数规划---[USACO 2010 Feb S]Chocolate Eating
题目 贝西收到了N（1 <= N <= 50,000）块巧克力，但她不想吃得太快，因此她想为接下来的D（1 <= D <= 50,000）天制定巧克力食用计划，以便在那些天中最大化她的最低幸福水平。 贝西的幸福水平是一个整数，起始值为0，在夜间睡觉时减半（如果必要的话向下取整）。然而，当她吃掉第i块巧克力时，她的幸福水平增加了整数 Hi （1 <= Hi <= 1,000,000）。如果她在一天
[USACO 2.4.4] Bessie Come Home
题目描述 现在是晚餐时间,而母牛们在外面分散的牧场中。农民约翰按响了电铃,所以她们开始向谷仓走去。你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只速度最快的母牛)。 在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。有时，两个牧场(可能是自我相同的)之间会有超过一条道路相连。至少有一
usaco——Friday
Friday the Thirteenth Is Friday the 13th really an unusual event? That is, does the 13th of the month land on a Friday less often than on any other day of the week? To answer this question, writ
usaco——gift1
Greedy Gift Givers A group of NP (2 ≤ NP ≤ 10) uniquely named friends has decided to exchange gifts of money. Each of these friends might or might not give some money to any or all of the other fr
usaco日记——ride
近几天开始做usaco，希望在此记录一下。同时也希望有人能对我的代码提点儿建议（但愿吧。。。）； Your Ride Is Here It is a well-known fact that behind every good comet is a UFO. These UFOs often come to collect loyal supporters from here on