技术教程 3.26省选模拟+NOI-ONLINE 正文

3.26省选模拟+NOI-ONLINE

2022-10-19,,

今日趣闻:

这三个人都是同机房的,卡最优解(大常数选手不参与)....以至于最优解第一页都是我们机房的(有图为证,共三人)

$NOI\ online$

$T1$

首先模拟一遍记录这个点当前单调栈前面位置,然后线段树(主席树)查询多少下标小于某个数的

#include<bits/stdc++.h>

#define MAXN 500005

using namespace std;

struct Tree

{

       int ls,rs,sum;

}tr[MAXN<<5];

struct node

{

       int a,b;

}poz[MAXN];

int n,q,tot,top,rt[MAXN],sta[MAXN],wei[MAXN];

void Init()

{

     top=0;

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

     {

          while(top&&(poz[sta[top]].a==poz[i].a||poz[sta[top]].b<=poz[i].b)) top--;

          wei[i]=sta[top];

          sta[++top]=i;

     }

}

void build(int &now,int l,int r)

{

     if(!now) now=++tot;

     if(l==r) return ;

     int mid=(l+r)>>1;

     build(tr[now].ls,l,mid);

     build(tr[now].rs,mid+1,r);

}

void Merge(int &rt1,int rt2,int l,int r,int poz)

{

     rt1=++tot;

     if(l==r)

     {

         tr[rt1].sum=tr[rt2].sum+1;

         return ;

     }

     int mid=(l+r)>>1;

     if(poz<=mid)

     {

         tr[rt1].rs=tr[rt2].rs;

         Merge(tr[rt1].ls,tr[rt2].ls,l,mid,poz);

     }

     else

     {

         tr[rt1].ls=tr[rt2].ls;

         Merge(tr[rt1].rs,tr[rt2].rs,mid+1,r,poz);

     }

     tr[rt1].sum=(tr[tr[rt1].ls].sum+tr[tr[rt1].rs].sum);

}

int query(int rt1,int rt2,int l,int r,int k)

{

    if(l==r)

    {

       return tr[rt2].sum-tr[rt1].sum;

    }

    int mid=(l+r)>>1;

    if(k<=mid) return query(tr[rt1].ls,tr[rt2].ls,l,mid,k);

    else return (tr[tr[rt2].ls].sum-tr[tr[rt1].ls].sum)+query(tr[rt1].rs,tr[rt2].rs,mid+1,r,k);

}

int main()

{

    scanf("%d%d",&n,&q);

    for(int i=1;i<=n;i++) scanf("%d",&poz[i].a);

    for(int i=1;i<=n;i++) scanf("%d",&poz[i].b);

    Init();

    build(rt[0],0,n);

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

    {

        Merge(rt[i],rt[i-1],0,n,wei[i]);

    }

    for(int i=1,res,l,r;i<=q;i++)

    {

        scanf("%d%d",&l,&r);

        printf("%d\n",query(rt[l-1],rt[r],0,n,wei[l]));

    }

}

$T2$

随机化吧,看种子呗(会正解的$dalao$们能不能私信教教我啊)

#include<bits/stdc++.h>

#define MAXN 1000005

using namespace std;

bool vis[MAXN];

vector<int>peo[MAXN];

int pf;

void sol()

{

     int n;

     scanf("%d",&n);

     int Tim=n*20;

     for(int i=1;i<=n;i++) peo[i].clear();

     for(int i=1,num,poz;i<=n;i++)

     {

         scanf("%d",&num);

         for(int j=1;j<=num;j++)

         {

              scanf("%d",&poz);

              peo[i].push_back(poz);

         }

     }

     srand(time(0));

     int cnt;

     bool flag=false;

     while(Tim--)

     {

            int p1=rand()%n+1,p2=rand()%n+1;

            if(peo[p1].size()>peo[p2].size()) swap(p1,p2);

            for(int i=0;i<peo[p1].size();i++)

            {

                   vis[peo[p1][i]]=true;

            }

           cnt=0;

           for(int i=0;i<peo[p2].size();i++)

           {

                  cnt+=(vis[peo[p2][i]]?1:0);

           }

           for(int i=0;i<peo[p1].size();i++)

            {

                   vis[peo[p1][i]]=false;

            }

           if(cnt==peo[p1].size()) continue;

           if(cnt==0) continue;

           puts("YES");

           printf("%d %d\n",p1,p2);

           flag=true;

           break;

     }

     if(!flag)

     {

         puts("NO");

     }

}

int T;

int main()

{

    scanf("%d",&T);

    while(T--) sol();

}

$T3$

$KD-tree$四维偏序就好了,据说用$Min-Max$反演可以变为三维偏序(咕咕咕),貌似想复杂了(各位有什么简单方法啊)

上午模拟赛一直在罚坐...

模拟赛

打了一场模拟赛,又双叒叕垫底了

$T1$想了半天差分和网络流,没有分析出性质,还需要增强分析能力

$T2$设计状态出了问题,一直卡在了重合部分,在容斥里面没想出来

$T3$博弈论$kill$

$T1$

//首先考虑左下角和右上角操作是没用的

//所有的状态可以由1解决,而且代价小

//考场上想到了差分+网络流,其实没什么关系.

//考虑在矩阵上搞一搞事情,转化一下矩阵

//a[i][j]=(c[i][j]+c[i+1][j]+c[i][j+1]+c[i+1][j+1])%2;这不就是(奇怪的)差分吗...

//对于操作1,我们是翻转一个点,对于操作是,翻转(x,y)

//对于操作4,我们是翻转四个点,全是1我们才会翻转,而且只操作一次就好

//然后就很水了,这种结论题还是不怎么好整

#include<bits/stdc++.h>

#define INF 2147483647

#define int long long

#define MAXN 1000005

using namespace std;

int head[MAXN],nxt[MAXN],val[MAXN],to[MAXN],tot=1;

int Num[505][505];

char mp[505][505];

int dis[MAXN];

int n,m,opt,Ans;

queue<int>q;

void add(int u,int v,int w)

{

//     cout<<"add: "<<u<<" "<<v<<endl;

     tot++;

     to[tot]=v;

     val[tot]=w;

     nxt[tot]=head[u];

     head[u]=tot;

}

bool bfs(int s,int t)

{

//     for(int i=1;i<=t;i++) dis[i]=-1;

     memset(dis,-1,sizeof(dis));

     dis[s]=0;

     q.push(s);

     while(!q.empty())

     {

            int now=q.front();

            q.pop();

           for(int i=head[now];i!=-1;i=nxt[i])

           {

                  int y=to[i];

//                  cout<<"now: "<<now<<" "<<y<<endl;

//                  system("pause");

                  if(dis[y]!=-1||!val[i]) continue;

                  dis[y]=dis[now]+1;

                  q.push(y);

           }

     }

     return dis[t]!=-1;

}

int dfs(int now,int ed,int flow)

{

    if(now==ed) return flow;

    int rest=flow;

    for(int i=head[now];i!=-1;i=nxt[i])

    {

        int y=to[i];

        if(dis[y]!=dis[now]+1||!val[i]) continue;

        int k=dfs(y,ed,min(rest,val[i]));

        val[i]-=k;

        val[i^1]+=k;

        rest-=k;

        if(!k) dis[y]=-1;

    }

    return flow-rest;

}

signed main()

{

    freopen("dream.in","r",stdin);

    freopen("dream.out","w",stdout);

    scanf("%d%d%d",&n,&m,&opt);

    if(opt==0)

    {

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

        {

            scanf("%s",mp[i]+1);

        }

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

        {

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

            {

                Num[i][j]=(mp[i][j]=='W'?0:1);

            }

        }

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

        {

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

            {

                Num[i][j]+=Num[i+1][j]+Num[i][j+1]+Num[i+1][j+1];

                Num[i][j]%=2;

            }

        }

        bool flag=false;

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

        {

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

            {

                if(Num[i][j]&&Num[n][j]&&Num[i][m]&&Num[n][m])

                {

                    flag=true;

                    goto EB;

                }

            }

        }

        EB:;

        int res=0;

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

        {

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

            {

                res+=Num[i][j];

            }

        }

        if(!flag)

        {

            cout<<res;

        }

        else

        {

            cout<<(res-4)+3;

        }

    }

    else

    {

        memset(head,-1,sizeof(head));

        int S=n+m+1,T=n+m+2;

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

        {

            scanf("%s",mp[i]+1);

        }

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

        {

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

            {

                Num[i][j]=(mp[i][j]=='W'?0:1);

            }

        }

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

        {

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

            {

                Num[i][j]+=Num[i+1][j]+Num[i][j+1]+Num[i+1][j+1];

                Num[i][j]%=2;

            }

        }

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

        {

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

            {

                if(Num[i][j]&&Num[n][j]&&Num[i][m])

                {

                   add(i,j+n,1);

                   add(j+n,i,0);

    //               cout<<"add1: "<<i<<" "<<j+n<<endl;

                }

            }

        }

        for(int i=1;i<n;i++) add(S,i,1),add(i,S,0);

        for(int i=1;i<m;i++) add(i+n,T,1),add(T,i+n,0);

        int flow=0;

        while(bfs(S,T))

        {

              flow+=dfs(S,T,INF);

        }

        Num[n][m]^=(flow&1);

        int res=0;

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

        {

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

             {

                  res+=Num[i][j];

             }

        }

        cout<<res-flow;

    }

}

$T2$

//考试时候想到了容斥,需要处理一堆东西

//首先有效区间不多,可以离散化

//其次关于最大值不同的区间,可以分别计数

//而且小的优先级更高,可以完全覆盖最大值大的区间

//问题转化也比较好说,首先分开考虑是必然的

//其次是,处理每一类最大值

//我们现在问题转化为一个区间必须有一个点为最大值

//大部分都很好说,就是那个区间重叠不会处理了

//先说没有重合的统计答案

//就是总方案-不合法的

//重合的话使用dp转移

//大概明白了,其实就是把有断点排序,找上一个区间染色

//然后枚举上一步决策,让这一步合法就好了

#include<bits/stdc++.h>

#define INF 2147483647

#define int long long

#define mod 998244353

#define MAXN 2005

using namespace std;

int T,n,Q,A;

struct Node

{

    int l,r,L,R,m;

    bool operator <(const Node &b)const

    {

        if(l!=b.l) return l<b.l;

        else r<b.r;

    }

}q[MAXN],seg[MAXN<<2];

int num,b[MAXN<<1],cnt,Min[MAXN<<1],f[MAXN<<1][MAXN<<1];;

bool cmp(Node x,Node y)

{

    return x.m<y.m;

}

int my_pow(int a,int b)

{

    int res=1;

    while(b)

    {

        if(b&1)

        {

            res=res*a%mod;

        }

        a=a*a%mod;

        b>>=1;

    }

    return res;

}

int calc(int x)

{

    Node pos[MAXN<<1];

    int tot=0,m=0,pl[MAXN<<1],pr[MAXN<<1];

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

    {

        if(Min[i]==x)

        {

            pos[++tot]=seg[i];

            pl[++m]=seg[i].l;

            pr[m]=seg[i].r;

        }

    }

    if(tot==0) return -1;

    sort(pl+1,pl+m+1);

    sort(pr+1,pr+m+1);

    int lim[MAXN];

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

    {

        lim[i]=0;

    }

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

    {

        if(q[i].m==x)

        {

            int L=lower_bound(pl+1,pl+m+1,q[i].L)-pl,R=upper_bound(pr+1,pr+m+1,q[i].R)-pr-1;

            lim[R]=max(lim[R],L);

        }

    }

    f[0][0]=1;

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

    {

        f[i][i]=0;

        int base0=my_pow(x-1,pos[i].r-pos[i].l+1);

        int base1=my_pow(x,pos[i].r-pos[i].l+1);

        for(int j=0;j<i;j++)

        {

            if(j>=lim[i])

            {

                f[i][j]=f[i-1][j]*base0%mod;

            }

            else f[i][j]=0;

            f[i][i]=(f[i][i]+f[i-1][j]*(base1-base0+mod)%mod)%mod;

        }

    }

    int res=0;

    for(int i=0;i<=tot;i++)

    {

        res=(res+f[tot][i])%mod;

    }

    return res;

}

unordered_map<int,int>book;

void solve()

{

    scanf("%d%d%d",&n,&Q,&A);

    cnt=0;

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

    {

        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].m);

        q[i].L=q[i].l,q[i].R=q[i].r;

        b[++cnt]=q[i].l,b[++cnt]=q[i].r;

    }

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

    cnt=unique(b+1,b+cnt+1)-b-1;

    num=0;

    book.clear();

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

    {

        if(b[i-1]+1<=b[i]-1) seg[++num]={b[i-1]+1,b[i]-1,b[i-1]+1,b[i]-1,0};

        seg[++num]={b[i],b[i],b[i],b[i],0},book[b[i]]=num;

    }

    if(seg[num].r!=n) seg[num+1]={seg[num].r+1,n,seg[num].r+1,n,0},num++;

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

    {

        q[i].l=book[q[i].l],q[i].r=book[q[i].r];

    }

    memset(Min,63,sizeof(Min));

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

    {

        for(int u=q[i].l;u<=q[i].r;u++)

        {

            Min[u]=min(Min[u],q[i].m);

        }

    }

    set<int>S;

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

    {

        S.insert(q[i].m);

    }

    int ans=1;

    for(int x:S)

    {

        int res=calc(x);

        if(res==-1)

        {

            printf("0\n");

            return;

        }

        else ans=ans*res%mod;

    }

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

    {

        if(Min[i]>A) ans=ans*my_pow(A,seg[i].r-seg[i].l+1)%mod;

    }

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

    return;

}

signed main()

{

    freopen("value.in","r",stdin);

    freopen("value.out","w",stdout);

    scanf("%d",&T);

    while(T--) solve();

    return 0;

}

$T3$

//神奇的博弈问题

//开始有一些地方有石子,每次选择满足条件p,q和一个位置

//在这个位置减去一个石子,其余位置加一个石子

//本题就是mod 2的情况下

//如果原来

#include <bits/stdc++.h>

#define MAXN 300005

using namespace std;

int n,q,SG[MAXN],cnt[350];

void sol(int x,int p,int w)

{

    int c=0,y=x;

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

    {

        if(y%p!=0)

        {

           break;

        }

        y/=p;

        c^=SG[y];

        if(c<303)cnt[c]=x;

    }

}

void GSG(int x)

{

    for(int i=1,j=2;;i++)

    {

        if(x%j!=0) break;

        sol(x,j,i);

        j*=2;

    }

    for(int i=1,j=3;;i++)

    {

        if(x%j!=0) break;

        sol(x,j,i);

        j*=3;

    }

    for(int i=0;;i++)

    {

        if(cnt[i]!=x)

        {

           SG[x]=i;

           return;

        }

    }

}

int main()

{

    freopen("forward.in","r",stdin);

    freopen("forward.out","w",stdout);

    int T;

    scanf("%d",&T);

    for(int i=1,b=0,c=0;i<=T;i++)

    {

        c=0;

        memset(cnt,0,sizeof(cnt));

        scanf("%d%d",&n,&q);

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

        {

            GSG(j);

        }

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

        {

            scanf("%d",&b);

            if(b==0) c^=SG[j];

        }

        if(c==0) printf("lose\n");

        else printf("win\n");

    }

    return 0;

}

3.26省选模拟+NOI-ONLINE的相关教程结束。

《3.26省选模拟+NOI-ONLINE.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!