CSU OJ 代码搜集(1200-1300)

1206: Card game

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
double dp[55][55][650];
int a[55],b[55];
 
int check(char ch)
{
      if(ch=='A')  return 1;
      if(ch=='X')  return 10;
      if(ch=='J')   return 11;
      if(ch=='Q')  return 12;
      if(ch=='K')  return 13;
      return ch-'0';
}
 
int main()
{
       int n,k,t;
       scanf("%d",&t);
       while(t--)
       {
               char str[3];
               double C=1;
               double f1[650],f2[650];
               int sum1=0,sum2=0;
               scanf("%d%d",&n,&k);
               for(int i=1;i<=k;i++)
                     C=C*(n-i+1)/i;
               for(int i=1;i<=n;i++)
               {
                     scanf("%s",str);
                     a[i]=check(str[0]);
                     sum1+=a[i];
               }
               for(int i=1;i<=n;i++)
               {
                     scanf("%s",str);
                     b[i]=check(str[0]);
                     sum2+=b[i];
               }
               memset(dp,0,sizeof(dp));
              for(int i=0;i<=n;i++)
                  dp[i][0][0]=1;
             for(int i=1;i<=n;i++)
                  for(int j=1;j<=i&&j<=k;j++)
                       for(int d=1;d<=sum1;d++)
                       {
                           if(d>=a[i])
                                dp[i][j][d]=dp[i-1][j][d]+dp[i-1][j-1][d-a[i]];
                           else
                                dp[i][j][d]=dp[i-1][j][d];
                        }
              for(int i=1;i<=sum1;i++)
                  f1[i]=1.0*dp[n][k][i]/C;
              memset(dp,0,sizeof(dp));
              for(int i=0;i<=n;i++)
                  dp[i][0][0]=1;
              for(int i=1;i<=n;i++)
                  for(int j=1;j<=i&&j<=k;j++)
                       for(int d=1;d<=sum2;d++)
                       {
                             if(d>=b[i])
                                  dp[i][j][d]=dp[i-1][j][d]+dp[i-1][j-1][d-b[i]];
                             else
                                  dp[i][j][d]=dp[i-1][j][d];
                        }
            f2[0]=0.0;
            for(int i=1;i<=sum1;i++)
            {
                  f2[i]=1.0*dp[n][k][i]/C;
                  f2[i]+=f2[i-1];
            }
            double  cnt=0;
            for(int i=1;i<=sum1;i++)
               cnt+=(double)f1[i]*f2[i-1];
            printf("%.6lf\n",1.0*cnt);
       }
  return 0;
}

1208: Fibonacci sum

#include<stdio.h>
#include<string.h>
#define MOD 1000000007
#define maxn 25
long long C[25][25];
long long ret[maxn][maxn];
long long init[maxn][maxn];
long long buf[maxn][maxn];
 
void matrixMul(long long a[][maxn] , long long b[][maxn] , long long n,long long mod)
{
    long long i,j,k;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            buf[i][j]=0;
        }
    }
    for(i=0;i<n;i++)
    {
        for(k=0;k<n;k++)
        {
            if(a[i][k]==0)
                continue;
            for(j=0;j<n;j++)
            {
                if(b[k][j]==0)
                    continue;
                buf[i][j]+=a[i][k]*b[k][j];
                if (buf[i][j]>=mod||buf[i][j]<=-mod)
                {
                    buf[i][j]%=mod;
                }
            }
        }
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            a[i][j]=buf[i][j];
        }
    }
}
 
void matrixMul(long long n,long long m,long long mod)
{
    long long i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            ret[i][j]=(i==j);
        }
    }
    for(;m;m>>=1)
    {
        if(m&1)
        {
            matrixMul(ret,init,n,mod);
        }
        matrixMul(init,init,n,mod);
    }
}
 
void initc()
{
    C[0][0]=C[1][0]=C[1][1]=1;
     for(int i=2;i<=20;i++)
     {
         for(int j=0;j<=i&&j<=20;j++)
         {
             if(j==0)
                 C[i][j]=1;
             else
                 C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
         }
     }
}
 
int main()
{
    initc();
    int t,n,k,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        if(n==1)
        {
            printf("1\n");
            continue;
        }
        else if(n==2)
        {
            printf("2\n");
            continue;
        }
        memset(init,0,sizeof(init));
        for(i=0;i<=k;i++)
        {
            for(j=0;j<=k-i;j++)
            {
                init[j][i]=C[k-i][j];
            }
        }
        for(i=0;i<=k;i++)
        {
            init[i][k+1]=C[k][i];
        }
        init[k+1][k+1]=1;
        matrixMul(k+2,n-2,MOD);
        long long ans=0;
        for(i=0;i<=k;i++)
        {
            ans=(ans+ret[i][k+1])%MOD;
        }
        ans=(ans+2*ret[k+1][k+1])%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}

1211: 大整数开平方练习

import java.util.*;
import java.math.*;


public class Main {
    public static void main(String [] args)
    {
        Scanner input = new Scanner(System.in);
        
        while(input.hasNext())
        {
            String str = input.next();
            BigInteger num = new BigInteger(str);
            int len = str.length();
            int len1 = (len+1)/2;
            BigInteger factor = BigInteger.valueOf(20);
            BigInteger factor1 = BigInteger.valueOf(10);
            
            BigInteger div = BigInteger.valueOf(0);
            BigInteger ans = BigInteger.valueOf(0);
            BigInteger left = BigInteger.valueOf(0);
            int t = 0 , index = 0;
            if(len%2 == 1){
                t = str.charAt(0)-'0';
                index+=1;
            }else{
                t = str.charAt(0)-'0';
                t = t*10 + str.charAt(1)-'0';
                index+=2;
            }
            int m = (int)Math.sqrt(t*1.0+0.1);
            ans = BigInteger.valueOf(m);
            div = BigInteger.valueOf(m).multiply(factor);
            left = BigInteger.valueOf(t-m*m);
        //    System.out.println(ans);
            BigInteger tmp = BigInteger.valueOf(0);
            
            for(int i=1 ; i<len1 ; i++ , index+=2){
                left = left.multiply(BigInteger.valueOf(100));
                int val = str.charAt(index)-'0';
                val = val*10+str.charAt(index+1)-'0';
                left = left.add(BigInteger.valueOf(val));
            //    System.out.println("div: "+i+" "+div+" "+left);
                int j=9;
                for(; j>=0 ; j--){
                    tmp = div.add(BigInteger.valueOf(j));
                    if(left.compareTo(tmp.multiply(BigInteger.valueOf(j)))>=0) break;
                }
                left = left.subtract(tmp.multiply(BigInteger.valueOf(j)));
                ans = ans.multiply(factor1).add(BigInteger.valueOf(j));
                div = ans.multiply(factor);
            }
            System.out.println(ans);
        }
    }
}

1219: 建食堂

#include <iostream>
#define INF 1e9
using namespace std;
const int maxn = 105;
int n,m;
int dp[maxn][maxn];
 
void init()
{
    for(int i = 0;i < n;++i)
        for(int j = 0;j < n;++j)
            if(i == j) dp[i][j] = 0;
            else       dp[i][j] = INF;
}
 
bool floyd()
{
    for(int k = 0;k < n;++k)
        for(int i = 0;i < n;++i)
            for(int j = 0;j < n;++j)
                dp[i][j] = min(dp[i][k] + dp[k][j],dp[i][j]);
    for(int i = 0;i < n;++i){
        dp[i][n] = 0;
        for(int j = 0;j < n;++j){
            if(dp[i][n] >= INF) return false;
            dp[i][n] = max(dp[i][j],dp[i][n]);
        }
    }
    return true;
}
 
int main(void)
{
    int a,b,c;
    while(cin >> n >> m){
        init();
        while(m--){
            cin >> a >> b >> c;
            dp[a][b] = dp[b][a] = c;
        }
        bool flag = floyd();
        int res = INF;
        for(int i = 0;i < n;++i){
            res = min(res,dp[i][n]);
        }
        if(flag) cout << res << endl;
        else     cout << "Can not" << endl;
    }
    return 0;
}
 

1226: ACM小组的内战

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define SIZE 300
 
char s1[SIZE], s2[SIZE], s3[SIZE], s4[SIZE], a[SIZE], b[SIZE], c[SIZE], d[SIZE];
bool f1[100], f2[100];
 
int main()
{
    while( scanf( "%s%s%s%s", s1, s2, s3, s4) == 4)
    {
        memset( f1, false, sizeof f1);
        memset( f2, false, sizeof f2);
        int len = strlen( s1);
        for( int i = 0; i < len; i ++)
        {
            if( !f1[ s1[i] - 48 ]  && !f2[ s2[i] - 48] ) {
                a[ s1[i] - 48 ] = s2[i];
                f1[ s1[i] - 48 ] = true;
                b[ s2[i] - 48 ] = s1[i];
                f2[ s2[i] - 48 ] = true;
            }
            if( f1[ s1[i] - 48 ] && a[ s1[i] - 48 ] != s2[i])
                f1[ s1[i] - 48 ] = false;
 
            if( f2[ s2[i] - 48 ] && b[ s2[i] - 48 ] != s1[i])
                f2[ s2[i] - 48 ] = false;
        }
        bool flag = true;
        len = strlen(s3);
        for( int i = 0; i < len; i ++)
        {
            if( !f1[ s3[i] - 48 ]) {
                flag = false;
                break;
            }
            else
                c[i] = a[ s3[i] - 48 ];
        }
        if( flag)
            for( int i = 0; i < len; i ++)
                printf( "%c", c[i]);
        else
            printf( "Wrong");
        printf( "\n");
        flag = true;
        len = strlen(s4);
        for( int i = 0; i < len; i ++)
        {
            if( !f2[ s4[i] - 48 ]) {
                flag = false;
                break;
            }
            else
                d[i] = b[ s4[i] - 48];
        }
        if( flag)
            for( int i = 0; i < len; i ++)
                printf( "%c", d[i]);
        else
            printf( "Wrong");
        printf( "\n");
    }
    return 0;
}

1228: ACM小组的数字游戏

#include<iostream>  
using namespace std;  
int a[17], i, j, pos;  
bool isOk(int positon)  
{  
    if ((a[positon] < 1) || (a[positon]>16))  
        return false;  
    for (int i = 0; i < positon; i++)  
        if (a[i] == a[positon])  
            return false;  
    if ((positon != pos) && a[positon] == 1)  
        return false;  
    if ((positon == pos) && a[positon] != 1)  
        return false;  
    return true;  
}  
int main()  
{  
    cin >> i >> j;  
    pos = (i - 1) * 4 + j;  
    for (a[1] = 1; a[1] <= 16; a[1]++)  
        if (isOk(1))  
            for (a[2] = 1; a[2] <= 16; a[2]++)  
                if (isOk(2))  
                    for (a[3] = 1; a[3] <= 16;a[3]++)  
                        if (isOk(3))  
                        {  
                            a[4]= 34 - a[1] - a[2] - a[3];  
                            if (isOk(4))  
                                for (a[5] = 1; a[5] <= 16;a[5]++)  
                                    if (isOk(5))  
                                    {  
                                        a[6] = 34 - a[1] - a[2] - a[5];  
                                        if (isOk(6))  
                                            for (a[7] = 1; a[7] <= 16;a[7]++ )  
                                                if (isOk(7))  
                                                {  
                                                    a[8] = 34 - a[5] - a[6] - a[7];  
                                                    if ((a[3] + a[4] + a[7] + a[8] == 34) && isOk(8))  
                                                        for (a[9] = 1; a[9] <= 16; a[9]++)  
                                                            if (isOk(9))  
                                                                for (a[10] = 1; a[10] <= 16;a[10]++)  
                                                                    if (isOk(10))  
                                                                    {  
                                                                        a[11] = 34 - a[6] - a[7] - a[10];  
                                                                        if (isOk(11))  
                                                                        {  
                                                                            a[12] = 34 - a[9] - a[10] - a[11];  
                                                                            if (isOk(12))  
                                                                            {  
                                                                                a[13] = 34 - a[1] - a[5] - a[9];  
                                                                                if (isOk(13) && (a[4] + a[7] + a[10] + a[13] == 34))  
                                                                                {  
                                                                                    a[14] = 34 - a[2] - a[6] - a[10];  
                                                                                    {  
                                                                                        if (isOk(14) && a[9] + a[10] + a[13] + a[14] == 34)  
                                                                                        {  
                                                                                            a[15] = 34 - a[3] - a[7] - a[11];  
                                                                                            if (isOk(15))  
                                                                                            {  
                                                                                                a[16] = 34 - a[13] - a[14] - a[15];  
                                                                                                if (isOk(16) && (a[11] + a[12] + a[15] + a[16] == 34) && (a[1] + a[4] + a[13] + a[16] == 34) && (a[1] + a[6] + a[11] + a[16] == 34))  
                                                                                                {  
                                                                                                    for (int i = 1; i <=16; i++)  
                                                                                                    {  
                                                                                                        if (i % 4 != 0)  
                                                                                                            cout << a[i] << " ";  
                                                                                                        else  
                                                                                                        cout <<a[i]<< endl;  
                                                                                                    }  
                                                                                                    cout << endl;  
                                                                                                }  
                                                                                            }  
                                                                                        }  
                                                                                    }  
   
                                                                                }  
                                                                            }  
                                                                        }  
                                                                    }  
                                                }  
                                    }  
                        }  
    return 0;  
}  

1230: 平面上的点

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
 
#define ll long long
 
void exgcd(ll  a,ll  b,ll  &x,ll  &y)
{
       if(b==0)
       {
            x=1; y=0;
            return ;
       }
       else
       {
             exgcd(b,a%b,y,x);
             y=y-x*(a/b);
       }
}
 
ll gcd(ll a,ll b)
{
     return b==0?a:gcd(b,a%b);
}
 
ll   cal(ll  xx1,ll  xx2,ll  yy1,ll  yy2,ll  a,ll  b,ll  m)
{
     ///一定要保证a,b,m为非负
     if(m<0)
     {
           m=-m; a=-a; b=-b;
     }
     if(a<0)
     {
           a=-a; ll tmp=xx1;
           xx1=-xx2;
           xx2=-tmp;
     }
     if(b<0)
     {
          b=-b;
          ll tmp=yy1;
          yy1=-yy2;
          yy2=-tmp;
     }
      ll  x0,y0,d1,t1,t2,t3,t4;
      ll  x1,y1;
      d1=gcd(a,b);
     if(m%d1!=0) return 0;
       a/=d1; b/=d1; m/=d1;
      exgcd(a,b,x0,y0);
      x0*=m,y0*=m;
      ///因为是关于t的单调函数,所以对于下边界要向上取整
      ///对于上边界要向下取整
      t1=ceil(double(xx1-x0)/b); t2=floor(double(xx2-x0)/b);
      t3=ceil(double(y0-yy2)/a); t4=floor(double(y0-yy1)/a);
      t1=max(t1,t3);  t2=min(t2,t4);
      if(t2<t1) return 0;
      return t2-t1+1;
}
 
int main()
{
       //freopen("in.txt","r",stdin);
       //freopen("test.txt","w",stdout);
       ll  a,b,c,d;
       ll  x1,x2,y1,y2,z1,z2;
       while(scanf("%lld%lld%lld%lld",&a,&b,&c,&d)!=EOF)
       {
              scanf("%lld%lld%lld%lld%lld%lld",&x1,&x2,&y1,&y2,&z1,&z2);
              if(a==0&&b==0)
              {
                    ll  cnt=0;
                    for(int z=z1;z<=z2;z++)
                    {
                         if(c*z+d==0)
                             cnt++;
                    }
                    cnt*=(x2-x1+1)*(y2-y1+1);
                    printf("%lld\n",cnt);
                    continue;
              }
              if(a==0)
              {
                     ll  cnt=0;
                     for(int z=z1;z<=z2;z++)
                     {
                            ll  tmp=-1*(d+c*z);
                            if(tmp%b==0&&tmp/b>=y1&&tmp/b<=y2)
                                 cnt++;
                     }
                     cnt*=(x2-x1+1);
                     printf("%lld\n",cnt);
                     continue;
              }
              if(b==0)
              {
                   ll  cnt=0;
                   for(int  z=z1;z<=z2;z++)
                   {
                        ll   tmp=-1*(c*z+d);
                        if(tmp%a==0&&tmp/a>=x1&&tmp/a<=x2)
                             cnt++;
                   }
                   cnt*=(y2-y1+1);
                   printf("%lld\n",cnt);
                   continue;
              }
              ll ans=0;
              for(int z=z1;z<=z2;z++)
              {
                   ll  m=-1*(d+c*z);
                   ans+=(cal(x1,x2,y1,y2,a,b,m));
              }
              printf("%lld\n",ans);
       }
   return 0;
}

1232: 懒汉的旅行

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <sstream>
#include <algorithm> 
//#include <map>
#include <set>
#include <cmath>
#include <bitset>
#define INF 0x3f3f3f3f
using namespace std;
struct edge{
    int v;int len;
};
struct status{
    int step,cost,u,oil;
    bool operator < (const status &b) const
    {
        if(step != b.step) return step > b.step;
        else if(cost != b.cost) return cost > b.cost;
        else if(oil != b.oil) return oil < b.oil;
    }
}mark[105];
vector<edge> vec[105];
int N,M,L,Y;
int start,finish;
int bfs()
{
    priority_queue<status> q;
    q.push((status){0,0,start,L}) ;
    while(!q.empty())
    {
        status now = q.top();
        q.pop();
 
        bool f = false;
        if(now.cost<mark[now.u].cost) f = true,mark[now.u]=now;
        if(now.step<mark[now.u].step) f = true, mark[now.u]=now;
        if(now.oil>mark[now.u].oil) f = true, mark[now.u]=now;
        if(!f)continue;
 
        if(now.u == finish)
            return now.cost;
 
        for(auto &Next : vec[now.u])
        {
            status tmp = now;
            tmp.u = Next.v;
            if(Next.len > L)
                continue;
            if(tmp.oil >= Next.len)
                q.push((status){now.step,now.cost,Next.v,now.oil-Next.len});
            q.push((status){now.step+1,now.cost+Y*(L-now.oil),Next.v,L-Next.len});
        }
    }
    return -1;
}
int main()
{
    while(scanf("%d%d%d%d",&N,&M,&L,&Y) != EOF)
    {
        for(int i = 0 ; i <= N ; i++)
            mark[i]=(status){INF,INF,i,-1},vec[i].clear();
        scanf("%d%d",&start,&finish);
        for(int i = 0 ; i < M ; i++)
        {
            int u,v,l;
            scanf("%d%d%d",&u,&v,&l);
            vec[u].push_back((edge){v,l});
            vec[v].push_back((edge){u,l});
        }
        printf("%d\n",bfs());
    }
    return 0;
}

1233: 病毒的复制

# include <stdio.h>
# define MAX 1000003
 
typedef struct Matrix
{
    long long a,b;
    long long c,d;
} matrix;
 
long long x[2], t;
 
int solve(matrix mat)
{
    int tot;
    matrix cur, cross, tmp;
    cur = mat;
    if (t & 0x1) cross = cur;
    else
    {
        cross.a = cross.d = 1;
        cross.b = cross.c = 0;
    }
    while (t>0)
    {
        t >>= 1;
        tmp = cur;
        cur.a = (tmp.a*tmp.a+tmp.b*tmp.c) % MAX;
        cur.b = (tmp.b*(tmp.a+tmp.d)) % MAX;
        cur.c = (tmp.c*(tmp.a+tmp.d)) % MAX;
        cur.d = (tmp.d*tmp.d+tmp.b*tmp.c) % MAX;
        tmp = cross;
        if (t & 0x1)
        {
            cross.a = (tmp.a*cur.a+tmp.b*cur.c) % MAX;
            cross.b = (tmp.a*cur.b+tmp.b*cur.d) % MAX;
            cross.c = (tmp.c*cur.a+tmp.d*cur.c) % MAX;
            cross.d = (tmp.c*cur.b+tmp.d*cur.d) % MAX;
        }
    }
    tot = (int)((cross.a*x[0]+cross.b*x[1]+cross.c*x[0]+cross.d*x[1])%MAX);
    return tot;
}
 
int main()
{
    int tot;
    matrix mat;
    while (~scanf("%Illd%lld%lld%lld%lld%lld%lld", &x[0],&x[1],&mat.a,&mat.c,&mat.b,&mat.d,&t))                              
    {
        tot = solve(mat);
        printf("%d\n", tot);
    }
    return 0;
}

1238: 兵临城下

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
 
int const maxn=31000;
long long Min[maxn*4],Max[maxn*4];
 
void Build(int rt,int l,int r)
{
       if(l>=r)
       {
            Min[rt]=0;
            return ;
       }
       int m=(l+r)/2;
       Build(rt*2,l,m);
       Build(rt*2+1,m+1,r);
       Min[rt]=min(Min[2*rt],Min[2*rt+1]);
}
 
void update(int rt,int l,int r,int x,int num)
{
        if(l>=r)
        {
               Min[rt]=num;
               return ;
        }
        int m=(l+r)/2;
        if(m>=x)
           update(rt*2,l,m,x,num);
        if(m<x)
           update(rt*2+1,m+1,r,x,num);
        Min[rt]=min(Min[rt*2],Min[2*rt+1]);
}
 
long long query(int rt,int l,int r,int ql,int qr)
{
        long long ans=0x7fffffff;
        if(ql<=l&&qr>=r)
        {
             return Min[rt];
        }
        int m=(l+r)/2;
       if(m>=ql)
           ans=min(ans,query(rt*2,l,m,ql,qr));
       if(m<qr)
           ans=min(ans,query(rt*2+1,m+1,r,ql,qr));
       return ans;
}
 
int main()
{
      //freopen("test0.in","r",stdin);
      //freopen("out.txt","w",stdout);
       int n,t,p;
       while(scanf("%d%d%d",&n,&t,&p)!=EOF)
       {
               memset(Min,0,sizeof(Min));
               while(p--)
               {
                     int x,y;
                     char str[10];
                     scanf("%d%s",&x,str);
                     if(str[0]=='p')
                     {
                            int l=1,r=n;
                            int tmp;
                            while(l<=r)
                            {
                                  int m=(l+r)/2;
                                  if(query(1,1,n,l,m)<=x)
                                      r=m-1,tmp=m;
                                  else
                                      l=m+1;
                            }
                            update(1,1,n,tmp,x+t*60);
                            printf("%d\n",tmp);
                     }
                     else
                     {
                            scanf("%d",&y);
                            int k=query(1,1,n,y,y);
                            //cout<<k<<endl;
                            if(k<=x)
                                 printf("Cannot\n");
                            else
                            {
                                  printf("Fire!\n");
                                  update(1,1,n,y,x+t*60);
                            }
                     }
               }
       }
   return 0;
}

1239: 审阅文稿

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char st1[20001],st2[12000001];
int nextt[1000001];
bool equ(int i,char a[],int j,char b[])
{
	if(a[i]==b[j]&&a[i+1]==b[j+1]) return true;
	return false;
}
void getnext()
{
	int i,j,len=strlen(st1);
	nextt[0]=-2;i=0;j=-2;
	while(i<len)
	{
		if(j==-2||equ(i,st1,j,st1))
		{
			i+=2;j+=2;//++i;++j;
			if(!equ(i,st1,j,st1)) nextt[i>>1]=j;
			else nextt[i>>1]=nextt[j>>1];
		}
		else j=nextt[j>>1];
	}
}
void kmp()
{
	int i=0,j=0;
	getnext();
	int l1=strlen(st1),l2=strlen(st2);
	int ans=0;
	while(i<l2)
	{
		if(j==-2||equ(j,st1,i,st2))
			i+=2,j+=2;
		else j=nextt[ j>>1 ];
		if(j==l1) ++ans,j=nextt[j>>1];
	}
	cout<<ans<<endl;
}
int main()
{
	while(scanf("%s",st1)!=EOF){
		scanf("%s",st2);
		kmp();
	}
	return 0;
}

1241: 数字序列

#include <cstdio>
#include <cstring> 
int vis[10010],num[10010],r[10010],fa[10010];//vis表示该头目节点是否访问过   num[i]表示i作为头目节点所表示的数,但不是确切的数,相对于集体来讲的    r[i]表示i节点与头目节点的相对值  fa[i]是i的父节点 
int find(int x) //压缩路径,并且使得r[i]等于i相对于根节点的值的大小 
{
	if(x==fa[x])
	{
		return x;
	}
	int tmp=fa[x];
	fa[x]=find(fa[x]);
	r[x]=r[x]+r[tmp];
	return fa[x];
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		char op[2];
		memset(vis,0,sizeof(vis));
		memset(num,0,sizeof(num));
		for(int i=1;i<=n;i++)
		{
			fa[i]=i;
			r[i]=0;
		}
		int flag=0;
		for(int i=0;i<m;i++)
		{
			scanf("%s",op);
			if(op[0]=='B')
			{
				int a,b,c;
				scanf("%d%d%d",&a,&b,&c);
				int fx=find(a);
				int fy=find(b);
				if(fx!=fy)//两集体合并 
				{
					fa[fy]=fx;
					r[fy]=r[a]-r[b]-c;//更新b的头目节点相对于a的头目节点的大小 
					if(vis[fy])//如果b的集体已经有确切的值了 
					{
						int tmp=num[fy]-r[fy];
						if(vis[fx])//如果a集体也已经有确切的值了 
						{
							if(num[fx]!=tmp)//
							{
								flag=1;
							}
						}
						else
						{
							num[fx]=tmp;
							vis[fx]=1;
						}
					}
				}
				else//ab是一个集体中的 
				{
					if(r[a]-r[b]!=c)
					{
						flag=1;
					}
				}
			}
			else
			{
				int a,b;
				scanf("%d%d",&a,&b);
				int fx=find(a);
				int tmp=b-r[a];
				if(vis[fx])
				{
					if(num[fx]!=tmp)
					{
						flag=1;
					}
				}
				else
				{
					num[fx]=tmp;
					vis[fx]=1;
				}
			}
		}
		if(flag)
		{
			printf("RE\n");
		}
		else
		{
			for(int i=1;i<=n;i++)
			{
				if(find(i)==i&&vis[i]==0)
				{
					flag=1;
					break;
				}
			}
			if(flag)
			{
				printf("WA\n");
			}
			else
			{
				printf("AC\n");
			}
		}
	}
	return 0;
 } 

1244: 琼脂糖双向免疫扩散试验

#include<stdio.h>
#include<math.h>
#define EPS 1e-5
int main()
{
    double rg,rb,cg,cb,d,t,s,res;
    while(scanf("%lf%lf%lf%lf%lf%lf%lf",&rb,&rg,&cb,&cg,&d,&t,&s)!=EOF)
    {
        ///directly calculate
        res=s*rg*cg/rb/cb+1.0;
        res=d/res;
        ///判断条件上WA了几次,精度没必要用EPS的
        if(rb-res>=0.0000||d-rg-res<=0.0000||(rb*cb-res*t<EPS))
            printf("Can not\n");
        else
            printf("%.4lf\n",res);
    }
    return 0;
}

1245: 信使核糖核酸转录后剪接

#include<stdio.h>
#include<string.h>
#define N 1000010
 
char t(char c)
{
    if(c=='A')
        return 'U';
    if(c=='G')
        return 'C';
    if(c=='C')
        return 'G';
    if(c=='T')
        return 'A';
}
char dna[N],mrna[N];
int main()
{
 
    int i,j,la,lb,f;
    while(scanf("%s%s",dna,mrna)!=EOF)
    {
        la=strlen(dna);
        lb=strlen(mrna);
        f=1;
        for(i=0;i<la;++i)
            dna[i]=t(dna[i]);
 
        if(la<lb)
            f=0;
        else
        for(i=la-1,j=0;j<lb;--i,++j)
        {
            for(;i>=0&&(dna[i]!=mrna[j]);--i);
            if(i==-1)
            {
                f=0;//表示匹配失败
                break;
            }
        }
        if(f)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

1246: 十二指肠钩口线虫

#include<stdio.h>  
  
int main()  
{  
    int s,v,t,m,e;  
    while(scanf("%d%d%d%d%d",&s,&v,&t,&m,&e)!=EOF)  
    {  
        int res=e*s;  
        int n=e/t;///完成吸血的个数  
        int f=(e-m)/t;///完成渗血的个数  
        if(f<0)  
            f=0;  
        res+=f*m*v;  
        for(int i=f+1;i<=n;++i)  
            res+=(e-i*t)*v;  
        printf("%d\n",res);  
    }  
    return 0;  
}

1247: 有髓鞘神经纤维动作电位传导

#include<stdio.h>
#include<string.h>
#define N 10001
int main()
{
    int n,t1,t2,l,k,u,i,j;
    int pre[N],tim[N],hasNext[N],allTime;
    while(scanf("%d%d%d",&n,&t1,&t2)!=EOF)
    {
        memset(hasNext,0,(n+1)*sizeof(int));
        for(i=1;i<=n;++i)
        {
            scanf("%d%d%d",&u,&l,&k);
            pre[i]=u;
            hasNext[u]=1;
            if(k)
            {
                int a,b;
                scanf("%d",&a);
                tim[i]=a;
                for(j=1;j<k;++j)
                {
                    scanf("%d%d",&a,&b);
                    tim[i]+=b-a;
                }
                scanf("%d",&b);
                tim[i]+=l-b;
                tim[i]=tim[i]*t1+t2;
            }
            else
                tim[i]=l*t1+t2;
        }
        int minn=1<<30,minInd,maxx=0,maxInd;
        for(i=1;i<=n;++i)
        {
            if(!hasNext[i])
            {
                allTime=0;
                j=i;
                while(j!=0)
                {
                    allTime+=tim[j];
                    j=pre[j];
                }
                if(allTime<minn)
                {
                    minn=allTime;
                    minInd=i;
                }
                if(allTime>maxx)
                {
                    maxx=allTime;
                    maxInd=i;
                }
            }
 
        }
        printf("%d %d\n",minInd,maxInd);
    }
    return 0;
}
 

1248: 非变性聚丙烯酰胺凝胶电泳

#include<stdio.h>
#include<string.h>
#define N   2001
int mass[N];
bool dp[N];
int main()
{
    int n,m,i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        m-=18;
        for(i=0;i<n;++i)
        {
            scanf("%d",&mass[i]);
            mass[i]-=18;
        }
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(i=0;i<n;++i)
        {
            for(j=(m<<1);j>=mass[i];--j)
                    dp[j]=dp[j]||dp[j-mass[i]];
        }
        for(i=0;;i++)
        if(dp[m-i]||dp[m+i])
        {
            if(dp[m-i])
                j=m+18-i;
            else if(dp[m+i])
                j=m+18+i;
            break;
        }
        printf("%d\n",j);
    }
    return 0;
}

1249: 竞争性酶抑制剂和同工酶

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
#define N 155
#define INF 1<<30
int n,m,f[N][N];
int s,e,c,pre[N];
 
int bfs()
{
    queue< int > q;
    memset(pre,-1,sizeof(pre));
    q.push(s);
    pre[s]=0;
    int k,i,inc=INF;
    while(!q.empty())
    {
        k=q.front();
        q.pop();
        for(i=1;i<=n;++i)
        if(i!=s&&pre[i]==-1&&f[k][i])
        {
            pre[i]=k;
            q.push(i);
            inc=min(inc,f[k][i]);
            if(i==e)
                return inc;
        }
    }
    return 0;
}
int flow()
{
    int res=0;
    while(1)
    {
        int inc=bfs();
        if(inc==0)
            break;
        res+=inc;
        int i=e,j;
        for(;i!=s;)
        {
            j=pre[i];
            f[j][i]-=inc;
            f[i][j]+=inc;
            i=j;
        }
    }
    return res;
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        memset(f,0,sizeof(f));
        while(m--)
        {
            scanf("%d%d%d",&s,&e,&c);
            f[s][e]+=c;
        }
        scanf("%d%d",&s,&e);
        for(int i=1;i<=n;++i)
            f[e][i]=f[i][s]=0;
        printf("%d\n",flow());
    }
    return 0;
}

1256: 天朝的单行道

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=5005,maxm=20005,INF=1<<30;
int n,m,e;
// v存储对应有向边的终点,nxt存储当前边起点相连的下一条边的编号
//   first存储对应起点的第一条边的编号,dis存储当前状态下的从起点
//    开始到当前点的最小权重和(一直在更新),inq储存是否在队列
// 中的标记 ,w储存对应边的权重
int v[maxm],nxt[maxm],w[maxm],first[maxn],dis[maxn],inq[maxn],fa[maxn];
int find(int a){return fa[a]==a?a:fa[a]=find(fa[a]);}
bool merge(int a, int b){
    int faa=find(a),fab=find(b);
    if(faa==fab)return false;
    fa[fab]=faa;
    return true;
}
void add(int a, int b, int c){
    v[e]=b;
    nxt[e]=first[a];
    w[e]=c;
    first[a]=e++;
}
void spfa(int source){
    queue<int> q;
    dis[source]=0;
    inq[source]=1;
    q.push(source);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        inq[tmp]=0;
        for(int i = first[tmp]; i != -1; i=nxt[i]){
            if(dis[v[i]]>dis[tmp]+w[i]){
                dis[v[i]]=dis[tmp]+w[i];
                if(!inq[v[i]]){
                    q.push(v[i]);
                    inq[v[i]]=1;
                }
            }
        }
    }
}
 
int main(){
    while(~scanf("%d%d",&n,&m)){
        e=0;
        memset(first,-1,sizeof(first));
        memset(inq,0,sizeof(inq));
        for(int i = 0; i < maxn; i++)dis[i]=INF;
        for(int i = 0; i <= n; i++)fa[i]=i;
        for(int i = 0; i < m; i++){
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b,0);
            add(b,a,1);
            merge(a,b);
        }
        if(find(1)==find(n))
            spfa(1);
        if(dis[n]==INF)
            printf("-1\n");
        else
            printf("%d\n",dis[n]);
    }
    return 0;
}

1258: 维护序列

#include <iostream>
#include <string.h>
#include <stdio.h>
 
using namespace std ;
 
#define MAXN 10005
 
#define M(x , y) (x+y)>>1
#define L(x) x<<1
#define R(x) x<<1|1
struct Tree{
    int l ;
    int r ;
    int sum ;
    int lazy;
}tree[MAXN * 4] ;
int n ;
int m ;
inline void pushup(int c){
    int l = L(c) ;
    int r = R(c) ;
    tree[c].sum = tree[l].sum ^ tree[r].sum ;
    if(tree[l].lazy && tree[r].lazy)
        tree[c].lazy = 1 ;
}
void build(int l ,int r , int c){
    tree[c].l = l ;
    tree[c].r = r ;
    tree[c].sum = 0  ;
    tree[c].lazy = 0 ;
    if(l == r)
        return ;
    build( l , M(l, r) , L(c)) ;
    build( (M(l , r)) + 1 , r , R(c)) ;
}
void insert(int v , int l , int c){
    if(tree[c].l == l && tree[c].r==l){
        tree[c].sum = v ;
        if(!v)
            tree[c].lazy = 1 ;
        return ;
    }
    int m = M(tree[c].l , tree[c].r) ;
    if(l <= m){
        insert(v , l , L(c)) ;
    }
    else{
        insert(v , l , R(c)) ;
    }
    pushup(c) ;
}
void update(int l , int r , int c){
    if(tree[c].lazy)
        return  ;
    if(l == r && tree[c].l==tree[c].r && l==tree[c].l){
        if(tree[c].sum != 0){
            int k = tree[c].sum & (-tree[c].sum) ;
            tree[c].sum = tree[c].sum^k ;
            if(!tree[c].sum){
                tree[c].lazy = 1 ;
            }
        }
        return ;
    }
    int m = M(tree[c].l , tree[c].r) ;
    if(l==tree[c].l && r == tree[c].r){
        update(l , m , L(c) ) ;
        update(m + 1 , r , R(c)) ;
    }
    else if(m >= r){
        update(l  , r , L(c)) ;
    }
    else if(m < l){
        update(l , r ,  R(c)) ;
    }
    else {
        update(l , m , L(c)) ;
        update(m+1 , r , R(c)) ;
    }
    pushup(c) ;
}
 
void query(int &ans , int l , int r , int c){
    if(tree[c].lazy){
        ans ^= 0 ;
        return ;
    }
    if(tree[c].l == l && tree[c].r == r){
        ans ^= tree[c].sum ;
        return ;
    }
    int m = M(tree[c].l , tree[c].r) ;
    if(r <= m){
        query(ans , l , r , L(c)) ;
    }
    else if(l > m){
        query(ans , l , r , R(c)) ;
    }
    else{
        query(ans , l     , m , L(c)) ;
        query(ans , m + 1 , r , R(c)) ;
    }
}
 
int main(){
    while(scanf("%d%d" , &n , &m) != EOF){
 
        int x ;
        int y ;
        int k ;
        build(1 , n , 1) ;
        for(int i = 1 ; i <= n ; i ++){
            scanf("%d" , &x) ;
            insert(x , i , 1 ) ;
        }
 
        for(int i = 1 ; i <= m ; i ++){
            scanf("%d%d%d" , &k , &x , &y) ;
            if(k == 1){
                update(x , y , 1) ;
            }
            else{
                int ans = 0 ;
                query(ans , x , y , 1) ;
                printf("%d\n" , ans) ;
            }
        }
    }
    return 0 ;
}
 

1259: 跳跳

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct stu
{
    int i,j;
};
int a[101][101],m;
char s[101][101];
queue<struct stu> q;
void xtd(int i,int j)
{
    struct stu n;
    int i1,j1;
    if(s[i][j]>='2'&&s[i][j]<='9')
        for(i1=0;i1<m;i1++)
            for(j1=0;j1<m;j1++)
                if(s[i1][j1]==s[i][j]&&!a[i1][j1]){
                    n.i=i1;
                    n.j=j1;
                    q.push(n);
                    a[i1][j1]=a[i][j];
                }
}
int bfs(struct stu n)
{
    int i,j,flag=0;
    q.push(n);
    a[n.i][n.j]=1;
    while(!q.empty()){
        n=q.front();
        i=n.i;
        j=n.j;
        q.pop();
        if(s[i][j]=='E'){
            flag=1;
            break;
        }
        if(s[i][j]!='1'){
            if(i-1>=0&&s[i-1][j]!='1'&&!a[i-1][j]){
                n.i=i-1;
                n.j=j;
                q.push(n);
                a[i-1][j]=a[i][j]+1;
                xtd(i-1,j);
            }
            if(i+1<m&&s[i+1][j]!='1'&&!a[i+1][j]){
                n.i=i+1;
                n.j=j;
                q.push(n);
                a[i+1][j]=a[i][j]+1;
                xtd(i+1,j);
            }
            if(j-1>=0&&s[i][j-1]!='1'&&!a[i][j-1]){
                n.i=i;
                n.j=j-1;
                q.push(n);
                a[i][j-1]=a[i][j]+1;
                xtd(i,j-1);
            }
            if(j+1<m&&s[i][j+1]!='1'&&!a[i][j+1]){
                n.i=i;
                n.j=j+1;
                q.push(n);
                a[i][j+1]=a[i][j]+1;
                xtd(i,j+1);
            }
        }
    }
    return flag;
}
int main()
{
    int i,j,t;
    struct stu n,k;
    while(scanf("%d",&m)!=EOF){
        getchar();
        for(i=0;i<m;i++){
            for(j=0;j<m;j++){
                scanf("%c",&s[i][j]);
                if(s[i][j]=='S'){
                    n.i=i;
                    n.j=j;
                }
                else if(s[i][j]=='E'){
                    k.i=i;
                    k.j=j;
                }
            }
            getchar();
        }
        memset(a,0,sizeof(a));
        while(!q.empty())
            q.pop();
        t=bfs(n);
        if(t)
            printf("%d\n",a[k.i][k.j]-1);
        else
            printf("Oh No!\n");
    }
    return 0;
}

1262: 安全密码

#include <cstdio>
#include <string.h> 
#include <iostream>
 
using namespace std;
 
int main()
{
#ifdef LOCAL
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
#endif
    char s[55];
    int a1,a2,a3,a4;
    while(scanf("%s",s)!=EOF)
    {
    	a1=0;a2=0;a3=0;a4=0;
    	int l=strlen(s);
    	for(int i=0;i<l;i++)
    	{
			if(l<8)
				break;
			if(s[i]>=65&&s[i]<=90)
    			a1++;
    		else if(s[i]>=97&&s[i]<=122)
    			a2++;
    		else if(s[i]>=48&&s[i]<=57)
    			a3++;
    		else
    			a4++;
		}
		if(a1*a2*a3||a1*a2*a4||a1*a3*a4||a2*a3*a4)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

1264: 惠民工程

#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std; 
int pre[1005];
struct node
{
 int p1;
 int p2;//p1,p2分别对应的两个居民点            
 int v;//铺设管道所需的费用                  
} way[1005];
int m,n;
 
void init()
{
	memset(pre,0,sizeof(pre));
	memset(way,0,sizeof(way));
	for(int i=1;i<=m;i++)//初始化,每一个点当做是一个父节点
	 pre[i]=i;
}
 
int cmp(node a,node b) 
{
return a.v<b.v;
}
 
int find(int x)//查找父节点                   
{
 int ret=x;
 while(pre[ret]!=ret) //如果查找到的父节点不是它本身,就直接把它当做一个新的父节点
  ret=pre[ret];
  int t=x,r;//下面是路径压缩
  while(t!=ret)         
  {
   r=pre[t];   //在改变上一级额的父节点之前 用临时变量将它记录起来
   pre[t]=ret;//把上级节点改为父节点
   t=r;
  }
  return ret;
}
 
int join(int x,int y)  //判断两个点是否连通        
{
  int fx=find(x);
  int fy=find(y);
  if(fx!=fy)//如果已经联通就不用管,否则将它并入之前的连通分支中                
  {
   pre[fx]=fy;
   return 1;  
  }
  return 0;  
}
 
int main()
{  
  while(~scanf("%d%d",&m,&n))
  {
   init();
   for(int i=0;i<n;i++)
     scanf("%d%d%d",&way[i].p1,&way[i].p2,&way[i].v);
     
     sort(way,way+n,cmp); //排序,目的是为了优先考虑成本低的将它并入连通分支  
     
     int ans=0;
      for(int i=0;i<n;i++)
       if(join(way[i].p1,way[i].p2))//如果已经联通就只需计算管道费用就行 
           ans+=way[i].v;
           
          int count=0;
          for(int i=1;i<=m;i++) 
             if(pre[i]==i)//判断是否都连通
                 count++;
                
      if(count>1)//如果不连通
        printf("?\n");
        else
          printf("%d\n",ans);
  }
  return 0;
} 
 

1268: Pingpang Balls

#include<stdio.h>
int abs(int a, int b)
{
    if(a >= b)
        return a - b;
    else
        return b -a;
}
int main()
{
    int N, S, D1, D2, D3, T, W[25], i, flag1, flag2, flag3;
    scanf("%d", &T);
    while(T --)
    {
        i = flag1 = flag2 = flag3 = 0;
        scanf("%d%d%d%d%d", &N, &S, &D1, &D2, &D3);
        for(i = 0; i < N; i ++)
            scanf("%d", &W[i]);
        for(i = 0; i < N; i ++)
        {
            if(abs(W[i], S) <= D1)
                flag3 ++;
            else if(abs(W[i], S) > D1 && abs(W[i], S) <= D2)
                flag2 ++;
            else if(abs(W[i], S) > D2 && abs(W[i], S) <= D3)
                flag1 ++;
        }
        printf("%d %d %d\n", flag3, flag2, flag1);
    }
    return 0;
}

1269: Morse Code Wristwatch

#include<stdio.h>
#include<algorithm>
using namespace std;
char mp[20][25];
int aa[25]= {0,1,2,0,0,0};
int pp[25]= {0,1,2,2,1,0};
int mm[25]= {0,2,2,0,0,0};
int num[15][9]= {{0,2,2,2,2,2},{0,1,2,2,2,2},{0,1,1,2,2,2},{0,1,1,1,2,2},{0,1,1,1,1,2},{0,1,1,1,1,1},{0,2,1,1,1,1},{0,2,2,1,1,1},{0,2,2,2,1,1},{0,2,2,2,2,1},};
 
void dian(int n,char c)
{
    for(int i=1; i<=5; i++)
        mp[i][n]=c;
}
void doit(int biao,char c)
{
    int *p;
    if(c=='A')
        p=aa;
    else if(c=='M')
        p=mm;
    else if(c=='P')
        p=pp;
    else
        p=num[c-'0'];
    for(int i=1; i<=5; i++)
    {
        if(p[i]==1)
        {
            mp[i][biao]='#';
            mp[i][biao+1]='.';
        }
        if(p[i]==2)
        {
            mp[i][biao]='#';
            mp[i][biao+1]='#';
        }
        if(p[i]==0)
        {
            mp[i][biao]='.';
            mp[i][biao+1]='.';
        }
    }
}
 
 
int main()
{
    char s[200];
    int t;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        gets(s);
        int biao=1;
        for(int i=0; s[i]!=0; i++)
        {
            if(s[i]!=' ')
            {
                dian(biao++,'.');
                doit(biao,s[i]);
                biao+=2;
            }
        }
        for(int i=1; i<=5; i++)
        {
            for(int j=1; j<=18; j++)
            {
                printf("%c",mp[i][j]);
            }
            puts("");
        }
        puts("");
    }
    return 0;
}

1272: Karma

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
const double eps = 1e-8;
const double PI = acos(-1.0);
 
int sgn(double x)
{
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    else return 1;
}
struct Point
{
    double x,y;
    Point() {}
    Point(double _x,double _y)
    {
        x = _x;
        y = _y;
    }
    Point operator -(const Point &b)const
    {
        return Point(x - b.x,y - b.y);
    }
    //叉积
    double operator ^(const Point &b)const
    {
        return x*b.y - y*b.x;
    }
    //点积
    double operator *(const Point &b)const
    {
        return x*b.x + y*b.y;
    }
    //绕原点旋转角度B(弧度值),后x,y的变化
    void transXY(double B)
    {
        double tx = x,ty = y;
        x = tx*cos(B) - ty*sin(B);
        y = tx*sin(B) + ty*cos(B);
    }
};
struct Point px[1010],dbx[10];
 
struct Line
{
    Point s,e;
    Line() {}
    Line(Point _s,Point _e)
    {
        s = _s;
        e = _e;
    }
    //两直线相交求交点
    //第一个值为0表示直线重合,为1表示平行,为0表示相交,为2是相交
    //只有第一个值为2时,交点才有意义
    pair<int,Point> operator &(const Line &b)const
    {
        Point res = s;
        if(sgn((s-e)^(b.s-b.e)) == 0)
        {
            if(sgn((s-b.e)^(b.s-b.e)) == 0)
                return make_pair(0,res);//重合
            else return make_pair(1,res);//平行
        }
        double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
        res.x += (e.x-s.x)*t;
        res.y += (e.y-s.y)*t;
        return make_pair(2,res);
    }
};
 
double dist(Point a,Point b)
{
    return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+((a.y-b.y))*((a.y-b.y)));
}
 
double CalcArea(Point a,Point b,Point c,int n)
{
    Point p[3];
    p[0]=a;
    p[1]=b;
    p[2]=c;
    double res = 0;
    for(int i = 0; i < n; i++)
        res += (p[i]^p[(i+1)%n])/2;
    return fabs(res);
}
 
bool OnSeg(Point P,Line L)
{
    return
        sgn((L.s-P)^(L.e-P)) == 0 &&
        sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 0 &&
        sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0;
}
 
bool ok(Point a,Point b,Point c,Point p)//P点是否在三角形abc内或者在三角形的边上
{
    Line ab=Line(a,b);
    Line ac=Line(a,c);
    Line bc=Line(b,c);
    pair<int,Point> j;
    j=ab&(ac);
    if(j.first!=2)
    {
        if(!OnSeg(p,ab) && !OnSeg(p,bc) && !OnSeg(p,ac))
            return 0;
        else
            return 1;
    }
    double spab=CalcArea(p,a,b,3);
    double spac=CalcArea(p,a,c,3);
    double spbc=CalcArea(p,c,b,3);
    double sabc=CalcArea(c,a,b,3);
    if(fabs(sabc-(spab+spbc+spac))<=eps)
        return 1;
    return 0;
}
bool vis[1010];
int main()
{
    double x,y;
    int t,n,m,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        scanf("%lf%lf%lf%lf",&dbx[2].x,&dbx[2].y,&dbx[0].x,&dbx[0].y);
        for(i=0; i<n; i++)
            scanf("%lf%lf",&px[i].x,&px[i].y);
        int cont=0;
        memset(vis,false,sizeof vis);
        for(i=1; i<=m; i++)
        {
            scanf("%lf%lf",&x,&y);
            dbx[i%2].x=x;
            dbx[i%2].y=y;
            for(j=0; j<n; j++)
            {
                if(vis[j])
                    continue;
                if(ok(dbx[0],dbx[1],dbx[2],px[j]))
                {
                    cont++;
                    vis[j]=true;
                }
            }
        }
        printf("%d\n",cont);
    }
    return 0;
}

1282: Sphenic Number

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
 
long long ans[1500005];
 
long long p[200005], a[200005], tt = 0;
void prime()
{
    int i, n=130000, j;
    a[1] = 0;
    for(i = 2; i <= n; i++)
        a[i] = 1;
    for(i = 2; i <= n; i++)
        if(a[i])
        {
            p[tt++] = i;
            for(j = i; j <= n;j += i)
                a[j] = 0;
        }
}
int main()
{
    prime();
    int T, n, t = 0;
    for(int i = 0; i < tt; i++)
    {
        for(int j = i + 1; j < tt; j++)
        {
            for(int k = j + 1; k < tt; k++)
            {
                if(p[i] * p[j] * p[k]>539251)
                    break;
                ans[t++] = p[i] * p[j] * p[k];
            }
        }
    }
    sort(ans, ans + t);
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        printf("%lld\n", ans[n - 1]);
    }
    return 0;
}

1294: Coins

#include <cstdio>
#include <map>
#include <cstring>
#define LL long long int
using namespace std;
int main()
{
//    freopen("in.cpp","r",stdin);
    int len,k;
    scanf("%d%d",&len,&k);//长度和K值
    char a;
    int max = 0;//用来记录最后的结果,初始状态为0
    map<LL,int> m;
    LL sum = 0;
    m[0] = 0;
    getchar();
    for(int i=1; i<=len; ++i)
    {
        a = getchar();
        if(a == 'O')
            ++sum;//O,加1
        else sum -= k;//R,加-K
        map<LL,int>::iterator it;
        it = m.find(sum);
        if(it != m.end())//出现重复
        {
            if(max < i-(*it).second)//出现更大长度
                max = i-(*it).second;//更新MAX
        }
        else
            m[sum] = i;//未出现重复,保存
    }
    printf("%d\n",max);
    return 0;
}

1299: Number Transformation II

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#define pi acos(-1)
#define ll long long 
#define oo 2139062143
#define MAXN 200005
using namespace std;
struct node
{
       int next;
}h[MAXN];
int n,m,dp[MAXN],p[3000000][2];
int main()
{
       int x,i,k;
       m=0;
       memset(h,0,sizeof(h));
       memset(p,0,sizeof(p));
       for (i=1;i<=MAXN;i++)
          for (x=i*2;x<=MAXN;x+=i)
          {
                p[++m][0]=i;
                p[m][1]=h[x].next;
                h[x].next=m;        
          } 
       while (~scanf("%d%d",&n,&m))
       {  
             memset(dp,0x7f,sizeof(dp));
             dp[n]=0;
             for (x=n;x<=m;x++) 
             {
                   k=h[x].next;
                   while (k)
                   {
                        i=p[k][0];
                        if (x+i<=m)
                           if (dp[x+i]==-1 || dp[x+i]>dp[x]+1)
                              dp[x+i]=dp[x]+1;
                        k=p[k][1];
                   }
             }
             if (dp[m]==oo) printf("sorry, can not transform\n");
               else       printf("%d\n",dp[m]);
       }
       return 0;
}

 

上一篇:2019年苹果发布会:没有5G但更便宜的iPhone,真香还是丑拒?


下一篇:PHP开发实战1200例 中文pdf扫描版(61M) 下载