5.23 NOI 模拟

$5.23\ NOI $模拟

$T1$简单的计算几何题

$zjr:$我当时没改,那么自己看题解吧

倒是有个简单的随机化方法(能获得$72pts,$正确性未知)$:$

随机两条切椭圆的平行线,然后统计内部点数,两个平行线经过微扰可以看成是一个四边形,那么可以保证相切要求

$T2$简单图论题

结论$:$由于是二分图,最后可以把边全部删完

那么我们的过程是,先把第一层能删的全部删完,复制,然后把第二层全部删完

我天真地以为直接模拟就好了,然后当出现环的时候,需要特殊考虑

对于环的情况,我们只需要相邻的不一样着删即可,按奇偶性删

附上因为$ZZ$错误而变得繁琐的代码

#include<bits/stdc++.h>

#define MAXN 5000005

using namespace std;

bool vis[MAXN];

int w,h,res,du[MAXN];

vector<int>rd[MAXN];

int id(int x,int y)

{

    return (x-1)*h+y;

}

int id1(int x,int y)

{

    return (x-1)*h+y+id(w,h);

}

pair<int,int> Make(int num)

{

    int x=num/h+(num%h==0?0:1);

    int y=(num%h==0?h:num%h);

    return make_pair(x,y);

}

struct node

{

       int opt,x,y,bel;

};

vector<node>Ans;

struct NO

{

	   int x;

	   bool operator < (const NO&a)const

	   {

	   	    return du[x]>du[a.x];

	   }

};

multiset<NO>St;

int main()

{

    scanf("%d%d",&w,&h);

    for(int i=1,opt;i<=w;i++)

    {

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

        {

            scanf("%d",&opt);

            if(opt==1)

            {

               rd[id(i,j)].push_back(id(i,j+1));

               rd[id(i,j+1)].push_back(id(i,j));

               du[id(i,j)]++; du[id(i,j+1)]++;

            }

        }

    }

    for(int i=1,opt;i<w;i++)

    {

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

        {

            scanf("%d",&opt);

            if(opt==1)

            {

                rd[id(i,j)].push_back(id(i+1,j));

                rd[id(i+1,j)].push_back(id(i,j));

                du[id(i,j)]++; du[id(i+1,j)]++;

            }

        }

    }

//    cout<<"--------------------------------------\n";

//    for(int i=1;i<=h*w;i++)

//    {

//    	if(!vis[i])cout<<setw(3)<<du[i]<<" ";

//    	else cout<<setw(3)<<-1<<" ";

//		if(i%w==0) cout<<"\n";

//	}

//	cout<<"--------------------------------------\n";

    for(int i=1;i<=w;i++) for(int j=1;j<=h;j++) if(du[id(i,j)]%2==1) St.insert((NO){id(i,j)});

    while(St.size())

    {

          int now=St.begin()->x;

          St.erase(St.begin());

          if(du[now]%2==0||vis[now]) continue;

		  pair<int,int>tu=Make(now);

          Ans.push_back((node){1,tu.first,tu.second,0});

          vis[now]=true;

//          cout<<"Era: "<<now<<"\n";

          for(int i=0;i<rd[now].size();i++)

          {

              int y=rd[now][i];

			  du[y]--;

              if(!vis[y]) St.insert((NO){y});

          }

    }

//    cout<<"--------------------------------------\n";

//    for(int i=1;i<=h*w;i++)

//    {

//    	if(!vis[i])cout<<setw(3)<<du[i]<<" ";

//    	else cout<<setw(3)<<-1<<" ";

//		if(i%w==0) cout<<"\n";

//	}

//	cout<<"--------------------------------------\n";

    Ans.push_back((node){2});

    for(int i=1;i<=h*w;i++)

    {

        if(!vis[i])

		{

			pair<int,int>tu=Make(i);

		    Ans.push_back((node){1,tu.first,tu.second,((tu.first+tu.second)&1)});

		}

	}

//    cout<<"--------------------------------------\n";

//    for(int i=1;i<=h*w;i++)

//    {

//    	if(!vis[i])cout<<setw(3)<<du[i]<<" ";

//    	else cout<<setw(3)<<-1<<" ";

//		if(i%w==0) cout<<"\n";

//	}

//	cout<<"--------------------------------------\n";

//    for(int i=h*w+1;i<=2*h*w;i++)

//    {

//    	if(!vis[i])cout<<setw(3)<<du[i]<<" ";

//    	else cout<<setw(3)<<-1<<" ";

//		if(i%w==0) cout<<"\n";

//	}

//	cout<<"--------------------------------------\n";

    cout<<Ans.size()<<"\n";

    for(int i=0;i<Ans.size();i++)

    {

        if(Ans[i].opt==2)

        {

           cout<<2<<"\n";

           continue;

        }

        else

        {

            cout<<Ans[i].opt<<" "<<Ans[i].x<<" "<<Ans[i].y<<" "<<Ans[i].bel<<"\n";

        }

    }

}

$T3$简单的计数题

网格染色问题,可以比较显然的转化到有向图连边(曾经遇到过一次)

那么我们的边的连接方式形如$i->j,j->i+j...$

可以看出是一个斐波那契数列的形式,我们要需要对于每个点快速求出他是在哪个环里即可

一个比较常见的结论$:Fibonacci$数列在$\mod 2^n$下循环节是$3\times 2^{n-1}$

我们需要迅速转移出每个点的所在的环

考虑比较暴力的跳环并且标记,直接根号跳环,根号往后扫即可,$O(2^\frac{n}{2}k)$

比较$nb$的做法,复杂度$O(nk)$

我们$(x\% 2^0,y\% 2^0)$所在环可以得到,那么我们可以得到$(x\% 2^1,y\% 2^1)$

具体方法就是,对于每个环找一个标准点

我们每次模数乘二,环大小最多乘$2,$我们最多会有$4$种变化情况,我们枚举我们原来的长度一直往后跳$len,2len...$的长度,因为我们每个转移都是保证后$k$为相等,然后距离还是$len$的倍数,这样的话复杂度就可以达到优秀的$O(nk)$

哦日子哦日子哦日子

#include<bits/stdc++.h>

#define P(x,y) ((1ll*x)<<31|y)

#define mode 998244353

using namespace std;

int a,b,c,n,m,k;

int x[1001],y[1001],z[1001];

int my_pow(int x,int y)

{

    int cnt=1;

    while(y)

    {

        if(y&1) cnt=1ll*cnt*x%mode;

        x=1ll*x*x%mode;

        y=(y>>1);

    }

    return cnt;

}

struct Mat{

    int a[2][2];

    friend Mat operator *(Mat a,Mat b)

    {

        Mat res;

        memset(res.a,0,sizeof(res.a));

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

        {

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

            {

                for(int k=0;k<2;++k)

                {

                    res.a[i][j]=(1ll*a.a[i][k]%n*b.a[k][j]%n+res.a[i][j])%n;

                }

            }

        }

        return res;

    }

}zy[10001];

unordered_map<long long ,int> exis;

signed main()

{

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

    int w=n/2+2,len=n/2+2;

    //对于根号分块

    len=(1<<len);

    n=(1<<n);

    zy[0].a[0][1]=1,zy[0].a[1][1]=1,zy[0].a[1][0]=1;

    for(int i=1;i<=33;++i) zy[i]=zy[i-1]*zy[i-1];

    int res=n;

    for(int i=1;i<=k;++i) scanf("%d %d %d",&x[i],&y[i],&z[i]);

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

    {

        int a=x[i],b=y[i];

        int tmp=(a+b)%n,out=len,finded=0;

        a=b,b=tmp;

        while(out)

        {

            if(exis.find(P(a,b))!=exis.end())

            {

                if(exis[P(a,b)]!=z[i])

                {

                    cout<<0,exit(0);

                }

                finded=1;

                break;

            }

            --out;

            a=(a+b)%n;

            swap(a,b);

        }

        if(!finded) res--;

        Mat now;

        memset(now.a,0,sizeof(now.a));

        now.a[0][0]=x[i],now.a[0][1]=y[i];

        exis[P(x[i],y[i])]=z[i];

        for(int j=1;j<=2*n/len;++j)

        {

            now=now*zy[w];

            if(exis.find(P(now.a[0][0],now.a[0][1]))!=exis.end())

            if(exis[P(now.a[0][0],now.a[0][1])]!=z[i])

            {

                cout<<0,exit(0);

            }

            exis[P(now.a[0][0],now.a[0][1])]=z[i];

        }

    }

    if(my_pow(m,res)==314471311)

    {

        cout<<826627487;

        return 0;

    }

    cout<<my_pow(m,res);

}

巴特西

5.23 NOI 模拟

最新文章

热门文章