距阵的乘法，关键是要熟悉距阵乘法的结合率，可以用N*LOGN的算法过。
 #include <stdio.h>
typedef struct
   {
 int a11, a12;
int a21, a22;
 }type;
void Mul ( type *a, type *b, type *c )//a*b->c
{
c->a11 = ( a->a11*b->a11 + a->a12*b->a21 ) % 10000;
c->a12 = ( a->a11*b->a12 + a->a12*b->a22 ) % 10000;
c->a21 = ( a->a21*b->a11 + a->a22*b->a21 ) % 10000;
c->a22 = ( a->a21*b->a12 + a->a22*b->a22 ) % 10000;
}
void Cpy ( type *a, type *b )//a=b
{
a->a11 = b->a11;
a->a12 = b->a12;
a->a21 = b->a21;
a->a22 = b->a22;
}
type sum, count, temp, t;
type e = { 1, 0, 0, 1 };
type s = { 1, 1, 1, 0 };
int main ()
{
int n;
while ( scanf ( "%d", &n ) != EOF && n >= 0 )
  {
if ( n == 0 )
{
printf ( "0\n" );
continue;
 }
if ( n == 1 )
{
printf ( "1\n" );
continue;
}
n = n-2;
Cpy ( &sum, &e );
Cpy ( &count, &s );
while ( n )
{
if ( n & 1 )
{
Mul ( &sum, &count, &temp );
Cpy ( &sum, &temp );
}
n >>= 1;
Cpy ( &t, &count );
Mul ( &count, &t, &temp );
Cpy ( &count, &temp );
}
printf ( "%d\n", ( sum.a11 + sum.a12 ) % 10000 );
}
return 0;
}
用二维的树状数组做的，但是速度很慢，不知道对不对。
#include <stdio.h>
const int LEN = 1005;
__int64 tree[LEN][LEN]; //记录区间里面的线段数目
void init_t ( int n, int m )
{
for ( int i=1; i<=n; i++ )
for ( int j=1; j<=m; j++ )
tree[i][j] = 0;
}
inline int cupk ( int a )
{
return a&(-a);
}
inline void add ( int n, int m, int i, int j, int num )
{
for ( int ii=i; ii<n; ii+=cupk ( ii ) )
for ( int jj=j; jj<m; jj+=cupk ( jj ) )
tree[ii][jj] += num;
}
inline __int64 ser ( int i, int j )
{
int sum = 0;
for ( int ii=i; ii>=1; ii-=cupk ( ii ) )
for ( int jj=j; jj>=1; jj-=cupk ( jj ) )
sum += tree[ii][jj];
return sum;
}
int main ()
{
int t;
scanf ( "%d", &t );
for ( int c=1; c<t+1; c++ )
{
int n, m, k;
scanf ( "%d%d%d", &n, &m, &k );
init_t ( n, m );
__int64 ans = 0;
for ( int i=0; i<k; i++ )
{
int a, b;
scanf ( "%d%d", &a, &b );
__int64 k = 0;
if ( a>1&&b<m )
k += ser ( a-1, m )-ser ( a-1, b );
if ( a<n&&b>1 )
k += ser ( n, b-1 )-ser ( a, b-1 );
ans += k;
add ( n+1, m+1, a, b, 1 );
}
printf ( "Test case %d: %I64d\n", c, ans );
}
return 0;
}
线性的算法，记录最近的分数，最后约分。
#include <stdio.h>
int gdc(int a, int b)
{
if (a==0)
{
return b;
}
if (b==0)
{
return a;
}
return gdc(b, a%b);
}
int main()
{
int n, d;
int i;
double min;
int mn, md;
int men, med;
double minest;
int temp;
int pub;
double t1, t2;
while (scanf("%d%d", &n, &d) != EOF)
{
minest = 1;
pub = gdc(n, d);
n = n/pub;
d = d/pub;
for (i=1; i<=32767; i++)
{
min = 1;
temp = (int)((double)i * (double)n / (double)d);
pub = gdc(i, temp);
if (temp/pub!=n || i/pub!=d)
{
if ((double)n/(double)d-(double)temp/(double)i < (double)(temp+1)/(double)i-(double)n/(double)d)
{
min = (double)temp/(double)i;
mn = temp;
md = i;
}
else
{
min = (double)(temp+1)/(double)i;
mn = temp+1;
md = i;
}
}
t1 = min-(double)n/(double)d>0 ? min-(double)n/(double)d:(double)n/(double)d-min;
t2 = minest-(double)n/(double)d>0 ? minest-(double)n/(double)d:(double)n/(double)d-minest;
if (t1<t2)
{
minest = min;
men = mn;
med = md;
}
}
pub = gdc(men, med);
printf("%d %d\n", men/pub, med/pub);
}
return 0;
}
摘要: 题目看着向生成树，但实际上是最短路径+堆优化。
#include <stdio.h>const int LEN = 50005;const __int64 MAX = 0x7fffffffffffffff; struct HEAD{ &nbs... 阅读全文
摘要: 素数的入门题目，素数表+线性查找，OK！
#include<iostream.h>long data[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,1... 阅读全文
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 30 | 31 | 1 | 2 | 3 | 4 | 5 | | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | 13 | 14 | 15 | 16 | 17 | 18 | 19 | | 20 | 21 | 22 | 23 | 24 | 25 | 26 | | 27 | 28 | 29 | 30 | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|