5.23 NOI 模拟
$5.23\ NOI $模拟
\(T1\)简单的计算几何题
\(zjr:\)我当时没改,那么自己看题解吧
倒是有个简单的随机化方法(能获得\(72pts,\)正确性未知)\(:\)
随机两条切椭圆的平行线,然后统计内部点数,两个平行线经过微扰可以看成是一个四边形,那么可以保证相切要求
\(T2\)简单图论题
结论\(:\)由于是二分图,最后可以把边全部删完
那么我们的过程是,先把第一层能删的全部删完,复制,然后把第二层全部删完
我天真地以为直接模拟就好了,然后当出现环的时候,需要特殊考虑
对于环的情况,我们只需要相邻的不一样着删即可,按奇偶性删
附上因为\(ZZ\)错误而变得繁琐的代码
#include
#define MAXN 5000005
using namespace std;
bool vis[MAXN];
int w,h,res,du[MAXN];
vectorrd[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 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;
};
vectorAns;
struct NO
{
int x;
bool operator < (const NO&a)const
{
return du[x]>du[a.x];
}
};
multisetSt;
int main()
{
scanf("%d%d",&w,&h);
for(int i=1,opt;i<=w;i++)
{
for(int j=1;jx;
St.erase(St.begin());
if(du[now]%2==0||vis[now]) continue;
pairtu=Make(now);
Ans.push_back((node){1,tu.first,tu.second,0});
vis[now]=true;
// cout<<"Era: "<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< \(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
#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 exis;
signed main()
{
scanf("%d %d %d",&n,&m,&k);
int w=n/2+2,len=n/2+2;
//对于根号分块
len=(1<