葡京手机登陆网址青蛙的约会,纪念2遍炸

题目:

洛谷P1516 青蛙的约会,洛谷p1516约会

1.SEVERINA

题材叙述

四只青蛙在网上相识了,它们聊得很兴高采烈,于是认为很有须求见一面。它们很欢畅地发现它们住在同样条纬度线上,于是它们约定各自朝西跳,直到碰到停止。不过它们出发从前忘记了一件很重庆大学的工作,既没有问清楚对方的本性,也未尝预订会晤包车型客车具体位置。然而青蛙们都以很乐天的,它们觉得若是一贯朝着某些方向跳下去,总能蒙受对方的。可是唯有这八只青蛙在同临时间跳到同一些上,不然是永恒都不容许遇见的。为了扶助那五只乐观的青蛙,你被必要写一个顺序来判定那三只青蛙是或不是能够遭受,会在如何时候境遇。

笔者们把那八只青蛙分小名为青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往北为正方向,单位长度1米,这样大家就拿走了一条首尾相接的数轴。设青蛙A的着眼点坐标是x,青蛙B的落脚点坐标是y。青蛙A三回能跳m米,青蛙B三次能跳n米,四只青蛙跳一遍所开销的时光同一。纬度线总司长L米。今后要你求出它们跳了五次之后才会赶上。

【标题叙述】

输入输出格式

输入格式:

 

输入只包涵一行几个整数x,y,m,n,L

其中0<x≠y < =2000000000,0 < m、n < =2000000000,0 < L
< =2100000000。

 

输出格式:

 

出口相会所需求的运气,即便永远不可能遇见则输出一行”Impossible”。

 

告诉二个文本串和N个格局串,供给文本串由若干能够重新的方式串首尾相接而成的方案数模1 337 377。

输入输出样例

输入样例#1: 复制

1 2 3 4 5

出口样例#1: 复制

4

【输入格式】

说明

逐条测试点2s

 $$x+S*m\%L-(y+S*n)\%L=0$$

$$x-y+S*(m-n)+L*p=0$$

$$S*(m-n)+L*p=y-x$$

 

这么就化简成了ax+by的款型

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #define LL long long 
 5 using namespace std;
 6 const LL MAXN=400001;
 7 inline LL read()
 8 {
 9     char c=getchar();LL x=0,flag=1;
10     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
11     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*flag;
12 }
13 LL gcd(LL a,LL b)
14 {
15     return b==0?a:gcd(b,a%b);
16 }
17 inline void IM()
18 {
19     printf("Impossible");
20     exit(0);
21 }
22 LL x,y;
23 LL exgcd(LL a,LL b,LL &x,LL &y)
24 {
25     if(b==0)    {    x=1,y=0;return a;}
26     LL r=exgcd(b,a%b,x,y);
27     LL tmp=x;
28     x=y;y=tmp-(a/b)*y;
29     return r;
30 }
31 LL bgx,bgy,stepm,stepn,L;
32 int main()
33 {
34     bgx=read(),bgy=read(),stepm=read(),stepn=read(),L=read();
35     if(stepm-stepn<0)    swap(stepm,stepn),swap(bgx,bgy);
36     if((bgy-bgx)%gcd((stepm-stepn),L)!=0)    IM();
37     
38     LL r=exgcd(stepm-stepn,L,x,y);
39     x=x*(bgy-bgx)/r,
40     L=L/gcd(stepm-stepn,L);
41     
42     x=(x%L+L)%L;//处理x可能为负 
43     printf("%lld",x);
44     return 0;
45 }

 

http://www.bkjia.com/cjjc/1230356.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1230356.htmlTechArticle洛谷P1516 青蛙的约会,洛谷p1516约会 标题叙述
三只青蛙在网上相识了,它们聊得相当热情洋溢,于是认为很有要求见一面。它们很笑容可掬地觉察它们…

先是行为文本串。

其次作为一个平头N,表示有N个格局串。以下N行,每行贰个方式串,任意七个格局串分化,且不存在其余任何字符。文本串和形式串都以小写字母。

【输出格式】

方案数模1337377。

【输入样例1】

abcd

4

a

b

cd

ab

【输出样例1】

2

【输入样例2】

afrikapaprika

4

afr

ika

pap

r

【输出样例2】

1

【输入样例3】

ababababababababababababababababababababab

3

a

b

ab

【输出样例3】

759775

【数据范围】

1<=N<=4 000,文本串长不超过300 000,方式串长不抢先100。

 

 

2.组装

【标题叙述】

数轴上有m个生产车间能够生产零件。一共有n种零件,编号为1~n。第i个车间的坐标为xi,生产第pi种零件(1<=pi<=n)。你供给在数轴上的某部地方修建3个组建车间,把这么些零件组装起来。为了节约运输费用,你必要最小化cost(1)+cost(2)+…+cost(n),其中cost(x)表示生产第x种零件的车间中,到组建车间距离的平方的相当的小值。

 

【输入格式】

输入第二行为七个整数nm,即零件的体周密和生产车间的个数。以下m行每行多个整数xipi(1<=pi<=n)。输入依据生产车间从左到右的顺序排列(即xi<=xi+1。注意车间地方能够重复)。输入保险每一种零件都有车间生产。

 

【输出格式】

输出仅一行,即组装车间的最优地方(能够和有个别生产车间重合),四舍五入保留二人小数。输入有限协助最优地点惟一。

 

【输入输出样例】

assemble.in

assemble.out

3 5

-1 3

0 1

2 3

4 2

5 2

2.0000

assemble.in

assemble.out

4 8

-10 2

-8 1

-5 1

-1 3

3 4

4 3

6 2

9 4

0.7500

 

【数据范围】

编号

1-4

5-10

n

<=15

<=10000

m

<=25

<=100000

xi

<=100

<=100,000

 

 

 

3.探险

【标题叙述】

牙神指导一支探险队乘坐从倍喜那里借来的紫褐面包车去乡下探险。

噩运的是,面包车的油箱撞上地上的石块后漏了,现在他们开一单位长度须要消耗一单位油(原本的消耗加上漏的也就是一单位),他们只好停了下去做打算。

他们决定走直线公路去近年来的乡镇修车。方今她们还剩P单位油,从他们所在的地点到都市的离开为L单位长度,直线公路上有N个小型加油站,每一种地点有Wi的油能够加。由于加油相当慢,他们又很心急,所以牙神下令让您帮衬总括二个加油次数最少的同时能到城市的停站方案。

专注:没有油的时候就不可能继承前行了。

 

【输入文件】

第二行二个整数N。

接下去N行,每行八个整数Di,Wi,表示这些加油站到城市和市场的离开和油量。

第N+2行多少个整数L,P。

 

【输出文件】

仅一行,表示答案,假诺不可能到达,那么输出”-1”

 

【样例输入】

4

4 4

5 2

15 10

11 5

25 10

 

【样例输出】

2

 

【样例解释】

开10单位长度恰好到达3号站获得10单位油,然后再开4公里获得4号站的5单位油,然后直接开到城市和商场即可。

【数据规模】

对于100%的数据
N<=10000,Wi<=100,Di<=L<=1000000,P<=1000000

 题解:

t1:首先考虑暴力dp,f[i]表示前i位匹配数,很明显是n^2L的算法

能够用hash优化dp,复杂度降为nl

最后:字母树

字母树优化至o(L)

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
char str[105],z[N],c;
int n,m,top=1,ans1,flag[N];
struct node
{
    int ne[26],sum;
}f[N];
void newone(int a)
{
    memset(f[a].ne,-1,sizeof(f[a].ne));
    f[a].sum=0;
}
void build(char str[])
{
    int p=0;
    for (int i=0;str[i];i++)
     {
        int x=str[i]-'a';
        if (f[p].ne[x]==-1)
         {
            f[p].ne[x]=top;
            newone(top);
            top++;
         }
        p=f[p].ne[x];
     }   
    f[p].sum++;
}
int ans(int x,int add)
{
    int p=0,int1;
    for (int i=0;i<1000;i++)
     {
        int1=z[x]-'a';
        p=f[p].ne[int1];
        if (p==-1) return 0;
        if (f[p].sum>0) 
         {
            flag[x]+=add;
            flag[x]=flag[x]%1337377;
         }
        x++;
     }
    return f[p].sum;
}
int main()
{
    freopen("severina.in","r",stdin);
    freopen("severina.out","w",stdout);
    scanf("%s",z+1); 
    scanf("%d",&m); 
    newone(0);
    for (int i=1;i<=m;i++)
     {
        scanf("%s",&str);
        build(str);
     }
    n=strlen(z+1);
    flag[0]=1;
    for (int i=0;i<=n;i++)
     {
        flag[i]=flag[i]%1337377;
        if (flag[i]>0)ans(i+1,flag[i]);
     }
    printf("%d",flag[n]);
    return 0;
}

t2:本卷中最难的一题。

设想暴力枚举每一个零件由哪一部分机械成立,时间复杂度:o(c1c2c3…cm)

优化:

每个机器先由第三个创设,在三个个未来运动

具体看

http://www.cnblogs.com/jianglangcaijin/p/4204478.html

代码:

 

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=100005;
double aa,bb,ans,fmin,x[N],y;
int c[N],r[N],count1[N],n,m,n1;
struct xx
{
    double num;
    int next;
}z[N];
bool cmp(xx a,xx b)
{
    return a.num<b.num;
}
int read()
{
    int x=0;char ch=getchar();
    bool zositive=1;
    for (;!isdigit(ch);ch=getchar())
     if (ch=='-')zositive=0;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    return zositive?x:-x;
}
int main()
{
    freopen("assemble.in","r",stdin);
    freopen("assemble.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=m;i++)
     {
        x[i]=read();c[i]=read();
        if(!r[c[i]]) 
         {
            aa+=x[i];
            bb+=x[i]*x[i];
         }
        else    
         {
            count1[i]=r[c[i]];
            z[++n1].num=(x[i]+x[r[c[i]]])/2;
            z[n1].next=i;
         }
        r[c[i]]=i;
     }
    sort(z+1,z+n1+1,cmp);
    ans=y=aa/n;
    fmin=bb-2*aa*y+y*y*n;
    for(int i=1;i<=n1;i++)
     {
        bb-=x[count1[z[i].next]]*x[count1[z[i].next]];
        aa-=x[count1[z[i].next]];
        bb+=x[z[i].next]*x[z[i].next];
        aa+=x[z[i].next];
        y=aa/n;
        if (fmin>bb-2*aa*y+y*y*n) 
         {
            fmin=bb-2*aa*y+y*y*n;
            ans=y;
         }
     }
    printf("%.4lf",ans);
    return 0;
}

 

t3:堆优化,其实o(n^2)大暴力也得以

专注是到极限的离开

代码:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int f[N],ff[N],p,l,n,a[N],b[N];
void up(int x)
{
    if (x==1)return;
    if (f[x]>f[x/2])
     {
         swap(f[x],f[x/2]);
         up(x/2);
     }
}
void down(int x)
{
    int i=x;
    if (x*2<=l&&f[i]<f[x*2])i=x*2;
    if (x*2<l&&f[i]<f[x*2+1])i=x*2+1;
    if (i!=x)
     {
         swap(f[i],f[x]);
         down(i);
     }
}
int cmp(int x,int y)
{
    return a[x]<a[y];
}
int main()
{
    freopen("exp.in","r",stdin);
    freopen("exp.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
    scanf("%d%d",&a[n+1],&p);
    for (int i=1;i<=n;i++)a[i]=a[n+1]-a[i];    
    for (int i=1;i<=n;i++)ff[i]=i;
    sort(ff+1,ff+n+1,cmp); 
    ff[n+1]=n+1;
    n++;
    int q=p,ans=0;
    for (int i=1;i<=n;i++)
     {
         q=q-a[ff[i]]+a[ff[i-1]];
         while (q<0)
          {
              ans++;
              if (ans==i)
               {
                   puts("-1");
                   return 0;
               }
              q+=f[1];
              f[1]=f[l--];
              down(1);
          }
         f[++l]=b[ff[i]];
         up(l);
     } 
    printf("%d",ans); 
    return 0; 
}