Z算法（exkmp）

这算法和马拉车非常像，它用来在 的时间内求一个 函数，其中 代表以 开头的字符串与 的lcp的长度。

Z-box：设 ，则定义区间 为一个Z-box。

对于 ，按定义来看 ，但是有时候会令 ，这个看具体题目的情况。

和马拉车非常像，Z算法也是采用dp的思路。

它在遍历的时候，维护一个Z-box区间 ，其中 是当前遇到的所有Z-box区间中最大的。

然后分类讨论：

，这时候如果 ，那么它所代表的Z-box的右边界更大，这里直接暴力做。

，这时候通过画图可以知道 ，因此我们考虑 。

若 ，这代表 也会 ，因此 。

否则 会突破右边界，对于突破右边界的情况，暴力即可。

1
2
3
4
5
6
7
8
9
10
11
12
13

int Z[_];
void exkmp(const string &s){
	int n = s.length();
	for(int i = 1, l = 0, r = 0; i < n; i++){
		if(Z[i-l] <= r - i)
			Z[i] = Z[i-l];
		else{
			Z[i] = max(r - i + 1, 0);
			while(i + Z[i] < n && s[i+Z[i]] == s[Z[i]]) ++Z[i];
			l = i; r = i + Z[i] - 1;
		}
	}
}

因为右边界只会增加 次，因此复杂度为 。

例题：https://www.luogu.com.cn/problem/P5410

https://codeforces.com/contest/1968/problem/G2

Manacher

求回文串的一个 的算法。笔者退役太久忘记了一些细节，这里重新回顾一下。

首先马拉车只能求奇回文串，因此需要在原串相邻字符间加符号，具体是这么干的：

mambaout -> $#m#a#m#b#a#o#u#t#

这样的话，原串的以字母为中心的奇回文串对应处理后的串中以字母为中心的长度为 的奇回文串。

原串的以字母之间的间隔为中心的偶回文串对应处理后的串中以 # 为中心的长度为 的奇回文串。

然后考虑马拉车算法。马拉车主要基于dp的思想。

遍历处理后的串，假设当前遍历到位置 。

然后在处理的同时维护一个变量 和变量 ，代表以 为中心的回文串，其右边界最远，为 。

然后考虑转移，如果 ，则暴力计算 的情况，然后把 更新为 ， 更新为对应的右边界。

否则可以得知 最短的回文串的情况为 。然后继续暴力拓展。

如果拓展后的右边界大于 则更新 和 。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void Manacher(){
    int l = 0;
    Ma[l++] = '$';
    Ma[l++] = '#';
    for(int i = 0; i < n; ++i){
        Ma[l++] = A[i];
        Ma[l++] = '#';
    }
    Ma[l] = 0;
    int mx = 0, id = 0;
    for(int i = 0; i < l; ++i){
        Mp[i] = mx > i ? min(Mp[2*id-i], mx-i):1;
        while(i >= Mp[i] && i+Mp[i] < l && Ma[i+Mp[i]] == Ma[i-Mp[i]]) Mp[i]++;
        if(i + Mp[i] > mx){
            mx = i + Mp[i];
            id = i;
        }
    }
}

由于 最多被更新 次，因此该算法复杂度为 。

Xv6 kernel Spinlock

Xv6操作系统内核为我们提供了两类锁：自旋锁（spinlock）和睡眠锁（sleeplock）。它们虽然都有锁的特性，但是它们具有不同的特点，应用场景也不相同。

今天我们先来讨论xv6内部spinlock的实现，首先来看 spinlock.h 内对spinlock的声明：

1
2
3
4
5
6
7
8

// Mutual exclusion lock.
struct spinlock {
  uint locked;       // Is the lock held?

  // For debugging:
  char *name;        // Name of lock.
  struct cpu *cpu;   // The cpu holding the lock.
};

十分简单，不是吗？除去debugging部分，就一个变量 locked 记录这个lock是否被某个CPU给占用。

在xv6中，lock的locked字段为0表示该lock没有被占用，字段为1表示该lock被占用了。

这可以通过 spinlock.c 中的 initlock 方法看出：

1
2
3
4
5
6
7

void
initlock(struct spinlock *lk, char *name)
{
  lk->name = name;
  lk->locked = 0;
  lk->cpu = 0;
}

对于一个给定的 spinlock ，我们需要一组函数 acquire 和 release 来分别获取与释放锁。

对于 acquire 方法，我们需要检测当前锁的 locked 变量值，若为1则继续循环（这就是自旋这个词的由来），为0则获取锁，将 locked 更改为1。

因为 spinlock 本身就是共享资源（即多个CPU的多个进程共享内存中的同一个资源），任何进程对同一个自旋锁需要互斥地访问。因此以下 for 循环体内部的代码需要转换为原子操作：

1
2
3
4
5
6
7
8
9

void acquire(struct spinlock *lk)  
{
	for(;;) {
		if(lk->locked == 0) {
			lk->locked = 1;
			break;
		}
	}
}

这里的 for 就是自旋。

xv6使用了RISCV的 amoswap 指令。从字面意义上看，就是原子交换操作。

具体来讲，xv6在acquire内部使用了指令 amoswap.w.aq a5, a5, (s1) 。这段指令的含义是从内存地址 (s1) 中读取一个32位的值（根据amoswap.w.aq 中第一个点后的 w 看出，实际上内存地址 (s1)对应的是 spinlock 中 uint 类型（刚好32位）的 locked 值），与寄存器 a5 内部存储的值进行交换。寄存器 a5 存的值在执行该指令之前就被设置为1了。也就是说，交换过后的 locked 值必然为1，而代码会根据交换过后的寄存器 a5 的值是否为0来获取锁。

来看看xv6内部 acquire 的实现：

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

// Acquire the lock.
// Loops (spins) until the lock is acquired.
void
acquire(struct spinlock *lk)
{
  push_off(); // disable interrupts to avoid deadlock.
  if(holding(lk))
    panic("acquire");

  // On RISC-V, sync_lock_test_and_set turns into an atomic swap:
  //   a5 = 1
  //   s1 = &lk->locked
  //   amoswap.w.aq a5, a5, (s1)
  while(__sync_lock_test_and_set(&lk->locked, 1) != 0)
    ;

  // Tell the C compiler and the processor to not move loads or stores
  // past this point, to ensure that the critical section's memory
  // references happen strictly after the lock is acquired.
  // On RISC-V, this emits a fence instruction.
  __sync_synchronize();

  // Record info about lock acquisition for holding() and debugging.
  lk->cpu = mycpu();
}

重点在于 __sync_lock_test_and_set(&lk->locked, 1) 这个函数。通过 gdb 可以看出其对应的汇编代码：

在这里我们看到了我们熟悉的 amoswap 指令。

另外，后面一行的 __sync_synchronize(); 是一个栅栏指令，它用于告诉编译器不要对指令进行重新排序以进行优化。

例如以下场景：

1
2
3

acquire(&lock);
x = 1;
release(&lock);

通过编译器优化，可能会重排指令，把 x=1 放到加锁前或者释放锁之后。这显然是不被允许的。

__sync_synchronize(); 的作用是强制将其前后的 load/store 指令进行分隔。因此acquire 函数与 release 函数内部使用了该指令来保证 x=1 不会跑出去。

另外，acquire 函数开头调用了 push_off() 方法。根据注释说明，它是关闭了中断。

我操？为啥要关闭中断？这个锁跟中断有什么勾八关系？

这个其实是xv6内部实现的问题。因为在xv6内部，有一些设备中断会和内核内部的代码使用同一个 spinlock ，例如 xv6 book 提到的 tickslock ，用于保护各CPU时钟内部的 ticks 时间帧的不变量。

对于计时器中断，会调用下面函数：

1
2
3
4
5
6
7
8

void
clockintr()
{
  acquire(&tickslock);
  ticks++;
  wakeup(&ticks);
  release(&tickslock);
}

但是xv6的sleep系统调用也使用了该锁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

uint64
sys_sleep(void)
{
  int n;
  uint ticks0;

  argint(0, &n);
  acquire(&tickslock);
  ticks0 = ticks;
  while(ticks - ticks0 < n){
    if(killed(myproc())){
      release(&tickslock);
      return -1;
    }
    sleep(&ticks, &tickslock);
  }
  release(&tickslock);
  return 0;
}

这会出现什么问题？

假设 sys_sleep 首先获取了 tickslock ，然后进入了 sleep(&ticks, &tickslock) 进入阻塞状态。

然后对应的CPU的计时器产生中断，想获取锁，但是被阻止，因此进入自旋。

但是只有计时器获取了锁，才能进入临界区，执行 ticks++; 来增加时间戳，从而才有 sys_sleep 从阻塞状态恢复的可能。

也就是说，产生了死锁。

为了防止这种情况，我们应当防止一个 spinlock 在能被中断处理函数获取时，在获取期间允许中断。xv6为了实现方便，直接对所有的 spinlock 在被占用时，直接关闭了中断。并在对应的 release 函数尾部重新开放中断：

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

// Release the lock.
void
release(struct spinlock *lk)
{
  if(!holding(lk))
    panic("release");

  lk->cpu = 0;

  // Tell the C compiler and the CPU to not move loads or stores
  // past this point, to ensure that all the stores in the critical
  // section are visible to other CPUs before the lock is released,
  // and that loads in the critical section occur strictly before
  // the lock is released.
  // On RISC-V, this emits a fence instruction.
  __sync_synchronize();

  // Release the lock, equivalent to lk->locked = 0.
  // This code doesn't use a C assignment, since the C standard
  // implies that an assignment might be implemented with
  // multiple store instructions.
  // On RISC-V, sync_lock_release turns into an atomic swap:
  //   s1 = &lk->locked
  //   amoswap.w zero, zero, (s1)
  __sync_lock_release(&lk->locked); 

  pop_off();
}

这里的 pop_off 方法就是开放中断。

在 spinlock 被占用期间关闭中断有以下好处：一个 spinlock 不应当被占用太久。因此在处理一个关键的任务时，对其加锁，会阻止时间片轮转，使该进程能享受所有CPU资源来集中处理当前任务，这样的化 spinlock 就不会自旋太久。

但是如果我们在某些代码中可能会同时获取多个锁，对应的会释放多个锁。那么我们在释放第一个锁的时候，是不能直接开放中断的，要等所有锁被释放后才能中断。

因此我们对于每个CPU都要有一个计数器，来统计当前CPU获取了多少个锁。关于每个CPU的结构体声明在 proc.h 下：

1
2
3
4
5
6
7

// Per-CPU state.
struct cpu {
  struct proc *proc;          // The process running on this cpu, or null.
  struct context context;     // swtch() here to enter scheduler().
  int noff;                   // Depth of push_off() nesting.
  int intena;                 // Were interrupts enabled before push_off()?
};

这里的 noff 字段就是我们需要的计数器。而 intena 则代表着获取第一个锁之前，CPU的中断状态。

接下来我们来看 push_off 和 pop_off 方法：

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

// push_off/pop_off are like intr_off()/intr_on() except that they are matched:
// it takes two pop_off()s to undo two push_off()s.  Also, if interrupts
// are initially off, then push_off, pop_off leaves them off.

void
push_off(void)
{
  int old = intr_get();

  intr_off();
  if(mycpu()->noff == 0)
    mycpu()->intena = old;
  mycpu()->noff += 1;
}

void
pop_off(void)
{
  struct cpu *c = mycpu();
  if(intr_get())
    panic("pop_off - interruptible");
  if(c->noff < 1)
    panic("pop_off");
  c->noff -= 1;
  if(c->noff == 0 && c->intena)
    intr_on();
}

可以发现，一切都清晰了很多。在 push_off 中，如果第一次获取锁，我们会先记录一下当前的中断状态。方法是调用 intr_get ，它在 riscv.h 中声明：

1
2
3
4
5
6
7

// are device interrupts enabled?
static inline int
intr_get()
{
  uint64 x = r_sstatus();
  return (x & SSTATUS_SIE) != 0;
}

这里的 SSTATUS 是一个特殊的寄存器，里面有 SIE bit 来记录是否开启中断，有 SPP bit 来记录当前mode是user mode还是 supervisor mode。在这里我们只需要 SIE bit 就行啦。

关于 spinlock 在xv6的实现细节，就讲这么多。

五月份了，得开始准备专业课的笔面试了~

主要问题来自于各类经验贴。持续更新

数学

复习资料整理：

https://zhuanlan.zhihu.com/p/567252248?utm_id=0

线性代数

问：特征值为0，和矩阵的秩有什么关系。

答： 矩阵的秩等于其非零特征值的数目。

拓展：对于对称矩阵A，其特征值都是实数。可进行特征分解：。若A满秩，则U的列向量构成线性空间 的一组正交基。

问：半正定矩阵的特征和性质。

答：其对应的二次型 对于任意的向量 皆非负，其特征值也非负。

拓展：如果是正定矩阵的话，其对应的二次型为0等价于 为零向量，其特征值都是正的，即满秩。正定矩阵对应于线性空间 上的一个椭球面。

概率论

问：说一下先验概率和后验概率。

答：

问：贝叶斯、全概率、条件概率

答：

问：大数定律是什么

答：

离散数学

问：给你一个真值表，如何推出真值表达式。

答：找出输出端为1的各行，每行的输入变量作乘，1为变量本身，0为变量取非，最后把各式进行求和即可。

问：一个有向图是有向树的条件

答：1.只有一个结点入度为0；2.边数为点数减一。

问：说出偏序、全序、良序的定义

答：

问：集合的划分、集合的基数、无穷集合的比较、单射、满射、等价关系、偏序关系、全序关系、布尔格、欧拉图、哈密顿图、树的定义、有向边树的定义。

答：逆天

高数

问：函数的极限定义。导数的定义。

答：设函数 在点 的某一去心邻域有定义，若存在常数a，对于任意给定的正数 ，都存在 使不等式 在 时恒成立，则a为函数 当 时的极限。

（白话：某个点的极限就是一个常数，该点的某个去心邻域内部的点的函数值都满足和该常数的差的绝对值小于任意小的正数）

问：一致性的定义。

答：

问：拉格朗日中值定理是什么

答：这个定理主要解释的是”平均变化率等于瞬时变化率“。具体来讲，如果函数满足在某个闭区间[a,b]上可导，在开区间(a,b)上连续，那么在开区间(a,b)上必存在一个点使得该点的导数等于平均变化率，即 。

问：介绍一下间断点。

答：间断点就是非连续点，即不满足函数极限等于函数值的点。根据左右极限将间断点分为第一类和第二类间断点，第一类间断点左右极限相等，但不等于函数值；第二类间断点指左极限或右极限不存在的点。

408

数据结构

问：讲一下两种最小生成树算法，以及如何优化。

答：Prim基于扩展点集的方法求解，每次迭代都取出与当前已加入树的点集距离最近的点加入点集。优化方法：用一个斐波那契堆来维护权重最小的边

Kruskal基于扩展边集的方法来求解。它依次取出边权小到大的边加入树，并在此之前判断是否会出现环。优化方法：并查集判联通分量。

问：给出几种求最长回文子串的解法。

答：暴力的话，可以用类似于区间dp的东西，令 表示 是否为回文串，第一维枚举长度。

然后可以枚举中心点，向外拓展，这些都是 的。

也可以把向外拓展的那个for用二分+哈希优化一下，

一般正常做都是用manacher，。

简单介绍原理的话，就是用类似于动态规划的思想，在转移的时候维护当前右边界最靠右的回文子串。根据当前位置 与右边界的大小分类讨论，如果 更大的话直接暴力， 小的话可以用维护的回文子串来转移，然后暴力拓展。均摊 。

问：树的直径怎么求。

答：随机找一个点，dfs求出离它最远的点u。然后同理找到离u最远的点v，直径即为uv。

证明可以用反证法，画画图就知道了。

问：介绍一下Huffman编码。

答：Huffman是一种前缀编码，它基于每个字符的出现频率来贪心地构建Huffman树，然后根据不同的根到叶节点的路径来得到对应的编码。

问：哪些排序算法是稳定的，哪些不稳定

答：稳定排序算法定义：关键字相同的排列顺序在排序前后不变。

问：各种排序算法及其时间复杂度。

答：

插入排序：

• 直接插入排序（当前元素插入前面已经有序的序列，）
• 折半插入排序（优化为二分查找，但是涉及到元素移动，复杂度依然是 )
• 希尔排序（增量分组插入排序，玄学算法）

交换排序：

• 冒泡排序（相邻元素交换，使最小的值一个个"冒泡"出来，）
• 快速排序（效率基于split算法（可以刷刷力扣熟悉一下？），分治，最坏情况 ，理想情况 ）

选择排序：

• 简单选择排序（选择当前最小元素，）
• 堆排序（建堆（自底向上），然后一个一个删除根，）。

归并排序：。

基数排序：， 为关键字个数， 为队列个数。

桶排序：， 为辅助空间大小。

操作系统

问：计算机启动过程。

答：

问：中断的定义。和异常有什么不同。

答：

问：经典的wait signal写代码。这个东西很无聊，只能记得自己多练，记住一些常用模型（生产者消费者、读者写者等）

问：线程进程的区别，线程同步的方式

答：

问：操作系统的四大作用

答：抽象硬件为用户接口，使计算机易于使用；提高资源的利用率，例如多道程序设计技术；

计算机网络

问：拥塞避免和流量控制

答：拥塞避免是TCP拥塞控制中采用的一个算法，其原理是在TCP发送方拥塞窗口达到一定阈值后，线性地缓慢增加拥塞窗口，这样能够有效避免拥塞。流量控制是TCP的一种限制发送方速率的算法，TCP采用滑动窗口机制实现，TCP接收端可在返回的TCP确认报文段中根据自身情况设置发送方的接收窗口大小，来达到对发送方的流量控制。

问：路由算法

答：路由协议分为两种：内部网关协议和外部网关协议。

内部网关协议之一RIP是基于距离向量的，要求自治系统内的每一个路由器都要维护到其它AS内每一个网络的距离记录，这里的距离用跳数来度量。RIP认为距离短的路由就是好的路由，在和相邻路由器（只和相邻路由器）交换信息时会根据这个原则贪心地更新自己的距离向量。RIP存在路由环路问题。

开放路径优先OSPF是基于链路状态的，它在原本RIP距离的基础上提出了“代价”这一度量指标。OSPF路由器会产生链路状态通告LSA，采用洪泛的方式对其余同AS上的路由器进行更新，最后趋于一致。在此基础上OSPF路由器会基于LSA构建的链路状态数据库，采用类似于dijkstra的算法求出到其它网络的最短路径，并以此指定路由策略。

外部网关协议有BGP，BGP要求每个AS都至少有一个路由器作为“BGP发言人”，一个BGP发言人和其它发言人交换信息需要建立一个TCP连接，然后在此基础上交换BGP报文，交换后基于自己的策略采用相应的路由算法。

计算机组成原理

问：说一下cache。cache的替换算法有哪些？

答：

数据库

问：数据库中数据的四个特性

答：

软件工程

问：给代码，求问满足不同路径下的变量集合（黑盒）

问：给代码，求问哪行出问题，如何改进（白盒）

问：课：软件生命周期、软件开发模型（瀑布、螺旋、敏捷）并比较（各自的优点适用的场景）、软件测试方法、什么是黑白盒测试、白盒测试有哪些（语句覆盖、判断覆盖、条件覆盖、路径覆盖、判断条件覆盖）、路径覆盖是否一定是条件覆盖

答：逆天

AI

勾八东西

问：介绍一下SVM原理？

答：

问：什么是凸函数？如何判断凸函数？

答：

问：有监督学习和无监督学习区别

答：

英语

问：用英文介绍自己最满意的项目。

答：I'm sorry to say I didn't do any valuable projects during my undergraduate years. If I must say so, I will introduce a online operating-system related project proposed by MIT.

问：你觉得最骄傲的一件事情

问：介绍一下你的学校？为什么来我们学校？

问：介绍一下你的家乡？

机试

作为ACMer，也要在意机试。不要自视甚高，眼高手低。

这是我少数的能拿的出手的东西，但也不要压力太大

去年南软的四道：

1. 面向对象，考察桥接模式和抽象工厂模式
2. 前缀和
3. 环形染色问题
4. 凸包算法

太变态了，考凸包？

问：一个N个正数的集合，找出和为M的子集

答：dfs???

只输出一个方案的话可以搞个背包。

杂项

问：你如果遇到无法解决的事情会怎么办

答：如果是学习或科研方面的工作，我会借助chatgpt这类工具以及一些网络上的资源来获得解答。如果是生活中的事情，我会求助于身边人，并且通过这件事情进行反思。

问：你认为你的缺点？并如何改善

答：我是个比较敏感的人，这可能并不能算做一个严格意义上的缺点。对于一件事情，我可能会提前想象出它的结果，从而导致犹豫，造成没办法在有效的时间内做出比较有效的结果。换句话说，我不是那种敢于做出突破自我的工作的人。我认为这是因为我没有专心于行动本身，从而导致自己喜欢浪费时间胡思乱想，或许这就是 终日而思，不如须臾之所学也。

问：你认为的自己的优点有哪些？

答：我认为我的自我学习能力比较强。在大学期间，我在没有任何人带我教我的情况下从零开始入坑算法竞赛，并在自我努力下能力逐渐变强，最后获得一系列ICPC等奖项。其次我是一个兴趣驱动的人，对于我感兴趣的东西，我会花时间一步一步的去弄懂它的原理，我认为因为兴趣本身，学习才会变成一个快乐的过程。

问：介绍一下你最近了解的时政（逆天

答：阿赛jumping？好的985也不比中专差。

模拟面试

1、正交矩阵有什么性质？

答：正交矩阵和它自身的转置相乘为单位矩阵。几何意义上，它所对应的线性变换为空间中的旋转和反射，即向量在正交矩阵变换下的长度和夹角保持不变。

2、矩阵的迹有什么性质？

答：矩阵的迹为矩阵对角元的和。也是所有特征值的和。对于若干的向量或矩阵相乘所得矩阵，它们相互之间轮换得到的矩阵的迹是相等的。

3、说一下你对特征值和特征向量的理解。

答：定义上，一个方阵的特征值是满足以下方程的解 ，其中 为特征值， 为其对应的特征向量。几何意义上，特征向量在方阵A上进行线性变换等价于进行 倍的长度收缩。

在机器学习中，特征向量一般代表着矩阵的“特征信息”。例如PCA降维中，我们都是先求样本的协方差矩阵，然后进行特征分解（或者奇异值分解），将样本尽量投影到其部分特征向量（一般按特征值从大到小排序）所张成的空间上，一般认为这么降维能够最大化无监督样本的特征信息。（凭记忆瞎说的，毕竟我不是搞AI的）

4、介绍一下最短路算法及其优化。

答：单源最短路径可采用经典的dijkstra算法。dijkstra只能用在正权图上，它是基于贪心的思想：它维护一个已求出最短路值的点集和未求出最短路值的点集。构建一个数组dis来表示通过已求出点集能得到的最短路径，每次从未求出点集中找出dis最小的放到已求出点集，然后再根据该点更新dis，这样迭代下去可求出所有点的最短路。朴素算法是 的，在图稀疏的时候可以采用堆优化将复杂度变为 。

多源最短路采用floyd算法，它是基于动态规划的思想，通过枚举中转结点来转移状态：。时间复杂度为 。

5、介绍一下你的项目。

答：

ABC351E - Jump Distance Sum

题意

二维平面上有 个点，对于横纵坐标之和具有相同奇偶性的点，距离为切比雪夫距离。否则距离为0.

求所有点对之间的距离之和。

切比雪夫距离与曼哈顿距离的转换

这题我在比赛中没想出来，虽然退役了，但还是有点丢人。

其实这是个很常见的套路了：将难求的切比雪夫距离转换为好求的曼哈顿距离。

先考虑曼哈顿距离的式子，它比较简单： 然后考虑到切比雪夫有 之类的东西，我们可以将上式进行转化： 乐，其实就是四种情况取最大值。 中两项取正，两项取负。

然后考虑切比雪夫距离： 展开： 我操，也是四项。

那么，令 ，代入一下，你会发现，卧槽，和曼哈顿的形式一样！

总结

所以，求曼哈顿距离时，可以将点 变成 ，然后求切比雪夫距离。

反之，求切比雪夫距离时，可以将点 变成 ，然后求曼哈顿距离。

解法

先将所有的点按奇偶性分两块，对每一块内部进行上面切比雪夫->曼哈顿的转化，然后求总距离是很简单的。

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

public class Main {
    static Scanner sc = new Scanner(System.in);
    static final int N = 1010;


    public static void main(String[] args) {
        int n = sc.nextInt();
        ArrayList<Integer>[] A = new ArrayList[4];
        for(int i = 0; i < 4; i++) A[i] = new ArrayList<>();
        for(int i = 0; i < n; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            if((x+y)%2==0){ // 转化，这里不除二，在最后答案再除二
                A[0].add(x+y);
                A[1].add(x-y);
            }else{
                A[2].add(x+y);
                A[3].add(x-y);
            }
        }
        long ans = 0;
        for(int i = 0; i < 4; i++){
            Collections.sort(A[i]);
            long s = 0; int cnt = 0;
            for(int x: A[i]){
                ++cnt; s += x;
                ans += (long)cnt * x - s;
            }
        }
        System.out.println(ans/2);
    }
}