洛谷3684 [CERC2016]机棚障碍 Hangar Hurdles 题解

并查集写成Merge(e[i].v,e[i].v)调了三天奥里给都给我调出来了。不过这都70分可见数据有多水

题意

给定一个$n\times n$的网格图,其中部分格点有障碍物使得箱子不能置于其上。规定箱子是一个奇数边长的正方形,其坐标为其中心格点的坐标。箱子只能上下左右移动,每次询问从一个格点能移动到另一个格点的最大箱子。

分析

此题看似简单,实则恶心的一匹。

  • 我们先考虑将问题转化。如果求出每个格点能放置的最大箱子,设为格点权,那么每次询问就变成了求出两点路径上最小点权最大的路径。每次bfs,复杂度无法承受。
  • 接着发现联通的点权相同的格点可以缩成一个点,因为在这个联通块内移动是不会改变经过的最小点权的。
  • 于是在上下左右四个方向移动转化为了在相邻的联通块内移动。我们可以在相邻的联通块内连边,将边权设为两点点权的最小值,于是只要求出最大瓶颈路就可以了。
  • 任意两点间的最大瓶颈路可以用如下算法求:将边降序排序,依次加入图中,两点第一次联通时其路径即为最大瓶颈路。正确性显然。
  • 发现这就是Kruskal求最大生成树的过程,于是只要在生成树上查询路径最小值就可以了。

经过以上转化,此题解决(指口头)。

实现

实现才是这道题的重头戏。

part1 求出MaxSize

  • 首先设图中障碍为1,其余为0,对原图进行前缀和,以快速求出目标矩阵中有没有障碍物。

  • 对每个格点进行二分,得到每个格点能放置的最大箱子设为MaxSize。其中因为边长只能为奇数,二分时是对中心点到边界的距离进行二分。

  • 复杂度$O(n^2logn)$

    代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    //第一部分:预处理出每个点的最大矩形
    namespace DealMatrix {
    int sum[maxn][maxn];//前缀和,障碍为1
    int maxsize[maxn][maxn];

    inline char check(const int &i,const int &j,const int &s) {
    if(i-s<1||j-s<1||i+s>n||j+s>n) return false;//大了
    if(sum[i+s][j+s]-sum[i-s-1][j+s]-sum[i+s][j-s-1]+sum[i-s-1][j-s-1]) return 0x0;
    return 0xff;
    }
    inline int getsize(const int &i,const int &j) {
    int l=0,r=n/2,mid,ans=0;
    while(l<=r) {
    mid=(l+r)>>1;
    if(!~check(i,j,mid)) ans=mid,l=mid+1;
    else r=mid-1;
    }
    return ans*2+1;
    }
    void main() {
    for(int i(1);i<=n;i++)
    for(int j(1);j<=n;j++)
    sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+(map[i][j]=='#');
    for(int i(1);i<=n;i++)
    for(int j(1);j<=n;j++) {
    if(map[i][j]=='.')
    maxsize[i][j]=getsize(i,j);
    else maxsize[i][j]=-1;
    }
    }
    }

    part2 缩点并连边

  • 将MaxSize相同的点缩在一起,可以使用Bfs或者并查集。我这里使用的是Bfs。

  • 连边时设$u<v$,先加入要求生成树的图里。注意要判重,我这里使用的是unordered_map

  • 复杂度$O(n^2)$,将unordered_map的每次操作当成常数级别。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
namespace BuildGraph {
int belong[maxn][maxn],cnt;//联通块编号
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

using DealMatrix::maxsize;
char vis[maxn][maxn];
inline void Search(const int &i,const int &j,const int &col) {
static std::queue< std::pair<int,int> > q;
vis[i][j]=0xff;belong[i][j]=col;
q.push(std::make_pair(i,j));
while(!q.empty()) {
int x=q.front().first;
int y=q.front().second;
q.pop();
for(int k(0);k<4;k++) {
int nx=x+dx[k],ny=y+dy[k];
if(nx<1||ny<1||nx>n||ny>n||maxsize[nx][ny]!=maxsize[i][j]||!~vis[nx][ny])
continue;
vis[nx][ny]=0xff;
belong[nx][ny]=col;
q.push(std::make_pair(nx,ny));
}
}
}

void main() {
static std::unordered_map< int,std::unordered_map<int,char> > s;
for(int i(1);i<=n;i++)
for(int j(1);j<=n;j++)
if(~vis[i][j]&&~maxsize[i][j])
Search(i,j,++cnt);
for(int i(1);i<=n;i++)
for(int j(1);j<=n;j++) {
if(!~maxsize[i][j]) continue;
for(int k(0);k<4;k++) {
int x=i+dx[k],y=j+dy[k];
int p=belong[i][j],q=belong[x][y];
if(x<1||y<1||x>n||y>n||!q||p==q) continue;
if(p>q) swap(p,q);
if(!~s[p][q]) continue;
s[p][q]=0xff;
Graph_1::e[++Graph_1::m]=Graph_1::Edge(p,q,min(maxsize[i][j],maxsize[x][y]));
}
}
N=cnt;
Graph_1::Kruscal();
}
}

part3 求出最大生成树

这个没什么说的。并查集我使用的是路径压缩+按秩合并版本,复杂度最优。复杂度$O(m\alpha(n))$,其中$m$为边数。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
namespace Graph_1 {
struct Edge {
int u,v,w;
Edge(const int &u,const int &v,const int &w)
:u(u),v(v),w(w) {}
Edge() {}
}e[maxm<<2];
int m;char InTree[maxm<<2];
struct Compare {
bool operator () (const Edge &a,const Edge &b) {
return a.w<b.w;
}
}cmp;

struct UnoinFindSet {
int fa[maxm],rank[maxm];
void Init() {
for(int i(1);i<=N;i++) fa[i]=i,rank[i]=1;
}
int Find(const int &x) {
return (x == fa[x]) ? x : (fa[x] = Find( fa[x] ));
}
inline void Merge(const int &u,const int &v) {
int x(Find(u)),y(Find(v));
if(x!=y) {
if(rank[x]<rank[y]) fa[x]=y,rank[y]=max(rank[y],rank[x]+1);
else fa[y]=x,rank[x]=max(rank[x],rank[y]+1);
}
}
inline bool Same(const int &u,const int &v) {
return Find(u)==Find(v);
}
}U;

void Kruscal() {
std::sort(e+1,e+1+m,cmp);
U.Init();
for(int i(1);i<=m;i++) {
if(U.Same(e[i].u,e[i].v)) continue;
U.Merge(e[i].u,e[i].v);
InTree[i]=0xff;
}
}
}

part4 树上快速查询

  • 这里方法很多,可以倍增,树剖还有LCT。这里采用的是树剖+ST表。复杂度预处理$n^2logn$,每次查询$n^2logn$。
  • 注意求出的生成树可能是森林。
  • 另外,因为前面把点权转化为边权,这里又把边权转化为点权处理,所以树剖询问时不能加上lca的贡献。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// 第三部分树剖最小值,在最小生成树上查询瓶颈路。注意,可能是一个森林
namespace Tree {
struct Edge {
int v,next,w;
Edge(const int &v,const int &next,const int &w)
:v(v),next(next),w(w) {}
Edge() {}
}e[maxm<<1];
int head[maxm],cnt;
inline void AddEdge(const int &u,const int &v,const int &w) {
e[++cnt]=Edge(v,head[u],w);
head[u]=cnt;
}

int val[maxm];//边权转化为点权
namespace STTable {
int f[maxm][21],Log[maxm];
void Init() {
memset(f,0x3f,sizeof f);
for(int i(0),w(1);w<=N;i++,w<<=1) Log[w]=i;
for(int i(1);i<=N;i++) if(!Log[i]) Log[i]=Log[i-1];
for(int i(1);i<=N;i++)
f[i][0]=val[i];
for(int j(1);j<21;j++)
for(int i(1);i<=N;i++)
if(1+(1<<j)-1<=N)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int QueryMin(const int &l,const int &r) {
if(l>r) return inf;
int o(Log[r-l+1]);
return min(f[l][o],f[r-(1<<o)+1][o]);
}
}

int size[maxm],fa[maxm],son[maxm],w[maxm],depth[maxm],belong[maxm],Cnt_Tree;
void dfs1(const int &u) {
belong[u]=Cnt_Tree;
size[u]=1;depth[u]=depth[fa[u]]+1;
for(int i(head[u]);i;i=e[i].next) {
const int &v=e[i].v;
if(v==fa[u]) continue;
fa[v]=u;
dfs1(v);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v,w[u]=e[i].w;
}
}
int top[maxm],dfn[maxm],stamp;
void dfs2(const int &u,const int &anc) {
dfn[u]=++stamp;
top[u]=anc;
if(son[u]) dfs2(son[u],anc),val[dfn[son[u]]]=w[u];
for(int i(head[u]);i;i=e[i].next) {
const int &v=e[i].v;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);val[dfn[v]]=e[i].w;
}
}

inline int GetMin(int u,int v) {
int ans=inf;
while(top[u]!=top[v]) {
if(depth[top[u]]<depth[top[v]]) swap(u,v);
ans=min(ans,STTable::QueryMin(dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if(depth[u]>depth[v]) swap(u,v);
ans=min(ans,STTable::QueryMin(dfn[u]+1,dfn[v]));
return ans;
}

void main() {
for(int i(1);i<=Graph_1::m;i++)
if(!~Graph_1::InTree[i]) {
AddEdge(Graph_1::e[i].u,Graph_1::e[i].v,Graph_1::e[i].w);
AddEdge(Graph_1::e[i].v,Graph_1::e[i].u,Graph_1::e[i].w);
}
for(int i(1);i<=N;i++)
if(!dfn[i]) {
Cnt_Tree++;
dfs1(i);
dfs2(i,i);
}
STTable::Init();
}
}

part4 处理询问

注意亿点细节。例如,不在一棵树上以及所询问的点就是障碍时,返回无解。

代码:

1
2
3
4
5
6
7
8
9
inline int Query(const int &x1,const int &y1,const int &x2,const int &y2) {
if(map[x1][y1]=='#'||map[x2][y2]=='#') return 0;
int u=BuildGraph::belong[x1][y1],v=BuildGraph::belong[x2][y2];
if(u==v) return DealMatrix::maxsize[x1][y1];
if(Tree::belong[u]!=Tree::belong[v]) return 0;
int ans=Tree::GetMin(u,v);
if(ans==inf) return 0;
return ans;
}

至此,此题终于做完了。我的代码共354行,算得上是我打过的最长的代码了。还不是因为加了个七十多行的快速读写

卡常技巧-快速IO

在$OI$中,卡常是一门奇怪又必备的技巧,在某些毒瘤题如Ynoi中需要用到许多卡常技巧才能卡入时限。这里给出我自己的快速$IO$卡常代码。

一、快速读入

1、带符号整形

最简单基础的快读。

1
2
3
4
5
6
inline int read(int &x) {
x=0;bool k=false;char c=getc();
while(!isdigit(c)) {k|=(c=='-');c=getc();if(c==EOF) return 0;}
while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getc();}
x*=(k?-1:1); return 1;
}

或换个写法

1
2
3
4
5
6
inline int read(int &x) {
x=0;bool k=false;char c=getc();
for(;!isdigit(c);c=getc()) {k|=(c=='-');if(c==EOF) return 0;}
for(;isdigit(c);c=getc()) {x=(x<<1)+(x<<3)+(c^48);c=getc();}
x*=(k?-1:1); return 1;
}

其中getc为读入一个字符的函数,函数返回值为是否读到数。在对x的位运算处,不排除有更优秀的写法。

2、单个字符

如果只是要求读入字符,可以直接

1
2
3
inline int read(char &c) {
return (c=getc())!=EOF;
}

如果对读入的字符有要求,如必须是字母或数字等,可以使用cctype库中函数来判断读入。以读入非空字符为例:

1
2
3
4
inline int read(char &c) {
while(c=getc(),isspace(c));
return c!=EOF;
}

注意EOF标识符在isspace中返回真。

3、字符串

采用和scanf一样的读入方式,即在读入空字符时停止。

1
2
3
4
5
6
inline int read(char *s) {
*s=getc();
while(isspace(*s)) {*s=getc();if(*s==EOF) return 0;}
while(!isspace(*s)&&*s!=EOF) {s++;*s=getc();}
*s='\0'; return 1;
}

4、浮点数

因为浮点数精度问题,它的手动读入并不好写,并且出错率或误差率远远大于用scanfstd::cin读入。

这里给出我的一个浮点数读入实现,仅供参考。

1
2
3
4
5
6
7
8
9
inline int read(double &x) {
x=0;bool k=false;double d=1;char c=getc();
while(!isdigit(c)) {k|=(c=='-');c=getc();if(c==EOF) return 0;}
while(isdigit(c)) {x=x*10+(c^48);c=getc();}
if(c!='.') return 1;
c=getc();
while(isdigit(c)) {d/=10.0;x+=d*(c^48);c=getc();}
x*=(k?-1.0:1.0); return 1;
}

在读入小数部分时d临时保存当前位。

二、快速输出

1、带符号整形

一般有递归和非递归两种写法。这里采用非递归写法,因为时间效率较高。

1
2
3
4
5
6
7
inline void write(int x) {
static char buf[30];int p=-1;
if(x<0) {putc('-');x=-x;}
if(x==0) putc('0');
else for(;x;x/=10) buf[++p]=x%10+48;
for(;p!=-1;p--) putc(buf[p]);
}

putc为输出单个字符函数,buf为缓存区,一般开到20即可。

2、单个字符

没什么说的,就直接输出。

1
inline void write(const char &c) {putc(c);}

3、字符串

因为传参的最佳匹配原因,字符串要分两种重载方式。

1
2
3
inline void write(char *s) {
while(*s!='\0') putc(*s),s++;
}
1
2
3
inline void write(const char *s) {
while(*s!='\0') putc(*s),s++;
}

当传入char *s时,最佳匹配是template<tyename T> write(Type x),而不是write(const char *s)。更佳的匹配是write(char *s)。所以要写两个重载。

4、浮点数

浮点数的快输由于精度以及四舍五入的问题,比快读更加难写并且容易出锅。

这里给出一种鬼畜的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int pre=1,rep;
inline void write(double x) {
static char buf[50];int p=-1;
for(rep=1;rep<=pre;rep++) x*=10.0;
x=(int)x;
if(x<0) {putc('-');x=-x;}
if(x==0) buf[++p]='0';
else {
for(rep=1;rep<=pre;rep++,x/=10) buf[++p]=(int)x%10+48;
buf[++p]='.';
if((int)x==0) buf[++p]=48;
else for(;(int)x;x/=10) buf[++p]=(int)x%10+48;
}
for(;p!=-1;p--) putc(buf[p]);
}

调用时

1
write(round(x*10.0)/10.0);

此处保留$k$位小数就乘除$10^k$

做题记录(三)

[POI2011]ROT-Tree Rotations

树上线段树合并。考虑在每个叶节点建一颗权值线段树,然后向上合并。

因为交换子树只会影响到跨越左右子树的逆序对数,所以考虑决策是否交换。

在合并左右子树的权值线段树时,设左子树当前节点为$a$,右子树的当前节点为$b$,$lc,rc$分别为权值线段树中的左右儿子。则不交换在当前值域产生的逆序对数为$sum[rc[a]]*sum[lc[b]]$,交换在当前值域产生的逆序对数为$sum[lc[a]]*sum[rc[b]]$。取最大值统计即可。

数学杂项

一. 组合数公式

$$ C^n_m = \frac{m!}{n!(m-n)!} , n \geq m $$
那么可以在$O(n^2)$的复杂度上递推出组合数

1
2
3
4
5
6
memset(C,0,sizeof C);
for(int i=0;i<=n;i++) {
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=C[i-1][j-1]+C[i-1][j];
}

由组合数定义易证得
$$ C^n_m = \frac{m-n+1}{n} C^{n-1}_m $$
于是也可以在$O(n)$的复杂度上递推出组合数

1
2
C[0]=1;
for(int i=1;i<=n;i++) C[i]=C[i-1]*(n-i+1)/i;//先乘后除,避免小数,但要考虑溢出的情况

注意,第二种方法因为有除法,所以不能取模。在需要给组合数取模时,应使用第一种方法。

二. 二项式定理

对于一个多项式$(a+b)^n$,其展开后的系数构成杨辉三角。即
$$ (a+b)^n = \sum_{r=0}^n C^r_n a^{n-r} b^r $$
所以,可以通过递推组合数来求解杨辉三角即多项式系数。
例题:洛谷1313 计算系数 洛谷2822 组合数问题
难题:UVa1635 Irrelevant Elements

三. 卢卡斯定理

数论中Lucas定理描述为:
设p为素数,$a,b\in N^*$,并且
$$ a=a_kp^k+a_{k-1}p^{k-1}+ \cdots +a_1p+a_0,\ $$
$$ b=b_kp^k+b_{k-1}p^{k-1}+ \cdots +b_1p+b_0,\ $$
这里$0\leq a_i,b_i \leq p-1$都是整数,$i=0,1,2,…,k.$.那么:
$ C^b_a \equiv C^{b_k}{a_k} \cdot C^{b_{k-1}}{a_{k-1}} \cdot \cdots \cdot C^{b_0}_{a_0} (mod : p) $
证明略。

应用:

求$C^m_n mod : k$,其中$n,m\leq 10^{10}$,k是素数且较小.

四. 容斥原理

在计数时,必须注意无一重复,无一遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。 即:

$$
\left| A_1 \cup A_2 \cup \cdots \cup A_m \right| = \sum_{i=1}^m \left| a_i \right| - \sum_{j=i+1}^m \left| A_i \cup A_j \right| + \sum_{k=j+1}^m \left| A_i \cup A_j \cup A_k \right| - \cdots + \left( -1^{m-1} \right)\left| A_1 \cup A_2 \cup A_3 \cup \cdots \cup A_m \right|
$$

五. 欧拉函数

定义:小于或等于n的正整数中与n互质的数的数目, 记作$\varphi \left(n\right)$.定义式 :

$$
\varphi \left(n\right) = \sum_{S \in {p_1p_2p_3 \cdots p_n}} (-1)^{|S|} \frac{n}{\prod_{p_i \in S} p_i}
$$

可乘性:$\varphi \left(p \cdot q\right)=\varphi \left(p\right) \cdot \varphi \left(q\right)$, 当且仅当$p,q$互质

计算式:$\varphi \left(n\right) = n \cdot \prod_{p|n} (1-\frac{1}{p})$

1
2
3
4
5
6
7
8
9
10
inline int euler_varphi(int n) {
int ans=n,m=sqrt(n);
for(R i=2;i<=m;i++) {
if(n%i) continue;
ans=ans/i*(i-1);
while(n%i==0) n/=i;
}
if(n>1) ans=ans/n*(n-1);
return ans;
}

线性递推:

1
2
3
4
5
6
7
8
9
10
void get_varphi(int n) {
varphi[1]=1;
for(R i(2);i<=n;i++) {
if(varphi[i]) continue;
for(R j(i);j<=n;j+=i) {
if(!varphi[j]) varphi[j]=j;
varphi[j]=varphi[j]/i*(i-1);
}
}
}

六. 欧拉定理

$$
a^c \equiv \begin{cases}
a^{c \bmod \varphi \left(m\right) } & gcd\left(a,m\right)=1 \\
a^c & gcd\left(a,m\right)\neq 1 \pmod m , c<\varphi \left(m\right) \\
a^{\left(c \bmod \varphi \left(m\right)\right)+\varphi \left(m\right)} & gcd\left(a,m\right)\neq 1 \pmod m , c \geq \varphi \left(m\right)
\end{cases}
\pmod m
$$

模版:洛谷P5091

QT题单数学练习

GCD等于XOR GCD XOR


$$
\sum_{i=1}^n\sum_{j=i}^n\left[gcd(i,j)=i \operatorname{xor} j\right]
$$

$$
\operatorname{gcd}(a,b)=a \operatorname{xor}b=c\quad (a\ge b)\\
\Rightarrow \operatorname{gcd}(\frac{a}{c},\frac{b}{c})=1,\
$$

异或为不借位的减法,所以两数差一定不大于两数异或

$$
a-b\le c\quad,\\
\Rightarrow \frac{a}{c}-\frac{b}{c}\le 1
$$

综上,$a-b=a\operatorname{xor}b$。先枚举$a$的约数,再枚举$a$。预处理前缀和即可。

Same GCDs

设$d=gcd(a,m)$,则
$$
gcd\left(\frac{a}{d},\frac{m}{d}\right)=gcd\left(\frac{a+x}{d},\frac{m}{d}\right)=1
$$
得到
$$
\frac{a+x}{d} \perp \frac{m}{d} \Leftrightarrow \frac{x}{d} \perp \frac{m}{d}
$$
所以$a$仅仅是将$[0,m-1]$的数进行了一段平移,答案为$\varphi\left(\frac{m}{d}\right)$

2-SAT

洛谷4782
题意:给定m个约束条件,形式为$x_i,x_j$,表示$x_i$为真/假或$x_j$为真/假,给每个变量赋值使得所有条件得到满足。

方法:

将问题转化为图论问题。设$x$表示变量$x$取false,¬$x$表示变量$x$取true。建立$2 \times n$个点,设$x_i$对应点$i$,¬$x_i$对应点$i+n$,则连有向边的意义为若前者成立则后者必成立。利用给出条件连边建图:

约束条件 连边
$x_i$ or $x_j$ $i+n \rightarrow j , j+n \rightarrow i$
¬$x_i$ or $x_j$ $i \rightarrow j , j+n \rightarrow i+n$
$x_i$ or ¬$x_j$ $i+n \rightarrow j+n , j \rightarrow i$
¬$x_i$ or ¬$x_j$ $i \rightarrow j+n , j \rightarrow i+n$

以一言以蔽之:对于每个约束,若其中一个变量不满足条件,则另一个必须满足。
连边代码如下位运算毒瘤

1
2
AddEdge(u+n*(a^1),v+n*(b&1));
AddEdge(v+n*(b^1),u+n*(a&1));

接下来需要找出是否有可行解。可以发现,$i$是$j$的前驱当且仅当$i$点的取值条件成立时$j$点的取值条件成立(此处取值条件指点所指的变量为truefalse),并且有$i$点的取值条件不成立时$j$点的取值条件不一定成立。显然,当$x_i$和¬$x_i$属于同一个强连通分量时,不存在可行解(存在互相矛盾)。因此,只要使用$tarjan$缩点,在每个强连通分量中看有没有$i$和$i+n$的点对即可实现。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int low[maxn<<1],dfn[maxn<<1],stamp,belong[maxn<<1],cnt;
int s[maxn<<1],top;
char ins[maxn<<1];
void tarjan(int u) {
dfn[u]=low[u]=++stamp;
s[++top]=u;ins[u]=0xff;
for(R i(head[u]);i;i=e[i].next) {
const int &v=e[i].v;
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]) {
cnt++;
while(s[top+1]!=u) {
belong[s[top]]=cnt;
ins[s[top--]]=0x0;
}
}
}

for(R i(1);i<=n;i++)
if(belong[i]==belong[i+n])
return write("IMPOSSIBLE\n"),0;

最后,要找出一组可行解。由上文可知,当$i$为$i+n$的前驱时,$x_i$取true;当$i+n$为$i$的前驱时,$x_i$取false(让前者不成立,后者成立)。在$tarjan$时,标号数组belong即为反向的拓扑序。因此,通过此数组即可得出前驱后继关系,即$i \text{为j的前驱} \Leftrightarrow belong[i]>belong[j]$。
代码如下:

1
2
for(R i(1);i<=n;i++)
write((int)(belong[i]>belong[i+n])," \n"[i==n]);

最后放出完整代码,不要说我快读毒瘤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <cstdio>
#include <cctype>
#include <cstring>
#define R register int

namespace quick {
#define tp template<typename Type>
namespace in {
inline char getc() {
static char buf[1<<21],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read(char *s) {
*s=getc();
while(isspace(*s)) {*s=getc();if(*s==EOF) return 0;}
while(!isspace(*s)&&*s!=EOF) {s++;*s=getc();}
*s='\0'; return 1;
}
tp inline int read(Type &x) {
x=0;bool k=false;char c=getc();
while(!isdigit(c)) {k|=(c=='-');c=getc();if(c==EOF) return 0;}
while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getc();}
x*=(k?-1:1); return 1;
}
template <typename Type,typename... Args>
inline int read(Type &t,Args &...args) {
int res=0;
res+=read(t);res+=read(args...);
return res;
}
}
using in::read;
namespace out {
char buf[1<<21];int p1=-1;const int p2=(1<<21)-1;
inline void flush() {
fwrite(buf,1,p1+1,stdout);
p1=-1;
}
inline void putc(const char &c) {
if(p1==p2) flush();
buf[++p1]=c;
}
inline void write(char *s) {
while(*s!='\0') putc(*s),s++;
}
inline void write(const char *s) {
while(*s!='\0') putc(*s),s++;
}
tp inline void write(Type x) {
static char buf[30];int p=-1;
if(x<0) {putc('-');x=-x;}
if(x==0) putc('0');
else for(;x;x/=10) buf[++p]=x%10+48;
for(;p!=-1;p--) putc(buf[p]);
}
inline void write(const char &c) {putc(c);}
template <typename Type,typename... Args>
inline void write(Type t,Args ...args) {
write(t);write(args...);
}
}
using out::write;
using out::flush;
tp inline Type max(const Type &a,const Type &b) {
if(a<b) return b;
return a;
}
tp inline Type min(const Type &a,const Type &b) {
if(a<b) return a;
return b;
}
tp inline void swap(Type &a,Type &b) {
a^=b^=a^=b;
}
tp inline Type abs(const Type &a) {
return a>=0?a:-a;
}
#undef tp
}
using namespace quick;

const int maxn=1e6+20,inf=0x3f3f3f3f;
int n,m;

struct Edge {
int v,next;
Edge(int v=0,int next=0) :v(v),next(next) {}
}e[maxn<<2];
int head[maxn<<1],k;
inline void AddEdge(const int &u,const int &v) {
e[++k]=Edge(v,head[u]);
head[u]=k;
}

int low[maxn<<1],dfn[maxn<<1],stamp,belong[maxn<<1],cnt;
int s[maxn<<1],top;
char ins[maxn<<1];
void tarjan(int u) {
dfn[u]=low[u]=++stamp;
s[++top]=u;ins[u]=0xff;
for(R i(head[u]);i;i=e[i].next) {
const int &v=e[i].v;
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]) {
cnt++;
while(s[top+1]!=u) {
belong[s[top]]=cnt;
ins[s[top--]]=0x0;
}
}
}

int main(void) {
#ifndef ONLINE_JUDGE
freopen("sat.in","r",stdin);
#endif
read(n,m);
for(R i(1);i<=m;i++) {
R u,a,v,b;
read(u,a,v,b);
AddEdge(u+n*(a^1),v+n*(b&1));
AddEdge(v+n*(b^1),u+n*(a&1));
}
for(R i(1);i<=(n<<1);i++) if(!dfn[i]) tarjan(i);
for(R i(1);i<=n;i++)
if(belong[i]==belong[i+n])
return write("IMPOSSIBLE\n"),flush(),0;
write("POSSIBLE\n");
for(R i(1);i<=n;i++)
write((int)(belong[i]>belong[i+n])," \n"[i==n]);
flush();
return 0;
}

洛谷1587 [NOI2016]循环之美 题解

题面

题意:

给定$n,m,k$,求对于$1\le x \le n,1\le y\le m$,$\frac{x}{y}$满足数值上互不相等且在$k$进制下为纯循环小数的个数。

从小数部分第一位开始的循环小数,称为纯循环小数。特别地,整数为纯循环小数。

解法:

要满足数值上互不相等,只需统计最简分数,即$x\perp y$即可。

接下来要判定纯循环小数。

引理:$\frac{x}{y},(x\perp y)$在$k$进制下是循环小数当且仅当$y\perp k$

证明:

设$\frac{x}{y}$为纯循环最简小数,在$k$进制下其循环节长为$l$。

由纯循环小数定义可知$\frac{x}{y}k^l-\frac{x}{y}=\frac{x}{y}\left(k^l-1\right)\in Z$($Z$为整数集)。

又$x\perp y$,则$y|\left(k^l-1\right)$。

接下来反证。假设$y\not\perp k$。因为有$k^l \not\perp \left(k^l-1\right)$,即$k\not\perp \left(k^l-1\right)$,可推出$y\not \perp \left(k^l-1\right)$,与上文结论矛盾。

证毕。

转化

于是,问题转化为了求$\sum_{x=1}^n\sum_{y=1}^m\left[x\perp y\right]\left[y\perp k\right]$。

反演并改变枚举顺序可得
$$
\sum_{x=1}^n\sum_{y=1}^m\left[x\perp y\right]\left[y\perp k\right]\\
=\sum_{x=1}^n\sum_{y=1}^m\left[y\perp k\right]\sum_{d|x,d|y}\mu(d)\\
=\sum_{d=1}^{min(n,m)}\mu(d)\left[d\perp k\right]\lfloor\frac{n}{d}\rfloor\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\left[y\perp k\right]\\
$$

设$f\left(n,k\right)=\sum_{i=1}^n\left[i\perp k\right],g\left(n,k\right)=\sum_{i-1}^n\mu(i)\left[i\perp k\right]$,则$\sum_{x=1}^n\sum_{y=1}^m\left[x\perp y\right]\left[y\perp k\right]=\sum_{d=1}^{min(n,m)}\mu(d)\left[d\perp k\right]\lfloor\frac{n}{d}\rfloor f\left(\lfloor\frac{m}{d}\rfloor,k\right)$

因为平方因子与其他数与它是否互质无关,不妨设$k$无完全平方因子(若有将其除掉)。设$p$为$k$的一个质因子,则对于$f$有
$$
f(n,1)=\sum_{i=1}^n1=n,\\
f(n,k)= \sum_{i=1}^n\left[i\perp k\right]= \sum_{i=1}^n\left[i\perp \frac{k}{p}\right]-\sum_{i=1}^n\left[i\perp \frac{k}{p}\right]\left[p|i\right]\\
=f\left(i,\frac{k}{p}\right)-\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\left[ip\perp \frac{k}{p}\right]=f\left(i,\frac{k}{p}\right)-\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\left[i\perp \frac{k}{p}\right]\\
=f\left(i,\frac{k}{p}\right)-f\left(\lfloor\frac{n}{p}\rfloor,\frac{k}{p}\right),\qquad \left(p|k,p\in P\right)
$$

对于$g$有:

$$
g\left(n,1\right)=\sum_{i=1}^n\mu(i),\\
g\left(n,k\right)=\sum_{i=1}^n\mu(i)\left[i\perp k\right]=\sum_{i=1}^n\mu(i)\left[i\perp \frac{k}{p}\right]-\sum_{i=1}^n\mu(i)\left[i\perp \frac{k}{p}\right]\left[p|i\right]\\
=g\left(n,\frac{k}{p}\right)-\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\mu(ip)\left[ip\perp \frac{k}{p}\right]\\
=g\left(n,\frac{k}{p}\right)-\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\mu(i)\mu(p)\left[i\perp p\right]\left[i\perp \frac{k}{p}\right]\\
=g\left(n,\frac{k}{p}\right)-\mu(p)\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\mu(i)\left[i\perp k\right]\\
=g\left(n,\frac{k}{p}\right)+g\left(\lfloor\frac{n}{p}\rfloor,k\right)\qquad \left(p|k,p\in P\right)\\
\left(\quad \mu(p)=-1 \quad \right)
$$

以上$P$为质数集,利用了莫比乌斯函数的性质$\mu(ab)=\mu(a)\mu(b)\left[a\perp b\right]$

于是,对于$k=1$的情况,$f$可$O(1)$求解,$g$使用杜教筛即可。

对于$k>1$的情况,递归求解即可。

最后数论分块即可求解。递归部分时间复杂度$O\left(\sqrt n\frac{logk}{loglogk}\right)$,杜教筛部分时间复杂度$O(n^{\frac{2}{3}})$。

思路来自于11Dimensions。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <cstdio>
#include <cctype>
#include <cstring>
#include <unordered_map>
#define R register int
using std::unordered_map;

namespace quick {
#define tp template<typename Type>
namespace in {
inline char getc() {
static char buf[1<<21],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read(char *s) {
*s=getc();
while(isspace(*s)) {*s=getc();if(*s==EOF) return 0;}
while(!isspace(*s)&&*s!=EOF) {s++;*s=getc();}
*s='\0'; return 1;
}
tp inline int read(Type &x) {
x=0;bool k=false;char c=getc();
while(!isdigit(c)) {k|=(c=='-');c=getc();if(c==EOF) return 0;}
while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getc();}
x*=(k?-1:1); return 1;
}
template <typename Type,typename... Args>
inline int read(Type &t,Args &...args) {
int res=0;
res+=read(t);res+=read(args...);
return res;
}
}
using in::read;
namespace out {
char buf[1<<21];int p1=-1;const int p2=(1<<21)-1;
inline void flush() {
fwrite(buf,1,p1+1,stdout);
p1=-1;
}
inline void putc(const char &c) {
if(p1==p2) flush();
buf[++p1]=c;
}
inline void write(char *s) {
while(*s!='\0') putc(*s),s++;
}
inline void write(const char *s) {
while(*s!='\0') putc(*s),s++;
}
tp inline void write(Type x) {
static char buf[30];int p=-1;
if(x<0) {putc('-');x=-x;}
if(x==0) putc('0');
else for(;x;x/=10) buf[++p]=x%10+48;
for(;p!=-1;p--) putc(buf[p]);
}
inline void write(const char &c) {putc(c);}
template <typename Type,typename... Args>
inline void write(Type t,Args ...args) {
write(t);write(args...);
}
}
using out::write;
using out::flush;
tp inline Type max(const Type &a,const Type &b) {
if(a<b) return b;
return a;
}
tp inline Type min(const Type &a,const Type &b) {
if(a<b) return a;
return b;
}
tp inline void swap(Type &a,Type &b) {
a^=b^=a^=b;
}
tp inline Type abs(const Type &a) {
return a>=0?a:-a;
}
#undef tp
}
using namespace quick;

typedef long long ll;
const int maxn=1e6+20,limit=1e6,inf=0x3f3f3f3f;
int n,m,k;

int mu[maxn];//g的第一维
int prime[maxn],cnt,pk[maxn],tot;
void Init(int &k) {
static char not_prime[maxn];
mu[1]=1;
for(R i(2);i<=limit;i++) {
if(~not_prime[i]) prime[cnt++]=i,mu[i]=-1;
for(R j(0);j<cnt&&prime[j]<=limit/i;j++) {
not_prime[i*prime[j]]=0xff;
if(i%prime[j]==0) break;
mu[i*prime[j]]=-mu[i];
}
}
for(R i(1);i<=limit;i++) mu[i]+=mu[i-1];
for(R i(0);i<cnt&&prime[i]<=k;i++) {
while(k%(prime[i]*prime[i])==0) k/=prime[i];
if(k%prime[i]==0) pk[tot++]=prime[i];
}
}
#define f1(i) i
#define g1(i) mu[i]
unordered_map<int,ll> G1;
ll GetG1(const int &n) {
if(n<=limit) return g1(n);
if(G1[n]) return G1[n];
ll ans=1;
for(R i(2),j;i<=n;i=j+1) {
j=n/(n/i);
ans-=(ll)(j-i+1)*GetG1(n/i);
}
return G1[n]=ans;
}

unordered_map <int,unordered_map <int,ll> > F,G;
ll f(const int &n,const int &k,const int &now=0) {
if(!n) return 0;
if(k==1) return ll(f1(n));
if(F[n][k]) return F[n][k];
return F[n][k]=f(n,k/pk[now],now+1)-f(n/pk[now],k/pk[now],now+1);
}

ll g(const int &n,const int &k,const int &now=0) {
if(!n) return 0;
if(k==1) return GetG1(n);
if(G[n][k]) return G[n][k];
return G[n][k]=g(n,k/pk[now],now+1)+g(n/pk[now],k,now);
}

int main(void) {
#ifndef ONLINE_JUDGE
freopen("bea.in","r",stdin);
#endif
read(n,m,k);
Init(k);
ll ans=0;
for(R i(1),j;i<=n&&i<=m;i=j+1) {
j=min(n/(n/i),m/(m/i));
ans+=(ll)(g(j,k)-g(i-1,k))*(n/i)*f(m/i,k);
}
write(ans,'\n');
flush();
return 0;
}

注意n和m不要交换,我就是因为这个调了一上午

  • Copyrights © 2020 柳苏明
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信