这一题的一个比较简单的思路，就是对于一个点 $a_i$，找到 $y$ 坐标在区间 $[y_i + m, max_y]$ 内的所有点中，$x_i$ 的前驱和后继，然后更新答案。

对于二维平面上的的区间查询问题，树套树应该是最经典的解法了。比如这一题可以用线段树套平衡树，对于线段树的每个节点 $[L, R]$ 上建立一个平衡树，保存输入序列上 $y$坐标 落在 $[L, R]$ 内的点的 $x$ 坐标。因为平衡树本身支持查询前驱和后继，所以实现树套树之后就很简单了，该算法的时间复杂度为 $O(n \log^2 n)$。不过似乎树套树主要用来解决带修的这种问题，并且不容易调试，码长略长，所以还是思考另外的做法。

跟磁力块那一题的解法类似，可以用分块做，一开始觉得用分块时间复杂度可能比较高（当时还准备放弃写树套树，幸亏我太蒻了没学过树套树，要不然掉进坑里了），但是实际好像相当快？

对于每个块用 $y$ 值排序，内部用 $x$ 值排序，对于每一个点，二分找到满足条件（即 $y$ 坐标和该点的 $y$ 坐标的差 $\ge m$）的最小的块（预先保存每个块的最小 $y$ 值），由于预先排序保证了这个块之后的块也都满足条件，然后再在这些块内部二分找到 $x$ 坐标的前驱和后继，更新答案，然后对于最左的块的左边一个块，朴素枚举，更新答案。

对于每一个点的查询操作，时间复杂度为 $O(\sqrt n \log n)$

故总时间复杂度为 $O(n \sqrt n \log n)$

当然，这样的时间复杂度还是很高，但是还有很多优秀的算法：

譬如 skylake 大佬的算法：通过维护 $y$ 坐标的区间最值，然后用尺取法，保证两个最值的差 $\ge m$，然后更新答案。这个算法实在是太优秀了，并且代码写出来极为简洁，好像是大佬开始比赛十分钟秒掉的？简直叹为观止 orzorz%%%%%%%%，我还没有学过 RMQ，可能不是很了解，不过据推测这个时间复杂度是 $O(n \log n + n)$？果然犇人写犇算法，直接比我的算法快一个数量级（虽然可能这一题数据太水，我的代码反而快了大雾）。

再譬如 关神犇 提出的算法：维护两个二叉堆，堆内以 $y$ 坐标为关键字，并且在堆外以 $x$ 为关键字排序。每次枚举一个点就取出两个堆中满足条件的点，更新答案，然后弹出这些数（因为已经以 $x$ 为关键字排序，所以在当前点之后的点不会离这些点更近，即这些点对于答案已经没有贡献了），之后把该点存入堆内。这个算法实在是太神了（关神犇您是我的神orzorzorz%%%%%%%%%%%%%%%），因为只进行了 $2n$ 次插入和 $n$ 次删除操作，每个操作的时间复杂度是 $\log n$，所以总时间复杂度为 $O(n \log n)$。看这道题的标签里有优先队列，也许正解就是这个，为此再次膜拜神犇叹为观止的做题直觉orzorz。

当然，除此之外，还有用线段树维护区间最值的神犇的方法，具体思路和 skylake 大佬的大同小异，不过线段树实现代码更加冗长，这里不再赘述。

上述各位神犇的思路我都进行了代码实现，可以去 我的博客 察看作为参考。

选择了第一个选左边或者右边之后，不难想到第一个选到的数所对应的另一个数一定要最后一个输出，为了达到最后一个输出，这个两边的数要分开处理，左边的数对应的都是 L，右边的数对应的都是 R。

将这两边看做两个队列 $L$ 和 $R$，首先我们感性地考虑：两边队头对应的另一个数一定比较 “远”，猜测可能是两边队列的队尾。接下来我们证明一定是队尾：

假设接下来要确定的回文子串的长度是 $l$（先前确定在答案序列中的数已在队列中删除），那么 $|L| + |R| - 2 = l - 2$，就是说除了这两个数之外的 $l - 2$ 个数都要先弹出队列，如果对应的这个数不在队尾，那么除非包括这个数弹出，弹出队列的数量达不到 $l - 2$，就是说这个数把队列卡住了。由此，队头对应的数一定是队尾，如果两个队列的队尾都没有对应的数，就说明无解。

确定队头对应的数一定是其中一个队列的队尾之后，把这个两个数从队列中删除也就不难了，只需实现两个双端队列，弹出一个队头之后把这个队尾也弹出就行了，假设队头的答案序列位置是 $k$，那么对应的队尾的位置就是 $n - k + 1$。

考虑字典序，我们优先把第一个数选为 L，并且队头也要优先考虑 L 。

题面由wzw改编自NOIP1998 提高组 进制位

前置结论：

1.进制为n-1

2.单个字母对应的数字即为所在行两位数个数

3.单个字母对应的数字即为其在表中(除表头)出现的次数-1

证明：

1.因为n-1个不同的数，所以最少n-1进制。假设为n进制，那么一定有一个数没有出现，设为k

(1)k=0或1，1+(n-1)=10，不成立

(2)1<k≤n-1，1+(k-1)=k，不成立

同理可证大于n-1进制的情况不成立，故进制一定为n-1。

2.字母对应的数字为0…n-2，易证结论2。

3.设字母对应的数字为x，则x=0+x=1+(x-1)=2+(x-2)=... =(x-1)+1=x+0

方法

法1：

dfs暴力枚举每个字母所对应的数。

法2：(根据结论1、2)

预处理每个数的值和字母与数字的对应关系，枚举每个数检验。

法3：(根据结论3)

统计得出单个字母对应的数字，判断合法性。

代码

法1代码：

#include <bits/stdc++.h>

using namespace std;

char s[15][15][10];

int n,p,tot=0,num[15],cd[30];

bool ok[15]={0},qwq=0;

vector<int>v;

void dfs(int pt){

   if (qwq==1)return ;

   if (pt==tot+1){

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

           cd[v[i]]=num[i+1];

       }

       bool yes=0;

       for (int i=2;i<=n;i++){

           for (int j=2;j<=n;j++){

               int now=0;

               for (int k=1;k<=strlen(s[i][j]+1);k++){

                   now*=p;now+=cd[s[i][j][k]-'A'];

               }

               if (now!=cd[s[1][i][1]-'A']+cd[s[j][1][1]-'A']){

                   yes=1;break;

               }

           }

           if (yes==1)break;

       }

       if (yes==0){

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

               cout<<char(v[i]+'A')<<"="<<cd[v[i]]<<" ";

           }

           cout<<endl<<p<<endl;

           qwq=1;

       }

       return ;

   }

   for (int i=0;i<p;i++){

       if (ok[i]==0){

           num[pt]=i;

           ok[i]=1;dfs(pt+1);

           ok[i]=0;

       }

   }

   return ;

}

int main(){

   freopen ("murasame_adultxp3.in","r",stdin);

   freopen ("murasame_adultxp3.out","w",stdout);

   scanf("%d",&n);

   bool has[30]={0};

   for (int i=1;i<=n;i++){

       for (int j=1;j<=n;j++){

           scanf("%s",s[i][j]+1);

           if (s[i][j][1]!='+'){

               for (int k=1;k<=strlen(s[i][j]+1);k++){

                   if (has[s[i][j][k]-'A']==0){

                       v.push_back(s[i][j][k]-'A');tot++;

                       has[s[i][j][k]-'A']=1;

                   }

               }

           }

       }

   }

   for (p=tot;p<=10;p++){

       memset(ok,0,sizeof(ok));

       dfs(1);

   }

   if (qwq==0){

       cout<<"FccKcuf"<<endl;

   }

   return 0;

}

法2代码：

#include<bits/stdc++.h>

using namespace std;

inline int read()

{

   char ch=getchar();

   int f=1,x=0;

   while (ch<'0' || ch>'9')

   {

       if (ch=='-') f=-1;

       ch=getchar();

   }

   while (ch>='0' && ch<='9')

   {

       x=x*10+ch-'0';

       ch=getchar();

   }

   return f*x;

}

int n,ans[15],mp[26];

char s[15][15][3];

inline bool check(int x,int y) //检验 (x,y)

{

   int sum=ans[x]+ans[y]; //和

   int cur=s[x][y][1]-'A'; //处理十位

   if (sum>=n-1 && mp[cur]!=1) return 0; //如果和 >=n-1 但没有进位

   if (sum>=n-1) sum-=n-1,cur=s[x][y][2]-'A'; //处理个位

   if (mp[cur]!=sum) return 0; //不相等

   return 1;

}

signed main()

{

   n=read();

   for (int j=1;j<=n;j++) scanf("%s",s[1][j]+1);

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

   {

       int cnt=0;

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

       {

           scanf("%s",s[i][j]+1);

           cnt+=strlen(s[i][j]+1)>=2;

       }

       ans[i]=cnt;

       mp[s[i][1][1]-'A']=cnt;

   }

   for (int i=2;i<=n;i++) for (int j=2;j<=n;j++) if (!check(i,j)) return 0&puts("ERROR!");

   for (int i=2;i<=n;i++) printf("%c=%d ",s[i][1][1],ans[i]);

   return !printf("\n%d",n-1);

}

法3代码：

#include<bits/stdc++.h>

using namespace std;

char a[10][10][5];

int n,g[300];

int main(){

   freopen("murasame_adultxp3.in","r",stdin);

   freopen("murasame_adultxp3.out","w",stdout);

   ios::sync_with_stdio(0);

   cin.tie(0);

   cout.tie(0);

   cin>>n;

   for(int i=1;i<=n;i++){

       for(int j=1;j<=n;j++){

           cin>>a[i][j];

       }

   }

   for(int i=2;i<=n;i++){

       for(int j=2;j<=n;j++){

           if(strlen(a[i][j])==1){

               g[a[i][j][0]]++;

           }

       }

   }

   for(int i=2;i<=n;i++){

       for(int j=2;j<=n;j++){

           int x=g[a[i][1][0]]-1,y=g[a[1][j][0]]-1;

           int z=0;

           int l=strlen(a[i][j]);

           for(int k=0;k<=l-1;k++){

               int val=g[a[i][j][k]]-1;

               z=z*(n-1)+val;

           }

           if(x+y!=z){

               cout<<"FccKcuf"<<endl;

               return 0;

           }

       }

   }

   for(int i=2;i<=n;i++){

       cout<<a[1][i][0]<<"="<<g[a[1][i][0]]-1<<" ";

   }

   cout<<endl<<n-1<<endl;

   return 0;

}

因为这篇题解原文是用 Markdown 写成，在 我的博客 上面可能会有更好的阅读体验

考虑一个合法的括号序列长什么样子：(...) ，即由外面的括号和里面的部分组成，有用的信息来自于内部，于是我们关注内部可以由什么组成：

根据定义，一个合法的括号序列，内部可以是：S、AA、ASA、A、AS、SA，其中，AA 和 ASA 比较特殊，因为它们本身就是一个 A，信息被包含在 A 中。于是得到一个公式：

$$A_{i, j} = A_{i + 1, j - 1} + S_{i + 1, j - 1} + AS_{i + 1, j - 1} + SA_{i + 1, j - 1} \notag$$

接下来，我们考虑这些部分的信息如何维护：

1. 对于 A：我们若将这个递推公式深究到底，会得到什么？什么情况下就递归不下去了？也许最后的 A 是一个 ()，这当然合法，并且这个信息无法从别处递推来，于是，对于这个，我们在遇到的时候需要统计一下。或者，(S) 也是一个合法的括号序列，再往下深究，就是一个 S ，就是说，如果 (S) 放到上面的公式中，最后会得到一个 S 的值，显然这个值得是 $1$
2. 对于 S：经过上面的讨论，$\forall i, j \in \mathbb{N^+}, S_{i, j} = 1$ 而这个等式成立的前提是 $i, j$ 中间的部分完全由 '*' 组成

对于 AS，SA，ASA，AA 这些由 A 和 S 这两个比较基本的部分组成的部分，我们用乘法原理，可以求出它们的值。即：

$$AS_{i, j} = \sum_{i \le k \le j}A_{i, k} \times S_{k + 1, j} \notag \\ SA_{i, j} = \sum_{i \le k \le j}S_{i, k} \times A_{k + 1, j} \notag \\ ASA_{i, j} = \sum_{i \le k \le j}A_{i, k} \times SA_{k + 1, j} \notag \\ AA_{i, j} = \sum_{i \le k \le j}A_{i, k} \times A_{k + 1, j} \notag \\$$

需要注意的是，如果我们将 AA 和 ASA 的信息累加到 A 中，会导致原来的信息被覆盖掉，导致出错，所以在程序实现中我们需要用一个数组来备份合并操作之前的信息。

$ \begin{aligned}ans &= \frac{\binom{num_l}{2} + \binom{num_{l + 1}}{2} + \dots + \binom{num_r}{2}}{\binom{r - l + 1}{2}} \\ &= \frac{num_l(num_l - 1) + num_{l + 1}(num_{l + 1} - 1) + \dots + num_r(num_r - 1)}{(r - l + 1)(r - l)} \\ &= \frac{(num_l^2 + num_{l + 1}^2 + \dots + num_r^2) - (num_l + num_{l + 1} + \dots + num_r)}{(r - l + 1)(r - l)} \\ &= \frac{(num_l^2 + num_{l + 1}^2 + \dots + num_r^2) - (r - l + 1)}{(r - l + 1)(r - l)} \end{aligned} $

而

$ (n + 1)^2 = n^2 + 1 + 2n \\ (n - 1)^2 = n^2 + 1 - 2n $

所以对于每一个询问 $[l, r]$，我们只需要将当前询问的分子加上 $2n + 1$ 即可 $O(1)$ 地将答案扩展至 $[l, r + 1]$ 或 $[l - 1, r]$，而对于缩小区间的操作，同理。

于是，我们可以用 $\mid l' - l \mid + \mid r' - r \mid$ 次操作转移至下一询问区间。

而利用分块，将所处分块作为第一关键字，将右区间作为第二关键字，可以实现 $O(n \sqrt n)$ 的时间复杂度。

前置知识

$Lucas$ 定理，中国剩余定理（$CRT$），费马-欧拉定理。

费马-欧拉定理

设 $a,m$ ∈ $N^+$，且 $gcd$（$a,m$）= $1$，则我们有： $a^φ$≡$1$($/mod m$)。

其中，φ($m$) 称为对模 $m$ 缩系的元素个数。

此外，$a$ 对模 $m$ 的阶必整除 $φ$($m$)。

证明如下：（自己度娘）

https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86/891345

Lucas定理

中国剩余定理（CRT）

题面概述

存在一个整数 $N$，对于约数$d$（$d|N$），求 $C_d^n$ 对 $999911659$ 取模的值

思路

$O(N)$预处理，$O(1)$查询：

先求出模 $p$ 意义下的阶乘，逆元以及逆元阶乘（因为求逆元满足积性函数）。

对于任意一个小于p的组合数 $C_m^n$，可以直接用 $jc[m] /times invjc[n] /times invjv[m-n]求出，其中 $jc[i]$ 指到 $i$ 的阶乘, $invjc[i]$ 指到 $i$ 的阶乘逆元

代码就不贴了……

0ms，0Mid