51nod1417 天堂里的游戏

发表于 2016-05-09 | 分类于 acm

1417 天堂里的游戏
基准时间限制：1 秒空间限制：131072 KB 分值: 10 难度：2级算法题
收藏
关注
多年后，每当Noder看到吉普赛人，就会想起那个遥远的下午。

Noder躺在草地上漫无目的的张望，二楼的咖啡馆在日光下闪着亮，像是要进化成一颗巨大的咖啡豆。天气稍有些冷，但草还算暖和。不远的地方坐着一个吉普赛姑娘，手里拿着塔罗牌，带着耳机，边上是她的狗。狗看起来有点凶，姑娘却漂亮。Noder开始计算各种搭讪方式的成功概率，然而狗的存在……。

奇怪的事情发生了，姑娘自己走了过来，把耳机戴在Noder的耳朵上，里面播放着：“……Knock-knock-knockin’ on heaven’s door ……”。姑娘冲他诡异的一笑，Noder只觉得自己眼前一阵眩晕，然后就站在了天堂的门口。

正当Noder惊魂未定的时候，走来一个美女，要求和他一起玩个数学游戏。美女提议：“让我们各自亮出硬币的一面，或正或反。如果我们都是正面，那么我给你A元，如果我们都是反面，我给你B元（A + B为偶数）。剩下的情况你给我（A + B） / 2元就可以了。

Noder知道这个游戏他多半要输，可他并不在乎，他只想让自己输的慢一点。

那么你来帮美女计算一下，她选择出正面的概率应该是多少（以最简分数形式输出）？

当Noder输光了钱后从草地上醒来，吉普赛姑娘已经不见了，只留下了这样一张塔罗牌，上面印有那个美女的照片。

关于样例的解释：

美女采取了(3/8,5/8)这个方案，不论Noder采用什么方案，都是不能改变局面的。如果全部出正面，每次的期望收益是 (3+3+3-2-2-2-2-2)/8=-1/8元；如果全部出反面，每次的期望收益也是(-2-2-2+1+1+1+1+1)/8=-1/8元。而任何策略无非只是上面两种策略的线性组合，所以期望还是-1/8元。

Input
第1行：一个数T，表示后面用作输入测试的数的数量（1 <= T <= 20)。
第2 - T + 1行：每行2个数A, B中间用空格分隔。(1 <= A, B <= 10^9，且A + B为偶数)。
Output
输出共T行，对应美女选择正面的概率，以最简分数形式输出，具体请参看输出样例。
Input示例
2
3 1
1 3
Output示例
3/8
5/8
PS: 给的提示标签是博弈论，结果是个数学问题；
不管是正是反，女的赢的几率都是一样的，所以左边的式子设正面为x，右边的式子设反面为x，写出期望，然后两边相等，就可以列方程了，然后最大公约数用辗转相乘法弄一下就出来了

#include<stdio.h>
typedef long long LL;
LL gcd(LL a,LL b){
    return b==0 ? a : gcd(b,a%b);
}
int main(){
    int t;
    while(~scanf("%d",&t)){
        while(t--){
            LL a,b;
            LL x,y;
            scanf("%I64d%I64d",&a,&b);
            x=a+3*b;
            y=4*(a+b);
            LL t=gcd(x,y);
            printf("%I64d/%I64d\n",x/t,y/t);
        }
    }
}

51nod1265四点共面

发表于 2016-04-11 | 分类于 acm

1265 四点共面
基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题
给出三维空间上的四个点（点与点的位置均不相同），判断这4个点是否在同一个平面内（4点共线也算共面）。如果共面，输出”Yes”，否则输出”No”。
Input
第1行：一个数T，表示输入的测试数量(1 <= T <= 1000)
第2 - 4T + 1行：每行4行表示一组数据，每行3个数，x, y, z, 表示该点的位置坐标(-1000 <= x, y, z <= 1000)。
Output
输出共T行，如果共面输出”Yes”，否则输出”No”。
Input示例
1
1 2 0
2 3 0
4 0 0
0 0 0
Output示例
Yes

/*利用四点组成构成的三个向量的混合积为0来判断是否共面*/
#include<stdio.h>
struct point{
    double x,y,z;
};
int main(){
    int t;
    point a,b,c,d;
    double r1,r2,r3,r4,r5,r6,r7,r8,r9;
    scanf("%d",&t);
    while(t--){
        scanf("%lf%lf%lf",&a.x,&a.y,&a.z);
        scanf("%lf%lf%lf",&b.x,&b.y,&b.z);
        scanf("%lf%lf%lf",&c.x,&c.y,&c.z);
        scanf("%lf%lf%lf",&d.x,&d.y,&d.z);
        r1=a.x-b.x; r2=a.y-b.y; r3=a.z-b.z;
        r4=a.x-c.x; r5=a.y-c.y; r6=a.z-c.z;
        r7=a.x-d.x; r8=a.y-d.y; r9=a.z-d.z;
        double n=r1*r5*r9+r2*r6*r7+r3*r4*r8-r3*r5*r7-r2*r4*r9-r1*r6*r8;
        if(n==0)
            printf("Yes\n");
        else
             printf("No\n");
    }
}

51nod1212无向图最小生成树

发表于 2016-04-10 | 分类于 acm

1212 无向图最小生成树
基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题
收藏
关注
N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。

Input
第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000)
第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)
Output
输出最小生成树的所有边的权值之和。
Input示例
9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8
Output示例
37
prim算法：

#include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f3f
int G[1001][1001];
int vis[1001],lowc[1001];
int prim(int G[][1001],int n){
    int i,j,p,minc,res=0;
    memset(vis,0,sizeof(vis));//全部初值为0表示没有访问过；
    vis[1]=1;
    for(i=2;i<=n;i++)
        lowc[i]=G[1][i];
    for(i=2;i<=n;i++){
        minc=inf;
        p=-1;
        for(j=1;j<=n;j++){
            if(vis[j]==0&&lowc[j]<minc)
                {minc=lowc[j];p=j;}
        }
        if(inf==minc) return -1;//原图不连通
        res+=minc;
        vis[p]=1;
        for(j=1;j<=n;j++){//更新lowc[]
            if(vis[j]==0&&lowc[j]>G[p][j])
                lowc[j]=G[p][j];
        }
    }
    return res;
}
int main(){
    int n,m;
    int x,y,w;
    while(~scanf("%d %d",&n,&m)){
        memset(G,inf,sizeof(G));
        while(m--){
            scanf("%d%d%d",&x,&y,&w);
            G[x][y]=G[y][x]=w;
        }
        printf("%d\n",prim(G,n));
    }
}

kruskal算法：

#include <stdio.h>
#include <algorithm>

using namespace std;

#define _min_(a,b) ((a)<(b)?(a):(b))
#define INF 0x3f3f3f3f
#define MAX_N 1005
#define MAX_E 50005

struct edge
{
    int u;
    int v;
    int cost;
};

edge es[MAX_E];

int N,M;
int W[MAX_N][MAX_N];
int mincost[MAX_N];
bool used[MAX_N];

bool cmp(edge e1, edge e2)
{
    return e1.cost < e2.cost;
}

// union-find set
int par[MAX_N];
int rank[MAX_N];
void init_inion_find(int n)
{
    for(int i=0;i<n;i++){
        par[i]=i;
        rank[i]=0;
    }
}
int find(int x)
{
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}
void unite(int x,int y)
{
     x=find(x);
     y=find(y);
     if(x==y){
         return;
     }
     if(rank[x]<rank[y]){
         par[x]=y;
     }else{
          par[y]=x;
          if(rank[x]==rank[y]){
              rank[x]++;
          }
     }
}
bool same(int x, int y)
{
     return find(x)==find(y);
}
// end of union-find set

void init()
{
    for(int i=0;i<MAX_N;i++){
        for(int j=0;j<MAX_N;j++){
            W[i][j]=INF;
        }
        mincost[i]=INF;
        used[i]=false;
    }
}

long long kruskal()
{
    long long res=0;
    for(int i=0;i<M;i++){
        edge e=es[i];
        if(!same(e.u, e.v)){
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

int main()
{
    //freopen("18_kruskal.txt","r",stdin);
    init();
    scanf("%d %d",&N,&M);
    for(int i=0;i<M;i++){
        int u,v,cost;
        scanf("%d %d %d",&u,&v,&cost);
        es[i].u = u-1;
        es[i].v = v-1;
        es[i].cost = cost;
    }
    sort(es,es+M,cmp);

    init_inion_find(N);

    long long res = kruskal();
    printf("%lld\n",res);
    return 0;
}

51nod1240莫比乌斯函数

发表于 2016-04-10 | 分类于 acm

莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作为莫比乌斯函数的记号。（据说，高斯(Gauss)比莫比乌斯早三十年就曾考虑过这个函数）。

具体定义如下：
如果一个数包含平方因子，那么miu(n) = 0。例如：miu(4), miu(12), miu(18) = 0。
如果一个数不包含平方因子，并且有k个不同的质因子，那么miu(n) = (-1)^k。例如：miu(2), miu(3), miu(30) = -1,miu(1), miu(6), miu(10) = 1。
给出一个数n, 计算miu(n)。
Input
输入包括一个数n，(2 <= n <= 10^9)
Output
输出miu(n)。
Input示例
5
Output示例
-1

#include<stdio.h>
int num;
int miu(int n){
    int i,cnt;
    for(i=2;i*i<=n;i++){
        cnt=0;
        if(n%i==0){
            num++;
            while(n%i==0){
                n=n/i;
                cnt++;
            }
            if(cnt>=2)
                return 0;
        }
    }
    return (num%2==0)?-1:1;
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        num=0;
        if(n==1)
            printf("1\n");
        else{
           printf("%d\n",miu(n));
        }
    }
}

51nod1256乘法逆元

发表于 2016-04-10 | 分类于 acm

1256 乘法逆元

基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题收藏关注
给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K M % N = 1，如果有多个满足条件的，输出最小的。
Input
输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9)
OutPut
输出一个数K，满足0 < K < N且K M % N = 1，如果有多个满足条件的，输出最小的。
Input示例
2 3
Output示例

思路：K M % N = 1等价于 KM=NX+1 即 KM+N*(-X)=1

根据扩展欧几里德算法，求出K和（-X）；

而K是应为正整数，即需要若K为负整数，则需要将之化正，即与负数取模同理，将K加上N，直至K>0为止，所得的数即为最小的乘法逆元；

若K为正整数，则直接输出即可

#include<stdio.h>
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-(a/b)*y;
    return r;
}
int main(){
    int n,m,x,y;
    while(~scanf("%d%d",&m,&n)){
        exgcd(m,n,x,y);
        while(x<0)
            x+=n;
        printf("%d\n",x);
    }
}

51nod1264线段相交

发表于 2016-04-10 | 分类于 acm

1264 线段相交
基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题
给出平面上两条线段的两个端点，判断这两条线段是否相交（有一个公共点或有部分重合认为相交）。如果相交，输出”Yes”，否则输出”No”。
Input
第1行：一个数T，表示输入的测试数量(1 <= T <= 1000)
第2 - T + 1行：每行8个数，x1,y1,x2,y2,x3,y3,x4,y4。(-10^8 <= xi, yi <= 10^8)
(直线1的两个端点为x1,y1 | x2, y2,直线2的两个端点为x3,y3 | x4, y4)
Output
输出共T行，如果相交输出”Yes”，否则输出”No”。
Input示例
2
1 2 2 1 0 0 2 2
-1 1 1 1 0 0 1 -1
Output示例
Yes
No
做这到题首先要了解叉乘的概念~~http://blog.csdn.net/hustspy1990/article/details/11082745
然后还要知道两条线段相交的必要条件 http://dev.gameres.com/Program/Abstract/Geometry.htm#%E5%88%A4%E6%96%AD%E4%B8%A4%E7%BA%BF%E6%AE%B5%E6%98%AF%E5%90%A6%E7%9B%B8%E4%BA%A4

/*  (a-c)×(d-c)*(d-c)×(b-c)>=0&&(c-a)×(b-a)*(b-a)×(d-a)>= 0就可以判断ab,cd相交*/
/*  p1×p2 = x1y2 - x2y1 = - p2×p1-----（叉乘公式）*/
#include<stdio.h>
struct point
{
    double x,y;
};
//struct point a,b,c,d;
int mp(point a,point b,point c,point d){
    double C=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y);
    double D=(d.x-c.x)*(b.y-c.y)-(b.x-c.x)*(d.y-c.y);
    if(C*D<0) return 0;
    else return 1;
}
bool check(point a , point b , point c , point d){
    if(!mp(a,b,c,d)) return false;
    if(!mp(c,d,a,b)) return false;
    return true;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        point a,b,c,d;
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y);
        if(check(a,b,c,d))
            printf("Yes\n");
        else
             printf("No\n");
    }
}

51nod1242 斐波那契数列矩阵快速幂

发表于 2016-04-08 | 分类于 acm

斐波那契数列的定义如下：

F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n >= 2)

(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …)
给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。

Input
输入1个数n(1 <= n <= 10^18)。
Output
输出F(n) % 1000000009的结果。
Input示例
11
Output示例
89

#include<stdio.h>
#define mod 1000000009
 struct node{
    long long int c[2][2];
} t;
long long int n;
node mul(node a,node b){//矩阵乘法
    node c;
    int i,j,k;
    for(i=0;i<2;i++){
        for(j=0;j<2;j++){
            c.c[i][j]=0;
            for(k=0;k<2;k++)
                c.c[i][j]+=(a.c[i][k]*b.c[k][j])%mod;
        c.c[i][j]=c.c[i][j]%mod;
        }
    }
    return c;
}
node kuaisumi(long long int n){
   node res = t;
    if(n<0)
        return res;
    while(n){
        if(n&1)
            res=mul(res,t);
        t=mul(t,t);
        n=n>>1;
    }
    return res;
}
int main(){
    while(~scanf("%lld",&n)){
        t.c[0][0] = 1;
        t.c[0][1] = 1;
        t.c[1][0] = 1;
        t.c[1][1] = 0;
        node res=kuaisumi(n-2);
        printf("%lld\n",res.c[0][0]);
    }
}

51nod1174区间中最大的数

发表于 2016-04-05 | 分类于 acm

1174 区间中最大的数
基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题收藏关注
给出一个有N个数的序列，编号0 - N - 1。进行Q次查询，查询编号i至j的所有数中，最大的数是多少。
例如: 1 7 6 3 1。i = 1, j = 3，对应的数为7 6 3，最大的数为7。（该问题也被称为RMQ问题）
Input
第1行：1个数N，表示序列的长度。(2 <= N <= 10000)
第2 - N + 1行：每行1个数，对应序列中的元素。(0 <= S[i] <= 10^9)
第N + 2行：1个数Q，表示查询的数量。(2 <= Q <= 10000)
第N + 3 - N + Q + 2行：每行2个数，对应查询的起始编号i和结束编号j。(0 <= i <= j <= N - 1)
Output
共Q行，对应每一个查询区间的最大值。
Input示例
5
1
7
6
3
1
3
0 1
1 3
3 4
Output示例
7
7
3

自己写的O（n）的也能水过，特地去看了一下RMQ算法~

然后就变成O（logn)了

参考博客http://blog.csdn.net/liang5630/article/details/7917702

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int dp[10010][30],num[10010];

void RMQ_init(int n){
    int i,j;
    memset(dp,0,sizeof(dp));
    for(i=1;i<n;i++)
        dp[i][0]=num[i];
    for(j=1;(1<<j)<=n;j++){
        for(i=0;i+(1<<j-1)<n;i++)
        dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
    }
}
int RMQ(int L,int R){
    int k=0;
    while((1<<(k+1))<=R-L+1) ++k;
    return max(dp[L][k],dp[R-(1<<k)+1][k]);
}
int main(){
    int n,m,i,j;
    while(~scanf("%d",&n)){
        for(i=1;i<=n;i++)
            scanf("%d",&num[i]);
        RMQ_init(n);
        scanf("%d",&m);
        int L,R;
        for(i=1;i<=m;i++){
            scanf("%d %d",&L,&R);
            printf("%d\n",RMQ(L+1,R+1));
        }
    }
}

51nod1079中国剩余定理

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

1089 最长回文子串 V2（Manacher算法）
基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题
回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。

Input
输入Str（Str的长度 <= 100000)
Output
输出最长回文子串的长度L。
Input示例
daabaac
Output示例
5

看到这道题才特意去看了下Manacher算法；
参考博客：http://blog.csdn.net/pi9nc/article/details/9251455
　　　　　http://blog.sina.com.cn/s/blog_70811e1a01014esn.html

#include<stdio.h>
#include<string.h>
#include<algorithm>
int p[200003];
char s[100001];
char str[200003];
using namespace std;
void pk(int len){
    int i;
    int mx=0,id=0;
    for(i=1;i<len;i++){
        if(mx>i)
            p[i]=min(p[2*id-i],mx-i);
        else
            p[i]=0;
        while(str[i+p[i]+1]==str[i-p[i]-1])
            p[i]++;
        if(p[i]+i>mx){
            id=i;
            mx=p[i]+id;
        }
    }
}
int main(){
    int len,ans=0,i,l=2;
    scanf("%s",s);
    len=strlen(s);
    str[0]='$';
    str[1]='#';
    for(i=0;i<len;i++){
        str[l++]=s[i];
        str[l++]='#';
    }
    //str[len]='\n';
    pk(l);
    for(i=0;i<l;i++)
        ans=max(ans,p[i]);
    printf("%d\n",ans);
}

51nod1134 最长递增子序列

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

给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）
例如：5 1 6 8 2 4 5 10，最长递增子序列是1 2 4 5 10。

Input
第1行：1个数N，N为序列的长度(2 <= N <= 50000)
第2 - N + 1行：每行1个数，对应序列的元素(-10^9 <= S[i] <= 10^9)
Output
输出最长递增子序列的长度。
Input示例
8
5
1
6
8
2
4
5
10
Output示例
5
刚开始我想到的也是动态规划，然后自己写。提交发现超时了=.=

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main(){
   // freopen("C://Users//Administrator//Desktop//duipai2//1.txt","r",stdin);
//freopen("C://Users//Administrator//Desktop//duipai2//out1.txt","w",stdout);
    int n,i,j,ans=0;
    int dp[50005];
    long long str[50005];
    for(i=1;i<50005;i++)
        dp[i]=1;
   // memset(dp,1,sizeof(dp));
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&str[i]);
        for(j=1;j<i;j++){
            if(str[j]<str[i]&&dp[j]>=dp[i])
                dp[i]=dp[j]+1;
        }
    }
   // for(i=1;i<=n;i++)
   //     printf("%d  ",dp[i]);
    for(i=1;i<=n;i++)
         ans=max(ans,dp[i]);
    printf("%d\n",ans);
}

然后参考了网上大神的代码也是动态规划=.=但是优化了，所以AC了~~

#include"stdlib.h"
#include"stdio.h"
#include"algorithm"
using namespace std;
const int maxn=1e5;
int dp[maxn];//dp[i]表示递增数量i的最小值
int a[maxn];
int main()
{
    int n,len=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    dp[len]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>dp[len])
          dp[++len]=a[i];
        else
        {
            int pos=lower_bound(dp+1,dp+len,a[i])-dp;
            //在dp[]找第一个>=a[i]下标
            dp[pos]=a[i];
        }
    }
 //   for(int i=1;i<=n;i++)
      //printf("%d  ",dp[i]);
    //printf("\n");
    printf("%d\n",len);
    return 0;
 }