文章列表
英文原题 中文题译
大意：在棋盘上方若干个骑士和一个国王，要让他们汇聚到一个格子上，其中骑士带上国王走这样国王上马之后不计代价。问，汇集他们的最小代价是多少步。（骑士走马步，国王走任意一相邻格）。
国 ...
英文原题 中文题译
大意：农场之间有路构成稀疏无向图，若干奶牛分散在不同农场，要让奶牛到某个农场集合，如何代价最小。
稀疏图上求到所有点对的最短路径，用Bellman Ford算法的队列实现(SPFA)，其思想是：开始时队列中只有源节点，不断取出队列中的首节点，并对其相邻节点检查是否可用该节点更新其距离，若可，且相邻节点不在队中，则将其入队。这和宽度优先搜索很像，所不同的是每个节点可以多次入队。
在求得最短路径之后计算集合的代价取最小值即可。
/*
ID: blackco3
TASK: butter
LANG: C++
*/
#include <iostream& ...
英文原题 中文题译
大意：有人发明了一种有8个块三种变换方式的平面魔方，给定初始和目标状态，要求求出最少需要的变换的数量并给出具体的变换方式。
每个状态是1-8的一个全排列，状态空间为8!，可以用康托展开得到排列的字典序列数，从而用8!的状态空间来存储访问标记和跟踪标记。
我在这里用了另一种方式，每个状态用8×3＝24位表示（3位表示0-7），可放在一个整数内。注意到这7个数的位置就可以确定8个数的全排列，因而1<<21个标记可以顺序的表示所有状态，每个标记为U/A/B/C分别表示未访问、从变换A/B/C得到，需2位，从而1<<18个整数的数组可以表示整个状态空 ...
英文原题 中文题译
大意：给出整数a[i][j]和b[i]，i,j=1,2,3，有X={x[i]|i=1,2,3,s.t 存在y,对j=1,2,3 x[1]*a[1][j]+ x[3]*a[2][j]+ x[3]*a[3][j]=y*b[j]}，找出X中使x[i]最小的和。举例说明，三组整数为(1:2:3),(3:7:1),( 2:1:2)，目标为(3:4:5)，则8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5)。没有比8+1+5更小的了。
数据限制条件：a[i][j],b[i],x[i]均为小于100的整数。
...
英文原题 中文题译
大意：有五个纺车飞轮，每个都有最多五个缺口，飞轮转速恒定，有缺口对齐（飞梭可以跑）的最小时刻。
数据限制：全是整数，输出也是整数。
不用考虑真正的模拟，在小数时刻有缺口对齐的情况，只需考虑0-360秒下0-360度每个度是否是缺口。
这是我写的第二个版本。第一个版本试图模拟缺口，WA后发现描述中缺口可以大于180度，这样，一个缺口与另一个缺口的交可能是两个缺口，需考虑的情况过于复杂，想想，这肯定不是需要找的答案，就放弃先。唉。又一次。
ＰＳ:考虑一下不离散的情况，如何处理？
/*
ID: blackco3
TASK: spin
LANG: C++
...
英文原题 中文题译
大意：求至多有L个1的第i个N位二进制数（1<=L<=N<=31)。
举个例子：N=5,L=3,i=19，则为10011。考虑小于10000的(4位数)中至多3个1的有c(4,0)+c(4,1)+c(4,2)+c(4,3)=15个，大于等于10000小于10010的2个，大于等于10010小于10011的一个，则10011为所求。
从这个分析中可以看到这是个组合问题，tri[i][j]为在i位数中有j个位为1的数值的个数即c(i,j)，可以通过杨辉三角求得，然后计算得tri_sum[i][j]为在i位数中至多有j位为1的数值的个数。给定N,L,i, ...
英文原题 中文题译
大意：找N!的第一个非0位的值。
一个字：水。
/*
ID: blackco3
TASK: fact4
LANG: C++
*/
#include <iostream>
using namespace std;
int main() {
freopen("fact4.in", "r", stdin);
freopen("fact4.out", "w", stdout);
int n;
cin >> n ;
int r ...
英文原题 中文题译
大意：在长01串中找长度在A,B之间的子串的重复次数，按顺序输出最大的N个重复次数，且输出相应的子串，要求相同的子串按二进制大小排列输出（每行6个）。
数据限制：1 <= A <= B <= 12，1 <= N < 50，字符串最大长度200，000
例子：
2 4 2
01010010010001000111101100001010011001111000010010011110010000000
输出：
23
00
15
01 10
表示，00出现23次最多，其次01,10各出现15次。
很显然用tries来做是最合适的，长度最 ...
英文原题 中文题译
大意：在一张白色大纸上放若干个不透明的矩形纸片，每个纸片有一种颜色（可以是白色），这样，有重叠的话，后放的纸片的颜色覆盖了之前的颜色。问最后每种颜色占多大面积。
数据限制条件：底板长宽N<=10000，纸条数量K<=1000，颜色数C<=2500，所有数值都是整数。纸条的边界与底板边界均平行。
最粗暴的设想，设一个底板大小的二维数组，来一张纸条，把相应区域的颜色都改变。不过，显然这是不可接受的：空间O(N^2)，时间O(K*N^2)。
纸条的边界与底板边界均平行，使得可以用离散化，这样，区间的数量不是N^2，而是(2K)^2。暴力算法的时间复杂度 ...
英文原题 中文题译
大意：给定若干个邮票面值和最大可用的邮票数，计算从1开始可连续表达的面值的最大值。如，面值1，3的两种邮票，最多5张邮票，可连续表示1-13的面值，而无法贴出面值14来。
设min_stamp[i]为在给定k种邮票面值v[j],0<=j<k下所需要用的最小邮票数，min_stamp[0]=0为初始值，min_stamp[i]=min(min_stamp[i-v[j]]+1),0<=j<k。计算得第一个超过可用邮票数的i，取i-1即为所求。
需注意的两点：可表示的最大面值为最大邮票面值*给定邮票数。初始给出的邮票没排序。
/*
ID: ...
英文原题 中文题译
大意：给定若干素数p1,..pk，找第N个素因子全为这些已知素数的合数。
又是一开始定错了方向，开始了整晚的折磨。唉。最后，完整的过了。
一上来，分析算法时就确定用优先队列找已有的最小的数，把接下来的乘积放如队列中。接着噩梦开始了。马上发现，数可能重复，而优先队列中无法排除重复数，于是想自己写一个可以清除重复数的优先队列，结果发现写不出来。倒是写了个二项堆模板。
无奈之下，用set来记录已经插入的数。依然错，发现输出的是负数，显然是整数越界。弄了很久才想起来long long next=cur*primes[i];之后判断next是否越界是无效的，必须先转换类型（ ...
英文原题 中文题译
简单的0-1背包问题。与装箱问题不同，后者是NP-hard的。
/*
ID: blackco3
TASK: inflate
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
#define _max_time_ 10001
int main() {
freopen("inflate.in", "r", stdin);
freopen("inflate.out&quo ...
英文原题 中文题译
最原始和经典的最小生成树，用了个最土最简单的办法做，编译了直接提交通过。
/*
ID: blackco3
TASK: agrinet
LANG: C++
*/
#include <iostream>
using namespace std;
#define _max_farm_ 100
int n_farm, dist[_max_farm_][_max_farm_], is_conn[_max_farm_];
int main() {
freopen("agrinet.in", "r", ...
英文原题 中文题译
大意：在平面上有N个点，若干条直线边连接其中部分点，使得其构成至少两个连通片。现要增加一条连接两个不同连通片的边，使得新的连图片的周长最小。
最初的想法如下：
－－－－－－－－－－－－ ...
英文原题 中文题译
加权图上的单源最短路径。本身是最简单的。题目加了一些限制，如，节点从a-z,A-Z编号，最后只输出大写编号的节点到Z节点的最短路径中最短的一个。
走了不少弯路，一开始想用邻接表做，后来一想，整个节点最多52个，应该用最简单的矩阵表示。Dijstraka算法也是用最简单的n^2实现，没有用优先队列来选取最小元素。在节点数大的时候，还是用优先队列实现合适。
/*
ID: blackco3
TASK: comehome
LANG: C++
*/
#include <iostream>
#include <memory.h>
usi ...