C++博客-zhongguoa

网络编程小例

zhongguoa — Wed, 12 May 2010 02:01:00 GMT

摘要: //server.c 1#include 2#include 3#include 4#include 5#include ... 阅读全文

zhongguoa 2010-05-12 10:01 发表评论

连堆都不会用

zhongguoa — Tue, 02 Dec 2008 00:12:00 GMT

心烦

zhongguoa 2008-12-02 08:12 发表评论

旋转卡壳

zhongguoa — Wed, 27 Aug 2008 21:57:00 GMT

转得老子的脑壳子都卡住了

zhongguoa 2008-08-28 05:57 发表评论

终于明白了凸包

zhongguoa — Tue, 29 Jul 2008 18:35:00 GMT

明天再看看具体的代码怎么写

zhongguoa 2008-07-30 02:35 发表评论

pku1032关于数论的一个结论

zhongguoa — Sat, 10 May 2008 05:45:00 GMT

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

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

假设最大积的分解为

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

(a1
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}

zhongguoa 2008-05-10 13:45 发表评论

itoa

zhongguoa — Thu, 08 May 2008 12:48:00 GMT

功能: 把一整数转换为字符串
用法: 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
#include
int main(){
int number = 123456;
char string[25];
itoa(number, string, 10);
printf("integer = %d string = %s\n", number, string);
return 0;
}

zhongguoa 2008-05-08 20:48 发表评论

并查集的模板

zhongguoa — Thu, 10 Apr 2008 15:28:00 GMT

#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;
}

zhongguoa 2008-04-10 23:28 发表评论

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

zhongguoa — Wed, 09 Apr 2008 04:54:00 GMT

#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 &&k <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);
    }
}

zhongguoa 2008-04-09 12:54 发表评论

最小公共子序列

zhongguoa — Tue, 08 Apr 2008 05:27:00 GMT

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 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; }

zhongguoa 2008-04-08 13:27 发表评论

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

zhongguoa — Tue, 08 Apr 2008 04:53:00 GMT

Problem

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

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;
}

zhongguoa 2008-04-08 12:53 发表评论