湖南大学ACM程序设计新生杯大赛（同步赛）

C Do you like Banana ?
https://www.nowcoder.com/acm/contest/55/C
分析：判断两条线段是否相交

#include <bits/stdc++.h>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define rep(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
#define fi first
#define se second
#define sz(a) (a.size)
#define lb lower_bound
#define ub upper_bound
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef long long ll;
typedef unsigned long long ull;
const int MOD=1e9+7;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const double pi=acos(-1.0);
const int N=1e5+5;
const int dir[4][2]= {0,1,1,0,0,-1,-1,0};
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        double x1,x2,y1,y2,x3,x4,y3,y4,k1,k2;
        double w1,w2,w3,w4;
        int flag=0;
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
        if((x2-x1)==0)             
        {
            if((x3>=x2&&x4<=x2)||(x4>=x2&&x3<=x2))
                flag+=1;
        }
        else                   
        {
            k1=(double)(y2-y1)/(x2-x1);
            w3=k1*(x3-x2)+y2;
            w4=k1*(x4-x2)+y2;
            if((y3>=w3&&y4<=w4)||(y3<=w3&&y4>=w4))     
                flag+=1;
        }
        if((x4-x3)==0)               
        {
            if((x2>=x3&&x1<=x3)||(x1>=x3&&x2<=x3))
                flag+=1;
        }
        else
        {
            k2=(double)(y4-y3)/(x4-x3);
            w1=k2*(x1-x3)+y3;
            w2=k2*(x2-x3)+y3;
            if((y2>=w2&&y1<=w1)||(y2<=w2&&y1>=w1))
                flag+=1;
        }
        if(flag==2)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

D Number
https://www.nowcoder.com/acm/contest/55/D
分析：打表

const int N=1e4+5;
bool is_pr[N];
int prime[N],cnt;
void sieve()
{
    cnt=0;
    mem(is_pr,0);
    for(int i=2; i*i<=N; i++)
        if(!is_pr[i])
        {
            for(int j=i*i; j<=N; j+=i)
                is_pr[j]=1;
        }
    for(int i=2; i<=N; i++)
        if(!is_pr[i]) prime[cnt++]=i;
}
ll _pow(ll a,ll n)
{
    ll ans=1;
    for(int i=0; i<n; i++) ans*=a;
    return ans;
}
const int maxn=5e7;
int num=0,a[maxn];
void init()
{
    num=0;
    int p1,p2,p3;
    for(int i=0; i<cnt&&prime[i]<90; i++)
    {
        p1=_pow(prime[i],4);
        if(p1>maxn) break;
        for(int j=0; j<cnt&&prime[j]<400; j++)
        {
            p2=_pow(prime[j],3);
            if(p1+p2>maxn) break;
            for(int k=0; k<cnt&&prime[k]<8000; k++)
            {
                p3=_pow(prime[k],2);
                if(p3>maxn||p1+p2+p3>maxn) break;
                a[num++]=p1+p2+p3;
            }
        }
    }
    sort(a,a+num);
    num=unique(a,a+num)-a;
}
int main()
{
    int n;
    sieve();
    init();
    while(~scanf("%d",&n))
    {
        int i;
        for(i=0; i<num&&a[i]<=n; i++);
        printf("%d\n",i);
    }
    return 0;
}

E Permutation
https://www.nowcoder.com/acm/contest/55/E
分析：猜~ n<=2时 Yes ,n>2时 No
或者 暴力打表看看
证明：

G The heap of socks
https://www.nowcoder.com/acm/contest/55/G
分析： a+b

H Yuanyuan Long and His Ballons
https://www.nowcoder.com/acm/contest/55/H
分析： 环形染色问题公式法 公式为:(k-1)^n+(-1)^n*(k-1)
证明见：http://www.doc88.com/p-906234600579.html
快速幂就可以了
WA了两次的地方是 这里取模的数是 1e8+7 !!!!!!!

cosnt int MOD=1e8+7;
ll pow_mod(ll a,ll b,ll mod)
{
    ll ans=1;
    a%=mod;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int main()
{
    int T;
    ll n,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&k);
        ll ans=(pow_mod(k-1,n,MOD)%MOD+pow_mod(-1,n,MOD)*(k-1)%MOD+MOD)%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}

I Piglet treasure hunt Series 1
https://www.nowcoder.com/acm/contest/55/I
分析：记忆化+dfs
注意从边界开始搜索， 不能暴力搜！！ 反正我是这样的。。

const int dir[4][2]= {0,1,1,0,0,-1,-1,0};
char s[N][N];
bool vis[N][N];
int n,m,ans;
bool in(int x,int y)
{
    if(x>=0&&x<n&&y>=0&&y<m) return true;
    return false;
}
void dfs(int x,int y)
{
    ans++;
    vis[x][y]=1;
    rep(i,0,4)
    {
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(in(nx,ny)&&!vis[nx][ny]&&s[nx][ny]=='.')
            dfs(nx,ny);
    }
}
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    while(~scanf("%d%d",&n,&m)&&n+m)
    {
        int cnt=0;
        rep(i,0,n) scanf("%s",s[i]);
        mem(vis,0);
        ans=0;
        rep(i,0,n)
        {
            rep(j,0,m)
            {
                if(s[i][j]=='.') cnt++;
                if((!i||i==n-1||!j||j==m-1)&&s[i][j]=='.'&&!vis[i][j])
                    dfs(i,j);
            }
        }
        int g=gcd(cnt,ans);
        printf("%d/%d\n",ans/g,cnt/g);
    }
    return 0;
}

L Liao Han
https://www.nowcoder.com/acm/contest/55/L
分析：一个开关门的问题 ，可以发现规律公式， 答案就是sqrt(n)
但是！！！ 输入的时候要用long double
如果用long long ，当调用sqrt()参数类型是double，double的范围是15-16位数，存不下18位，所以会WA， 成就99.98的 通过率
痛的领悟……

int main()
{
    long double n;
    while(cin>>n)
    {
        if(n==0) break;
        cout<<ll(sqrt(n))<<endl;
    }
    return 0;
}