对数

教学目标

• 公式$\sum a(i)$,$a(i)$:以$i$为结点的值是什么
• 本质++不重不漏++集合分类问题

题目: 黑白气球

有一排黑白气球,你可以随机选两个球,问有多少种方法选到颜色不同的球?

• 第一行表示有多个气球
• 0表示白色
• 1表示黑色

6
0 1 1 0 0 1

输出

9

代码

//Author by [Rainboy](https://github.com/rainboylvx) 
//date: 2024-05-03 17:22:44
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,m;
int a[maxn];
int ans;

int main (int argc, char *argv[]) {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
    }

    //枚举以i为结尾
    for(int i = 2;i <= n ;++i ) // i: 1->n
    {
        // 枚举对应的起点
        for(int j = 1;j <= i-1 ;++j ) // j: 1->i
        {
            if( a[j] != a[i])
                ans++;
        }
    }
    std::cout << ans << "\n";

    return 0;
}

解释

本质这是一个++不重不漏++的集合分类问题

先给每个气球进行编号

0 1 1 0 0 1
1 2 3 4 5 6

那么答案的$9$对气球如下:

证明这是一个集合问题:

原题目部我们: 1. 任何选一对 2. 且这一对的颜色不同

我们一步一步做,任选一对气球,可以得到集合$A = \{(1,2),{1,3},{2,3},{1,4},{2,4}, \cdots,(5,6)\}$这样的集合,然后去除集合$A$中颜色相同的一对气球,得到集合$B = \{(1,2), (1,3), (2,4), (3,4), (2,5), (3,5), (1,6), (4,6), (5,6) \}$,那么问题的答案就是集合$B$的基数(元素数量)

集合分类

如果我们可以把集合$B$++不重不漏++的分成多个子集合$b_i$,那么答案就是$\sum |b_i|$

显然按对数的结尾的数字,可以把集合$B$++不重不漏++的分成多个子集$b_i$.$b_i$表示结尾为$i$的元素形成的集合.例如$b_3 = \{(1,3)\}$.

证明:

• 不重: 显然以$i$为结尾的元素不可能和以$j$为结尾的元素在同一个集合
• 不漏: 任意一个元素一定会以$i \in [1,n]$为结尾

总结

对数类问题的通常解法就是按结尾位置,把集合分类.关键在于如何快速的求取一个子集的数量.

对于对数类问题,对数问题的公式: \sum s(i)

这里用到了集合与分类加法原理

练习题目