CF771

A

题意:给定一个\(1\sim n\)的排列,选择一段区间\([l,r]\),把这段区间翻转一下,使得翻转后排列的字典序最小

\(n\leq 500\)

题解:

由于是排列,所以每一位上的数字各不相同。根据贪心的想法,我们想让这个序列最靠前的地方变得尽可能的小。所以只要找到最靠前的一个位置\(i\),让我们有比它小的数字,然后用它和它后面最小的数字作为左右端点\(l,r\),翻转中间部分。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e6+10,mod=1e9+7,inf=2e9;
    int n,pos1,pos2;
    int a[N];
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        int T;cin>>T;
        while(T--)
        {
            cin>>n;
            pos1=n,pos2=0;
            for(int i=1;i<=n;++i)
            {
                cin>>a[i];
                for(int j=1;j<i;++j)
                {
                    if(a[j]>a[i]&&(j<pos1||(j==pos1&&a[i]<a[pos2])))
                    {
                        pos1=j,pos2=i;
                    }
                }
            }
            if(pos2) reverse(a+pos1,a+pos2+1);
            for(int i=1;i<=n;++i) cout<<a[i]<<' ';
            cout<<'\n';
        }
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/

B

题意:

给定一个序列\(A\),如果相邻两项\(a_i\)和\(a_{i+1}\)奇偶性不同,就可以交换相邻两项,求问能不能通过交换让序列变得不下降(即对任意\(1\leq j<n,a_j<=a_{j+1}\))

\(n\leq 1e5\)

题解:

对整个序列来说,序列中的所有奇数的相对位置永远不会改变,而奇数和偶数的相对位置可以随意交换。同理,所有偶数的相对位置永远不会改变。

所以只要判断,序列中所有的奇数是不是不下降的,所有的偶数是不是不下降的。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e6+10,mod=1e9+7,inf=2e9;
    int n;
    int a[N];
    int pre[2];
    inline void main()
    {   
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        int T;cin>>T;
        while(T--)
        {
            cin>>n;
            bool flag=1;
            for(int i=1;i<=n;++i) cin>>a[i];
            pre[0]=pre[1]=0;
            for(int i=1;i<=n;++i)
            {
                int b=a[i]&1;
                if(a[i]<pre[b]) flag=0;
                pre[b]=a[i];
            }
            if(flag) cout<<"YES\n";
            else cout<<"NO\n";
        }
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/

C

题意:给定一个序列\(A\),如果\(i<j\)并且\(a_i>a_j\),就把\(i\)和\(j\)连起来,问最后一共有几个互不相连的部分?

\(n\leq 2e5\)

题解:

如果暴力去实现这个过程无疑是\(O(n^2)\)的,但是观察暴力连边的过程

CF771

这样子,\(<6,1>\)之间很明显不用连边,因为\(6\)的右边有一个\(2\),它比\(1\)要大,如果\(2\)向\(1\)连了边,\(6\)又向\(2\)连了边,那么\(<6,1>\)这条边就很多余。

所以说,我们每个数字向右需要连边的数字一定是\((2,4,…)\)这样递增的。

那么就用一点技巧来做:倒着遍历这个序列,然后顺便维护一个从\(i+1\)到\(n\)的递增的一个序列。

但是有一点小bug:

如果是\(6,4,7,1\)

那么\(6\)右边递增的序列应该是\(4,7\)

\(6<7\),所以\(6\)不会向\(7\)连边,但是\(7>1\),\(6\)本来应该向\(1\)连边的,这里没有\(1\),而是被\(7\)给挤出去了。

所以应该算一下每一个位置上数字连到数字中的最大值和最小值。

如果现在往右连边的数字的最大值,大于,右边那个数字连到数字的最小值,就可以连。

这样每连一条边,互不相连部分的个数就减一。可以证明每条边都是有用的,不会导致已经联通的部分重复连接。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e6+10,mod=1e9+7,inf=2e9;
    int n;
    int a[N];
    int st[N],top;
    int maxn[N],minn[N],col[N];
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        int T;cin>>T;
        while(T--)
        {
            cin>>n;top=0;
            for(int i=1;i<=n;++i)
            {
                cin>>a[i];
                col[i]=i;
                maxn[i]=minn[i]=a[i];
            }
            int sum=n;
            for(int i=n;i;--i)
            {
                while(top&&maxn[col[i]]>minn[col[st[top]]])
                {
                    maxn[col[st[top]]]=max(maxn[col[i]],maxn[col[st[top]]]);
                    minn[col[st[top]]]=min(minn[col[i]],minn[col[st[top]]]);
                    col[i]=col[st[top]];
                    --top;
                    --sum;
                }
                st[++top]=i;
            }
            cout<<sum<<'\n';
        }
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/

D

题意:有一个\(n*m\)的画布,每次会选一个格子\((x,y)\),然后把\((x,y),(x+1,y),(x,y+1),(x+1,y+1)\)涂成同一种颜色,后涂的覆盖先涂的,问存不存在一种涂色方法,把画布最后涂成给定的模样。

\(n\leq 1000\)

题解:

因为后来的覆盖先来的,正着涂色要考虑覆盖问题。所以把这个问题倒着做。

问题变成了,每次选一个格子\((x,y)\),然后把\((x,y),(x+1,y),(x,y+1),(x+1,y+1)\)上的颜色都擦掉,前提是这四个格子中有且仅有一种颜色,问能不能把整个画布上的颜色全擦了。然后把擦颜色的顺序倒着输出出来,就是涂色顺序。

擦颜色就很方便,因为不用考虑后来的覆盖问题,能擦哪里擦哪里就可以。

但是不能每次都把整个画布检查一遍,来决定擦哪里。

我们可以把一开始就能擦的地方放进队列里。然后如果某一个地方,它之前不能擦,而现在能擦了,那么这个地方一定在上一次擦除地方的周围一圈。所以每擦一个地方的颜色,就检查一下周围一圈是不是新出现了可以擦去的地方,可以擦去就放进队列。

因为以每个地方只会擦一次,所以最后复杂度是\(O(n*m)\)的

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e6+10,mod=1e9+7,inf=2e9;
    int n,m;
    bool vis[1010][1010];//有没有被擦过
    bool vis2[1010][1010];//是不是以这个格子为基准点擦颜色了
    int a[1010][1010];
    int top;
    struct node
    {
        int x,y,z;
    };
    node st[N];
    queue<node> q;
    inline int check(int i,int j)
    {
        if(i<1||j<1||i>n||j>m) return 0;
        int col=0;
        if(!vis[i][j]) col=a[i][j];
        else if(!vis[i+1][j]) col=a[i+1][j];
        else if(!vis[i][j+1]) col=a[i][j+1];
        else if(!vis[i+1][j+1]) col=a[i+1][j+1];
        if((col==a[i][j]||vis[i][j])&&(col==a[i+1][j+1]||vis[i+1][j+1])&&(col==a[i+1][j]||vis[i+1][j])&&(col==a[i][j+1]||vis[i][j+1])) return col;
        return 0;
    }
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        cin>>n>>m;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j) cin>>a[i][j];
        for(int i=1;i<n;++i)
        {
            for(int j=1;j<m;++j)
            {
                if(check(i,j)) q.push((node){i,j,a[i][j]});
            }
        }
        while(!q.empty())
        {
            int x=q.front().x,y=q.front().y;
            if(vis2[x][y]){q.pop(); continue;}
            st[++top]=q.front();
            q.pop();
            vis2[x][y]=1;
           // cout<<x<<' '<<y<<"!!"<<endl;
            vis[x][y]=vis[x+1][y]=vis[x][y+1]=vis[x+1][y+1]=1;
            int tmp;
            if((tmp=check(x-1,y))&&!vis2[x-1][y]) q.push((node){x-1,y,tmp});
            if((tmp=check(x+1,y))&&!vis2[x+1][y]) q.push((node){x+1,y,tmp});
            if((tmp=check(x,y-1))&&!vis2[x][y-1]) q.push((node){x,y-1,tmp});
            if((tmp=check(x,y+1))&&!vis2[x][y+1]) q.push((node){x,y+1,tmp});
            if((tmp=check(x+1,y+1))&&!vis2[x+1][y+1]) q.push((node){x+1,y+1,tmp});

        }
        bool flag=1;
        for(int i=1;i<n;++i)
        {
            for(int j=1;j<m;++j)
            {
                if(!vis[i][j]) flag=0; 
            }
        }
        if(!flag) cout<<"-1\n";
        else
        {
            cout<<top<<'\n';
            while(top)
            {
                cout<<st[top].x<<' '<<st[top].y<<' '<<st[top].z<<'\n';
                --top;
            }
        }
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/

E

题意:

给定数组\(A\),初始时值都是\(0\),颜色都是\(1\)

有以下操作:

\(1:\)把区间\([l,r]\)涂成颜色\(c\)

\(2:\)把所有颜色为\(c\)的格子加\(val\)

\(3:\)查询\(pos\)位置的值

解答:

肯定不能不连续的给区间加数,考虑线段树颜色均摊。用一个全局标记记录每个颜色的值的改变量,当改变某个位置上的颜色时,把这段区间先加上原来颜色的改变量,再减去当前颜色的改变量。这样两次赋值之间的颜色改变量就留在位置上了。

当查询一个颜色为\(c\)的点值时,返回\(ans[pos]+tag[c]\)。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e6+10,mod=1e9+7,inf=2e9;
    int n,m;
    string opt;
    int sum[N];
    struct segment_tree
    {
        int tag1[N<<2],tag2[N<<2];
        int col[N<<2];
        inline void build(int l,int r,int p)
        {
            col[p]=1;
            if(l==r) return;
            build(l,mid,ls(p));
            build(mid+1,r,rs(p));
        }
        inline void tag_union(int p,int c,int k)
        {
            tag1[p]+=k;
            if(c)col[p]=c,tag2[p]=c;
        }
        inline void pushdown(int p)
        {
            tag_union(ls(p),tag2[p],tag1[p]);
            tag_union(rs(p),tag2[p],tag1[p]);
            tag1[p]=tag2[p]=0;
        }
        inline void update(int tl,int tr,int l,int r,int p,int c)
        {
            if(col[p]&&tl<=l&&r<=tr)
            {
                tag_union(p,c,sum[col[p]]-sum[c]);
                return;
            }
            if(tag1[p]||tag2[p]) pushdown(p);
            if(tl<=mid) update(tl,tr,l,mid,ls(p),c);
            if(tr>mid) update(tl,tr,mid+1,r,rs(p),c);
            if(col[ls(p)]==col[rs(p)]) col[p]=col[ls(p)];
            else col[p]=0;
        }
        inline int query(int pos,int l,int r,int p)
        {
            if(l==r) return tag1[p]+sum[col[p]];
            if(tag1[p]||tag2[p]) pushdown(p);
            if(pos<=mid) return query(pos,l,mid,ls(p));
            return query(pos,mid+1,r,rs(p));
        }
    }T;
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        cin>>n>>m;
        T.build(1,n,1);
        for(int i=1;i<=m;++i)
        {
            cin>>opt;
            if(opt[0]=='C')
            {
                int x,y,z;cin>>x>>y>>z;
                T.update(x,y,1,n,1,z);
            }
            if(opt[0]=='A')
            {
                int x,y;cin>>x>>y;
                sum[x]+=y;
            }
            if(opt[0]=='Q')
            {
                int x;cin>>x;
                cout<<T.query(x,1,n,1)<<'\n';
            }
        }
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/

F

题意:

给\(n\)个数字,进行至多两次操作:每次选择一段区间\([l,r]\),然后把区间内的数字都减去\(x(x\leq min\{a_l,…a_r\})\),获得贡献\(x*(r-l+1)\),求最大贡献。

考虑两次区间的覆盖情况:相离,相交,覆盖。

相离:

很好做,两边分别做一个经典单调栈。

相交:

如果重复区间是\([l,r]\),其中最小值是\(h\),一条线往左扩展,另一条线往右扩展。

那么左边对某个位置\(i<l\)来说,它\([i,r]\)的最小值\(min_1\)决定了它的高度上限。而右边我们只能选择高度不超过\(h-min_1\)的部分。可以发现这部分可以用双指针实现。

右侧同理。

覆盖:

还是双指针,更好想。

就是他妈的难写,焯,还\(√ 8\)的卡常

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-8)
    const int N=1e4+10,mod=1e9+7,inf=2e9;
    int n,ans;
    int a[N];
    int pre[N],suf[N];
    int minn[N];
    int tmp[N];
    signed tl[N],tr[N],st[N],top;
    inline void work(int l,int r)
    {
        top=0;
        for(int i=l;i<=r;++i)
        {
            while(top&&a[st[top]]>a[i])
            {
                tr[st[top--]]=i;
            }
            st[++top]=i;
        }
        while(top) tr[st[top--]]=r+1;
        for(int i=r;i>=l;--i)
        {
            while(top&&a[st[top]]>a[i])
            {
                tl[st[top--]]=i;
            }
            st[++top]=i;
        }
        while(top) tl[st[top--]]=l-1;
    }
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        cin>>n;
        for(int i=1;i<=n;++i) cin>>a[i];
        for(int i=1;i<=n;++i)
        {
            int minn=a[i];
            for(int j=i;j<=n;++j)
            {
                minn=min(minn,a[j]);
                pre[j+1]=max(pre[j+1],minn*(j-i+1));
                suf[i]=max(suf[i],minn*(j-i+1));
            }
        }
        for(int i=0;i<=n+1;++i)
        {
            for(int j=i;j<=n;++j)
            {
                ans=max(ans,pre[i]+suf[j]);
            }
        }
        work(1,n);
        for(int i=1;i<=n;++i)
        {
            int l=tl[i]+1,r=tr[i]-1;
            minn[l]=a[l];
            for(int j=l+1;j<=n;++j) minn[j]=min(minn[j-1],a[j]);
            for(int j=n;j>r;--j) tmp[j]=max(minn[j]*(j-l+1),tmp[j+1]);
            minn[r]=a[r];
            for(int j=r-1;j>=1;--j) minn[j]=min(minn[j+1],a[j]);
            for(int j=1;j<l;++j) tmp[j]=max(minn[j]*(r-j+1),tmp[j-1]);
            int t1=n,qaq=a[i];
            int t2=r;
            minn[l]=a[l];
            for(int j=l+1;j<=n;++j) minn[j]=min(minn[j-1],a[j]);
            for(int j=l-1;j>=1;--j)
            {
                if(a[j]<qaq) qaq=a[j];
                while(t1>r&&minn[t1]+qaq<a[i]) --t1;
                ans=max(ans,qaq*(r-j+1)+tmp[t1+1]);
                ans=max(ans,qaq*(r-j+1)+(a[i]-qaq)*(t1-l+1));
                while(t2<n&&a[t2+1]>=qaq) ++t2;
                ans=max(ans,qaq*(l-j+t2-r)+a[i]*(r-l+1));
            }

            minn[r]=a[r];
            for(int j=r-1;j>=1;--j) minn[j]=min(minn[j+1],a[j]);
            t1=1,t2=l,qaq=a[i];
            for(int j=r+1;j<=n;++j)
            {
                if(a[j]<qaq) qaq=a[j];
                while(t1<l&&minn[t1]+qaq<a[i]) ++t1;
                ans=max(ans,qaq*(j-l+1)+tmp[t1-1]);
                ans=max(ans,qaq*(j-l+1)+(a[i]-qaq)*(r-t1+1));
                while(t2>1&&a[t2-1]>=qaq) --t2;
                ans=max(ans,qaq*(j-r+l-t2)+a[i]*(r-l+1));
            }
        }
        cout<<ans<<'\n';
    }
}
signed main()
{
    red::main();
    return 0;   
}
/*

*/
上一篇:初学算法-----分而治之-为何分治有更快的速度


下一篇:CF662C Binary Table——FWTXOR