richard-desktop

骑士周游是指在一个N×M的棋盘上，从某一点出发，按照国际象棋的跳法，不重复地经过每一个格子。其实本质上是求一个Hamilton回路。我们有时候需要对给定的一个棋盘，输出一个骑士周游的方案。往往首先想到的是搜索。但是搜索对于N，M较大的时候并不可取，这时候就会想到构造。我所了解的构造方法有两种，一种是在小棋盘的基础上每次增加宽度为2的路径，一种是把4个小棋盘合并起来。这里所要介绍的是后一种方法。而且这两种构造方法都对N，M有且均为偶数的要求。

首先，考虑N×N的棋盘。对棋盘进行黑白染色，得出马的路径必然是黑白相间的这一结论。又由于一条Hamilton回路上的黑白格子的数量应当相等，所以在N×N为奇数的时候问题无解。也就是在N为奇数的时候无解。反之，在N为偶数的情况下，一定存在Hamilton回路。

首先观察一下最基本的棋盘。由于4×4的棋盘无解，所以在这里我们只考虑6×6、6×8、8×8、 8×10、10×10、10×12的棋盘。据有关资料说，对于这些棋盘用回溯法可以在O(1)的时间内找到Hamilton回路，但是具体情况我不清楚。对于4个角上的格子，由于它们的度仅为2，而且观察有解的情况，必定是下面的情况。

而如果要得到8×6、10×8、12×10，只需要将6×8、8×10、10×12的棋盘旋转90度。对于的情形，我们就需要采用分治策略。方法如下：

1. 分治：将棋盘尽可能平均的分割成4块；
2. 合并：将4个子棋盘拼接。如下图：

这时，为了合并4个子棋盘，对于原有的边A-B、C-D、E-F、G-H，我们将它们变为A-G、B-D、C-F、E-H，这样就合并了4个子棋盘。至此，分治的过程结束。

上面的解法只是求得一个Hamilton回路，但是对于条件更弱的Hamilton通路，我们并没有类似的算法。

无限递降法就是一种特殊的反证法，它利用了最小自然数原理。先假设存在一个最小解，然后在这个最小解的基础上推出一个更小的解，再结合最小自然数原理得到矛盾，从而证明命题。

无限递降法经典的一个例子就是证明x⁴+y⁴=z²没有正整数解。

我们假定存在一个正整数解，那么其中必定存在一个解x₀,y₀,z₀使得z₀最小。我们得到必有(x₀,y₀)=1，否则会推出一个更小的解。由于是方程x²+y²=z²的一个本原解，所以x₀和y₀必然是一奇一偶，不妨设2|y₀，以及(y₀,z₀)=1。

我们有，由此及2不整除即得。我们又有

令。这里v>u>0,(u,v)=1，u,v都是奇数。进而有

我们又得到(v²-u²,(v²+u²)/2)=1，因为(v²-u²,v²+u²)|(2v²,2u²)=2(v²,u²)=2，又u,v都是奇数，所以2不整除(v²+u²)/2，所以(v²-u²,(v²+u²)/2)=1。

我们再令v²-u²=a²,(v²+u²)/2=b²，这里a>0,b>0,(a,b)=1,2|a,2不整除b。由u,v满足的条件及a,b得0<b<v<z₀，及u,a,v是方程x²+y²=z²的本原解且2|a。因此得到u=r²-s², a=2rs, v=r²+s²。所以r⁴+s⁴=b²，而b<z₀，与z₀的最小性矛盾，命题得证。

无限递降法对于构造的要求很高，确实不是一个很好用的方法。

题目在这里可以找到。

题目的大概意思是说，在整数格点的平面上有一个简单多边形（顶点坐标均为有理数），问其内部有多少格点。题目保证不会有格点出现在边界上。

三角剖分是不现实的，我们只能选择简单一些的梯形剖分。进而，我们需要计算一条直线下方的格点数目。这里的转化都比较简单，直接略过。接着，我们就把问题转化为了求一个这样的式子：

这是一个相当有趣的求值。显然，O(n)的算法并不能让我们满意。对于这个经典的问题，我们有和两种算法。由于细节问题很多，我介绍的是的算法。对算法有兴趣的同学可以查看相关的论文。

考察这个式子，首先，a和d都应该满足大于等于0，小于m的条件。否则我们可以通过变形得到新的a'和d'。我们如果要在时间内计算出它的值，一定要设法缩小它的规模。我们将这个式子呈现在平面坐标系中，发现这其实就是求下面的一个图中

所有蓝色点的数目。所有的水平直线表示用来截取的y=km的常函数，红色的点则是(i,a+di)。问题到现在就是求每个点向下引射线，一共和这些直线能够有多少交点。显然，这些直线一共有条。那么，我们对每条直线进行观察，发现如果我们只是求一条直线上有多少交点，是可以在O(1)的时间之内计算的。对于一条直线y=km，我们可以求出所有的交点数是。

至此，问题的规模已经被缩小了，我们得到新的式子：

这里，我们需要对等式的右边进行一些细节处理，因为a+dn和m可能大于d。这样，我们成功的把问题规模缩小了，而这是一个类似取模的缩小方式，我们自然得到每次问题的规模至少被缩小到原来的一半，那么算法的复杂度就是级别的。

NEERC2005主页在这里。

题目给定n和k，要求。

我们先找一下规律，发现与等差数列是有关系的。我们对于当前的i，令，。那么当i增大1时，如果q不变，p一定减少了q，那么将p一直减小到0，同时对这一段进行求和（用数列求和公式），同时i增大到下一段的开头。

详细情况见代码：

#include <cstdio>
#include <algorithm>

using namespace std;

int n,k;

__int64 sum(int a,int d,int n) {
  return (__int64)(2*a-d*n)*(n+1)/2;
}

int main() {
  freopen("joseph.in","r",stdin);
  freopen("joseph.out","w",stdout);
  scanf("%d%d",&n,&k);
  int i = 1,p,q,a;
  __int64 r = 0;
  while (i<=n) {
    q = k%i; p = k/i;
    if (p>0) a = q/p;
    else a = INT_MAX;
    r += sum(q,p,min(a,n-i));
    i += min(a,n-i)+1;
  }
  printf("%I64d\n",r);
  return 0;
}

就我所知，有三种时间复杂度为O(n)的方法可以求强连通分量，分别是Kosaraju、Tarjan和Gabow。

1. Kosaraju
   算法的步骤为
   • 对图G进行DFS，并按照遍历完成的先后顺序进行标号。
   • 将图G中所有的边反向得到G'。
   • 对G'进行DFS，每轮DFS都选择编号最大的点最为当前的遍历树的根。
   • 最后，遍历得到的森林就是SCC的集合。
   该算法的优点在于，最后得到的节点是按照拓扑序组织好的，在求解2-SAT的过程中十分方便。
2. Tarjan
   第一个求解SCC的算法，应用非常广泛，几乎任何和图的遍历有关的问题都可以套用Tarjan算法的思想（比如，求割点、桥、块等等）。
   在遍历时，对每一个节点定义时间戳，同时定义Low函数，含义为节点及其子孙通过非父子边的返祖边所能到达的最小时间戳。最后若Low函数等于其时间戳，则当前递归栈内存在一个SCC。
   代码如下：
   

   void dfs(int index) {
     low[index] = dfn[index] = cnt++;
     used[index] = 1;
     del[index] = 0;
     st[top++] = index;
     for (int i = last[index]; i!=-1; i = e[i].nxt)
       if (!used[e[i].y]) {
         dfs(e[i].y);
         if (low[index]>low[e[i].y]) low[index] = low[e[i].y];
       }
       else if (!del[e[i].y]) if (low[index]>dfn[e[i].y])
         low[index] = dfn[e[i].y];
     if (low[index]==dfn[index]) {
       do {
         root[st[--top]] = index;
         del[st[top]] = 1;
       } while (st[top]!=index);
     }
   }
   

3. Gabow
   算法的原理说起来太麻烦，还是直接给出代码。其实这个算法并不是很常用。
   

   #include <cstdio>
   #include <cstring>
   #include <stack>
   
   using namespace std;
   
   const int MAXN = 1000;
   
   struct node {
     int tar;
     node *nxt;
     node(int _tar,node *_nxt)
       : tar(_tar),nxt(_nxt) {}
   };
   
   node *g[MAXN];
   int n,m,co,all,dfn[MAXN],id[MAXN];
   stack<int> vec,path;
   
   void dfs(int x) {
     dfn[x] = co++;
     vec.push(x);
     path.push(x);
     for (node *i = g[x]; i!=NULL; i = i->nxt)
       if (dfn[i->tar]==-1) dfs(i->tar);
       else if (id[i->tar]==-1)
         while (dfn[path.top()]>dfn[i->tar]) path.pop();
     if (path.top()==x) path.pop();
     else return;
     for (int i; ;) {
       id[i = vec.top()] = all;
       vec.pop();
       if (i==x) break;
     }
     all++;
   }
   
   int main() {
     freopen("gabow.in","r",stdin);
     freopen("gabow.out","w",stdout);
     scanf("%d%d",&n,&m);
     memset(g,0,sizeof(g));
     for (int i = 0,a,b; i<m; i++) {
       scanf("%d%d",&a,&b); a--; b--;
       g[a] = new node(b,g[a]);
     }
     co = all = 0;
     memset(dfn,-1,sizeof(dfn));
     memset(id,-1,sizeof(id));
     for (int i = 0; i<n; i++)
       if (dfn[i]==-1) dfs(i);
     for (int i = 0; i<n; i++)
       printf("%d\n",id[i]);
     return 0;
   }