圈和块 – GNAQ 的心语屋

2020年9月3日2020年12月25日

随便讲点 2-SAT

~~我知道还有个连载咕着，不要提醒我。~~

2018年11月3日2018年11月6日

洛谷 P1660 数位平方和

最大的 $x$ 是 $S(999999) \,\, (K=6)$ ，这个数字是 $3188646$ 。其余待求函数值的 $x$ 都小于这个数字。

所以最多是 $4 \times 10^6$ 个元素求函数值然后再求个和，直接暴力。

试一下样例发现会出环，环上答案为环上最小值。

做完了。

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;cstdlib&gt;
#include&lt;queue&gt;
#include&lt;vector&gt;
#include&lt;map&gt;
#include&lt;set&gt;
#define ll long long
using namespace std;

ll ans,K,A,B;
const ll mod=10000007;
ll H[4000010],S[4000010];
int vis[4000010];

template&lt;typename int_t&gt;
void readx(int_t&amp; x)
{
	x=0; int_t k=1; char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

ll fastpow(ll an,ll p)
{
	ll ret=1;
	for (;p;p&gt;&gt;=1,an=an*an) if (p&amp;1) ret*=an;
	return ret;
}

ll GetS(ll val)
{
	if (S[val]) return S[val];
	ll ret=0;
	while (val)
	{
		ret+=fastpow(val%10,K);
		val/=10;
	}
	return S[val]=ret;
}

ll GetH(ll val)
{
	if (H[val]!=0) return H[val];
	if (vis[val]==2) return val;
	vis[val]++;
	ll S=GetS(val);
	H[val]=min(val,min(S,GetH(S)));
	vis[val]--;
	return H[val];
}

int main()
{
	readx(K); readx(A); readx(B);
	H[1]=1;
	for (int i=B;i&gt;=A;i--)
		ans=(ans+GetH(i))%mod;
	cout&lt;&lt;ans&lt;&lt;endl;
}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<iterator>

#include<cstdlib>

#include<queue>

#include<vector>

#include<map>

#include<set>

#define ll long long

using namespace std;

ll ans,K,A,B;

const ll mod=10000007;

ll H[4000010],S[4000010];

int vis[4000010];

template<typename int_t>

void readx(int_t& x)

{

x=0; int_t k=1; char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

ll fastpow(ll an,ll p)

{

ll ret=1;

for (;p;p>>=1,an=an*an) if (p&1) ret*=an;

return ret;

}

ll GetS(ll val)

{

if (S[val]) return S[val];

ll ret=0;

while (val)

{

ret+=fastpow(val%10,K);

val/=10;

}

return S[val]=ret;

}

ll GetH(ll val)

{

if (H[val]!=0) return H[val];

if (vis[val]==2) return val;

vis[val]++;

ll S=GetS(val);

H[val]=min(val,min(S,GetH(S)));

vis[val]--;

return H[val];

}

int main()

{

readx(K); readx(A); readx(B);

H[1]=1;

for (int i=B;i>=A;i--)

ans=(ans+GetH(i))%mod;

cout<<ans<<endl;

}

2018年9月13日2018年12月19日

从特殊的图论模型谈开去

最近停课集训算是让我短时间内也接触了不少图论模型，再加上之前的，够我写一篇文了。

在这篇里面我并不想谈关于弦图，区间图，PQTree，完美消除序列以及那篇文留下的几个大坑，我想从几个比较常用的和比较具有启发性的小玩意说起。

斯坦纳树

我是在做 [JLOI2015]管道连接的时候学习到 Steiner Tree Problem 的。这个东西是什么呢？

我们看一下背景……

背景

Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices). Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.

斯坦纳树问题 (STP) , 或者说最小斯坦纳树问题, 是一类 组合优化 问题的统称, 那么尽管这个问题可能被设定到许多环境中, 但它都是一类要求: 对于给定的一个对象集合和一个预先定义好的作用于对象的函数, 求出集合的最佳互联的问题.

我们常用的 Steiner Tree Problem 的一个同义指的是在图上的 STP . 也就是给定一个非负权边的无向图和一个顶点的子集 ( 这些给定的顶点通常被称为 terminals ) , 那么我们要求一个把 terminals 联通的最小权生成树. (虽然这个生成树可以有非 terminal 结点).

还有一些奇怪的变种比如 Euclidean Steiner tree problem 和 rectilinear minimum Steiner tree problem.

(这个翻译我真的尽力了.)(我再翻译一些)

这个问题可以说是(非负权的)最短路问题和 MST 问题的组合. 那么如果只有两个 terminals , 它显然是一个最短路问题. 如果所有的结点都是 terminals , 它则是一个 MST 问题.

虽然最短路问题和 MST 问题都是 P 问题, 他们的好哥们 Steiner Tree Problem 却是一个 NPC 问题! 但是虽然大多数 STP 都是 NP-hard 的, 但在某些限制条件下它可以在多项式时间内解决.

$P o l l a k - G i l b e r t$ 猜想

Pollak-Gilbert 猜想指出，平面上任意 $n$ 点集，斯坦纳最小树长与最小生成树之长的比值的最小值是 $\frac{\sqrt{3}}{2}$ 。

求解问题

子集DP。把 $j$ 的二进制各位的 $0/1$ 看做集合中各个元素选/不选，那么可以设计状态 dp[i][j] 来表示以 $i$ 作为根, 并且集合选择状态为 $j$ 的情况下的最优解答。

转移分两步：

先通过对 $j$ 进行划分求得对于 $i,j$ 下的最优解。
再通过 $i,j$ 去优化 $j$ 下的其他根的答案。

为什么只优化 $j$ 下的呢？因为其他联通状态会转移到 $j$ 或由 $j$ 转移得到。

第一种转移：

for (j = 0 to (1&lt;&lt;n)-1)
{
    for (i = 1 to n) if (i in j)
    {
        for (sub=(j-1)&amp;j;sub;sub=(sub-1)&amp;j)
        {
            dp[i][j]=min(dp[i][j],dp[i][sub]+dp[i][j-sub]);
        }
        
        if dp[i] isnot INF 
        {
            que.push(i); vis[i]=1;
        }
    }
    SPFA_Update(j);
}

for (j = 0 to (1<<n)-1)

{

for (i = 1 to n) if (i in j)

{

for (sub=(j-1)&j;sub;sub=(sub-1)&j)

{

dp[i][j]=min(dp[i][j],dp[i][sub]+dp[i][j-sub]);

}

if dp[i] isnot INF

{

que.push(i); vis[i]=1;

}

SPFA_Update(j);

}

除了枚举子集去更新之外，不要忘记要把有效状态放入队列。

第二种转移：

void SPFA_Update(int state)
{
    //SPFA
    //如何更新呢
    if (dp[v][state]&gt;dp[u][state]+edge.cost) 
    {
        dp[v][state]=dp[u][state]+edge.cost;
    }
}

void SPFA_Update(int state)

{

//SPFA

//如何更新呢

if (dp[v][state]>dp[u][state]+edge.cost)

{

dp[v][state]=dp[u][state]+edge.cost;

}

复杂度分析

我们枚举子集的复杂度应是 $n \times \sum (C_k^i \times 2^i) = n \times 3^k$

那个 SPFA 的复杂度是 $n \times 2^k$ 。

那么就是 $O(n \times 3^k)$ 。

流程回顾

枚举状态集S 
{ 
     枚举S的子集s 
     { 
         更新dp[S][1~n],将 dp[S][x]&lt;inf 的x入队 
     }
     SPFA更新(S) 
}

枚举状态集S

{

枚举S的子集s

{

更新dp[S][1~n],将 dp[S][x]<inf 的x入队

}

SPFA更新(S)

}

Advanced: 斯坦纳森林问题

并没有多大难度。

考虑这样一件事情：我们给定并非一组 terminals ，我们给定 $k$ 组。

对于这 $k$ 组 terminals ，我们只要求同组中的是互相联通的。求一个生成树的最小花费方案。

那么我们可以这样：

我们枚举一个状态 $w$ , 然后我们把 $w$ 二进制拆分对应的几个集合中的 terminals 看成一组 terminals 。然后去做 STP。

然后我们求全集的答案就是再次子集DP一遍：

for (w = 0 to (1&lt;&lt;k)-1)
{
    STP(w);
}
for (w = 0 to (1&lt;&lt;k)-1)
{
    for (sub=(w-1)&amp;w;sub;sub=(sub-1)&amp;w) 
    {
        DP[w]=min(DP[w],DP[sub]+DP[w-sub]);
    }
}
ans = DP[(1&lt;&lt;k)-1];

for (w = 0 to (1<<k)-1)

{

STP(w);

}

for (w = 0 to (1<<k)-1)

{

for (sub=(w-1)&w;sub;sub=(sub-1)&w)

{

DP[w]=min(DP[w],DP[sub]+DP[w-sub]);

}

ans = DP[(1<<k)-1];

就很简单做完了。

图的遍历问题

这个问题比较有来头，他牵涉到了图论的起源（或者说创生？）

背景是著名的所谓 Könisberg seven bridge problem ，相信大家都已经耳熟能详了。

由此我们诞生了 Euler 回路或者说， Euler 环游问题。

那么现在我们来看另一个更难的问题： the Chinese Postman Problem (CPP)

(注：下文顶点和结点混用，但其实是一回事，vertex or vertice)

一些记号

环游就是从结点 $v_0$ 出发最终回到 $v_0$ 的一个有序路径。

在一个无向正权图上，经过每条边至少一次的环游的权是经过边的权值与次数的乘积的和。

即: $v_0e_1,v_1e_2,\cdots ,e_nv_0$ 的权为 $\sum_{i=1}^{n} w_{e_i}$ 。

图的最优环游就是该图的最小权的环游。

问题描述

那么这个问题是这样被描述的：

给定一个无向正权联通图，求出最优环游。

求解

第一，如果图是一个 Euler 图，那么显然任意一个 Euler 环游都是一个最优环游。

第二：非 Euler 图

把这个图记为 $G$

我们使用一种方法就是重复边法，说白了很简单，我们先假设答案已经求得，我们先规定每条边只能经过一次，然后把答案中重复的边拆成多条边，在原图上画出。

记这个新图为 $G'$ ，这个 $G'$ 显然是一个 Euler 图。

那么我们的任务就是构造出这样一个 Euler 图 $G'$ 并且让它添加的边(称为重复边)的边权总和 $W$ 最小。

Edmonds-Johnson 算法

case 1: $G$ 正好有两个奇次(度)顶点

记这两个顶点为 $S,T$ ，跑最短路即可。

case 2: $G$ 有 $2n$ 个奇次顶点

我们使用 Edmonds 最小对集算法

思想：就是把 case 1 推广到了多组顶点上。

先用随便什么方法求出所有奇次顶点之间的最短路。 (Floyd or Dijkstra)

然后以这些奇次顶点为点集，做一个完全图，边权是两点间最短路。该图记为 $G_1$ 。

我们跑带花树求出 $G_1$ 的最小权完美匹配。(取负跑最大权完美匹配）

然后就做完了。

case 3:其余情况无解

注: 带花树写的只要不丑，差不多110行多点(含头文件IO等)。

注：我不会写。

2-SAT问题

缓更，但今晚肯定会更。

2018年2月27日

USACO 草鉴定Grass Cownoisseur

In an effort to better manage the grazing patterns of his cows, Farmer John has installed one-way cow paths all over his farm. The farm consists of N fields, conveniently numbered 1..N, with each one-way cow path connecting a pair of fields. For example, if a path connects from field X to field Y, then cows are allowed to travel from X to Y but not from Y to X.

Bessie the cow, as we all know, enjoys eating grass from as many fields as possible. She always starts in field 1 at the beginning of the day and visits a sequence of fields, returning to field 1 at the end of the day. She tries to maximize the number of distinct fields along her route, since she gets to eat the grass in each one (if she visits a field multiple times, she only eats the grass there once).

As one might imagine, Bessie is not particularly happy about the one-way restriction on FJ’s paths, since this will likely reduce the number of distinct fields she can possibly visit along her daily route. She wonders how much grass she will be able to eat if she breaks the rules and follows up to one path in the wrong direction. Please compute the maximum number of distinct fields she can visit along a route starting and ending at field 1, where she can follow up to one path along the route in the wrong direction. Bessie can only travel backwards at most once in her journey. In particular, she cannot even take the same path backwards twice.

INPUT: (file grass.in)

The first line of input contains N and M, giving the number of fields and the number of one-way paths (1 <= N, M <= 100,000).

The following M lines each describe a one-way cow path. Each line contains two distinct field numbers X and Y, corresponding to a cow path from X to Y. The same cow path will never appear more than once.

OUTPUT: (file grass.out)

A single line indicating the maximum number of distinct fields Bessie

can visit along a route starting and ending at field 1, given that she can

follow at most one path along this route in the wrong direction.

四句话题解(非常简单)：

Tarjan瞎缩一波点

然后单原SPFA求点1能到的点的答案贡献

然后跑单汇SPFA求能到点1的点的答案贡献

最后枚举反边判相连求答案

// luogu-judger-enable-o2
#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;cstdlib&gt;
#include&lt;iterator&gt;
#include&lt;queue&gt;
using namespace std;

struct ed
{
	int pre,to;
}edge[100010]={0};
int nodenum,edgenum,pointer[100010]={0},at=1,fx,tx;

int dfn[100010]={0},low[100010]={0},stackx[100010]={0},headx=0,tstamp=0,cache1;
bool instack[100010]={0};

int sccnum=0,belong[100010]={0},nodev[100010]={0};

ed edge1[100010]={0},edge2[100010]={0};
int at1=1,pt1[100010]={0},at2=1,pt2[100010]={0};
queue&lt;int&gt; que;
int mdp[100010]={0},mdn[100010]={0};

inline void readx(int&amp; x)
{
	x=0; int k=1; register char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline void Insert()
{
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	pointer[fx]=at;
	at++;
}

inline void Tarjan(int u)
{
	dfn[u]=low[u]=++tstamp; stackx[++headx]=u; instack[u]=true;
	int prex=pointer[u];
	while (prex)
	{
		if (!dfn[edge[prex].to])
		{
			Tarjan(edge[prex].to);
			low[u]=min(low[u],low[edge[prex].to]);
		}
		else if (instack[edge[prex].to]) low[u]=min(low[u],dfn[edge[prex].to]);
		prex=edge[prex].pre;
	}
	
	if (dfn[u]==low[u])
	{
		sccnum++;
		do
		{
			cache1=stackx[headx--];
			instack[cache1]=false; nodev[sccnum]++;
			belong[cache1]=sccnum;
		} while (cache1!=u);
	}
}

inline void Shrink()
{
	int prex=0;
	for (int i=1;i&lt;=nodenum;i++)
	{
		prex=pointer[i];
		while (prex)
		{
			if (belong[edge[prex].to]!=belong[i])
			{
				edge1[at1].pre=pt1[belong[i]];
				edge1[at1].to=belong[edge[prex].to];
				pt1[belong[i]]=at1;
				at1++;
				
				edge2[at2].pre=pt2[belong[edge[prex].to]];
				edge2[at2].to=belong[i];
				pt2[belong[edge[prex].to]]=at2;
				at2++;
			}
			prex=edge[prex].pre;
		}
	}
}

inline void LPFA()
{
	int prex; memset(instack,0,sizeof(instack));
	
	que.push(belong[1]); mdp[belong[1]]=nodev[belong[1]];
	while (!que.empty())
	{
		cache1=que.front(); que.pop();
		prex=pt1[cache1]; instack[cache1]=false;
		while (prex)
		{
			if (mdp[edge1[prex].to]&lt;mdp[cache1]+nodev[edge1[prex].to])
			{
				mdp[edge1[prex].to]=mdp[cache1]+nodev[edge1[prex].to];
				if (!instack[edge1[prex].to])
				{
					instack[edge1[prex].to]=true;
					que.push(edge1[prex].to);
				}
			}
			prex=edge1[prex].pre;
		}
	}
	
	memset(instack,0,sizeof(instack));
	que.push(belong[1]); mdn[belong[1]]=nodev[belong[1]];
	while (!que.empty())
	{
		cache1=que.front(); que.pop();
		prex=pt2[cache1]; instack[cache1]=false;
		while (prex)
		{
			if (mdn[edge2[prex].to]&lt;mdn[cache1]+nodev[edge2[prex].to])
			{
				mdn[edge2[prex].to]=mdn[cache1]+nodev[edge2[prex].to];
				if (!instack[edge2[prex].to])
				{
					instack[edge2[prex].to]=true;
					que.push(edge2[prex].to);
				}
			}
			prex=edge2[prex].pre;
		}
	}
}

int main()
{
	readx(nodenum); readx(edgenum);
	for (int i=1;i&lt;=edgenum;i++)
	{
		readx(fx); readx(tx);
		Insert();
	}
	
	for (int i=1;i&lt;=nodenum;i++) if (!dfn[i]) Tarjan(i);
	
	Shrink();
	LPFA();
	
	int prexx=0,ans=nodev[belong[1]];
	for (int i=1;i&lt;=nodenum;i++)
	{
		prexx=pointer[i];
		while (prexx)
		{
			if (belong[i]!=belong[edge[prexx].to] &amp;&amp; mdn[belong[i]] &amp;&amp; mdp[belong[edge[prexx].to]])
				ans=max(ans,mdp[belong[edge[prexx].to]]+mdn[belong[i]]-nodev[belong[1]]);	
			prexx=edge[prexx].pre;
		}
	}
	
	printf("%d\n",ans);
	return 0;
}

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

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

// luogu-judger-enable-o2

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#include<iterator>

#include<queue>

using namespace std;

struct ed

{

int pre,to;

}edge[100010]={0};

int nodenum,edgenum,pointer[100010]={0},at=1,fx,tx;

int dfn[100010]={0},low[100010]={0},stackx[100010]={0},headx=0,tstamp=0,cache1;

bool instack[100010]={0};

int sccnum=0,belong[100010]={0},nodev[100010]={0};

ed edge1[100010]={0},edge2[100010]={0};

int at1=1,pt1[100010]={0},at2=1,pt2[100010]={0};

queue<int> que;

int mdp[100010]={0},mdn[100010]={0};

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline void Insert()

{

edge[at].pre=pointer[fx];

edge[at].to=tx;

pointer[fx]=at;

at++;

}

inline void Tarjan(int u)

{

dfn[u]=low[u]=++tstamp; stackx[++headx]=u; instack[u]=true;

int prex=pointer[u];

while (prex)

{

if (!dfn[edge[prex].to])

{

Tarjan(edge[prex].to);

low[u]=min(low[u],low[edge[prex].to]);

}

else if (instack[edge[prex].to]) low[u]=min(low[u],dfn[edge[prex].to]);

prex=edge[prex].pre;

}

if (dfn[u]==low[u])

{

sccnum++;

{

cache1=stackx[headx--];

instack[cache1]=false; nodev[sccnum]++;

belong[cache1]=sccnum;

} while (cache1!=u);

}

inline void Shrink()

{

int prex=0;

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

{

prex=pointer[i];

while (prex)

{

if (belong[edge[prex].to]!=belong[i])

{

edge1[at1].pre=pt1[belong[i]];

edge1[at1].to=belong[edge[prex].to];

pt1[belong[i]]=at1;

at1++;

edge2[at2].pre=pt2[belong[edge[prex].to]];

edge2[at2].to=belong[i];

pt2[belong[edge[prex].to]]=at2;

at2++;

}

prex=edge[prex].pre;

}

inline void LPFA()

{

int prex; memset(instack,0,sizeof(instack));

que.push(belong[1]); mdp[belong[1]]=nodev[belong[1]];

while (!que.empty())

{

cache1=que.front(); que.pop();

prex=pt1[cache1]; instack[cache1]=false;

while (prex)

{

if (mdp[edge1[prex].to]<mdp[cache1]+nodev[edge1[prex].to])

{

mdp[edge1[prex].to]=mdp[cache1]+nodev[edge1[prex].to];

if (!instack[edge1[prex].to])

{

instack[edge1[prex].to]=true;

que.push(edge1[prex].to);

}

prex=edge1[prex].pre;

}

memset(instack,0,sizeof(instack));

que.push(belong[1]); mdn[belong[1]]=nodev[belong[1]];

while (!que.empty())

{

cache1=que.front(); que.pop();

prex=pt2[cache1]; instack[cache1]=false;

while (prex)

{

if (mdn[edge2[prex].to]<mdn[cache1]+nodev[edge2[prex].to])

{

mdn[edge2[prex].to]=mdn[cache1]+nodev[edge2[prex].to];

if (!instack[edge2[prex].to])

{

instack[edge2[prex].to]=true;

que.push(edge2[prex].to);

}

prex=edge2[prex].pre;

}

int main()

{

readx(nodenum); readx(edgenum);

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

{

readx(fx); readx(tx);

Insert();

}

for (int i=1;i<=nodenum;i++) if (!dfn[i]) Tarjan(i);

Shrink();

LPFA();

int prexx=0,ans=nodev[belong[1]];

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

{

prexx=pointer[i];

while (prexx)

{

if (belong[i]!=belong[edge[prexx].to] && mdn[belong[i]] && mdp[belong[edge[prexx].to]])

ans=max(ans,mdp[belong[edge[prexx].to]]+mdn[belong[i]]-nodev[belong[1]]);

prexx=edge[prexx].pre;

}

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

return 0;

}

斯坦纳树

背景

Pollak−Gilbert 猜想

求解问题

复杂度分析

流程回顾

Advanced: 斯坦纳森林问题

图的遍历问题

一些记号

问题描述

求解

Edmonds-Johnson 算法

2-SAT问题

$P o l l a k - G i l b e r t$ 猜想