文章列表
英文原题 中文题译
大意：将有理数表示为小数循环数，如：
1/3 = 0.(3)22/5 = 4.41/7 = 0.(142857)2/2 = 1.03/8 = 0.37545/56 = 0.803(571428)
本身很简单，注意小数循环不是靠字符串的比较，而是除到某位时的商和余数比较，如果商和余数相同，则开始重复。不过在做的时候犯了不少错，立此存照：
1.一开始无法在OJ上通过编译，报错itoa找不到，include了stdlib.h之后依然报错，改成_itoa还是报错，无奈上网查了查，原来GNU GCC不支持此函数，必 ...
英文原题 中文题译
大意：牛从迷宫走出来最多需要多少步。迷宫是用字符构造的，可能不止有一个出口，如这个宽5高3的迷宫，有两个出口，最远的格位于左下角，需9步走出。+-+-+-+-+-+| |+-+ +-+ + +| | | |+ +-+-+ + +| | | +-+ +-+-+-+多源最短路径问题。有几点需注意（在程序中体现）：1. 如何处理输入，显然需要整行读入。不过要注意的是，第一行是表示宽度和高度的数字，读入以后，\n依然在io中，此时用第一个fgets读到的是个空行。2. 如何表示格点和墙。一种方式用结构体，不方便。四个方向如何统一表示且统一从输入 ...
英文原题 中文题译
大意：奶牛丢了，农民要找牛。牧场是一块方形区域，其中有障碍物，奶牛每分钟走一格，如不遇到障碍或者到达边界不转向，每次转向费时一分钟，且总顺时针转向。农民也按次策略行动，给定牧场图，奶牛与农民的初始位置，问什么时候能找到牛，或者告知找不到牛。
简单的离散模拟。有几点要说的：
1.在处理输入时候把边界全部处理成障碍，可不用特别判断边界。不过我在这里犯了错，数组设定没做好结果输入越界，浪费了时间，晕。
2.如何判断不能找到牛？农民和奶牛的移动一定会在某时刻重复（相同位置、相同方向），记录重复的周期，在两个周期的最小公倍数范围内如果找不到牛，就永远找不到。看了看标程，很无耻的 ...
英文原题 中文题译
大意：公司之间相互持有股份，如果A有B的51%以上的股份，则控股B，如果A控股B1,....Bk，这些公司和A本身对公司C的股份之和在51%以上，则A也控股C。给定公司间的股份持有率，要求计算公司之间的控股关系。
控股关系看上去很像偏序关系，不过不是。但其类似的传递性吸引人往Watshell算法上去考虑。于是有了第一个版本的程序。注意到一次watshell是不足以计算出控股关系的，需要多次计算。
此题中的陷阱：通常我们会在计算传递关系时将股份直接相加，但在极端情况下，100个公司的数据就足以使得32位整数溢出。这看起来觉得很荒唐，但的确发生了。一个环形控股实例（官方 ...
英文原题 中文题译
大意：在1-9的数字中间加入运算符使得结果为0。
一共最多9个数，顺序固定，因而只有八个中间符号影响结果，每个符号三种可能性（+,-,space），也就是3^8=6561种可能性，不用多想了，直接枚举。
/*
ID: blackco3
TASK: zerosum
LANG: C++
*/
#include <iostream>
using namespace std;
#define _max_ 9
int signals[_max_], n;
char name[3]={' ', '+', '-', };
void zero_su ...
英文原题 中文题译
大意：给定钞票面值，问给定的钱数有多少种付钱方式。
设有m种钞票，每种面值为v[i](0<=i<m)，钱数为n的付钱方式为s[n]，则s[n]=sum_{0<=i<m}{s[n-v[i]]}。这是最简单直接了当的想法。但不对：这样会导致重复计数。重新考虑，事实上我们是在找方程sum_{0<=i<m}{x[i]*v[i]}=n的解的数目，应该对i做规划。显然有sum_{0<=i<m-1}{x[i]*v[i]}=n-x[m-1]*v[m-1]。令DP[j][s]=|{x[i]| sum_{0<=i<j}{x[i] ...
英文原题 中文题译
大意：给定节点数和树的高度，求完全二叉树的个数。
很多磨的一题。思路很清晰，DP也不难，关键在于边界条件处理，以及注意是完全二叉树，这样，左右子树要至少有一个节点或者为叶子节点。从而，偶数节点数的计数必然为0。
本来一个小时之前就还算顺利的做好了，但35,7的时候对，99 15的时候不对，晕了。头痛了半天，打开标程看了看，它计算lower的方式是通过full来做的。想了半天，怀疑自己的lower递归写错，于是按标程的思路重写了一遍。写完，马上骂自己是猪。想想这里的结果是摸P的（结果太大）,P=9901。也就是说，在计算中可能超出整数上限导致出错。而35 7既然对，那 ...
英文原题 中文题译
大意：给定一个单词表和一个字串，找字串的可被给定单词表表示的最长前缀的长度。
之前在POJ上做个一个恢复错排句子的题(POJ3504)，.例如，tihssnetnceemkaesprfecetsesne是一个没空格且被打错了字（除了单词的第一个和最后一个字母外其他字母的顺序有可能被敲错）的句子，可能的单词包括makes,perfect,sense,sentence,this。于是这个句子可以恢复成this sentence makes perfect sense。这题是用hash来计算的，hash函数需设计得与顺序无关。其他的部分，可以用动态规划，也可以用搜索。
用 ...
英文原题 中文题译
相当简单的逐个查找是否满足要求的数，注意题目里说数字是唯一的。
/*
ID: blackco3
TASK: runround
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
int digs[32], n_dig, visited[10];
int is_around( int num ) {
for( n_dig=0; num ; n_dig++ ){
if( (digs[n_dig]=num%10)==0 ...
英文原题 中文题译
题目大意：
一组灯，几个按钮，按一个按钮可以改变若干灯的开关状态。给定按按钮的计数次数和最终状态中若干个灯的状态，要求求出所有可能状态。
每个灯只有两个状态：开/关。每个按钮如果按两次就会恢复原样。因此，按钮计数器C实际上只有最多4次有效。对C>4，枚举每个按钮的开关状态，一共2^4=16个状态，检查是否与目标状态吻合，即可得解。
需要注意之处：枚举按钮动作之后判断是否符合计数器要求用两个条件，一是按键次数二是奇偶性。
调试时发现一个错：memset( lamps, 1, sizeof(int)*n_lamp );试图把lamps初始化为1，但结果是0x01 ...
英文原题 中文题译
题目大意：
给定N，求将集合{i|1<=i<=N}划分为两个元素和相等的子集的方案的个数。如，N=3时，{1,2}{3}共一个解。
1-N的数的和为(N+1)N/2，则如果此数为奇数，一定无解。若为偶数，则一定可构造出解。
如果直接暴力求解，粗略估计搜索空间为(n/2)!，不过可以快速剪枝。关键是从最大的数开始搜，每次增加一个未搜索的最大数，直到得到既定的和，或者超过和则剪枝。例如N=7，(7+1)*7/4=14，即每个集合的和为14。最大数7必然在某个集合中，这个数不用搜索。可从6开始，得1。5开始，得2。4开始，得3，继续搜索得2,1。3开始，就不 ...
英文原题 中文题译
大致题意：统计在古罗马计数法下从1-N出现的字母的个数。
罗马数字表示法至今沿用于表示目录，不过其用于表示大数不大方便。该表示由7个字母构成，分别是：I=1, V=5, X=10, L=50, C=100, D=500, M=1000。由I,II,III,IV,V,VI,VII,VIII,IX表示1-9，由X,XX,XXX,XL,L,LX,LXX,LXXX,XC表示10,20,...90，由C,CC,CCC,CD,D,DC,DCC,DCCC,CM表示100,200,...900，由M,MM,MMM表示1000,2000,3000。
计数有两种主要方式，一种是逐个生成字串 ...
英文原题 中文题译
大致题意：
奶牛需要补充多种维生素，农夫手头有N种药丸，每种可以补充一定维生素，每个药丸每天只能吃一颗，问最少需要多少药丸，且要求输出药丸字典序最小的排列。
经典的0-1背包问题，当然可以非递归回溯，不过这里可以直接递归。需说明的是注意递归的顺序，先选择吃，再选择不吃。如果吃了就行，那么不吃就不用再算了，因为只需要输出字典序最小的，而不吃的情况下继续搜索一者药丸数必定不会减少，二者字典序上升，故可以剪枝。同时注意在这里剪枝时需恢复数据。
/*
ID: blackco3
TASK: holstein
LANG: C++
*/
#include < ...
英文原题 中文题译
大致题意：
给定N、B、D，找N个二进制位数不大于B（即<2^B）的数使得其两两间二进制海明距离至少为D，要求输出最小的序列，每十个数一行。
样例输入N=16,B=7,D=3
输出的二进制分析：
0000000 : 0 111 ...
英文原题 中文题译
题目大意是：给定一个由数字123构成的数列，最少多少次交换可以使得其变成升序序列。
以前做过POJ上的USACO题中有类似的，大意是给定123的序列，不交换，但可改变数字的值，问至少要改变多少个值使得整个序列有序。比这个略难些。对此题，扫描整个数列，得到每个数字区间的位置，考虑到首先所有的在23区间的1必须交换回1区间，然后考虑这样的交换会导致多少3跑到区间2中。注意n_i_j中存在一些等式，所以计算不难。
可将此题推广，在长为N的序列中有M个数，最少多少交换可使得序列变成升序。这样，第一部分基本不变，需要N×M的数组来记录数字位置，如果N×M很大，则可以两次扫描， ...