A

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

 

    北冥有鱼，其名为鲲，鲲之大，不知其几千里也。

                                        ——《庄子·逍遥游》

    HtBest有一条可爱的小鲲，HtBest想和与小鲲比赛游泳，我们可以把游泳池看成一个圆环，两人从起点游一圈回到起点即可完成比赛。两人在距离小于k时（距离指的是在环上的距离，而非直线距离），他们会互相监督对方有没有全速向前游，如果发现有一方没有全速向前游，则视为作弊，聪明的HtBest为了省力（更为了赢得比赛），可以选择在两者相距超过k的时候，立马掉头反向游以更快到达起点，HtBest想让你求出小鲲最少比HtBest提前多长时间完成比赛。（若HtBest比小鲲先完成比赛，输出负数）

    说明：小鲲不会作弊。

输入描述:

一行，包含四个正整数，两两之间用空格分开：L(游泳池周长)、k(互相监督距离)、a(小鲲速度)、b(HtBest速度)。所有输入数据均不超过1e9。

输出描述:

一行，包含一个数，表示小鲲最少比HtBest提前多长时间完成比赛。（保留两位小数）。

 

示例1

输入

复制

4 3 2 1

输出

复制

2.00

说明

小鲲用时4/2=2，HtBest用时4/1=4，4-2=2。

示例2

输入

复制

10 2 3 1

输出

复制

-1.33

说明

出发1单位时间后，小鲲跑了3，HtBest跑了1，此时互相监督无效，HtBest作弊反向游，第2单位时间后，HtBest游回终点，小鲲用时10/3=3.33，2-3.33=-1.33。

AC:

注意,这是个环,鲲快到终点时与htbest的距离可能小于k,呢个时候htbest不可以往回走

#include
    
     #include
     
      #include
      
       using namespace std; int main(){    int l,k,a,b;    double t1,t2,dt;    scanf("%d%d%d%d",&l,&k,&a,&b);    t1=l*1.0/a;    if(a>b)    {    t2=k*1.0/(a-b);    if(2*t2
       
      
     
    

B

时间限制：C/C++ 2秒，其他语言4秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

    化而为鸟，其名为鹏。鹏之背，不知其几千里也。

                                        ——《庄子·逍遥游》

    HtBest的小鲲长大变成了大鹏，大鹏在天际翱翔，看到了一片绵延的山脉，每座山都有自己的高度，大鹏想穿过这片山脉。由于他只能紧贴地面飞行，他想知道他一共要翻越几次大山（上升->平飞->下降，算一次，其中平飞可以没有），初始时，大鹏在山脉的左端。

输入描述:

第一行一个正整数n，表示山脉被分为n段。第二行有n个正整数ai两两之间用空格分开，ai表示山脉第i段的高度。

输出描述:

一行，包含一个正整数，表示大鹏需要翻越几次大山。

 

示例1

输入

复制

31 2 1

输出

复制

1

说明

大鹏先上升一次，再下降一次，共翻越1次。

示例2

输入

复制

33 1 2

输出

复制

0

说明

大鹏先下降一次，再上升一次，共翻越0次。

示例3

输入

复制

31 2 3

直接简单处理,注意ai会大于int,要用long long

AC:

#include
    
     #include
     
      using namespace std; int main(){    int n,flag,sum;    long long x,y;    sum=flag=0,y=-1;    scanf("%d",&n);    for(int i=0;i
      
       y)               flag=1;            else if(x
      
     
    

C

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

    桃花一簇开无主，可爱深红映浅红。

                                        ——《题百叶桃花》

    桃花长在桃树上，树的每个节点有一个桃花，调皮的HtBest想摘尽可能多的桃花。HtBest有一个魔法棒，摘到树上任意一条链上的所有桃花，由于HtBest法力有限，只能使用一次魔法棒，请求出Htbest最多可以摘到多少个桃花。

输入描述:

第一行有一个正整数n，表示桃树的节点个数。接下来n-1行，第i行两个正整数ai,bi ，表示桃树上的节点ai,bi之间有一条边。

输出描述:

第一行一个整数，表示HtBest使用一次魔法棒最多可以摘到多少桃花。

 

示例1

输入

复制

31 22 3

输出

复制

3

示例2

输入

复制

31 21 3

输出

复制

3

示例3

输入

复制

41 22 33 4

输出

复制

4

备注:

对于100%的测试数据：1 ≤ n ≤ 1000000数据量较大，注意使用更快的输入输出方式。

求连通图中最长距离的两点距离,先随便找个点求最长距离点

然后从最长距离点为起点,求最长距离,第二次求到的即是该连通图最长距离,直接两次dfs

我用vector有时候超时,有时候通过,换用链式前向星直接ac;

AC:

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 1024000using namespace std;int head[2*maxn],cnt,maxs,maxi,vis[2*maxn]; struct node{    int u,v,next;}edge[2*maxn]; void add_edge(int u,int v){    edge[cnt].u=u;    edge[cnt].v=v;    edge[cnt].next=head[u];    head[u]=cnt++;} void dfs(int x,int sum){    vis[x]=1;    if(sum>maxs)        maxs=sum,maxi=x;    for(int i=head[x];i!=-1;i=edge[i].next)        if(!vis[edge[i].v])            dfs(edge[i].v,sum+1);} int main(){    int n,a,b;    memset(head,-1,sizeof(head));    memset(vis,0,sizeof(vis));    memset(edge,0,sizeof(edge));    cnt=0;    scanf("%d",&n);    for(int i=0;i
       
      
     
    

H

 

直接用kruskal算法

ac:

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 100007using namespace std;int n,m,a,b,w;int f[maxn];struct node{    int a,b,w;}tree[maxn*5];int cmp(node x,node y){    return x.w
       
      
     
    

 J:

用矩阵快速幂解决,也可以直接公式法解决

ac:

#include
    
     using namespace std;#define ll long long#define P 1000000007int n,k,p,i;int Pow(int x,int y){    int s=1;    for(;y;y>>=1,x=(ll)x*x%P)        if(y&1)s=(ll)s*x%P;    return s;}int main(){    cin>>n>>k>>p;    if(k==1)        cout<<((ll)n*(n-1)/2%P*p+n)%P<
    

转自:

ac:

#include
    
     #include
     
      #define ll long long#define mod int(1e9+7)ll k, p;struct jz{    ll num[3][3];    jz(){ memset(num, 0, sizeof(num)); }    jz operator*(const jz &p)    {        jz ans;        for (int k = 0; k < 3;++k)        for (int i = 0; i < 3;++i)        for (int j = 0; j < 3; ++j)            ans.num[i][j] = (ans.num[i][j] + num[i][k] * p.num[k][j] % mod) % mod;        return ans;    }}pp;jz POW(jz x, ll n){    jz ans;    for (int i = 0; i < 3; i++) ans.num[i][j] = 1;    for (; n; n>>=1, x=x*x)    if (n & 1)ans = ans*x;    return ans;}void init(){    pp.num[0][0] = 1; pp.num[0][1] = k; pp.num[0][2] = 1;    pp.num[1][1] = k; pp.num[1][2] = 1; pp.num[2][2] = 1;}int main(){    ll n;    scanf("%d%d%d", &n, &k, &p);    ll s2 = 1 + k + p;    if (n == 1){ printf("1\n"); return 0; }    else if (n == 2){ printf("%lld\n", s2); return 0; }    init();    pp = POW(pp, n - 2);    printf("%lld", (pp.num[0][0] + pp.num[0][1] + (p*pp.num[0][2])%mod) % mod);    return 0;}
     
    

发电:

简单线段树,注意除法时需要用逆元处理

#include
    
     #include
     
      #include
      
       #include
       
        #define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1#define maxn 1000007#define mod 1000000007#define ll long longusing namespace std;int n,m,x,y,z;long long sum[maxn];void pushup(int rt) {    sum[rt] =(sum[rt<<1]*sum[rt<<1|1])%mod;}ll finv2(ll a,ll b){    ll res=1;    b=b-2;    while(b)    {        if(b&1)            res=res*a%mod;        a=a*a%mod;        b>>=1;    }    return res;}void build(int l,int r,int rt){    if (l == r) {        sum[rt]=1;        return ;    }    int m = (l + r) >> 1;    build(lson);    build(rson);    pushup(rt);}void update(int p,int add,int l,int r,int rt) {    if (l == r) {        sum[rt] =(sum[rt]*add)%mod;        return ;    }    int m = (l + r) >> 1;    if (p <= m) update(p , add , lson);    else update(p , add , rson);    pushup(rt);}void update2(int p,int add,int l,int r,int rt) {    if (l == r) {        sum[rt] =sum[rt]*finv(add,mod)%mod;        return ;    }    int m = (l + r) >> 1;    if (p <= m) update2(p , add , lson);    else update2(p , add , rson);    pushup(rt);}long long query(int L,int R,int l,int r,int rt) {    if (L <= l && r <= R) {        return sum[rt];    }    int m = (l + r) >> 1;    long long a = 1,b=1;    if (L <= m) a= query(L , R , lson);    if (R > m) b= query(L , R , rson);    return (a%mod*b%mod)%mod;}int main(){    scanf("%d%d",&n,&m);    build(1,n,1);    for(int i=0;i