即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

河工大校赛深度总结+补题(未完待续)

编程语言 duan_1998 13℃ 0评论

【J题】爱看电视的LsF


题目来源:http://218.28.220.249:50015/JudgeOnline/problem.php?id=1269


【思路】


for循环暴力找数,注意好细节就可以(注意st的ed关系,大于和小于大部分代码是一样。)


【代码】


超长代码找不同


代码一

#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
bool shu[14];
int et[10];
int main()
{
    int k,st,ed;
    while(~scanf("%d%d%d",&k,&st,&ed))
    {
        mem(shu,0);//存按键数,0为可用按键,1为不可用
        for(int i=0; iint p;
            scanf("%d",&p);
            shu[p]=1;
        }
        if(k==10)//特判:当k的值为10时,没有按键可用,相减即可
            printf("%d\n",abs(ed-st));
        else
        {
            int p1=abs(st-ed),p2=0,p3=0;//记录没一种的p1(按加减),p2从ed往前找,p3从ed往后找//            
            if(st//当开始的数字小于结束的数字时
            {
                int f2=0,f1=0;//因为起初p2和p3的值都是0,如果经过以下暴力找不到符合值,那就变为INF,而f1,f2都是判断条件。
                for(int i=ed; i<=ed+p1; i++)//从ed往后找,限制条件,不能超过两者直接相减。
                {
                    int p=i,flag=0,l=0;//flag判定i的每一个位数里有没有按键坏掉的,若有,从0变成1
                    while(p)
                    {
                        if(shu[p%10])
                            flag=1;
                        p/=10; l++;//l记录位数
                    }
                    if(!flag){ p2=i-ed+l;f2=1; break;}
                }
                for(int i=ed-1; i>=0; i--)
                {
                    if(i==0){ p3=ed+1; f1=1; break; }//此处是sted的区别,这一句没用,留下它只是为了对比下面的那个相同的位置。
                    else
                    {
                        int p=i,flag=0,l=0;
                        while(p)
                        {
                            if(shu[p%10])
                                flag=1;
                            p/=10;l++;
                        }
                        if(!flag) { p3=ed-i+l; f1=1; break; }
                    }
                }
                if(!f2) p2=INF;
                if(!f1) p3=INF;
            }
            else if(edint f2=0,f1=0;
                for(int i=ed; i<=ed+(st-ed); i++)
                {
                    int p=i,flag=0,l=0;
                    if(i==0&&shu[0])
                        flag=1;
                    while(p)
                    {
                        if(shu[p%10])
                            flag=1;
                        p/=10; l++;
                    }
                    if(!flag){ p2=i-ed+l; f2=1; break;}
                }
                for(int i=ed-1; i>=0; i--)
                {
                    if(i==0) { p3=ed+1;f1=1;break; }//就是这一句。这一句特判必须有。
                    else
                    {
                        int p=i,flag=0,l=0;
                        while(p)
                        {
                            if(shu[p%10])
                                flag=1;
                            p/=10;l++;
                        }
                        if(!flag) {p3=ed-i+l; f1=1;break;}
                    }
                }
                if(!f2) p2=INF;
                if(!f1) p3=INF;
            }
            printf("%d\n",min(p1,min(p2,p3)));
        }
    }
}
//9 100 1
//0 1 2 3 4 5 6 7 8
//1 1 0
//0
//1 0 1
//0
//1 1 0
//1
//1 0 1
//1

折半也过。


代码二

#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
bool shu[14];
int et[10];
int main()
{
    int k,st,ed;
    while(~scanf("%d%d%d",&k,&st,&ed))
    {
        mem(shu,0);
        for(int i=0; iint p;
            scanf("%d",&p);
            shu[p]=1;
        }
        if(k==10)
            printf("%d\n",abs(ed-st));
        else
        {
            int p1=abs(st-ed),p2=0,p3=0;
                int f2=0,f1=0;
                for(int i=ed; i<=ed+p1; i++)
                {
                    int p=i,flag=0,l=0;
                    while(p)
                    {
                        if(shu[p%10])
                            flag=1;
                        p/=10; l++;
                    }
                    if(!flag){ p2=i-ed+l;f2=1; break;}
                }
                for(int i=ed-1; i>=0; i--)
                {
                    if(ed0){ p3=ed+1; f1=1; break; }
                    else
                    {
                        int p=i,flag=0,l=0;
                        while(p)
                        {
                            if(shu[p%10])
                                flag=1;
                            p/=10;l++;
                        }
                        if(!flag) { p3=ed-i+l; f1=1; break; }
                    }
                }
                if(!f2) p2=INF;
                if(!f1) p3=INF;
            printf("%d\n",min(p1,min(p2,p3)));
        }
    }
}

【G题】最大子段和


题目来源:http://218.28.220.249:50015/JudgeOnline/problem.php?id=1266


【思路】


取两个dp数组,一个存下当前奇数段最大值,另一个存下偶数段最大值,因为奇数段是由偶数段推出来的,所以有动态转移方程dp1[i]=max(dp2[i]+a[i],a[i])。


【代码】

const int N=1e5+10;
const int INF=0x3f3f3f3f;
int a[N];
int dp1[N],dp2[N];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,maxx=-INF;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        dp1[0]=dp2[0]=dp2[1]=-INF;
        for(int i=1; i<=n; i++)
        {
                dp1[i]=max(dp2[i-1]+a[i],a[i]);
                if(dp1[i]>maxx)
                    maxx=dp1[i];
                dp2[i]=dp1[i-1]+a[i];
        }
        printf("%d\n",maxx);
    }
}

【B题】地狱飞龙


题目来源:http://218.28.220.249:50015/JudgeOnline/problem.php?id=1261


【思路】


听说这是数值积分模板题,我也存一下模板。


【代码】

#include
#include

const double eps=1e-6;
double v1,v2,x,k;

double F(double t)//数值积分函数 
{
    double d=v1*v1*t*t+(v2*t-x)*(v2*t-x);
    return k/d;
}

double getAppr(double le,double ri)//三点simpson法  
{
    double mid=(le+ri)/2;
    return (F(le)+4.0*F(mid)+F(ri))*(ri-le)/6.0;//三点simpson公式
}

double Simpson(double le,double ri)
{
    double sum=getAppr(le,ri);
    double mid=(le+ri)/2;
    double sumLe=getAppr(le,mid);
    double sumRi=getAppr(mid,ri);
    return (fabs(sum-sumLe-sumRi)//eps为精度,用于算法自适应划分区间 
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf",&v1,&v2,&x,&k);
        double ans=Simpson(0,50000);
        printf("%.2lf\n",ans);
    }
    return 0;
}

【F题】Hmz 的女装(转)


题目来源:http://218.28.220.249:50015/JudgeOnline/problem.php?id=1265


【思路】


转载。。。


【代码】

typedef long long LL;
const LL MOD=1e9+7;
const int MAX=1e5+7;
int n,m,k;
LL a[MAX];
LL x,an;
int l,r;
int main()
{
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        a[0]=0;
        x=1;
        for(int i=1; i<=n; i++)
        {
            x=x*(LL)(k-1)%MOD;
            a[i]=(x-a[i-1]+MOD)%MOD;
        }
        while(m--)
        {
            scanf("%d%d",&l,&r);
            an=k*a[abs(r-l)-1]%MOD*a[n-(abs(r-l)+1)]%MOD;
            printf("%lld\n",an);
        }
    }
}

转载请注明:CodingBlog » 河工大校赛深度总结+补题(未完待续)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情