Ulm Local Contest 1996-2007 总结

题大部分都比较简单，或比较无聊

POJ1780 Code

题意：求一个长度为10^n+n-1的数字串，包含0..10^n-1的每个数的串(不足n位的前面补0)仅一次

算法：Euler Circuit O(10^n)

有点自动机的味道，一个n-1位的数字串作为一个状态的话，状态转移就是末尾加上0..9中的一个数，去掉第一位。每个点的状态转移对应一个数的串，要使每个串出现且仅出现一次，想到欧拉回路。10^n-1个点，每个点连10条边，以(n-1)个0为起点做欧拉回路(注意:会堆栈溢出，欧拉路要用非递归)

POJ2566 Bound Found

题意：已知一列数和一个数t，求这列数的一个子序列(连续)，是这个子序列的和的绝对值最接近t

算法：O(nlogn+n)

求出来所有的前缀和sum[i]，把sum从小到大排序，然后两个指针扫一遍就ok(因为abs(sum[i]-sum[j])==abs(sum[j]-sum[i])，所以...)

POJ2941 Homogeneous Squares

题意：n*n的方格中选n个格子，使这n个两两独立(独立是不同行不同列x1!=x2 && y1!=y2)。每个格子中有一个权值，若所有选法的格子之和都相等，那么这个矩阵就是homogeneous,否则不是，判断一个给出的矩阵是否homogeneous

算法：O(n^2)

原矩阵是homogeneous等价于每个2*2的子矩阵是homogeneous。因为把一种选法任意改变两个数就能得到另一种选法，而和的改变只是那两个格子，这两个格子必然是行列对换的(要不然就和其他的不“独立”了)，所以就是任何能组成正方形的四个点的对角线和相等的话就ok

POJ3370 Halloween treats

题意：已知n个数，从中选出若干个使之和是c(c小于n)的倍数

算法：抽屉原理　O(n)

一个不起眼的条件c小于n是这题的关键。设sum[i]为前缀和，由于c小于n，所以sum[1],sum[2],sum[3]...sum[n] 分别mod c的余数肯定至少有两个相同，比如sum[i]%c==sum[j]%c，那么(sum[j]-sum[i])%c==0，i+1..j这个序列一定符合条件。

有问题请留言或给我发Email