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

2017.11.25【NOIP提高组】模拟赛B组总结

程序员文章站 2024-03-18 23:21:28
...

普及组的忧伤激发了我努力的决心,这次要好好努力~
终于又有了一个比赛了!加油!
30+0+80=110 仍是一个很尬的分数。
T1:是一个很简单的题,但是在比赛的时候我并没有想到正解。
我盲目的想到了分块做,判断没有1操作时就直接用最长上升子序列做(n log n),然后剩余用暴力做,想水50分,但是由于最长上升子序列打成了最长不下降子序列,所以只有30分,本来可以80分的。
正解就很水了,我们每次把插入数的操作与他上一个编号连边,然后再把不插入的编号与它所跳回去的编号连边,这样直接dfs求值就可以了。但是当没有1操作时,这是一条链,导致栈会溢出。两种选择,一种打人工栈,一种打特判。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
struct cdy{int op,x;};
struct cdy1{int last,next,tov;};
int n,tot;
cdy q[500001];
cdy1 E[500001];
int fa[500001];
int f[500001];
int ans[500001];
int a[500001][2];
void insert(int x,int y)
{
    E[++tot].tov=y;
    E[tot].next=E[x].last;
    E[x].last=tot;
}
void dfs(int t)
{
    int i,j,k;
    int l,r,mid;
    for (i=E[t].last;i;i=E[i].next)
    {
        j=E[i].tov;
        if(q[j].op!=1) 
        {
            if(q[j].x>f[f[0]]) f[++f[0]]=q[j].x;
            else
            {
                l=1;r=f[0];
                while(l!=r)
                {
                    mid=(l+r)/2;
                    if(f[mid]>=q[j].x) r=mid;
                    else l=mid+1;
                }
                a[t][0]=l;a[t][1]=f[l];
                f[l]=q[j].x;
            }
        }
        ans[j]=f[0];
        dfs(j);
        if(q[j].op!=1) 
        {
            if(a[t][0]==2139062143) f[f[0]--]=0;
            else f[a[t][0]]=a[t][1];
        }
    }
}
int main()
{
    freopen("lis.in","r",stdin);
    freopen("lis.out","w",stdout);
    scanf("%d",&n);
    int i,j;
    bool flag=0;
    for (i=1;i<=n;++i)
    {
        scanf("%d%d",&q[i].op,&q[i].x);
        if(q[i].op==1) flag=1; 
    }
    memset(a,127,sizeof(a));
    f[0]=0;
    if(flag==0)
    {
        int l,r,mid;
        for (i=1;i<=n;++i)
        {
            if(q[i].x>f[f[0]]) f[++f[0]]=q[i].x;
            else
            {
                l=1;r=f[0];
                while(l!=r)
                {
                    mid=(l+r)/2;
                    if(f[mid]>=q[i].x) r=mid;
                    else l=mid+1;
                }
                f[l]=q[i].x;
            }
            printf("%d\n",f[0]);
        }
    }
    else
    {
        tot=0;
        for (i=1;i<=n;++i)
        {
            if(q[i].op==0) insert(i-1,i);           
            if(q[i].op==1) insert(q[i].x,i);
        }   
        dfs(0);
        for (i=1;i<=n;++i) printf("%d\n",ans[i]);
    }
}

T2:期望类的题,还是比较难的。
首先就是60分做法,(30分就不说了,暴力)我们枚举一个区间[i..j],这个我们假设这个区间里面都是1,那么就可以知道里面都是1的概率就是他们所有概率之积。这样我们还要保证区间两边的两个都必须是0,因为如果不是,这个区间就被一个大的区间所包含,这样我们就算重了,所以就要乘上1-{i-1的概率}再乘上1-{j+1的概率},这样在把概率一乘就出来了。
然后是100分。
首先我们可以想到用dp优化,我们设f[i][0/1/2/3]表示以i为结尾的连续若干个1的期望总值。0表示代价项为0次,1表示1次,2表示2次,3表示答案(3次)。这样每次更新的时候就是f[i][0]=(f[i-1][0]+1-a[i-1])*a[i];拆开括号就会发现这是一个累加的过程。
以此类推:
f[i][1]=(f[i-1][0]+f[i-1][1]+1-a[i-1])*a[i];
f[i][2]=(f[i-1][0]+f[i-1][2]+2*f[i-1][1]+1-a[i-1])*a[i];
f[i][3]=(f[i-1][0]+f[i-1][3]+3*f[i-1][2]+3*f[i-1][1]+1-a[i-1])*a[i];
ans+=f[i][3]*(1-a[i+1]);

#include<cstdio>
#include<iostream>
using namespace std;
int n;
int d[100001];
double a[100010];
double ans;
double f[100001][4];
int main()
{
    freopen("osu.in","r",stdin);
    freopen("osu.out","w",stdout);
    scanf("%d",&n);
    int i,j;
    for (i=1;i<=n;++i) 
        scanf("%lf",&a[i]);
    a[0]=a[n+1]=0;
    for (i=1;i<=n;++i)
    {
        f[i][0]=(f[i-1][0]+1-a[i-1])*a[i];
        f[i][1]=(f[i-1][1]+f[i-1][0]+1-a[i-1])*a[i];
        f[i][2]=(f[i-1][2]+2*f[i-1][1]+f[i-1][0]+1-a[i-1])*a[i];
        f[i][3]=(f[i-1][3]+3*f[i-1][2]+3*f[i-1][1]+f[i-1][0]+1-a[i-1])*a[i];    
        ans+=f[i][3]*(1-a[i+1]);
    }
    printf("%.1lf\n",ans);
}

T3:最水的一题,我们可以看到k<=10这个条件告诉我们我们可以直接跑每两个之间的最短路,最多也就12次SPFA。然后我用了一个状压DP来选这些情况。但是没有判断k=0的情况,还有初始值附小了,只得了80分。

#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 4557430888798830399
using namespace std;
struct cdy{int last,next,len,tov;};
int head,tail,n,m,k,s,t,tot;
cdy E[100010];
int dis[50010],d[1000010];
int p[20];
int dis_all[20][20];
bool bz[50010];
long long answer;
long long f[20][2000];
void insert(int x,int y,int z)
{
    E[++tot].tov=y;
    E[tot].len=z;
    E[tot].next=E[x].last;
    E[x].last=tot;
}
void spfa(int s)
{
    head=0,tail=1;int x,y,i;
    memset(dis,63,sizeof(dis));
    dis[p[s]]=0;memset(bz,0,sizeof(bz));
    bz[p[s]]=true;d[1]=p[s];
    while (head!=tail)
    {
        head++;x=d[head];
        for (i=E[x].last;i;i=E[i].next)
        {
            y=E[i].tov;
            if (dis[x]+E[i].len<dis[y])
            {
                dis[y]=dis[x]+E[i].len;
                if (bz[y]==false)
                {
                    bz[y]=true;tail++;d[tail]=y;
                    if(dis[d[head+1]]>dis[y]) swap(d[head+1],d[tail]);
                }
            }
        }
        bz[x]=false;
    }
    for (i=0;i<=k+1;++i)
        dis_all[s][i]=dis[p[i]];
}
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
    int i,x,y,z,j,s1;
    for (i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        insert(x,y,z);
    }
    answer=MAXN;
    for (i=1;i<=k;++i)
        scanf("%d",&p[i]);  
    p[0]=s;
    p[k+1]=t;
    for (i=0;i<=k;++i)
    {
        bz[i]=false;
        spfa(i);
    }
    if(k==0) 
    {
        if(dis_all[0][1]>=MAXN) printf("-1\n");
        else printf("%d\n",dis_all[0][1]);
        return 0;
    }
    bz[1]=true;
    memset(f,63,sizeof(f));
    for (i=1;i<=k;++i)
        f[i][1<<(i-1)]=dis_all[0][i];   
    for (s=1;s<=(1<<k)-1;++s)
        for (i=1;i<=k;++i)
            if((s&(1<<(i-1)))==0)
                for (j=1;j<=k;++j)
                    if(i!=j&&(s&(1<<(j-1))))
                    {
                        s1=s+(1<<(i-1));
                        f[i][s1]=min(f[i][s1],f[j][s]+dis_all[j][i]);
                    }
    --s;
    for (i=1;i<=k;++i)
        if(answer>f[i][s]+dis_all[i][k+1])answer=f[i][s]+dis_all[i][k+1];
    if(answer>=MAXN) printf("-1\n");
    else printf("%lld\n",answer);
}