51nod1057N的阶乘

发表于 2016-03-28 | 分类于 acm

输入N求N的阶乘的准确值。

Input
输入N(1 <= N <= 10000)
Output
输出N的阶乘
Input示例
5
Output示例
120
参考博客：blog.csdn.net/qq_33850438/article/details/50631619
大数乘法问题~
大神代码：

#include<stdio.h>  
int a[9999]={1,0},n,i,c,len,j;   
int main()    
{   
    scanf("%d", &n);  
    for ( len=1,j=2;j<=n; ++j)   
    {   
        for (c=0,i=0; i<len;++i)   
        {   
            a[i]= ( c+= a[i]*j ) % 100000; c/=100000;   
        }   
        if((a[i]=c)>0)++len;  
    }      
    printf("%d",a[--len]);  
    for(;len;)  
        printf("%05d", a[--len]);  
    return 0;   
}

51nod1085-----01背包

发表于 2016-03-27 | 分类于 acm

在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[101][10001];
int w[101],p[101];
int main(){
    int n,W,i,j;
    scanf("%d%d",&n,&W);
    for(i=1;i<=n;i++){
        scanf("%d %d",&w[i],&p[i]);
    }
    for(i=1;i<=n;i++)
        for(j=0;j<=W;j++){
            if(j<w[i])
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
    }
    printf("%d\n",dp[n][W]);
}

51nod1046快速幂取余

发表于 2016-03-26 | 分类于 acm

给出3个正整数A B C，求A^B Mod C。

例如，3 5 8，3^5 Mod 8 = 3。
Input
3个正整数A B C，中间用空格分隔。(1 <= A,B,C <= 10^9)
Output
输出计算结果
Input示例
3 5 8
Output示例
3

#include<stdio.h>
long long  quickmod(long long a,long long b,long long m){
    long long ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%m;//这里a是a^(2^i)%m
            b--;
        }
        b/=2;
        a=a*a%m;
    }
    return ans;
}
int main(){
    int a,b,m;
    while(scanf("%d%d%d",&a,&b,&m)!=EOF){
      long long   ans=quickmod(a,b,m);
        printf("%lld",ans);
    }
}

51nod贪心算法入门-----任务分配问题

发表于 2016-03-21 | 分类于 acm

任务执行顺序

有N个任务需要执行，第i个任务计算时占R[i]个空间，而后会释放一部分，最后储存计算结果需要占据O[i]个空间（O[i] < R[i]）。

分析：可以抽象成，从一个整数开始，每次减去a，再加上b (a,b都是正数)，要求每次操作都不产生负数。令a[i] = R[i], b[i] = R[i] – O[i]，O[i] < R[i],有0<b[i]<a[i]。所以尽管每次有减有加，但是加的没有减的多，总数在不断减小。所以——按照b[i]递增的顺序排序，是最“有利”的。

阅读全文 »

51nod动态规划-----矩阵取数

发表于 2016-03-21 | 分类于 acm

一个NN矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。
例如：3 3的方格。

1 3 3

2 1 3

2 2 1

能够获得的最大价值为：11。

阅读全文 »

51nod贪心算法入门-----独木舟问题

发表于 2016-03-20 | 分类于 acm

独木舟问题

n个人，已知每个人体重，独木舟承重固定，每只独木舟最多坐两个人，可以坐一个人或者两个人。显然要求总重量不超过独木舟承重，假设每个人体重也不超过独木舟承重，问最少需要几只独木舟？

分析：按照人的体重排序，最轻的人跟最重的人尽量安排在一条船上，如果超过就安排最重的.

阅读全文 »

51nod1079中国剩余定理

发表于 2016-03-20 | 分类于 acm

/**
 *中国剩余定理
 */
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#define  LL __int64
using namespace std;
/**
 *gcd(a,b)=d;则存在x,y,使d=ax+by
 *extended_euclid(a,b)=ax+by
 */
LL extended_euclid(LL a,LL b,LL &x,LL &y){//扩张欧几里的算法
    int d;
    if(b==0){
        x=1; y=0;
        return a;
    }
    d=extended_euclid(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}
/**
 *x=b[i](modw[i]) o<i<len
 *w[i]>0,且w[]中任意两个数互质
 */
LL chinese_remainder(int b[],int w[],int len){
    LL res,i,d,x,y,n,m;
    res=0; n=1;
    for(i=0;i<len;i++) n*=w[i];
    for(i=0;i<len;i++){
        m=n/w[i];
        extended_euclid(w[i],m,x,y);
        res=(res+y*m*b[i])%n;
    }
    return (n+res%n)%n;
}

int main()
{
	int len,b[12],w[12];
	while(cin>>len){
        for(int i=0;i<len;i++){
            cin>>w[i]>>b[i];
        }
        cout<<chinese_remainder(b,w,len)<<endl;

	}
	return 0;
}