1005 csp-s 60 凉凉

T1 嘟嘟噜

上来一看数据范围1e9就蒙蔽，然后不知所措的打了一个 $ O（n）$的无脑算法，由于本人真的脑小，导致O（n）的柿子推了好长时间，导致心态崩了，然后........ 今天能明白了log的算法，算是约瑟夫问题弄明白了，没有想到跳跃式的竟然可以log求。

#include<bits/stdc++.h>

using namespace std;

#define re register

inline int read()

{

    int x=,f=;char cc=getchar();

    while(cc>''||cc<''){if(cc=='-')f=-;cc=getchar();}

    while(cc>=''&&cc<=''){x=(x<<)+(x<<)+cc-'';cc=getchar();}

    return x*f;

}

const int maxn=;

int n,k,m,S;

int ans[maxn];

queue<int>q;

set<int>pc,fc;

stack<int>s;

int main()

{

    n=read(),k=read(),m=read(),S=read();

    for(int i=,u;i<=m;i++)

    {

        u=read();

        ans[u]=-;

    }

    q.push(S);

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

        if(i!=S&&ans[i]!=-)

        {

            if(i&)pc.insert(i);

            else fc.insert(i);

        }

    while(q.size()&&(!pc.empty()||!fc.empty()))

    {

        int x=q.front();q.pop();

        if((x&)==(k&))

        {

            for(auto it=pc.lower_bound(max(x-k+,k-x));it!=pc.end()&&*it<x+k;++it)

            {

                int zz=(k-(abs(x-*it)+))>>;

                if(zz>n-max(*it,x))break;

                q.push(*it);

                ans[*it]=ans[x]+;

                s.push(*it);

            }

            while(s.size())pc.erase(s.top()),s.pop();

            continue;

        }

        for(auto it=fc.lower_bound(max(x-k+,k-x));it!=fc.end()&&*it<x+k;++it)

        {

            int zz=(k-(abs(x-*it)+))>>;

            if(zz>n-max(*it,x))break;

            ans[*it]=ans[x]+;

            q.push(*it);

            s.push(*it);

        }

        while(s.size())fc.erase(s.top()),s.pop();

    }

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

    {

        if(!ans[i]&&(i!=S))ans[i]=-;

        printf("%d ",ans[i]);

    }

    return ;

}

T2 天才绅士少女助手克里斯蒂娜

看题就发现是原题，然后想到当时自己连题解都没有颓，就崩了，然后想到当时就是wba大神造的数据，我就感到了一丝不妙，其实就是拆一下柿子就出来了！

然后我就怀着爆零的心情去看T3

#include<bits/stdc++.h>

using namespace std;

#define int long long

inline int read()

{

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

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=;

const int mod=;

int n,m;

struct BIT

{

    int tr[maxn];

    inline int lowbit(int x){return x&(-x);}

    inline int query(int x)

    {

        int res=;

        while(x)

        {

            (res+=tr[x]+mod)%=mod;

            x-=lowbit(x);

        }

        return res;

    }

    inline void update(int x,int val)

    {

        while(x<=n)

        {

            (tr[x]+=val+mod)%=mod;

            x+=lowbit(x);

        }

        return ;

    }

}t1,t2,t3;

int a1[maxn],a2[maxn],a3[maxn];

struct node

{

    int x,y;

    inline void make(int _x,int _y){x=_x,y=_y;return ;}

}s[maxn];

signed main()

{

    //freopen("inputs2.in","r",stdin);

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

    for(int i=,x,y;i<=n;i++)

    {

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

        s[i].make(x,y);

    }

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

    {

        a1[i]=(s[i].x*s[i].x%mod)%mod;

        a2[i]=(s[i].y*s[i].y%mod)%mod;

        a3[i]=(s[i].x*s[i].y%mod)%mod;

        t1.update(i,a1[i]);

        t2.update(i,a2[i]);

        t3.update(i,a3[i]);

    }

    int opt=;

    while(m--)

    {

        opt=read();

        if(opt==)

        {

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

            s[p].x=x,s[p].y=y;

            int c1=a1[p],c2=a2[p],c3=a3[p];

            a1[p]=x*x%mod,a2[p]=y*y%mod;a3[p]=x*y%mod;

            t1.update(p,a1[p]-c1);

            t2.update(p,a2[p]-c2);

            t3.update(p,a3[p]-c3);

        }

        else

        {

            int l=read(),r=read();

            int ans=;

            ans=((t1.query(r)-t1.query(l-)+mod)%mod*(t2.query(r)-t2.query(l-)+mod)%mod+mod)%mod;

            int tt=((t3.query(r)-t3.query(l-)+mod)%mod+mod)%mod;

            ans=((ans-tt*tt%mod+mod)%mod+mod)%mod;

            printf("%lld\n",ans);

        }

    }

    return ;

}

就是一个LCIS，当时学的时候还被人消费来着（LSC LCIS）然后在看出是dp之后由于剩的时间过少，还想调T2所以直接打的爆搜，按说应该可以20分，但是只有10分，

3
考虑 DP. 设状态 dp(i, j) 表示 a 序列考虑到 i, b 序列考虑到 j 并且必须选 b j 的最
大长度. 当 a i = b j 时, 显然有转移 dp(i, j) = max k<j,b k <b j {dp(i − 1, k)} + 1.
于是从小到大枚举 j, 维护 max k<j,b k <a i {dp(i − 1, k)}, 直接转移即可.
时间复杂度 O(nm).

由于前几场考试T1过于水，导致之前的T1都切了，而且一般20分钟之内就可以A，所以这次T1拖了1个小时，就心态炸了，还是要历练！@……@

#include<bits/stdc++.h>

using namespace std;

#define re register

#define LL long long

template<class T>

inline void read(T &x)

{

    T f=;x=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    x=x*f;

}

int n,m;

const int maxn=;

LL a[maxn],b[maxn];

bool vis[maxn];

int ch[maxn],tot;

int dp[maxn][maxn];

int pre[maxn][maxn];

int sta[maxn],topp;

inline void ba(re int x,re int y)

{

    if(x==||y==)return;

    re int qq=pre[x][y];

    if(y!=qq)sta[++topp]=b[y];

    ba(x-,qq);

}

signed main()

{

    //freopen("inputs3.in","r",stdin);

    read(n);

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

        read(a[i]);

    read(m);

    for(re int i=;i<=m;i++)

        read(b[i]);

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

    {

        int res=,id=;

        if(b[]<b[])res=dp[i-][],id=;

        for(re int j=;j<=m;j++)

        {

            if(a[i]==b[j])

            {

                pre[i][j]=id;

                dp[i][j]=res+;

            }

            else

            {

                pre[i][j]=j;

                dp[i][j]=dp[i-][j];

            }

            if(b[j]<a[i])

            {

                if(res<=dp[i-][j])

                {

                    res=dp[i-][j],id=j;

                }

            }

        }

    }

    int ans=,id=;

    for(re int i=;i<=m;i++)

    {

        if(dp[n][i]>=ans)ans=dp[n][i],id=i;

    }

    printf("%d\n",dp[n][id]);

    ba(n,id);

    while(topp)

    {

        printf("%d ",sta[topp]);

        topp--;

    }

    return ;

}

巴特西

1005 csp-s 60 凉凉

最新文章

热门文章