526互联

NOIP A层联测9 & CSP模拟52

发布时间 2023-10-11 17:09:34作者: int_R

我的评价是三道傻逼题和一道牛逼题。

T4 上厕所时想了个奇怪东西打了一个半个小时 170 行结果剩 10 分钟发现假了，最后 \(k=1\) 都没来得及写就直接交了暴力。没想到 HZOJ 过了 50pts，喜了。但是 Accoders 上只过了 35pts，恼了。

T1 长春花

\(b^2\bmod p=(b\bmod p)^2\bmod p\)，所以可以先枚举 \(b\in [0,p-1]\) 求出所有可能的 \(b^2\bmod p\)。观察大样例发现 \(f(x)\) 不会很大，所以直接枚举 \(x\)，再从小到大枚举 \(a\)，每次检查 \((x-a^2)\bmod p\) 是否是可能的 \(b^2\bmod p\)，时间复杂度大概 \(O(p)\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10;
int p,ans;bool vis[MAXN];
int main()
{
#ifdef ONLINE_JUDGE
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>p;
    for(register long long b=0;b<p;++b) vis[b*b%p]=true;
    for(register int x=0;x<p;++x)
    {
        for(register long long a=0;a<p;++a)
        {
            ans=max(ans,(int)a);
            if(vis[(x-a*a%p+p)%p]) break;
        }
    }
    cout<<ans<<'\n';return 0;
}

T2 紫罗兰

枚举边，bfs 搜索包含这条边的最小环的个数（不是找最小环中包含这条边的个数，而是“包含这条边”作为前提条件，然后最小环的个数）。

就相当于去掉当前枚举的这条边，有多少条最短路径可以从 \(x\) 到 \(y\)。之后对于所有枚举的边中最小的“包含这条边的最小环”就是全局的最小环，统计一下即可。一个 \(x\) 元环在枚举边时每条边都计算了一次，所以要除以 \(x\)。时间复杂度 \(O(m(n+m))\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=3e3+10,MAXM=6e3+10,INF=1e9+7;
int n,m,to[MAXM<<1],nxt[MAXM<<1],head[MAXN],cnt;
int x[MAXM],y[MAXM],s,t,cur,dis[MAXN],d[MAXN],MIN=INF,ans[MAXN];
inline void add(int x,int y)
{
    to[++cnt]=y,nxt[cnt]=head[x];
    head[x]=cnt;return ;
}
inline void bfs()
{
    for(register int i=1;i<=n;++i) dis[i]=d[i]=0;
    dis[s]=d[s]=1;queue <int> q;q.push(s);
    while(!q.empty())
    {
        int x=q.front();q.pop();if(x==t||dis[x]>MIN) break;
        for(register int i=head[x];i;i=nxt[i])
        {
            if(i==cur*2-1||i==cur*2) continue;
            int y=to[i];
            if(!dis[y])
            {
                dis[y]=dis[x]+1,d[y]+=d[x];
                q.push(y);
            }
            else if(dis[y]==dis[x]+1) d[y]+=d[x];
        }
    }
    if(dis[t]) MIN=min(MIN,dis[t]),ans[dis[t]]+=d[t];return ;
}
int main()
{
#ifdef ONLINE_JUDGE
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>n>>m;
    for(register int i=1;i<=m;++i)
        cin>>x[i]>>y[i],add(x[i],y[i]),add(y[i],x[i]);
    for(register int i=1;i<=m;++i)
        s=x[i],t=y[i],cur=i,bfs();
    for(register int i=3;i<=n;++i)
        if(ans[i]){cout<<ans[i]/i<<'\n';return 0;}
    cout<<"0\n";return 0;
}

T3 天竺葵

\(c_{i+1}>b_i\times c_i,b_i\geq 1\) 可知 \(c_{i+1}\times b_{i+1}>c_i\times b_i\)。

那么就可以直接借鉴最长上升子序列 \(O(n\log n)\) 的做法，维护出当前最长的子序列，每次在 \(c_j\times b_j\) 中找到第一个大于等于 \(a_i\) 的位置 \(k\)，判断一下若 \(a_i\) 小于 \(c_k\) 则将 \(c_k\gets a_i\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
int n,b[MAXN],tot;long long a[MAXN],f[MAXN];
int main()
{
#ifdef ONLINE_JUDGE
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>n;
    for(register int i=1;i<=n;++i) cin>>a[i];
    for(register int i=1;i<=n;++i) cin>>b[i];
    for(register int i=1;i<=n;++i)
    {
        if(a[i]>f[tot]) ++tot,f[tot]=a[i]*b[tot];
        else
        {
            int k=lower_bound(f+1,f+1+tot,a[i])-f;
            if(a[i]*b[k]<f[k]) f[k]=a[i]*b[k];
        }
    }
    cout<<tot<<'\n';return 0;
}

T4 风信子

带修超级钢琴。

考虑用 \((l1,r1,l2,r2,x,y)\) 表示 \(\max\limits_{x\in[l1,r1],y\in[l2,r2]} a_x-a_y\)。发现当 \(l1=l2\leq r1=r2\) 或者 \(l1\leq r1<l2\leq r2\) 这两种情况比较好计算。\(x,y\) 是根据 \(l1,r1,l2,r2\) 确定的。

对于第一种情况用线段树维护，合并时答案为左儿子答案，右儿子答案，左儿子最大值减右儿子最小值，三者中的最大值，这是显然的，也是好维护的。第二种情况就是左区间最大值减右区间最小值，更容易了。

参考超级钢琴，我们使用一个堆来每次取出当前最优。处理完以后，我们要将剩下的部分分割成上面两种情况。

对于第一种情况，可以分割成：

\((l,x-1,l,x-1),(l,x-1,x,r),(x,x,x,x),(x,x,x+1,y-1),(x,x,y+1,r),(x+1,r,x+1,r)\)，这样考虑了所有情况，注意如果 \(x=y\) 就没有 \((x,x,x,x)\) 了，其他的注意一下使区间左端点不大于右端点就行。

对于第二种情况，可以分割成：

\((l1,x-1,l2,r2),(x,x,l2,y-1),(x,x,y+1,r2),(x+1,r1,l2,r2)\)，同样注意一下左端点不大于右端点。

这样每次可以快速求出当前最优，而 \(\sum k\leq 3\times 10^5\) 所以复杂度有保证，为 \(O(n\log n+(\sum k)(\log n+\log(\sum k)))\)。

线段树上要维护最大值，最小值，最大的 \(a_x-a_y\)，最大值的位置，最小值的位置，\(x\) 和 \(y\)。区间加就是最大值和最小值加，别的不变。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
const int MAXN=1e5+10,INF=1e9+7;
int n,m,a[MAXN];
namespace seg
{
    struct tree{int MAX,MIN,num,maxn,minn,ansx,ansy;}t[MAXN<<2];int add[MAXN<<2];
    inline void push_up(tree &p,tree ls,tree rs)
    {
        p.MAX=max(ls.MAX,rs.MAX);
        p.MIN=min(ls.MIN,rs.MIN);
        p.maxn=(ls.MAX>rs.MAX)?ls.maxn:rs.maxn;
        p.minn=(ls.MIN<rs.MIN)?ls.minn:rs.minn;
        p.num=max(max(ls.num,rs.num),ls.MAX-rs.MIN);
        if(p.num==ls.num) p.ansx=ls.ansx,p.ansy=ls.ansy;
        else if(p.num==rs.num) p.ansx=rs.ansx,p.ansy=rs.ansy;
        else p.ansx=ls.maxn,p.ansy=rs.minn;return ;
    }
    inline void build(int l,int r,int p)
    {
        if(l==r){t[p]={a[l],a[l],0,l,l,l,l};return ;}
        int mid=(l+r)>>1;
        build(l,mid,p<<1),build(mid+1,r,p<<1|1);
        push_up(t[p],t[p<<1],t[p<<1|1]);
        return ;
    }
    inline void spread(int p)
    {
        if(!add[p]) return ;
        t[p<<1].MAX+=add[p],t[p<<1|1].MAX+=add[p];
        t[p<<1].MIN+=add[p],t[p<<1|1].MIN+=add[p];
        add[p<<1]+=add[p],add[p<<1|1]+=add[p];
        add[p]=0;return ;
    }
    inline void change(int l,int r,int p,int x,int y,int z)
    {
        if(x<=l&&y>=r){t[p].MAX+=z,t[p].MIN+=z,add[p]+=z;return ;}
        int mid=(l+r)>>1;spread(p);
        if(x<=mid) change(l,mid,p<<1,x,y,z);
        if(y>mid) change(mid+1,r,p<<1|1,x,y,z);
        push_up(t[p],t[p<<1],t[p<<1|1]);return ;
    }
    inline tree query(int l,int r,int p,int x,int y)
    {
        if(x<=l&&y>=r) return t[p];
        int mid=(l+r)>>1;spread(p);
        tree a={-INF,INF,-INF},b={-INF,INF,-INF},ans;
        if(x<=mid) a=query(l,mid,p<<1,x,y);
        if(y>mid) b=query(mid+1,r,p<<1|1,x,y);
        push_up(ans,a,b);return ans;
    }
};
inline int A(int x,int l=1,int r=n,int p=1)
{
    if(l==r) return seg::t[p].MAX;
    int mid=(l+r)>>1;seg::spread(p);
    return (x<=mid)?A(x,l,mid,p<<1):A(x,mid+1,r,p<<1|1);
}
struct node
{
    int l1,r1,l2,r2,x,y;
    node(int l1,int r1,int l2,int r2):l1(l1),r1(r1),l2(l2),r2(r2)
    {
        if(l1==l2)
        {
            seg::tree P=seg::query(1,n,1,l1,r1);
            x=P.ansx,y=P.ansy;
        }
        else
        {
            seg::tree P1=seg::query(1,n,1,l1,r1);
            seg::tree P2=seg::query(1,n,1,l2,r2);
            x=P1.maxn,y=P2.minn;
        }
    };
    friend bool operator <(const node &x,const node &y){return A(x.x)-A(x.y)<A(y.x)-A(y.y);}
};
signed main()
{
#ifdef ONLINE_JUDGE
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>n>>m;
    for(register int i=1;i<=n;++i) cin>>a[i];
    seg::build(1,n,1);
    while(m--)
    {
        int opt,l,r,x,ans=0;cin>>opt>>l>>r>>x;
        if(opt==1) seg::change(1,n,1,l,r,x);
        if(opt==2)
        {
            priority_queue <node> q;
            q.push(node(l,r,l,r));
            while(x--)
            {
                node P=q.top();q.pop();
                ans+=A(P.x)-A(P.y);
                if(P.l1==P.l2)
                {
                    int l=P.l1,r=P.r1,x=P.x,y=P.y;
                    if(l!=x) q.push(node(l,x-1,l,x-1));
                    if(l!=x) q.push(node(l,x-1,x,r));
                    if(x!=y) q.push(node(x,x,x,x));
                    if(x<y-1) q.push(node(x,x,x+1,y-1));
                    if(y!=r) q.push(node(x,x,y+1,r));
                    if(x!=r) q.push(node(x+1,r,x+1,r));
                }
                else
                {
                    int l1=P.l1,r1=P.r1,l2=P.l2,r2=P.r2,x=P.x,y=P.y;
                    if(l1!=x) q.push(node(l1,x-1,l2,r2));
                    if(l2!=y) q.push(node(x,x,l2,y-1));
                    if(y!=r2) q.push(node(x,x,y+1,r2));
                    if(x!=r1) q.push(node(x+1,r1,l2,r2));
                }
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}