2010年5月12日

网络编程小例

     摘要: //server.c  1#include <stdlib.h> 2#include <stdio.h> 3#include <errno.h> 4#include <string.h> 5#include <unistd.h> ...  阅读全文
posted @ 2010-05-12 10:01 zhongguoa 阅读(318) | 评论 (0)编辑 收藏
2008年12月2日

连堆都不会用

心烦
posted @ 2008-12-02 08:12 zhongguoa 阅读(241) | 评论 (0)编辑 收藏
2008年8月28日

旋转卡壳

转得老子的脑壳子都卡住了
posted @ 2008-08-28 05:57 zhongguoa 阅读(532) | 评论 (0)编辑 收藏
2008年7月30日

终于明白了凸包

明天再看看具体的代码怎么写
posted @ 2008-07-30 02:35 zhongguoa 阅读(322) | 评论 (1)编辑 收藏
2008年5月10日

pku1032关于数论的一个结论

把自然数N分解成若干个互不相同的正整数,使乘积最大;

由于这种分解的数目是有限的,所以最大积存在;

假设最大积的分解为

n=a1+a2+a3+...+a[t-2]+a[t-1]+a[t]

(a1<a2<a3<...<a[t-2]<a[t-1]<a[t])

Now, from the five rules above, we could make the mutiple maximum.

to an N, find the integer k, fits

A=2+3+4+...+(k-1)+k <= N < A+(k+1)=B

Suppose N = A + p, (0 <= p < k+1)

1) p=0, then answer is Set A

2) 1<=p<=k-1 then answer is Set B - { k+1-p }

3) p=k, then answer is Set A - {2} + {k+2}
posted @ 2008-05-10 13:45 zhongguoa 阅读(445) | 评论 (0)编辑 收藏
2008年5月8日

itoa

功 能: 把一整数转换为字符串
用 法: char *itoa(int value, char *string, int radix);
详细解释:itoa是英文integer to string a(将整形数转化为一个字符串,并将值保存在a中)
的缩写.其中value为要转化的整数, radix是基数的意思,即先将value转化为几进制的数,之后在保存在a 中.
作用:实现数制之间的转化
比较:ltoa,其中l是long integer(长整形数)
备注:该函数的头文件是"stdlib.h"        
程序例:
#include <stdlib.h>
#include <stdio.h>
int main(){
    int number = 123456;
    char string[25];
    itoa(number, string, 10);
    printf("integer = %d string = %s\n", number, string);
    return 0;   
}
posted @ 2008-05-08 20:48 zhongguoa 阅读(1118) | 评论 (0)编辑 收藏
2008年4月10日

并查集的模板



#include<iostream>
using namespace std;

int pre[110],rank[110],n;
int find(int x){
    
int r=x;
    
while(pre[r]!=-1)
        r
=pre[r];
    
while(x!=r){
        
int q=pre[x];
        pre[x]
=r;
        x
=q;
    }

    
return r;
}

void unionone(int a,int b){
    
int t1=find(a);
    
int t2=find(b);
    
if(rank[t1]>rank[t2])
        pre[t2]
=t1;
    
else
        pre[t1]
=t2;
    
if(rank[t1]==rank[t2])
        rank[t2]
++;
    n
--;
}

int main(){
    
int m,i,begin,end;
    
while(1){
        scanf(
"%d""%d",&n,&m);
        
if(n==0&&m==0)
            
break;
        
for(i=0;i<=n;i++){
            rank[i]
=0;
            pre[i]
=-1;
        }

        
for(i=0;i<m;i++){
            scanf(
"%d""%d",&begin,&end);
            
if(find(begin)!=find(end))
                unionone(begin,end);
        }

        printf(
"%d\n",n-1);
    }

    
return 0;
}

posted @ 2008-04-10 23:28 zhongguoa 阅读(295) | 评论 (0)编辑 收藏
2008年4月9日

归并求逆序数模板,pku 2299 Ultra-QuickSort,注意long long

#include <stdio.h>
#define MAXN 500000

int height[MAXN+1],temp[MAXN+1];
__int64 sum;

void merge(int *a,int l,int mid,int r) {
    
int i,j,k;
    i
=0,j=l,k=mid;
    
while(j<mid &&<r)    {
        
if(a[j]>a[k]) {
            sum 
+= mid-j;
            temp[i
++= a[k++];
        }

        
else temp[i++= a[j++];
    }

    
while(j<mid)        
        temp[i
++= a[j++];
    
while(k<r)            
        temp[i
++= a[k++];
    
for(i=0; i<r-l; i++) a[l+i] = temp[i];
}

void divide(int *a,int l,int r) {
    
if(l+1<r) {
        
int mid = (l+r)>>1;
        divide(a,l,mid);
        divide(a,mid,r);
        merge(a,l,mid,r);
    }

}


int main() {
    
int n,i;
    
while(scanf("%d",&n)&&n) {
        
for(i=sum=0; i<n; i++) scanf("%d",&height[i]);
        divide(height,
0,n);
        printf(
"%I64d\n",sum);
    }

}
posted @ 2008-04-09 12:54 zhongguoa 阅读(569) | 评论 (0)编辑 收藏
2008年4月8日

最小公共子序列

Longest Common Subsequence

Problem

Given a sequence A = < a1, a2, ..., am >, let sequence B = < b1, b2, ..., bk > be a subsequence of A if there exists a strictly increasing sequence ( i1<i2<i3 ..., ik ) of indices of A such that for all j = 1,2,...,k, aij = bj. For example, B = < a, b, c, d > is a subsequence of A= < a, b, c, f, d, c > with index sequence < 1, 2, 3 ,5 >.
Given two sequences X and Y, you need to find the length of the longest common subsequence of X and Y.

Input

The input may contain several test cases.

The first line of each test case contains two integers N (the length of X) and M(the length of Y), The second line contains the sequence X, the third line contains the sequence Y, X and Y will be composed only from lowercase letters. (1<=N, M<=100)

Input is terminated by EOF.

Output

Output the length of the longest common subsequence of X and Y on a single line for each test case.

Sample input

6 4
abcfdc
abcd
2 2
ab
cd

Sample output

4
0

#include <stdio.h>
char x[105],y[105];
int c[109][109],i,j,leny,lenx;
int main(){
    
while(scanf("%d %d",&lenx,&leny)!=EOF){
        scanf(
"%s",&x);
        scanf(
"%s",&y);
        
for(i=0;i<=leny;i++)
            c[
0][i]=0;
        
for(i=1;i<=lenx;i++)
            c[i][
0]=0;
        
for(i=1;i<=lenx;i++){
            
for(j=1;j<=leny;j++){
                
if(x[i-1]==y[j-1])
                    c[i][j]
=c[i-1][j-1]+1;
                
else{
                    
if(c[i-1][j]>=c[i][j-1])
                        c[i][j]
=c[i-1][j];
                    
else c[i][j]=c[i][j-1];
                }

            }

        }

        printf(
"%d\n",c[lenx][leny]);
    }

    
return 0;
}

posted @ 2008-04-08 13:27 zhongguoa 阅读(468) | 评论 (0)编辑 收藏

最大公约数函数gcd(int a,int b)的构造和ax=b (mod n) 的解

Problem

Give you a modular equation ax=b (mod n). Count how many different x (0<=x<n) satisfying the equation.

Input

The input may contain several test cases.

Each test contains a line with three integers a, b and n, each integer is positive and no more than 10^9.

Input is terminated by EOF.

Output

For each test case, output a line containing the number of solutions.

Sample input

4 2 6

Sample output

2

#include <stdio.h>
long a,b,n;
int gcd(long a,long b){
    
if(a==0){
        
return b;
    }

    
else
    
{
        
return gcd(b%a,a);
    }

}

int main(){
    
while(scanf("%d %d %d",&a,&b,&n)!=EOF){
        
long d=gcd(a,n);
        
if(b%d==0)
            printf(
"%d\n",d);
        
else printf("0\n",d);
    }

    
return 0;
}
posted @ 2008-04-08 12:53 zhongguoa 阅读(1072) | 评论 (1)编辑 收藏
仅列出标题  下一页