文章列表
英文原题 中文题译
大意：
这题题意比较绕口，读懂了题目，就差不多了。干脆把中文翻译的放上来吧。
秀·谢夫（小奶牛）在花花公子杂志上中了大奖，于是她从农村搬到了城郊的一座别墅中。可是她还常常怀念乡 ...
英文原题 中文题译
大意：
有N个工件，每个工件要经过两道工序A,B，有若干台机器分别可用于A,B工序（不重合），每台机器有各自的加工时间。问最少何时A工序全部完成，最少何时B工序全部完成。
分析与实现
只有两道工序，很简单。分别计算A,B机器完成N个工件需要的时间，A工序的即为所求。对B工序，为使得总的最大时间最小，应该把A先加工出来的工件给B中加工最久的，这样依次统计B的完成时间。
工件加工的一般情况没这么简单，工序增加，或工件在每台机器上的加工时间是不同的（形成一个加工时间矩阵），都会使问题变得复杂。
/*
ID: blackco3
TASK: ...
郁闷。不小心覆盖了重写的。
英文原题 中文题译
最原始经典的网络流最大流问题，本身没什么好说的。网上关于网络流和算法的小blog不少，良莠不齐，这里推荐一篇辉夜的blog，里面有各个算法的大致介绍和简单评测。 ...
英文原题 中文题译
大意：
奶牛对牛栏有各自的喜好，一个奶牛进一个牛栏，一个牛栏只能放一只奶牛，问最多能放多少奶牛。
分析与实现：
最典型的二分图最大匹配问题。毫无疑问，用匈牙利算法。算法本身很 ...
英文原题 中文题译
大意：
奶牛们要从农场逃跑，约定了一组密码通讯系统：在字符串中插入COW，并将CO与OW之间的字符交换，例如：
aabbccdc变成aaCccObbWdd。奶牛会在同一字串上多次运用该方法加密以提高解密难度。现知原始字符串为 Begin the Escape execution at the Break of Dawn ，给定一个字符串，问是否是由该原始串加密而成，如果是，给出加密的次数。
分析与实现
看起来简单，其实不好做。一开始可以过滤掉一些明显不是的字符串，例如，字串每加密一次增加3个字符，除了加密的COW字符外，其余字符应与原始字符一 ...
英文原题 中文题译
大意：
给定N个正整数，确定由其加法不能表示的正整数的最大值。例如给若干个邮票面值，问最大不能被这些邮票组合出来的面值是多少。如果没有这样的最大值，则输出0 。
分析与实现：
看上去很面熟是吧，不过与之前的有所不同。
首先，怎样的面值组合没有最大不可表示的值？例如2,4，所有的奇数都不能表示，6,9，所有不能被3整除的都不能表示。于是规律是：N个数的最大公约数如果是1，那么一定存在这样的最大值，否则，不可表示的值可以无限大。
如果这样的最大值存在，怎么找？很简单，设其最小面值为k，那么如存在n使得n,n+1,...n+k-1都 ...
英文原题
大意：
农夫布朗的牧场上的篱笆已经失去控制了。它们分成了1~200英尺长的线段。只有在线段的端点处才能连接两个线段，有时给定的一个端点上会有两个以上的篱笆。结果篱笆形成了一张网分割了布朗的牧场。布朗想将牧场恢复原样，出于这个考虑，他首先得知道牧场上哪一块区域的周长最小。
布朗将他的每段篱笆从1到N进行了标号（N=线段的总数）。他知道每段篱笆的有如下属性：
该段篱笆的长度
该段篱笆的一端所连接的另一段篱笆的标号
该段篱笆的另一端所连接的另一段篱笆的标号
幸运的是，没有篱笆连接它自身。对于一组有关篱笆如何分割牧场的数据，写一个程序来计算出所有分割出 ...
英文原题
题意
一个闭合的栅栏是平面上的一些不相交的首尾相连的线段形成的多边形，有N个角(顶点) (3 < N < 200)。 顶点不重合，它以逆时针方式以数组{xi, yi}给出(i=1,2,...,N)。每一对相邻的顶点都是一条栅栏。因此共有N条 ...
英文原题
大意：有一个由最多26个大写字母构成的二叉树，如：
C / \ / \ B G / \ / A D H / \ E F
已知其前序遍历和中序遍历的结果，求其后序遍历。例如上面的树：
中序遍历串：ABEDFCHG
前序遍历串：CBADEFGH
计算得中序遍历串：AEFDBHGC
相当简单的一题：中序遍历串的第 ...
英文原题
大意：有S首歌，要放到D个CD里。每首歌有一个序号，每个CD有个序号，如果歌曲序号I放在CD（序号J）中，那么序号大于J的CD中不允许有序号小于I的歌曲。每个歌曲有个长度，CD可容纳的歌曲的长度相同并给定，每张CD中放的歌曲的总长度不能超过CD的容量T。求最多能放下多少首歌。
看看数据限制，S<=20, T<=20, D<=20，显然可以用简单的动态规划：best(s,t,d)表示序号s及之后的歌曲要放入最后d张CD中，其中序号最大的CD剩余的容量为t，其余CD剩余容量为T（初始容量）。那么，只有三种可能情况：
1.放弃歌曲s，那么s不能出现在之后的CD中，得 ...
英文原题
大意：给定一个三角形(0,0),(m,n),(p,0)求三角形内部的整数格点的数量。
可以用皮克定理求解：给定任意简单多边形，其面积A和内部格点数目i、边上格点数目b的关系：A = i + b/2 - 1。 而线段<(0,0),(n,m)>上的格点数(包含端点）等于n与m的最大公约数+1，从而对多边形而言，边上的格点数总和为边向量的xy分量最大公约数之和（去掉重复计数）。多边形面积为点积和。从而得解。
这里的实现包含了对一般简单多边形的处理。
对这个题而言，还可以参考图形学中的划线算法，对每行得到内部格点的最大最小值，求和得到解。
有意思的是，中文题译与英文原 ...
英文原题
中文题译
经典的求欧拉路径：给定最多两个奇数度顶点的连通图（保证有欧拉回路），要求出欧拉路径使得每条边均访问到且只访问一次。附加条件：在所有可能欧拉回路中求按访问的节点序号的字典序最小的一个。
求欧拉回路最快的线性时间算法是这样的：从任意一个节点出发，每访问一个节点，就将其入栈，并删除所访问的边，如果到达一个没有边的顶点，则将栈顶元素出栈并输出之。
要在常数时间内删除边，邻接表中就不能存邻接节点，而需存对边的引用（可以是指针，或者是索引），这里用的是指针。从而在一个顶点将某边删除之后另一顶点可常数时间判断出来。
由欧拉回路算法求欧拉路径，只需从两个奇数度顶点之一出发即可 ...
英文原题
中文题译
这是个与日常生活相关的题。商场促销，把许多商品捆绑销售并优惠价格，一个精明的先生拿着老婆给的购物清单来买东西，他准备给自己存点私房钱，所以，他不打算为省钱买不需要的东西（如果是女士来，就会这样），为此他扫描了一遍所有的优惠活动，决定按最优方式来购买以节省最多的钱。
数据限制条件：商品种类最多999项，优惠活动最多999项，每项最多捆绑５件商品，优惠价总是比原价总和便宜。先生要买的物品最多５种，每种最多５件。
分析：虽然商品种类最多999项，但既然先生不准备买多余的东西，可认为只有最多5项，凡是优惠条目中包含不需要的商品的一律忽略。这是预处理过程，不妨设要买的商品就 ...
英文原题
有如下一个双人游戏:N(2 <= N <= 100)个正整数的序列放在一个游戏平台上，两人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。
编一个执行最优策略的程序，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为两位玩家执行最优策略。
sample input ：
6
4 7 2 9 5 2
sample output :
18 11
解释：
下面是按最优策略取值的步骤：
A 2
B 5
A 9
B 2
A 7
B 4
这是个双人博弈问题。博弈的最优策略是使对方获利最小的情况下 ...
英文原题 中文题译
大意：给定一个01矩阵，计算其中全为１的方形子块的个数并按方块的边长计数分别输出。
矩阵大小不超过250，The simple the best，直接枚举。
1.首先读入矩阵后将数值取反，这样，在判断矩阵内是否有0变成判断是否有1，只需判断其元素和是否为即可，不需计算矩阵面积。
2.计数sum[i][j]为(1,1)到(i,j)的矩形区域内的元素之和，用递推式计算。注意这里我用了1..n_size作为坐标，而不是通常的0..(nsize-1)，这样可以避免计算中判断ir-1,ic-1是否小于0。不过别忘了在初始化也要这样。
3.从每个ir,ic坐标开始往下生成方块，并 ...