纪中2018暑假培训day7提高b组改题记录

由于今天太颓了，所以没有解释

t1：

Description

码零鼠是一只很喜欢mx数学的神犇，上面那个不是ta本人的样子。这天，ta在研究一个神奇的数列，这个数列是这样的：
a0 = 1
an = ai + aj   (n>=1, i,j均在[0,n-1]内均匀随机)
Ta想知道对于给定的n，an的期望值是多少，你能告诉ta吗？
出于ta对整数的热爱，你只需要输出答案向下取整后的值
 

 

Input

一个整数T，表示数据组数
每组数据一行，包括一个整数n

Output

一个整数E(an)，

一道快乐题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t;
long long a;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&a);
        printf("%lld\n",a+1);
    }
    return 0;
}

t2：

Description

 

Input

Output

dp+kmp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char b[200010];
int nxt[200010],f[200010];
int p,len,sum;
long long ans;
int main()
{
    scanf("%s",&b);
    int lenb=strlen(b);
    int j=0;
    for(int i=1;i<lenb;i++)
    {
        while(j!=0&&b[i]!=b[j])
            j=nxt[j];
        if(b[i]==b[j])
            nxt[i+1]=++j;
        else
            nxt[i+1]=0;
    }
    for(int i=2;i<=lenb; i++) 
      {
        if(i%2==0) f[i]++;
        f[i]+=f[nxt[i]];
        ans+=f[i];
      }
      cout<<ans;
      return 0;
}

t3：

Description

悠悠岁月，不知不觉，距那传说中的pppfish晋级泡泡帝已是过 去数十年。数十年 中，这颗泡泡树上，也是再度变得精彩，各种泡泡 天才辈出，惊艳世人，然而，似乎 不论后人如何的出彩，在他们的头 顶之上，依然是有着一道身影而立。 泡泡帝，pppfish。 现在，pppfish即将带着被自己收服的无数个泡泡怪前往下一个 空间，而在前往下 一个空间的道路上，有N个中转站，和M条空间虫洞连接中转站（双向通道，可有重 边，可有环），然而，通过虫洞 是要一定的条件的，pppfish将手下所有泡泡怪编号为 1，2 … +∞,对于每个空间虫洞，有两个值L和R，表示此虫洞只允许编号从L到 R的泡 泡怪通过，pppfish现在在1号中转站，他想带尽可能多的泡 泡怪到达N号中转站，于是 pppfish找到了机智的你，希望你告诉 他最多可以带多少个泡泡怪，同时他还想知道所 有泡泡怪的编号（若 有多组解取字典序最小的一组 )

 

Input

第一行两个用空格隔开的整数N，M(2<=N<=1000，0<=M<=3000) 接下来M行，每行四个用空格隔开的整数a，b，l，r 表示在a，b中转站间有一个空间虫洞允许编号l~r的泡泡怪通过。（1<=a， b<=N，1<=l<=r<=1e6

Output

第一行一个整数ans，表示最多能携带的泡泡怪数量 接下来一行ans个用空格隔开的正整数，表示泡泡怪的编号,从小到大依次输出,如 果没有泡泡怪能通过只要输出“0”就可以了

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,head[1010],cnt,disr[1010],ml,mr,flg,vis[1010];
struct Edge
{
    int v,nxt,l,r;
}e[6010];
void add(int u,int v,int l,int r)
{
    e[++cnt].nxt=head[u];
    e[cnt].v=v;
    e[cnt].l=l;
    e[cnt].r=r;
    head[u]=cnt;
}
void spfa(int x)
{
    queue<int>q;
    memset(disr,0,sizeof(disr));
    disr[1]=0x3f3f3f3f;
    vis[1]=1;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].l>x||e[i].r<x)
                continue;
            int mindisr=min(disr[u],e[i].r);
            if(disr[v]<mindisr)
            {
                disr[v]=mindisr;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    if((disr[n]-x>mr-ml)||(ml==0))
    {
        mr=disr[n];
        ml=x;
        flg=1;
    }
    if(x<=ml)
    {
        if(disr[n]-x==mr-ml)
        {
            mr=disr[n];
            ml=x;
            flg=1;
        }
    }
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b,ll,rr;
        scanf("%d%d%d%d",&a,&b,&ll,&rr);
        add(a,b,ll,rr);
        add(b,a,ll,rr);
    }
    for(int i=1;i<=cnt;i+=2)
    {
        spfa(e[i].l);
    }
    if(!flg)
        cout<<"0"<<endl;
    else
    {
        printf("%d\n",mr-ml+1);
        while(ml<=mr)
        {
            printf("%d ",ml);
            ml++;
        }
    }
    return 0;
}