博文
Zoj 1222 Just the Facts(2007-03-02 22:54:00)
摘要：这是标准的数学题。求N!的非零末位。
这也是标准的BT题，光是N就可以到100位。完全没有直接做的办法。还是看LeeMars的报告吧!
首先考虑某一个N!(N < 10)，我们先将所有5的倍数提出来，用1代替原来5的倍数的位置。由于5的倍数全被提走了，所以这样就不会出现尾数0了。我们先把0..9的阶乘的尾数列出来（注意，5的倍数的位置上是1），可以得到table[0..9] = (1, 1, 2, 6, 4, 4, 4, 8, 4, 6)。对于N < 5，直接输出table[N]即可；对于N > = 5，由于提出了一个5，因此需要一个2与之配成10，即将尾数除以2。注意到除了0 !和1!，阶乘的最后一个非零数字必为偶数（显然，因为在N!的质因数里2的个数要多），所以有一个很特别的除法规律：2 / 2 = 6，4 / 2 = 2，6 / 2 = 8，8 / 2 = 4。比较特殊的就是2 / 2 = 12 / 2 = 6， 6 / 2 = 16 / 2 = 8。这样我们就可以得到如下式子：
代码:
table[N]
F(N) = ------------ (0 <= N < 10)
2^([N/5])
再考虑复杂的。考虑某一个N!(N >= 10)，我们先将所有5的倍数提出来，用1代替原来5的倍数的位置。由于5的倍数全被提走了，所以这样就不会出现尾数0了。我们观察一下剩下的数的乘积的尾数，通过table表，我们发现这10个数的乘积的尾数是6，6 * 6的尾数还是6，因此我们将剩下的数每10个分成一组，则剩下的数的乘积的尾数只与最后一组的情况有关，即与N的最后一位数字有关。由于我们把5的倍数提出来了，N!中一次可以提出[N/5]个5的倍数，有多少个5，就需要有多少个2与之配成10，所以有多少个5，最后就要除以多少个2。注意到除2的结果变化是4个一循环，因此如果有A个5，只需要除(A MOD 4)次2就可以了。A MOD......
Zju 2759 Perfect Weighing Skill Ⅱ(2006-10-01 22:31:00)
摘要：
2087262
2006-10-01 22:05:43
Accepted
2759
C++
00:00.10
392K
Sirius.D
这题原来如此简单````根本用不到搜索,更谈不上剪枝..可在那时,却害的我肝肠寸断,为伊消得人憔悴.....可叹一位如花似玉的少年,就这样被zoj的Monthly吓的花容失色,颤抖抖,惊颤颤...
(正色道)此题(参见前文)只需把数改成三进制,不断的「借位」进位即可.
如6,即为2,0 == 1,-1,0;
35,即是1,0,2,2 == 1,1,0,-1;
如此这般,这般如此,1处取加,-1处取减,可爱的ac就在你的眼前.
#include <cstdio>
#include <string>
int b[19], n, l;
void pt()
{
int af = 0, bf = 0, i, x = 1;
for(i = 0; i <= l; i ++)
{
if(b[i] == -1)
{
af = 1;
if(bf)
printf(" ");
printf("%d", x);
bf = 1;
}
x *= 3;
}
if(!af)
printf("-1");
printf("\n");
af = 0, bf = 0, x = 1;
for(i = 0; i <= l; i ++)
{
......
Zju 1084 Channel Allocation(2006-08-29 20:12:00)
摘要：顶点着色的贪婪算法证明是存在的，即当前的算法得到只是给出最少颜色的一个上界。
算法描述：设G是一个图，它的顶点按某一顺序记为x1，x2,......xn.
(1) 对顶点x1指定颜色1。
(2)对每个i=2，3，....n,令p是在顶点x1,x2,...xi-1与xi相邻接的顶点中没有任何一个顶点着色p的最小的颜色，并且xi指定颜色p。
数学书上的定理为：设G是一个图，对于该图顶点的最大度为△，那么贪婪算法X产生G的顶点的一个（△+1）着色，因此 X（G）<=△+1
#include <cstdio>
#include <string>
int a[26][26], n, m, ans, c[26], b[26];
char s[26];
void greedy()
{
int i, k;
for(i = 0; i < n; i ++)
{
memset(b, 0, sizeof(b));
for(k = 0; k < n; k ++)
{
if(a[i][k] && c[k] != -1)
{
b[c[k]] = 1;
}
}
for(k = 0; k <= i; k ++)
{
if(!b[k]) break;
}
c[i] = k;
}
for(i = 0; i < n; i ++)
{
if(ans < c[i])
ans = c[i];
}
ans ++......
Zju 1619 Present(2006-08-08 22:40:00)
摘要：
2009974
2006-08-08 22:21:50
Accepted
1619
C++
00:00.02
392K
St.Crux
首先要知道什么是错排。
清楚了以后这个题就是弱题。即求：
C（n，m）——n个数里取m个的组合数 × 剩下的（n－m）个数的错排数
注意n＝＝m的情况
#include <cstdio>
int m, n;
double a[101];
int main()
{
//freopen("in.txt", "r", stdin);
a[1] = 0, a[2] = 1;
int i;
for(i = 3; i < 101; i ++)
{
a[i] = (i - 1) * (a[i - 1] + a[i - 2]);
}
while(scanf("%d %d", &n, &m) != EOF)
{
double pb = 1;
if(n == m)
{
//pb *= a[n];
for(i = 1; i <= n; i ++)
{
pb /= double(i);
}
}
else
{
pb *= a[n - m];
for(i = 1; i <= m; i ++)
{
pb /= double(i);
}
f......