度小满2018.9.26笔试链式边权

分手后的思念是犯贱 2022-05-10 08:36 151阅读 0赞

# 题目描述 #

![在这里插入图片描述][70]  
n个点，有n-1条边，每条边的权值被这样计算：  
在边左面的点称为x，在边右面的点称为y。x≠y。有多少这样的点对，那么这条边的权值就为多少。  
**提示：**  
第一条边能形成一个点对(1,2)  
第二条边能形成一个点对(2,1)  
所以，输出为1 1

# 动态规划 #

#include <pch.h>//vs2017建控制台程序自带的预编译头文件 #include <stdio.h> #include <vector> #include <iostream> using namespace std; int main() { int n; cin >> n; vector<int> a(n), w(n);//w存边的权值 for (int i = 0; i < n; i++) { scanf_s("%d", &a[i]); } for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (a[j] != a[i]) { w[i]++; w[j]--; } } if (i != 0) { w[i] = w[i] + w[i - 1]; } printf("%d ", w[i]); } return 0; }

重点解释一下，内层循环里面的加加和减减吧，还有`w[i] = w[i] + w[i - 1];`，这句一看就是很像是动态轨迹里面的递推式。  
以一个实际例子讲解吧：  
输入：  
4  
1 2 3 4  
输出：  
3 4 3

**初始时：**  
![在这里插入图片描述][70 1]  
**执行完第一次外层循环后：**  
![在这里插入图片描述][70 2]  
就得到了第一条边的权值，权值为3的含义是有这三个点对。剩下三个点的权值都为-1，假如1称为已经记录的点，那么这个-1就代表当前点与已记录点之间能形成多少点对，比如2这个点与已记录点1之间能形成一个点对(1,2)，所以2点在当前的权值为-1。（注意这里以及之后的“权值”不是指原题中指的权值）

**执行完第二次外层循环后：**  
![在这里插入图片描述][70 3]  
就得到了第二条边的权值，权值为4的含义是有这四个点对。首先这个2很好理解，从当前点2往后遍历，发现有两个点对(2,3)(2,4)。但是1和边右面的点还没有统计，但是也不需要统计，因为这个信息肯定包括在之前记录的点1的权值里面即(1,2)(1,3)(1,4)，但是由于(1,2)不应该包括进来，所以这时候之前在点2记录的权值-1即(1,2)就派上了用场，这样，(3-1)就得2即(1,3)(1,4)。

第三次外层循环也是一个道理。

**总结一下：**  
1.第i次循环结束后，第i条边的权值会被记录。也称0 - i的点们已经被记录，因为0 - i的点们和i+1 - n-1的点们之间能形成的点对数量已经被w\[i\]所记录，也就是题意的意思。

2.第i次循环结束后，从i+1 - n-1的点的权值也会被更新：注意i+1 - n-1的点们的权值必为负值，他的绝对值是指，当前点与已经记录的点之间形成的点对数量。

3.除开第一次外层循环，每次外层循环i中，对w\{i\}的更新都是两部分：第一是当前点i与边右面的点之间形成的点对数，这个是用内层循环做的；第二是0 - i-1的点们与边右面的点之间形成的点对数，这个信息已经被w\[i-1\]存储，但信息不是都需要的，需要除开0 - i-1的点们与点i之间形成的点对数，而这个需要除开的数量刚好就是当前w\[i\]存的负值的绝对值。

# 动态规划 #

这是第二种用法，python3代码。思路与上一种完全一样，但具体细节实现有所不同。

首先重点理解下我这句话，要得到一个数x和一个数的数组yArray之间可以形成多少个点对，只需要得到yArray的长度减去yArray中x的数量。

使用了`collections.Counter()`，是计数器的功能，可以得到一个键值key出现的次数。

import collections
     
    n = eval(input())
    a = list(map(int,input().split()))
     
    lw = collections.Counter()
    l_count = 0
    rw = collections.Counter(a)
    r_count = n
    res = [0] * (n-1)
    for i in range(n-1):
        lw[a[i]] += 1
        l_count += 1
        rw[a[i]] -= 1
        r_count -= 1
        res[i] = res[i-1] + (r_count - rw[a[i]]) - (l_count - lw[a[i]])
        #第0次循环不需要单独加判断，因为res[-1]=res[0]=0
     
    print( ' '.join(map(str,res)))

和上一种代码一样，在每次循环i中，`(r_count - rw[a[i]])`代表了当前点i与边右面的点之间形成的点对数。`res[i-1] - (l_count - lw[a[i]])`代表0 - i-1的点们与边右面的点之间形成的点对数，这个信息已经被`res[i-1]`存储，但需要除开一部分信息即0 - i-1的点们与点i之间形成的点对数，需要除开的信息刚好就是`(l_count - lw[a[i]])`，注意`lw[a[i]])`至少为1。

再解释一下，这个需要除开的信息，就是，边左面的点的数量减去边左面的点中`a[i]`出现的次数，即为0 - i-1的点们与点i之间形成的点对数。

[70]: /images/20220510/cea00429813047e0918ec70786946683.png
[70 1]: /images/20220510/6980426b30134c29ac7170af63c8a024.png
[70 2]: /images/20220510/3505b04610484553b3424c71db4555f2.png
[70 3]: /images/20220510/bbd23a453ec04e8aaaaf11c8f0dfac84.png