文章列表
Factorial
这个题目已经做过N多遍了，在各大OJ上都有。
题目大意：给定一个正整数n,求n!未尾有多少个0。
算法分析：我们很容易发现阶乘未尾的0是由5产生的，即n!中有多少个5就有多少个0。从而问题就转化为求n!中分解质因数后5的系数。我们对其进行分类计数，首先求是5的倍数的数多少个，然后再求25的倍数，再求125的倍数，…………，直到为0。最后把这些数全部加起来即为答案。为什么可以这样呢？比如求25的倍数时5不是每一个都出现了两次却只计数一次吗？非也！我们在求5的倍数时已经给25的倍数计数过一次，同理求5的倍数和求25的倍数时也给125的倍数计数过一次…… ...
The Next Palindrome
题目：A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palind ...
SPOJ Prime Generator
题目意思：给定两个正整数m,n,(1<=m<=n<=10^9,n-m<=100000),求m到n之间的所有素数。
方法1:对区间[m,n]内的每一个数进行miller_rabin素数测试(时间复杂度较高,约为1.37s~4.6s)
代码实现所需的算法有：
① 产生[0,1]及[0,m-1]之间的随机数函数Random(),Random(m)
② 手写乘法取模函数mul_mod()
③ 二分求幂a^b%n函数pow_mod(a,b,n)
④ Miller_rabin素数测试算法
#include < ...
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, write a program that will compute the frequency that the 13th of each month lands on Sunday, Monday, Tuesday ...
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 friends. Likewise, each friend might or might not receive money from any or all of the other friends. Your ...
此题很水，只是第一次看到这个题目的时候有点弄不懂题意，试了一下，才发现只要遇到42就停止输入，而不是继续读入而不处理。
1. Life, the Universe, and Everything
Problem code: TEST
Your program is to use the brute-force approach in order to find the Answer to Life, the Universe, and Everything. More precisely... rewrite small numbers from input to output. Stop ...
http://en.wikipedia.org/wiki/Baby-step_giant-step
我想证明的公式是：
Ax≡A(x%phi(C)+phi(C)) (mod C) (x>=phi(C))
其中phi(C)是指C的欧拉函数值,A,C,x均是正整数
首先引入欧拉定理：对于任意的整数n>1,若gcd(a,n)=1,则
aphi(n)≡1(mod n)
由欧拉定理、鸽巢定理以及a0≡1(mod n),知ax%n是一个周 ...
今天是我第一次在USACO上做题，虽然这是一个很简单很简单的题目，但是这个传说中USA培养参加IOI参赛选手的OJ，不仅让我有点向往啊。 这个OJ挺让人喜欢的。我很少自己认认真真的想题，也不少的OJ上都只是过过场，最近看 ...
1.当a,b,c都很小的时（如a,b,c<1000000），可以直接暴力枚举。
int res=1;
for(int i=1;i<=b;i++)
{
res=res*a%c;
}
cout<<res<<endl;
2.当a,b,c都较大时（如a,b,c<2000000000）,可以使用反复平方法法求幂。
B=x0*20+x1*21+x2*22+x3*23+……+xn*2n
AB=A^( x0*20+x1*21+x2*22+x3*23+……+xn*2n) , xi∈{0,1}
resi= A^( x0*20+x1*21+x ...
题目来源：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=116&problem=1338&mosmsg=Submission+received+with+ID+8905555
题目大意：见代码
题目分析：见代码
//Uva 10397 - Connect the Campus
//给定一些点及一些边，通过添加最少长度的线段使之所有点均连通
//并查集的应用
//先求出各连通分量
//再求出各个连通 ...
Corn Fields
题目来源：http://poj.org/problem?id=3254
题目大意：一个人买了一个N*M个方格组成的农场，有部分方格不能种植。现在需要种草给牛吃，而牛又不喜欢挨着吃（don’t share an edge–>两个方格无公共边），不种草也算一种方案，求种植方案数。
此题与Mondriaan's Dream 类似，就不多讲了。
#include <iostream>
#include <memory.h>
#define MOD 100000000
using namespace std;
const int ...
题目大意：在一个矩阵puzzle中寻找字典中的单词，输出单词的起始位置和方向；
使用trie树，叶子节点中记录方向和起始坐标，通过对每个puzzle中的字母为起始位置进行bfs即可。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
char puzzle[1050][1050];
struct node
{
...
Mondriaan's Dream
题目来源：http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=10710&courseid=38
题目大意：给一个h*w（1<=h,w<=11）的矩形，用1*2的小矩形去完全覆盖此大矩形且不能重叠，问一共有多少种覆盖方法？
题目分析： ...
HDU-1251-统计难题
- 博客分类：
- Data Structure
trie树的最基本题型，题目是要统计在一个字典中，有多少匹配指定前缀的单词，因为trie树是一棵前缀树，所以对于trie树的每个节点在插入时只要经过这个节点便对这个计数变量加一，最后按照trie查询进行统计；返回统计量即可。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct node
{
int num;
bool f;
int next[26];
void init(){num=0; ...