欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

湖南大学ACM程序设计新生杯大赛(同步赛)

程序员文章站 2022-06-04 12:24:52
...

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
或者 暴力打表看看
证明:湖南大学ACM程序设计新生杯大赛(同步赛)

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;
}
相关标签: 网络赛