UOJ Logo cxzxxjd的博客

博客

Noip2016题解&反思

2016-12-11 17:33:47 By cxzxxjd

玩具谜题(toy)

送分题。没有什么好说的。

直接按照题目的要求模拟即可。

标准的noip式day1T1。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<climits>
#include<iostream>
#define LL long long

using namespace std;

int n,m,a[100010];
char s[100010][20];

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d %s",&a[i],s[i]);
    int x=1,d,y;
    while (m--)
    {
        scanf("%d%d",&d,&y);
        if (a[x]==0)
        {
            if (d==0)
            {
                x-=y;
                if (x<1) x+=n;
            }
            else
            {
                x+=y;
                if (x>n) x-=n;
            }
        }
        else
        {
            if (d==0)
            {
                x+=y;
                if (x>n) x-=n;
            }
            else
            {
                x-=y;
                if (x<1) x+=n;
            }
        }
    }
    for (int i=0;i<strlen(s[x]);i++)
        putchar(s[x][i]);
    putchar('\n');
    return 0;
}

反思

这道题目没有什么失误,时间上也只花费了5min-。由于这类题目没法对拍,肉眼检查了一遍,还算正常。

天天爱跑步(running)

首先考虑暴力80分的做法(代码只提供60分的,原因下文会说),下面仔细的分解每一部分的点:

1(10):每个人的终点就是起点,那么直接对W_j=0的点,计算出现了几次即可。

2(10):所有的W_j=0,计算所有人的起点出现了几次即可。

3(25):直接对于每一个人的路线,暴力LCA,累加得到答案。

4(15):树退化成链,变成了区间操作。我们把跑的路径分成两类,即从小到大一类,从大到小一类。然后,我们扫一遍n,对当前位置i,正好经过的区间左边界为i的格式加入d[i],然后把右边界为i的对应的左边界x的d[x]-1,那么显然对于的当前处理到的位置i,答案就是d[i-W_i]和d[i+W_i],那么,前扫一遍后扫一遍即可。

5(20):以1结点为根建树,假设1结点的深度为0,结点i的深度为d[i],那么只有当d[i]=W_j的时候,这个结点的答案才不为0,而这种时候,他的答案就是所有能够通过这个结点的路径数量,那么,我们每次把路径的右端点的标记+1,这个结点的答案就是他所有孩子的权值和。

6(20):终点为1的。那么只存在从下到上上升的一部分,是下文正解的一部分,这里不赘述,代码也不提供。

那么下面来分析一下正解吧。

首先,对于一个人跑步的路径(x,y),我们把它分成两部分:(x,lca(x,y))和(lca(x,y),y)。

如果一个点i在从x到lca(x,y)的路径可以检测到的话,那么就有d[i]+w[i]=d[x]。

如果一个点i在从lca(x,y)到y的路径上可以检测到的话,那么就有d[i]-w[i]=d[y]-len(x,y)。

我们可以直接使用树剖来解决这类树上链的问题,但也可以考虑直接在树上标记,然后dfs解决:从x到y的一个路径,在x中a[d[x]]加一个,当dfs把lca(x,y)退栈的时候,x的影响就没有了,那么把a[d[x]]减掉。 在lca(x,y)那里需要把一个b[d[y]]加进来,在y出栈后,就把b[d[y]]减掉。 

每次ans[x]的答案就是子树a[d[x]+w[x]]+b[d[x]-w[x]]的数量。

但我们发现,这样做在树退化成链的时候会重复,我们需要特判一下,起点和终点相同的时候也会重复,也需要特判。

60分代码

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<climits>
#include<iostream>
#include<vector>
#define LL long long

using namespace std;

int n,m,b[100010],d[100010],ans[100010],l[100010],fa[100010];
vector<int > a[100010];
bool c[100010];
struct data
{
    int x,y;
}q[100010],p[100010],P[100010],Q[100010];

void dfs(int x)
{
    c[x]=false;
    for (int i=0;i<a[x].size();i++)
        if (c[a[x][i]])
        {
            d[a[x][i]]=d[x]+1;
            fa[a[x][i]]=x;
            dfs(a[x][i]);
        }
}

void DFS(int x)
{
    c[x]=false;
    for (int i=0;i<a[x].size();i++)
        if (c[a[x][i]])
        {
            DFS(a[x][i]);
            ans[x]+=ans[a[x][i]];
        }
}

bool cmp1(data x,data y){return x.x<y.x;}
bool cmp2(data x,data y){return x.y<y.y;}
bool cmp3(data x,data y){return x.x>y.x;}
bool cmp4(data x,data y){return x.y>y.y;}

int main()
{    
    scanf("%d%d",&n,&m);
    if (n%10==1)
    {
        int x,y;
        for (int i=1;i<n;i++)
            scanf("%d%d",&x,&y);
        for (int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        memset(ans,0,sizeof(ans));
        while (m--)
        {
            scanf("%d%d",&x,&y);
            if (b[x]==0) ans[x]++;
        }
        for (int i=1;i<n;i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
        return 0;
    }
    if (n%10==2)
    {
        int x,y;
        for (int i=1;i<n;i++)
            scanf("%d%d",&x,&y);
        for (int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        memset(ans,0,sizeof(ans));
        while (m--)
        {
            scanf("%d%d",&x,&y);
            ans[x]++;
        }
        for (int i=1;i<n;i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
        return 0;
    }
    if (n%10<=3)
    {
        int x,y;
        for (int i=1;i<n;i++)
            scanf("%d%d",&x,&y),a[x].push_back(y),a[y].push_back(x);
        for (int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        memset(c,true,sizeof(c));
        d[1]=1;
        dfs(1);
        while (m--)
        {
            scanf("%d%d",&x,&y);
            int l=0,r=0;
            if (d[x]>d[y]) 
            {
                l=0;
                while (d[x]>d[y])
                {
                    if (b[x]==l) ans[x]++;
                    x=fa[x];l++;
                }
                int z=y;
                while (x!=z)
                {
                    if (b[x]==l+r) ans[x]++;
                    z=fa[z];x=fa[x];
                    r++;
                }
                if (b[x]==l+r) ans[x]++;
                r=l+r+r;
                while (y!=x)
                {
                    if (b[y]==r) ans[y]++;
                    y=fa[y];
                    r--;
                }
            }
            else if (d[x]==d[y])
            {
                    int z=y;
                while (x!=z)
                {
                    if (b[x]==l+r) ans[x]++;
                    z=fa[z];x=fa[x];
                    r++;
                }
                if (b[x]==r) ans[x]++;
                r=r+r+1;
                while (y!=x)
                {
                    if (b[y]==r) ans[y]++;
                    y=fa[y];
                    r--;
                }
            }
            else
            {
                    int z=y;
                    while (d[z]>d[x])
                    {
                        r++;
                        z=fa[z];
                    }
                    while (z!=x)
                    {
                        l++;
                        if (b[x]==l) ans[x]++;
                        x=fa[x],z=fa[z];
                    }
                    if (b[x]==l) ans[x]++;
                    r=l+l+r;
                    while (y!=x)
                    {
                        if (b[y]==r) ans[y]++;
                        y=fa[y];
                        r--;
                    }
            }
        }
        for (int i=1;i<n;i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
        return 0;
    }
    if (n%10==4)
    {
        int x,y;
        for (int i=1;i<n;i++)
            scanf("%d%d",&x,&y);
        for (int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        int X=0,Y=0;
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            if (x<=y) q[++X].x=x,q[X].y=y,Q[X].x=x,Q[X].y=y;
            else p[++Y].x=x,p[Y].y=y,P[Y].x=x,P[Y].y=y;
        }
        sort(q+1,q+1+X,cmp1);
        sort(Q+1,Q+1+X,cmp2);
        int ql=1,Ql=1;
        memset(d,0,sizeof(d));
        for (int i=1;i<=n;i++)
        {
            while (q[ql].x<=i)
            {
                if (ql>X) break;
                d[q[ql].x]++;
                if (ql+1>X) {ql++;break;}else ql++;
            }
            if (i-b[i]>0) ans[i]+=d[i-b[i]];
            while (Q[Ql].y<=i)
            {
                if (Ql>X) break;
                d[Q[Ql].x]--;
                if (Ql+1>X) {Ql++;break;}else Ql++;
            }
        }        
        sort(p+1,p+1+Y,cmp3);
        sort(P+1,P+1+Y,cmp4);
        int pl=1,Pl=1;
        memset(d,0,sizeof(d));
        for (int i=n;i>=1;i--)
        {
            while (p[pl].x>=i)
            {
                if (pl>Y) break;
                d[p[pl].x]++;
                if (pl+1>Y) {pl++;break;}else pl++;
            }
            if (i+b[i]<=n) ans[i]+=d[i+b[i]];
            while (P[Pl].y>=i)
            {
                if (Pl>Y) break;
                d[P[Pl].x]--;
                if (Pl+1>Y) {Pl++;break;}else Pl++;
            }
        }        
        for (int i=1;i<n;i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
        return 0;
    }
    if (n%10==5)
    {
        int x,y;
        for (int i=1;i<n;i++)
            scanf("%d%d",&x,&y),a[x].push_back(y),a[y].push_back(x);
        for (int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        memset(c,true,sizeof(c));
        d[1]=0;
        dfs(1);
        memset(ans,0,sizeof(ans));
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            ans[y]++;
        }
        memset(c,true,sizeof(c));
        DFS(1);
        for (int i=1;i<n;i++)
            if (d[i]==b[i]) printf("%d ",ans[i]);else printf("0 ");
        if (d[n]==b[n]) printf("%d\n",ans[n]);else printf("0\n");
        return 0;
    }
    if (n%10==6)
    {

    }
    return 0;
}

满分代码

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<climits>
#include<iostream>
#include<vector>
#define LL long long

using namespace std;

int n,m,S,ans[300010],w[300010],c[300010],h[300010],to[600010],ne[600010],d[300010],p[600010][20];
vector <int > X[300010],Y[300010],ys[300010];
int xs[300010],Up[600010],Down[600010];

void dfs(int u)
{
    for (int i=h[u];i!=-1;i=ne[i])
    {
        if (!c[to[i]])
        {
            c[u]=1;
            d[to[i]]=d[u]+1;
            p[to[i]][0]=u;
            dfs(to[i]);
        }
    }
}

void init()
{
    for (int j=1;(1<<j)<=n;j++)
        for (int i=1;i<=n;i++)
            if (p[i][j-1]!=-1) p[i][j]=p[p[i][j-1]][j-1];
}

int lca(int x,int y)
{
    if (d[x]<d[y]) swap(x,y);
    int i;
    for (i=0;(1<<i)<=d[x];i++);i--;
    for (int j=i;j>=0;j--)
        if (d[x]-(1<<j)>=d[y]) x=p[x][j];
    if (x==y) return x;
    for (int j=i;j>=0;j--)
        if (p[x][j]!=-1 && p[x][j]!=p[y][j])
            x=p[x][j],y=p[y][j];
    return p[x][0];
}

void Add(int x,int y)
{
    S++;to[S]=x;ne[S]=h[y];h[y]=S;
    S++;to[S]=y;ne[S]=h[x];h[x]=S;
}

int Find(int x,int y)
{
    y=d[x]-y;
    int i;
    for (i=0;(1<<i)<=d[x];i++);i--;
    for (int j=i;j>=0;j--)
        if (d[x]-(1<<j)>=y) x=p[x][j];
    return x;
}

const int Const=300010;

void DFS(int u)
{
    int x=Up[d[u]+w[u]],y=Down[d[u]-w[u]+Const];
    Up[d[u]]+=xs[u];
    for (int j=0;j<Y[u].size();j++)
        Down[Y[u][j]+Const]++;
    for (int i=h[u];i!=-1;i=ne[i])
        if (!c[to[i]]) {c[to[i]]=1;DFS(to[i]);}
    ans[u]+=Up[d[u]+w[u]]+Down[d[u]-w[u]+Const]-x-y;
    for (int j=0;j<X[u].size();j++)
    {
        Up[X[u][j]]--;
        if (X[u][j]==d[u]+w[u]) ans[u]--;
    }
    for (int j=0;j<ys[u].size();j++)
          Down[ys[u][j]+Const]--;
}

int main()
{    
    scanf("%d%d",&n,&m);
    int x,y;
    memset(h,-1,sizeof(h));
    memset(d,0,sizeof(d));
    for (int i=1;i<n;i++)
        scanf("%d%d",&x,&y),Add(x,y);
    for (int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    memset(c,0,sizeof(c));
    d[1]=0;c[1]=1;dfs(1);init();
    memset(xs,0,sizeof(xs));
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        int z=lca(x,y);
        xs[x]++;
        Y[y].push_back(d[y]-(d[x]+d[y]-2*d[z]));
        X[z].push_back(d[x]);
        ys[z].push_back(d[y]-(d[x]+d[y]-2*d[z]));
    }
    memset(ans,0,sizeof(ans));
    memset(c,0,sizeof(c));
    memset(Up,0,sizeof(Up));
    memset(Down,0,sizeof(Down));
    c[1]=1;DFS(1);
    for (int i=1;i<n;i++)
        printf("%d ",ans[i]);
    printf("%d\n",ans[n]);
    return 0;
}

反思

这道题目主要的失误在于考场上时间安排的失误。

刚开始觉得,这题是D1T2,于是1h+都在思考正解,然后,弃疗去看T3,发现T3可做,然后T3煞笔一样的数据范围看错,边的输入了m,然后一直过不了大样例,调了整整1h+,这直接导致了T2来不及。

因为考场上,我想不出T2的正解,而从上面的分析就可以看出,T2的暴力是需要花很多时间的,时间花的越多,分数就越高。但我把时间浪费在了T3的调试上,T2的硬刚上。这都是考场上策略的失误。

说到底还是平时缺少训练,代码能力差,应考能力差的表现。

换教室(classroom)

首先是最短路,floyd即可。

暴力出奇迹,直接爆搜,80+。

那么对于正解,就是数学、dp相关的内容。

我们用f[i][j][k]表示前i节课,换掉j节课,其中第i节课(即最后一节)换或者不换(k=0 表示换,k=1表示不换)的期望。

然后考虑转移,由于期望可加,那么,我们只要一次用概率乘上当前情况的最短路即可。

但还要注意一些细节,题面中也说明了:1、有重边(56分);2、有自环(25分)。

注意,uoj的hack数据中,有m>n的情况,题目中也确实没有保证m<=n,所以也是一个细节。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<climits>
#include<iostream>
#include<vector>
#include<queue>
#define LL long long

using namespace std;

int n,m,v,e,c[2010],d[2010],a[2010][5],u[2010],o[310][310];
double p[2010],f[2010][2010][2];
struct data
{
    int x,y;
    data(int a=0,int b=0):x(a),y(b){}
};
vector<data > b[2010];

int main()
{
    //freopen("classroom.in","r",stdin);
    //freopen("classroom.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&v,&e);
    for (int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    for (int i=1;i<=n;i++)
        scanf("%d",&d[i]);
    for (int i=1;i<=n;i++)
        scanf("%lf",&p[i]);    
    for (int i=1;i<=v;i++)
        for (int j=1;j<=v;j++)
            o[i][j]=900000000;
    int x,y,z;
    for (int i=1;i<=e;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        o[x][y]=min(o[x][y],z);o[y][x]=min(o[y][x],z);
    }
    for (int k=1;k<=v;k++)
        for (int i=1;i<=v;i++)
            for(int j=1;j<=v;j++)
                if (i!=j && i!=k && j!=k)
                {
                    if (o[i][k]+o[k][j]<o[i][j]) o[i][j]=o[i][k]+o[k][j];
                }
    for (int i=1;i<=v;i++)
        for (int j=1;j<=v;j++)
            if (o[i][j]==900000000 || i==j) o[i][j]=0;
    for (int i=2;i<=n;i++)
    {
        a[i][1]=o[c[i-1]][c[i]];
        a[i][2]=o[c[i-1]][d[i]];
        a[i][3]=o[d[i-1]][c[i]];
        a[i][4]=o[d[i-1]][d[i]];
    }
    f[2][0][0]=(double)a[2][1];
    f[2][1][0]=(double)a[2][3]*p[1]+(double)a[2][1]*(1.0-p[1]);
    f[2][1][1]=(double)a[2][2]*p[2]+(double)a[2][1]*(1.0-p[2]);
    f[2][2][1]=(double)a[2][4]*p[1]*p[2]+(double)a[2][1]*(1.0-p[1])*(1.0-p[2])+(double)a[2][2]*(1.0-p[1])*p[2]+(double)a[2][3]*p[1]*(1.0-p[2]);
    for (int i=3;i<=n;i++)
    {
        f[i][0][0]=f[i-1][0][0]+a[i][1];
        if (i<=m) f[i][i][1]=f[i-1][i-1][1]+(double)a[i][4]*p[i-1]*p[i]+(double)a[i][1]*(1.0-p[i-1])*(1.0-p[i])+(double)a[i][2]*(1.0-p[i-1])*p[i]+(double)a[i][3]*p[i-1]*(1.0-p[i]);
        for (int j=1;j<=min(i-1,m);j++)
        {
            f[i][j][0]=f[i-1][j][1]+(double)a[i][3]*p[i-1]+(double)a[i][1]*(1.0-p[i-1]);
            if (i-1>j) f[i][j][0]=min(f[i][j][0],f[i-1][j][0]+(double)a[i][1]);            
            f[i][j][1]=f[i-1][j-1][0]+(double)a[i][1]*(1.0-p[i])+(double)a[i][2]*p[i];
            if (j-1>=1) f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+(double)a[i][4]*p[i-1]*p[i]+(double)a[i][3]*p[i-1]*(1.0-p[i])+(double)a[i][2]*(1.0-p[i-1])*p[i]+(double)a[i][1]*(1.0-p[i-1])*(1.0-p[i]));
        }
    }
    double ans=f[n][0][0];
    for (int i=1;i<=m;i++)
    if (i<=n)
    {
        if (n!=i) ans=min(ans,f[n][i][0]);
        if (n-i>=1) ans=min(ans,f[n][i][1]);
    }
    printf("%0.2lf\n",ans);
    return 0;
}

反思

可能是期望dp的题目第一次进入联赛吧,出题人给了很多的暴力分,暴力可以到80+。

这道题目的失分主要在于三个点:

1、数据范围看错,比赛的时候浪费了一个小时(边的读入少了);也是因为这个,导致最短路选了SPFA,于是TLE(30分)。

2、最后选取答案的时候,没有去掉一类情况(f[n][n][0])(5分)。

3、没有考虑自环的情况(20分)。

说了这么多,总之就是这道题目上的失误很多。平时训练很多题目注重于思考而疏于代码的练习,这是以后需要重点关注的。平时训练的时候很多题目来源于acm,Wa了以后会多次提交,而导致在比赛的时候,看错了数据范围,是个人平时做题习惯不好造成的。

组合数问题(problem)

基础的数学知识是$C_n^m$对应杨辉三角中的第$n$行$m$列的数。

那么,直接递推就可以得出整个杨辉三角。而对于能否被k整除的问题,直接$%k$即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#define LL long long

using namespace std;

int T,k,n,m,a[2010][2010];

int main()
{    
    scanf("%d%d",&T,&k);
    a[0][0]=1;a[1][0]=1;a[1][1]=1;
    for (int i=2;i<=2000;i++)
    {
        a[i][0]=1;a[i][i]=1;
        for (int j=1;j<i;j++)
            a[i][j]=(a[i-1][j-1]+a[i-1][j])%k;
    }
    for (int i=0;i<=2000;i++)
        for (int j=0;j<=2000;j++)
            if (a[i][j]==0 && j<=i) a[i][j]=1;else a[i][j]=0;
    for (int i=0;i<=2000;i++)
        for (int j=1;j<=2000;j++)
            a[i][j]+=a[i][j-1];
    for (int i=1;i<=2000;i++)
        for (int j=0;j<=2000;j++)
            a[i][j]+=a[i-1][j];
    while (T--)
    {
        scanf("%d%d",&n,&m);
        printf("%d\n",a[n][m]);
    }
    return 0;
}

反思

失误最严重的一道题目。

这道题目对于我而言,或者说对于所有的选手而言都理应是一道送分题。

从上面的题解也可以看出。

但是我在考场上的做法是判断$C_n^m$这个组合数的因子中有多少个k,然后的是递推,但是这样做的话,是有巨大的bug的:例如,当$k=6$的时候,因子中没有出现6,但出现了2和3,是能被6整除的。

所以导致了我在k为合数的时候,全部Wa,因此失掉了60分!

这是严重的失误,但失误绝对是因为平时训练时的习惯造成的。

当时在考场上,这道题目我还和暴力拍上了,很放心,当然,那么暴力的因子也是这么处理的,所以也错了。

本是想着万一这道题目出了什么岔子,暴力是要交上去的,所以也加了些许优化。

所以以后用来对拍的暴力,还是要用最保险的打法,不然,非常容易狗带(记得去年是因为对拍以后交错程序,也是Day2的T1)。

一次又一次的教训!一定要警示!

蚯蚓(earthworm)

直接调用STL中的$priority\_queue$,然后对于q,我们只需要在每次处理以后,当前处理的-q放入即可。期望得分65。

考虑q=0的做法。

我们只需要三个队列来处理。

一个队列存放没有切过的蚯蚓(已经进行过排序);

一个队列存放切过的前半段蚯蚓,另一个队列存放切过的后半段蚯蚓,这样的话,我们一定可以保证三个队列都是有序的,那么,我们每次要切的蚯蚓,只需要比较三个队列的头即可。这样的时间复杂度是$O(nlogn+m)$。

在这个基础上继续思考。

我们发现,由于每次+q,队列中所有元素的相对位置是不会发生变化的。

也就是说,我们可以用另外的一个变量在处理q(这个和用STL处理的时候类似),那么对于当前处理的,我们只要放进队里的时候-Q(表示当前总的q)即可,因为当前的放进的那个队列中一定是最小的,又由于当前次没有+q,只会更小,所以不会影响总体的顺序。

那么,复杂度类似的,仍然是$O(nlogn+m)$。

最后还有一个细节问题,是官网数据中没有涉及的,但UOJ的hack中有:

当u、v接近1000000000的时候,单纯的double处理会出现精度问题,为了避免这个问题,我们用$*u/v$代替$*p$来避免,但要注意开$long long$

90分程序

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#define LL long long

using namespace std;

priority_queue<int > Q;
int n,m,q,u,v,t,a[100010];
double p;

void read(int &x)
{
    x=0;char y=getchar();
    while (y<48 || y>48+9) y=getchar();
    while (y>=48 && y<=48+9) x=x*10+y-48,y=getchar();
}

char asdf[20];
void print(int x)
{
    if (x==0) putchar('0');
    int y=0;for (;x;x/=10) asdf[y++]=x%10+48;while (y--) putchar(asdf[y]);
} 

bool cmp(int x,int y)
{
    return x>y;
}
int x[100010],y[7000010],z[7000010];

int main()
{
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    p=(double)u/(double)v;
    if (q==0)
    {
        for (int i=1;i<=n;i++)
            read(a[i]);
        sort(a+1,a+1+n,cmp);
        int xl=0,yl=0,zl=0,xr=0,yr=0,zr=0;
        for (int i=1;i<=n;i++)
            x[++xr]=a[i];
        int o,y1,x2,T=0,i=0,X=1;
        while (m--)
        {
            i++;
            o=0;y1=0;
            if (xr-xl>0) if (x[xl+1]>o) o=x[xl+1],y1=1;
            if (yr-yl>0) if (y[yl+1]>o) o=y[yl+1],y1=2;
            if (zr-zl>0) if (z[zl+1]>o) o=z[zl+1],y1=3;
            if (y1==1) xl++;
            else if (y1==2) yl++;
            else zl++;
            if (X*t==i)
            {
                if (X==1) print(o);
                else putchar(' '),print(o);
                X++;
            }    
            y1=(int)(p*(double)(o));
            o=o-y1;
            y[++yr]=y1;z[++zr]=o;
        }
        i=0;X=1;
        putchar('\n');
        while (xr+yr+zr-xl-yl-zl>0)
        {
            o=0;y1=0;
            if (xr-xl>0) if (x[xl+1]>o) o=x[xl+1],y1=1;
            if (yr-yl>0) if (y[yl+1]>o) o=y[yl+1],y1=2;
            if (zr-zl>0) if (z[zl+1]>o) o=z[zl+1],y1=3;
            if (y1==1) xl++;
            else if (y1==2) yl++;
            else zl++;
            i++;
            if (X*t==i)
            {
                if (X==1) print(o+T);
                else putchar(' '),print(o+T);
                X++;
            }
        }    
        putchar('\n');
        return 0;
    }
    int x;
    for (int i=1;i<=n;i++)
        read(x),Q.push(x);
    int y,y1,z=0,i=0;x=1;
    while (m--)
    {
        i++;
        y=Q.top();
        Q.pop();
        if (x*t==i)
        {
            if (x==1) print(y+z);
            else putchar(' '),print(y+z);
            x++;
        }
        y1=(int)(p*(double)(y+z));
        y=y+z-y1;
        z+=q;
        Q.push(y1-z);Q.push(y-z);
    }
    putchar('\n');
    x=1,i=0;
    while (!Q.empty())
    {
        i++;
        if (x*t==i)
        {
            if (x==1) print(Q.top()+z);
            else putchar(' '),print(Q.top()+z);
            x++;
        }
        Q.pop();
    }
    putchar('\n');
    return 0;
}

满分代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#define LL long long

using namespace std;

void read(int &x)
{
    x=0;char y=getchar();
    while (y<48 || y>48+9) y=getchar();
    while (y>=48 && y<=48+9) x=x*10+y-48,y=getchar();
}

char asdf[20];
void print(int x)
{
    if (x==0) putchar('0');
    int y=0;for (;x;x/=10) asdf[y++]=x%10+48;while (y--) putchar(asdf[y]);
}

int n,m,q,u,v,t,a[100010],x[7000010],y[7000010],z[7000010];

bool cmp(int x,int y)
{
    return x>y;
}

int main()
{
    read(n);read(m);read(q);read(u);read(v);read(t);
    for (int i=1;i<=n;i++)
        read(a[i]);
    sort(a+1,a+1+n,cmp);
    int xl=0,xr=0,yl=0,yr=0,zl=0,zr=0;
    for (int i=1;i<=n;i++)
        x[++xr]=a[i];
    int Q=0,i=0,X=1,o,y1;
    while (m--)
    {
        i++;
        o=-INT_MAX;y1=0;
        if (xr-xl>0) if (x[xl+1]>o) o=x[xl+1],y1=1;
        if (yr-yl>0) if (y[yl+1]>o) o=y[yl+1],y1=2;
        if (zr-zl>0) if (z[zl+1]>o) o=z[zl+1],y1=3;
        if (y1==1) xl++;
        else if (y1==2) yl++;
        else zl++;
        o+=Q;Q+=q;
        if (X*t==i)
        {
            if (X==1) print(o);
            else putchar(' '),print(o);
            X++;
        }
        y1=(int)((LL)(o)*(LL)(u)/(LL)(v));
        o=o-y1;
        y[++yr]=y1-Q;z[++zr]=o-Q;
    }
    putchar('\n');
    i=0;X=1;
    while (xr+yr+zr-xl-yl-zl>0)
    {
        i++;
        o=-INT_MAX;y1=0;
        if (xr-xl>0) if (x[xl+1]>o) o=x[xl+1],y1=1;
        if (yr-yl>0) if (y[yl+1]>o) o=y[yl+1],y1=2;
        if (zr-zl>0) if (z[zl+1]>o) o=z[zl+1],y1=3;
        if (y1==1) xl++;
        else if (y1==2) yl++;
        else zl++;
        if (X*t==i)
        {
            if (X==1) print(o+Q);
            else putchar(' '),print(o+Q);
            X++;
        }
    }
    putchar('\n');
    return 0;
}

反思

总的来说,这道题目的算法并不是很难想到。

先前的Noip题中也有一道合并果子,因为可以直接用优先队列解,便没有深究。而其实,合并果子是有线性的做法的,也就是和上面所述的三个队列类似。

那么,这道题目就只能归结于平时做题的时候缺少思考,依赖于blog中的题解,没有独立思考的过程,没有去想更有的解法和策略。

这道题目,实际在考场的中的得分仅有65分,应该说,不考虑上述的情况,在考场上,应该是可以写出90分的算法的。而当时是觉得打个优先队列也有这么多分,就草草了事,去做T3了,而后来的话,似乎忘了这么一回事,一直在拍,在检查,没有想着去多拿一点分(结果连T1都跪了)。

愤怒的小鸟(angrybirds)

应该算是一道比较基础的状态压缩dp。

首先$O(n^2)$预处理。

表示确定两个点以后,我们可以求出抛物线的解析式,然后根据这个解析式求得有多少个点符合要求。

然后就是dp,f[i]表示状态为i(i转换为2进制以后,0表示不可行,1表示可行)最少需要多少次。

暴力背包转移即可。

这样的复杂度是$O(n^2*2^n)$,提出一种优化:

每次,对于一个状态,我们一定会将最前面的一个不可行的位置变为可行(因为最后一定要变为全部可行),那么,我们不需要每次都寻找$n^2$次,只需要对于当前的最前面一个不可行的位置找即可,这样,总的复杂度就变成了$O(n*2^n)$,但实际上,官方数据不需要优化。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#define LL long long

using namespace std;

int T,n,m,b[20],f[300010],c[400];
struct data
{
    double x,y;
}a[20];
const double EPS=1e-10;

int main()
{    
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
            scanf("%lf%lf",&a[i].x,&a[i].y);
         int s=0;
         for (int i=1;i<=n;i++)
             for (int j=i+1;j<=n;j++)
            {
                 double x1=a[i].x,y1=a[i].y,x2=a[j].x,y2=a[j].y,A,B;
                 if (x1*x1*x2!=x1*x2*x2)
                 {                                      
                     A=(x1*y2-x2*y1)/(x1*x2*x2-x1*x1*x2);
                     B=(y1-A*x1*x1)/x1;//A*x3*x3+B*x3-y1 
                     if (A<-EPS)// && abs(A-0)>1e-3)
                     {
                         s++;memset(b,0,sizeof(b));    //int q=0;
                         for (int k=1;k<=n;k++)
                         {
                             //printf("%0.30lf\n",A*a[k].x*a[k].x+B*a[k].x-a[k].y);
                             if (abs(A*a[k].x*a[k].x+B*a[k].x-a[k].y)<EPS) b[k]=1;
                         }
                         //if (q>=2) printf("%d %d\n",i,j); 
                         int t=0;
                        for (int k=1;k<=n;k++)
                            t=t<<1|b[k];
                        c[s]=t;
                    }
                 }
             }
        for (int j=(1<<(n))-1;j>=0;j--)
            f[j]=n;
        for (int i=1;i<=n;i++)
        {
            memset(b,0,sizeof(b));
            b[i]=1;
            int t=0;
            for (int k=1;k<=n;k++)
            t=t<<1|b[k];
            c[++s]=t;
        }
        f[0]=0;
        for (int i=1;i<=s;i++)
        {
            for (int j=(1<<(n))-1;j>=0;j--)
                f[j|c[i]]=min(f[j|c[i]],f[j]+1);
        }
        printf("%d\n",f[(1<<(n))-1]);
    }
    return 0;
}

反思

这道题目上的失误主要在于精度处理上的问题。

在联赛以前一直有这么一个心态:联赛肯定不会很难,所以在平时的训练中也会刻意的去回避这一类要处理精度的问题。

所以说,心态和策略的错误是这道题目的最大失误。

对于精度问题,犯了一下两个错误:

1、精度的问题,考虑的太少,我的eps只写了1e-4。看到成绩以后,发现这道题目拿了90分,一直以为是TLE。而在拿到官方数据以后,在发现是Wa,然后我把eps改成了1e-10,就过了。
2、在判断a<0的时候,忽略了精度问题(虽然不考虑也能A掉官方数据),应该改为a<-eps。

此类精度问题,在后面的训练中已经是不可回避的问题了,一定多做此类题目,增加处理精度的经验(记得在ZJOI2016上有过这样一份讲稿,要再去学习一下)。

总结

先说说今年的题目。

对这场Noip题目总的感觉是题目的顺序编排存在一定不合理性。

对于题目本身,Noip2016引入了从未有过的期望dp,对数据结构的考察在淡化。相对前几年,今年的题目更侧重与思考,减少了代码量。这应该也是以后算法竞赛的趋势吧。

但让我个人比较不爽的是,Noip对暴力选手过于照顾。尤其体现在D1T3上,暴力可以拿80分,这会让联赛没有区分度,让打残期望dp的选手(比如我)成为了名副其实的暴力选手,甚至分数还不如暴力选手。当然,对于D1T2这样,暴力可以有80分的题目,我个人还是比较提倡的。因为80分来自不同的部分,这样会体现出选手的不同能力水平。

扯了那么多,有什么用。

还是说说自己吧。

这场Noip考得非常差。

先前公开了一篇Noip酱油记(空间日志),迟迟没有公开的原因就是在测了余姚中学的数据以后,已经意识到了问题的严重性。

考完两场考试,回来的车上,估了一下自己的分数(即那篇酱油记中所述),怎么算都不会低于450,觉得不管怎样,卡个一等应该没什么大问题。也不会对后面的OI路造成非常大的影响。

但余姚中学的数据,我的测试结果是339,最终ccf的测试结果是396。

这是一个极差的分数,和我去年滚粗的成绩差不多。

简单地来说,和估分的主要差距在于D1T3最短路弄错,丢24分;D2T1出现制杖性错误,丢60分,这样加上去,和估分差不多。

成绩出来后,一度想过放弃,想过退役。但说实话,OI这七年一路走过来实则不易。

小学五年级下半年,宁波市比赛初赛狗带,六年级上半年慈溪市初赛狗带。当时还以初赛不好、复赛好为理由搪塞自己和父母,现在想来真是可笑至极(想想自己,也是从小学五年级开始学的,到了现在还不如那些初中开始的)。

初中的OI表面上看起来很顺利,初一二等,初二全省20,初三全省第一,一路上升。但其实背后,有非常惨烈的现实:难度相对比较高的宁波市比赛,除了初三获得二等第一以外,其余两年全部狗带。

现在看来,是Noip普及组的成绩使自己自负了,使自己觉得已经有了相当的OI水平。

那时候,除了偶尔做几道USACO,其余基本全是水水题。那时候根本不是道什么Codeforces,就连知道的poj也觉得是英文题而望而却步。初中的三年,浪费了。到了高中,本身课业繁忙,留给OI的时间没有初中那么充裕了,也是到了这时候,我才意识到初中都干什么去了。

但现在,到了这个时候,说这些过去的都是徒劳。

现在是12月中旬,Noip后的一个月。前一个月又是浑浑噩噩的过去了。

现在最主要的是要调整好自己的心态,找到自己的问题所在。为什么联赛后连续两点狗带,这不是运气的问题。这一定是自己实力的问题,平时的代码量不够,平时的训练不够,应考能力不强,临场发挥不好等等都是问题所在。

既然觉得自己到了这时候不应该放弃,上天也眷顾我送了一个一等。

我会以这次Noip为契机,更加努力的奋斗。

义无反顾的继续走下去。不管还要经历多少困苦,不管最后的结局如何。

自己选择的路,怎能轻言放弃,就算跪着也要走下去。

猛然忆起上林OJ曾经滚动的一句话:静心思考,反思过去

附件:Noip2016酱油记,一篇毫无营养的流水账,不过还是骗一波访问量吧 地址

评论

Smallnumber
前排留名
Archon
滋磁 ,加油!
BillXu2000
合并果子是指huffman编码吗?球教如何做到线性
cxzxxjd
@BillXu2000 回复里放不下QAQ 开两个队列,一个保存排序后的未合并果子,另一个队列保存合并后的果子,可以保证两个队列有序,那么每次取两个队头较小的,复杂度线性
cwystc
AntiLeaf
orz 已跪烂 话说D1T2的反思和D1T3的思路和代码被吃了......

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。