打开题面，T3似乎被换过了。(那我就更有理由直接弃掉了)

T1是我最害怕的乱搞题，赶紧扔了看T2。发现是个sb板子？雨天的尾巴弱化版？

然而线段树合并早忘干净了(最近几道可以线段树合并的题都是用别的方法做的QAQ)。yy了半天尝试码了一下发现完美爆炸，内心慌的一批，不停在想这水题现在得有多少多少人切了。

出去上了个厕所，期间被原先的同学抓住问了几句，回来感觉心态稍好。很快搞出一个$O(n^2\ log\ n)$的做法调了出来，感觉数据范围刚好不会被卡。然后开始肝T1，尝试了各种奇特办法都以码力不够(其实是思路太鬼畜)而告终。两个小时啥也没干无奈之下乱打了一个随机化扔了。中间突然想到T2线段树合并应该怎么写，但是觉得之前的做法也没问题就懒得改了。T3最后没读懂题暴力打挂。

……

T2果然被卡了。T1随机化突然不靠谱。

刚有几场考的凑合就又炸了，知识漏洞还是太多。

往好处想这次考试至少重新理解了线段树合并这个知识点，以后肯定不会出问题了。

至于乱搞题不会做，这只能说自己思维太死板，只会套学过的模式，遇到完全需要自己研究的就什么也想不出来了。有思维习惯的原因，但更多的还是缺乏练习，没有养成良好的思考方式。

A.Emotional Flutter

只要确定了出发点，那么每一步的位置就都确定了。

把黑块的边界通过$mod\ K$处理一下，把它们映射到$[0,K-1]$里。之后将区间排序，判断是否有连续的s个合法位置即可。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

const int N=5e5+5;

#define pa pair<int,int>

int S,K,n,a[N],T;

pa p[N];

void work()

{

    S=read();K=read();n=read();

    for(int i=1;i<=n;i++)

        a[i]=read();

    int sum=0,cnt=0;

    for(int i=1;i<=n;i++)

    {

        sum+=a[i];

        if((i&1)==0)continue;

        if(a[i]>=K)

        {

            puts("NIE");

            return ;

        }

        int lp=sum-a[i],rp=sum-1,bl=lp/K,br=rp/K;

        sum%=K;

        if(bl>=br)p[++cnt]=make_pair(lp%K,rp%K);

        else

        {

            p[++cnt]=make_pair(lp%K,K-1);

            p[++cnt]=make_pair(0,rp%K);

        }

    }

    sort(p+1,p+cnt+1);

    int res=0,x=-1;

    for(int i=1;i<=cnt;i++)

    {

        res=max(res,p[i].first-x-1);

        x=max(x,p[i].second);

    }

    res=max(res,p[1].first+K-x-1);

    if(res>=S)puts("TAK");

    else puts("NIE");

}

int main()

{

    T=read();

    while(T--)work();

    return 0;

}

B.Endless Fantasy

裸的线段树合并。注意到合并到叶结点时的信息处理。

#include<cstdio>

#include<iostream>

#include<cstring>

typedef long long ll;

#define pa pair<ll,int>

using namespace std;

const int L=1<<20|1;

char buffer[L],*S,*T;

#define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

const int N=4e5+5;

int n,m;

int to[N<<1],head[N],nxt[N<<1],tot;

pa ans[N];

void add(int x,int y)

{

    to[++tot]=y;

    nxt[tot]=head[x];

    head[x]=tot;

}

int type,root[N<<5],ls[N<<5],rs[N<<5],maxx[N<<5];

ll maxw[N<<5];

void up(int k)

{

    if(maxw[ls[k]]>=maxw[rs[k]])

    {

        maxw[k]=maxw[ls[k]];

        maxx[k]=maxx[ls[k]];

    }

    else

    {

        maxw[k]=maxw[rs[k]];

        maxx[k]=maxx[rs[k]];

    }

}

void update(int &k,int l,int r,int pos,int num)

{

    if(!k)k=++type;

    if(l==r)

    {

        maxw[k]+=num;

        maxx[k]=pos;

        return ;

    }

    int mid=l+r>>1;

    if(pos<=mid)update(ls[k],l,mid,pos,num);

    else update(rs[k],mid+1,r,pos,num);

    up(k);

}

int merge(int x,int y,int l,int r)

{

    if(!x||!y)return x+y;

    if(l==r)

    {

        maxw[x]=maxw[x]+maxw[y];

        maxx[x]=l;

        return x;

    }

    int mid=l+r>>1;

    ls[x]=merge(ls[x],ls[y],l,mid);

    rs[x]=merge(rs[x],rs[y],mid+1,r);

    up(x);

    return x;

}

void dfs(int x,int f)

{

    for(int i=head[x];i;i=nxt[i])

    {

        int y=to[i];

        if(y==f)continue;

        dfs(y,x);

        merge(root[x],root[y],1,m);

    }

    ans[x]=make_pair(maxw[root[x]],maxx[root[x]]);

}

int main()

{

    n=read();m=read();

    for(int i=1;i<n;i++)

    {

        int x=read(),y=read();

        add(x,y);add(y,x);

    }

    for(int i=1;i<=n;i++)

    {

        int x=read(),w=read();

        update(root[i],1,m,x,w);

    }

    dfs(1,0);

    for(int i=1;i<=n;i++)

        printf("%d %lld\n",ans[i].second,ans[i].first);

    return 0;

}

C.

不会做啊

巴特西

[CSP-S模拟测试47]反思+题解

A.Emotional Flutter

B.Endless Fantasy

C.

最新文章

热门文章