8.7模拟赛小结

· · 个人记录

T1 转圈圈

题目大意：给你一个只含有一个1的01串S 每次你可以翻转一段区间为k的子串 且给出m个禁止位置 必须保证1在任何时刻都不能出现在静止位置上

对于每个位置i 给出旋转到i位置时的最小次数 无法旋转到这个位置时输出-1

思考：原题要求我们每次枚举一段区间翻转 我们可以判断k的奇偶然后暴力 BFS 来搞 这样子可以保证最小次数 时间复杂度O(nk) 期望得分 56pts

继续探究： 为什么会TLE？我们重复访问了一个区间的点太多次了！怎么优化呢？开个 set 就行了 时间复杂度降至O(nlogn) 期望得分 100pts

注意：set并不能动态删点 所以要开一个栈或者队列存下要删的点统一删 56pts Code:

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,k,m,s;
int a[N],w[N],vis[N];
int q[N],l,r;
void bfs()
{
    q[++r]=s;
    vis[s]=1;
    w[s]=0;
    while(l<r)
    {
        int x=q[++l];
        if(k&1)
        {
            for(int i=max(1,x-k+1);i<=x;i++)
            {
                int mid=(i+i+k-1)/2;
                int pos=mid-(x-mid);
                if(a[pos]) continue;
                if(i+k-1>n) break;
                if(vis[pos]) continue;
                q[++r]=pos;
                vis[pos]=1;
                w[pos]=w[x]+1;
            }
        }
        else
        {
            for(int i=max(1,x-k);i<=x;i++)
            {
                int mid=(i+i+k-1)/2;
                int pos=mid-(x-mid)+1;
                if(i+k-1>n) break;
                if(a[pos]) continue;
                if(vis[pos]) continue;
                q[++r]=pos;
                vis[pos]=1;
                w[pos]=w[x]+1;
            }
        }
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&k,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        a[x]=1;
    }
    bfs();
    for(int i=1;i<=n;i++)
    {
        if(vis[i])printf("%d ",w[i]);
        else printf("-1 ");
    }   
    return 0;
}

AC code

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,k,m,st;
int a[N],w[N],vis[N];
int q[N],l,r;
int del[N],len;
set<int> s[2];
void bfs()
{
    fill(w+1,w+1+n,-1);
    q[++r]=st;
    w[st]=0;
    while(l<r)
    {
        int x=q[++l];
        if(k&1)
        {
            int mid=(max(1,x-k+1)*2+k-1)/2;
            int pos=mid*2-x-2;
            int times=min(x,n+1-k)-max(1,x-k+1)+1;
            int lpos=pos+2,rpos=pos+times*2;
            set<int>::iterator ls=s[x&1].lower_bound(lpos),rs=s[x&1].upper_bound(rpos);

            len=0;
            for(set<int>::iterator it=ls;it!=rs;it++)
            {
                pos=*it;
                del[++len]=pos;
                q[++r]=pos;
                w[pos]=w[x]+1;
            }
            for(int i=1;i<=len;i++)
                s[x&1].erase(del[i]);
        }
        else
        {
            int mid=(max(1,x-k)*2+k-1)/2;
            int pos=mid*2-x+1-2;
            int times=min(x,n+1-k)-max(1,x-k)+1;
            int lpos=pos+2,rpos=pos+times*2;
            set<int>::iterator ls=s[pos&1].lower_bound(lpos),rs=s[pos&1].upper_bound(rpos);
            len=0;
            for(set<int>::iterator it=ls;it!=rs;it++)
            {
                pos=*it;
                del[++len]=pos;
                q[++r]=pos;
                w[pos]=w[x]+1;
            }
            for(int i=1;i<=len;i++)
                s[pos&1].erase(del[i]);
        }
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&k,&m,&st);
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        a[x]=1;
    }
    for(int i=1;i<=n;i++) 
        if(i!=st&&!a[i]) s[i&1].insert(i);
    bfs();
    for(int i=1;i<=n;i++)
        printf("%d ",w[i]);
    return 0;
}

T2 扌舌 口丂 匚儿 酉己

疑云顶针 鉴定为纯纯迷惑

思考：

部分分1

先想全为?的10pts部分分 发现只要区间长度为偶数即合法

那么容易发现公式为：

\left\lfloor \frac{n}{2} \right\rfloor \cdot \left\lceil \frac{n}{2} \right\rceil

期望得分10pts

部分分2

考虑O(n^3)的做法

怎么才能匹配一段括号呢？

如果同时满足三个区间 明显为匹配区间

为什么？

那么其实可以保证构造出一种方案 使得这段串合法 我们可以预处理整个前后缀数组 然后其实 $a_i-a_j>0 \to a_i>a_j

根据以上推导 我们可以推导出O(n^3)的做法：

通过O(n^2)枚举区间 然后暴力O(n)判断

期望得分20pts

Code

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
string s;
ll ans,s1[N],s2[N];
int main()
{
    cin>>s;
    for(int i=1;i<=s.size();i++)
        s1[i]=s1[i-1]+(s[i-1]==')' ? -1:1);
    for(int i=s.size();i>=1;i--)
        s2[i]=s2[i+1]+(s[i-1]=='('?-1:1);
    for(int i=1;i<=s.size();i++)
    {
        for(int j=1;j<i;j++)//枚举 j~i 
        {
            int p=1;
            if((j-i+1)&1) continue;
            for(int k=j;k<=i;k++)
                if(s1[k]<s1[j-1]||s2[k]<2[i+1]) p=0;
            ans+=p;
        }
    }
    cout<<ans;
    return 0;
}

部分分3

考虑优化O(n^3)做法

容易发现代码 ``` for(int k=j;k<=i;k++) if(s1[k]<s1[j-1]||s2[k]<2[i+1]) p=0; ``` 其实就是在求 从$j$开始往后第一个比$s1_{j-1}$小的位置的下标 和 从$i$开始往前第一个比$s2_{i+1}$小的位置的小标中两个下标的**闭区间**中 是否包含$(i,j)$ 包含就统计答案 可以使用单调栈优化 时间复杂度$O(n^2)$ 期望得分`40pts` Code ``` #include<bits/stdc++.h> #define ll long long #define N 1000005 using namespace std; string s; ll ans,s1[N],s2[N]; ll a[N],b[N],q[N],l; int main() { cin>>s; for(int i=1;i<=s.size();i++) s1[i]=s1[i-1]+(s[i-1]==')' ? -1:1); for(int i=s.size();i>=1;i--) s2[i]=s2[i+1]+(s[i-1]=='(' ? -1:1); for(int i=0;i<=s.size();i++) { a[i]=s.size()+1; while(l&&s1[i]<s1[q[l]]) a[q[l--]]=i; q[++l]=i; } l=0; for(int i=s.size()+1;i>=1;i--) { b[i]=0; while(l&&s2[i]<s2[q[l]]) b[q[l--]]=i; q[++l]=i; } for(int i=1;i<=s.size();i++) { for(int j=1;j<i;j++)//枚举 j~i { int p=1; if((j-i+1)&1) continue; int r1=a[j-1],l2=b[i+1]; if(i<r1&&j>l2) ans++; } } cout<<ans; return 0; } ``` ### 正解 $O(n^2)$对于题目的数据还是太勉强了 我们要优化整个程序 必须先魔改一下原程序 将第二重枚举改成这样： ``` for(int i=1;i<=s.size();i++) { for(int j=b[i+1];j<=i-2;j++)//枚举 j~i { if((j-i)&1) continue; if(a[j]>i) ans++; } } ``` 容易发现$(j-i)\operatorname{and} 1=0 \to j \operatorname{and}1=i \operatorname{and} 1

这样子 可以分类讨论去掉一句话

然后看下一句 if(a[j]>i) ans++;

这不就是求一段区间内有多少个数比当前的数大吗？考虑主席树

可能会想到主席树 可以维护n棵的权值线段树 查询就在主席树上作差

但是仔细想想会发现 实际上i是单调递增的

那么我们可以考虑把(i,a_i)打包丢进优先队列里面 然后每次看看堆顶的a_x的值是不是小于等于当前是数 是的话就把它弹出优先队列 然后让对应点的数减少 弹出堆即可

单点修改，区间查询 鉴定为树状数组

时间复杂度O(nlogn) 期望得分100pts

Code

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
string s;
ll ans;
int s1[N],s2[N];
int a[N],b[N],q[N],l;
ll tr[2][N];
struct node{
    int x,v;
};
bool operator < (node a,node b)
{
    return a.v>b.v;
}
priority_queue<node> p[2]; 
void add(int p,int x,int v)
{
    x+=3;
    while(x<=s.size()+3)
    {
        tr[p][x]+=v;
        x+=x&-x;
    }
}
ll ask(int p,int x)
{
    x+=3;
    ll sum=0;
    while(x)
    {
        sum+=tr[p][x];
        x-=x&-x;
    }
    return sum;
}
int main()
{
    cin>>s;
    for(int i=1;i<=s.size();i++)
        s1[i]=s1[i-1]+(s[i-1]==')' ? -1:1);
    for(int i=s.size();i>=1;i--)
        s2[i]=s2[i+1]+(s[i-1]=='(' ? -1:1);
    for(int i=0;i<=s.size();i++)
    {
        a[i]=s.size()+1;
        while(l&&s1[i]<s1[q[l]])
            a[q[l--]]=i;
        q[++l]=i;
    }
    l=0;
    for(int i=s.size()+1;i>=1;i--)
    {
        b[i]=0;
        while(l&&s2[i]<s2[q[l]])
            b[q[l--]]=i;
        q[++l]=i;
    }
    for(int i=0;i<=s.size();i++)
    {
        while(!p[i&1].empty()&&p[i&1].top().v<=i)
        {
            add(i&1,p[i&1].top().x,-1);
            p[i&1].pop();
        }
        ans+=ask(i&1,i-2)-ask(i&1,b[i+1]-1);
        if(a[i]>i) add(i&1,i,1),p[i&1].push((node){i,a[i]});
    }
    cout<<ans;
    return 0;
}

T3 米哈游内战 USACO

我现在要点名一款????二字游戏

简要题意：给你一个字符串 只能交换相邻两个字符 求出让每个子串变成回文串的最小步数的和 变不了贡献就为-1 最后输出即可

思考：

怎样才是最小步数呢？

把原串抽象成01串

因为你只能交换相邻的字符 如果相邻字符相同后交换等于没有交换 一定不优

举个例子：110001001

交换第1,2个1是绝对不对的

因此 如果1的位置在p_1,p_2,p_3,…p_k

那么一定是 p_i\to p_{k-i+1} 两两对称

现在分析怎么才能两两对称

定义中点为mid

如果当前两点中点在mid左边 那么把右边的点右移 否则就把左边的点左移

最终点对一定是[x,len-x+1]

需要移动的步数为|mid-p_i+mid-p_{k-i+1}|

等价于|l+r-p_i-p_{k-i+1}|

所以答案就是

\sum\limits_{(l-r+1)and 1=1}|\frac{(l+r)}{2}-p_{\frac{k+1}{2}}|+\sum\limits_{i=1}^{k/2}|l+r-p_i-p_{k-i+1}|

前面的东西直接预处理了 后面的把p_i+p_{k-i+1}打包看成一个东西

这样l+r动态枚举 后面的东西打包好了 然后开两棵树状数组存一下个数和和就行了

枚举答案的方法就是枚举中间点 然后向两边扩展即可

时间复杂度O(n^2\log n)

code

#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define N 7505
#define ll long long
using namespace std;
int n;
ll ans;
int cnt,c[N];
string s;
struct tree{
    int tr[N*2];
    void clear(int n)
    {
        for(int i=1;i<=n*2;i++)
            tr[i]=0;
        return ;
    }
    void add(int x,int v)
    {
        while(x<=n*2)
        {
            tr[x]+=v;
            x+=x&-x;
        }
        return;
    }
    int ask(int x)
    {
        int sum=0;
        while(x)
        {
            sum+=tr[x];
            x-=x&-x;
        }
        return sum;
    }
}tr[2];
int main()
{
    cin>>s;
    n=s.size();
    s=" "+s;
    for(int l=1;l<=n;l++)
    {
        for(int r=l;r<=n;r++)
        {
            if(s[r]=='G') c[++cnt]=r;
            if(cnt&1 &&(r-l)&1) ans--;
            else if(cnt&1) ans+=abs((l+r)/2-c[cnt/2+1]);
        }
        cnt=0;
    }
    for(int i=1;i<=n;i++)
        if(s[i]=='G') c[++cnt]=i;
    c[cnt+1]=n+1;
    for(int i=1;i<=cnt;i++)//以c[i]为中点 
    {
        tr[0].clear(n),tr[1].clear(n);
        int sum=0;
        for(int j=1;i-j>=1&&i+j<=cnt;j++)
        {
            int p=c[i-j]+c[i+j];
            tr[0].add(p,1);
            tr[1].add(p,p);
            sum+=p;
            for(int l=c[i-j-1]+1;l<=c[i-j];l++)
                for(int r=c[i+j];r<=c[i+j+1]-1;r++)
                {
                    if((r-l)&1) continue;
                    int s1=tr[0].ask(l+r),s2=tr[1].ask(l+r);
                    ans+=1ll*s1*(l+r)-s2;
                    ans+=(sum-s2)-1ll*(j-s1)*(l+r);
                }
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        tr[0].clear(n);
        tr[1].clear(n);
        int sum=0;
        for(int j=0;i-j>=1&&i+j+1<=n;j++)
        {
            int p=c[i-j]+c[i+j+1];
            tr[0].add(p,1);
            tr[1].add(p,p);
            sum+=p;
            for(int l=c[i-j-1]+1;l<=c[i-j];l++)
                for(int r=c[i+j+1];r<=c[i+j+1+1]-1;r++)
                {
                    int s1=tr[0].ask(l+r),s2=tr[1].ask(l+r);
                    ans+=1ll*(l+r)*s1-s2;
                    ans+=1ll*(sum-s2)-1ll*(l+r)*(j+1-s1);
                }
        }
    }
    cout<<ans;
    return 0;
}

T4 抽卡 原题

摆(