树的重心

会议

xxxxxxxxxx
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int p=50001;
int n,hason[p],f[p],yy=1;
int u,v;
int tot,la[p*2],to[p*2],h[p];
void hsb(int x,int y)
{
    to[++tot]=y,
    la[tot]=h[x],
    h[x]=tot;
}
int hsc(int x,int y)
{
    for(int i=h[x];i;i=la[i])
    if(to[i]!=y)
    hason[x]+=1+hsc(to[i],x);
    return hason[x];
}
void hsa(int x,int y)
{
    f[x]=f[y]-(hason[x]+1)+(n-hason[x]-1);
    for(int i=h[x];i;i=la[i])
    if(to[i]!=y)hsa(to[i],x);
}
void hsd(int x,int y,int z)
{
    f[1]+=z;
    for(int i=h[x];i;i=la[i])
    if(to[i]!=y)
    hsd(to[i],x,z+1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        hsb(u,v),hsb(v,u);
    }
    hsc(1,0);
    for(int i=h[1];i;i=la[i])
    hsd(to[i],1,1);
    for(int i=h[1];i;i=la[i])
    hsa(to[i],1);
    for(int i=2;i<=n;i++)
    if(f[i]<f[yy])yy=i;
    printf("%d %d\n",yy,f[yy]);
    return 0;
}

set语法

xxxxxxxxxx
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
set<ll>a;
int main(){
    for(ll i=1;i<=10;i++){
        a.insert(i);
    }
    ll n=3;
    cout<< *a.lower_bound(n);
    cout<< *a.upper_bound(n); 
    return 0;
}

位运算符

在C/C++中，位运算符直接对整数的二进制位进行操作，常用于底层编程、性能优化或特定算法（如位掩码、加密等）。以下是主要的位运算符及其作用：

1. 按位与 &

• 作用：对两个操作数的每一位执行逻辑与操作（仅当两位均为1时结果为1）。

• 示例：

  xxxxxxxxxx
  int a = 5;    // 0101
  int b = 3;    // 0011
  int c = a & b; // 0001 (十进制1)
  

• 用途：

  • 清除特定位（如 x & 0xFE 清除最低位）。

  • 检查奇偶性（x & 1 为0则是偶数）。

2. 按位或 |

• 作用：对每一位执行逻辑或操作（任一位为1时结果为1）。

• 示例：

  xxxxxxxxxx
  int a = 5;    // 0101
  int b = 3;    // 0011
  int c = a | b; // 0111 (十进制7)
  

• 用途：

  • 设置特定位（如 x | 0x01 强制最低位置1）。

3. 按位异或 ^

• 作用：对每一位执行异或操作（两位不同时结果为1）。

• 示例：

  xxxxxxxxxx
  int a = 5;    // 0101
  int b = 3;    // 0011
  int c = a ^ b; // 0110 (十进制6)
  

• 用途：

  • 交换变量值（a ^= b; b ^= a; a ^= b;）。

  • 简单加密（通过异或密钥）。

4. 按位取反 ~

• 作用：对每一位取反（0变1，1变0）。

• 示例：

  xxxxxxxxxx
  int a = 5;    // 0101
  int b = ~a;   // 1010（假设8位，实际为补码表示的负数）
  

• 注意：结果与整数表示（补码）相关，通常得到负数。

5. 左移 <<

• 作用：将二进制位向左移动指定位数，右侧补0。

• 示例：

  xxxxxxxxxx
  int a = 5;    // 0101
  int b = a << 1; // 1010 (十进制10)
  

• 用途：

  • 等价于乘以2的幂（x << n 等于 x * 2^n）。

  • 快速构造位掩码。

6. 右移 >>

• 作用：将二进制位向右移动指定位数，左侧补符号位（算术右移）或0（逻辑右移，取决于编译器）。

• 示例：

  xxxxxxxxxx
  int a = -8;   // 11111000（假设8位）
  int b = a >> 1; // 11111100（算术右移，结果为-4）
  

• 用途：

  • 等价于除以2的幂（向下取整）。

  • 提取特定位（如 x >> 4 & 0xFF 获取高字节）。

关键注意事项：

1. 操作数类型：位运算符通常用于整数类型（int, char, long 等），浮点数需强制转换。

2. 优先级：位运算符优先级低于算术运算符（如 +、*），建议用括号明确顺序。

3. 符号位：右移时负数的行为依赖编译器（算术右移保留符号位）。

4. 溢出：左移可能导致未定义行为（如移出数据类型范围）。

示例代码

xxxxxxxxxx
#include <iostream>
using namespace std;

int main() {
    int flags = 0b1010; // 二进制1010（十进制10）
    flags |= 0b0001;    // 设置最低位 → 1011 (11)
    flags &= ~0b0010;   // 清除第2位 → 1001 (9)
    flags ^= 0b1100;    // 异或 → 0101 (5)
    int high_byte = (flags >> 4) & 0xFF; // 右移获取高字节
    cout << high_byte;  // 输出0（此处flags只有低字节）
    return 0;
}

位运算在嵌入式开发、图形处理、网络协议等场景中尤为重要，需谨慎使用以避免逻辑错误。

1LL与011区别

在C++中，1LL和011有本质区别：

1. 1LL：

   • 表示long long类型的整数1

   • 类型：long long

   • 值：1 (十进制)

   • 常用于确保大整数运算不溢出

2. 011：

   • 表示八进制(octal)整数

   • 类型：int

   • 值：9 (十进制)，因为011₈ = 9₁₀

   • 以0开头的整数字面量在C++中表示八进制

我将修改示例文件展示这一区别：

编辑

vector_array_example.cpp

+7-4

思考过程

代码修改成功，现在可以清晰展示1LL和011的区别。您可以这样测试：

xxxxxxxxxx
bashg++ vector_array_example.cpp -o vector_array_example
echo "0" | ./vector_array_example

预期输出示例：

xxxxxxxxxx
1LL 类型: x (表示long long，具体符号取决于编译器)
1LL 值: 1
011 类型: i (表示int)
011 值: 9
输出结果:

关键区别总结：

1. 类型不同：

   • 1LL是long long类型(8字节)

   • 011是int类型(通常4字节)

2. 进制不同：

   • 1LL是十进制

   • 011是八进制(前导0)

3. 使用场景：

   • 1LL用于需要大整数或明确类型的情况

   • 011用于八进制表示(现代代码中较少使用)

0x3f3f3f3f

0x3f3f3f3f是算法竞赛中常用的一个魔数(magic number)，让我详细解释：

1. 数值意义：

   • 十六进制表示，转换为十进制是1061109567

   • 32位系统中，二进制表示为：00111111001111110011111100111111

2. 典型用途：

   • 作为"无穷大"的替代值（比INT_MAX小但足够大）

   • 常用于初始化距离数组（如Dijkstra算法）

   • 优点：

     • 两个0x3f3f3f3f相加不会溢出

     • 满足memset初始化需求（每个字节都是0x3f）

树状数组

P1908 逆序对 - 洛谷

这段代码实现了一个计算数组中逆序对数量的算法。逆序对是指在数组中，如果前面的元素大于后面的元素，那么这两个元素构成一个逆序对。例如，在数组 [3, 1, 2] 中，(3, 1) 和 (3, 2) 是逆序对，总数为 2。

代码核心思想

1. 离散化：将原始数组中的元素映射到一个连续的区间，减少树状数组的空间占用。

2. 树状数组（Fenwick Tree）：用于高效查询和更新前缀和，从而统计逆序对数量。

3. 从后向前遍历：通过树状数组动态维护已处理元素的分布，利用前缀和快速计算逆序对。

代码分步解析

1. 头文件和全局变量

xxxxxxxxxx
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;  // 未使用
const ll MAXN = 5e5 + 5;

ll a[MAXN], b[MAXN], c[MAXN];  // a:原数组, b:离散化数组, c:树状数组
ll m, n;  // m:离散化后长度, n:原数组长度

• a 存储输入的原始数组。

• b 用于排序和离散化。

• c 是树状数组，用于动态统计前缀和。

• m 和 n 分别表示离散化后的数组长度和原数组长度。

2. 树状数组核心操作

(1) lowbit 函数

xxxxxxxxxx
ll lowbit(ll x) {
    return x & (-x);  // 返回x的最低位1所代表的值
}

• 计算 x 的二进制最低位 1 及其后面的 0 组成的数值（例如，x=6 (110) 时，lowbit(6)=2 (10)）。

(2) add 函数（更新操作）

xxxxxxxxxx
void add(ll x, ll y) {
    for (ll i = x; i <= m; i += lowbit(i)) 
        c[i] += y;  // 在位置x增加y（通常y=1）
}

• 从位置 x 开始，沿着树状数组的结构向上更新所有相关节点的值（每次增加 lowbit(i)）。

(3) sum 函数（查询前缀和）

xxxxxxxxxx
ll sum(ll x) {
    ll res = 0;
    for (ll i = x; i > 0; i -= lowbit(i)) 
        res += c[i];  // 累加从x到1的所有相关节点的值
    return res;
}

• 查询前 x 个元素的和（即 b[1..x] 的计数）。

3. 主处理逻辑 solve

xxxxxxxxxx
void solve() {
    cin >> n;  // 输入数组长度
    
    // 读入数组并复制到b
    for (ll i = 1; i <= n; i++) 
        cin >> a[i], b[i] = a[i];
    
    // 排序并离散化
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - b - 1;  // 去重后长度
    
    ll ans = 0;  // 逆序对计数器
    
    // 从后向前遍历
    for (ll i = n; i > 0; i--) {
        // 找到a[i]在离散化数组b中的位置
        ll pos = lower_bound(b + 1, b + m + 1, a[i]) - b;
        
        // 查询比a[i]小的元素个数（即sum(pos-1)）
        ans += sum(pos - 1);
        
        // 将当前元素加入树状数组
        add(pos, 1);
    }
    
    cout << ans << "\n";  // 输出逆序对总数
}

1. 输入处理：读取数组 a，并复制到 b 用于离散化。

2. 离散化：

   • 对 b 排序。

   • 使用 unique 去重，得到 m 个唯一值。

3. 逆序对统计：

   • 从后向前遍历 a：

     • 用 lower_bound 找到 a[i] 在离散化数组 b 中的位置 pos。

     • 查询 sum(pos-1)：统计已处理元素中比 a[i] 小的数的个数（这些数原本在 a[i] 后面，现在前面，说明是逆序对）。

     • 将 pos 位置的值加 1（表示 a[i] 已处理）。

4. 输出结果：累计的 ans 即为逆序对总数。

4. 主函数

xxxxxxxxxx
int main() {
    ios::sync_with_stdio(0);  // 关闭同步IO
    cin.tie(0), cout.tie(0);  // 解绑cin和cout
    
    ll t = 1;  // 测试用例数量
    while (t--) 
        solve();
    
    return 0;
}

• 优化输入输出速度（ios::sync_with_stdio(0) 等）。

• 处理单组测试用例（t=1）。

关键点总结

1. 离散化：将原始数据映射到连续区间，节省树状数组空间。

   • 例如，a=[3, 1, 2] 离散化为 b=[1, 2, 3]（排序去重后）。

2. 树状数组：高效维护动态前缀和。

   • add(pos, 1)：记录元素出现。

   • sum(pos-1)：查询比当前元素小的已处理元素数量。

3. 逆序对统计：

   • 从后向前遍历时，每遇到一个元素 a[i]，查询比它小的已处理元素数量，这些元素原本在 a[i] 右侧，现在左侧，构成逆序对。

示例演示

以 a=[3, 1, 2] 为例：

1. 离散化后 b=[1, 2, 3]（m=3）。

2. 从后向前处理：

   • i=3（a[3]=2）：

     • pos=2（lower_bound 找到 2 的位置）。

     • sum(1)=0（比 2 小的数尚未处理）。

     • add(2, 1)：树状数组 c[2]=1。

   • i=2（a[2]=1）：

     • pos=1。

     • sum(0)=0。

     • add(1, 1)：c[1]=1。

   • i=1（a[1]=3）：

     • pos=3。

     • sum(2)=c[2]+c[0]=1（比 3 小的数有 1 个：a[2]=1 和 a[3]=2 中的 2）。

     • add(3, 1)：c[3]=1。

3. 累计 ans=0 + 0 + 1 = 1？
   注意：实际代码中 ans 会累加 sum(pos-1) 的每次结果，正确逆序对应为 (3,1) 和 (3,2)，总数为 2。
   问题：代码逻辑实际统计的是“顺序对”而非逆序对？
   修正：代码逻辑是正确的，因为从后向前遍历时，sum(pos-1) 统计的是已处理元素中比当前元素小的，即原本在右侧的较小数，构成逆序对。例如：

   • 处理 3 时，已处理 1 和 2，sum(2)（比 3 小的数）是 2，但代码中是 sum(pos-1) 即 sum(2)（因为 pos=3 对应 3 的位置），实际应为 sum(2)（比 3 小的数有 1 和 2），但代码中 pos 是 3，sum(2) 是 c[2]=1（只有 2 被处理了？）。
     矛盾点：离散化后 b=[1,2,3]，a=[3,1,2] 的 pos 依次是 3, 1, 2。

   • i=3（a[3]=2）：pos=2，sum(1)=0，add(2,1) → c[2]=1。

   • i=2（a[2]=1）：pos=1，sum(0)=0，add(1,1) → c[1]=1。

   • i=1（a[1]=3）：pos=3，sum(2)=c[2]=1（只有 2 被处理了，但 1 也在前面？）。
     问题：sum(2) 只统计了 c[2]，但 c[1] 也应包含在内？
     原因：树状数组的 sum 是前缀和，sum(2)=c[2]+c[0]（但 c[0] 无效），实际树状数组的 sum 实现是累加所有 i 从 x 递减到 1 的 c[i]，因此 sum(2)=c[2]+c[0]（但 c[0] 未初始化，可能为 0）。
     正确逻辑：sum(pos-1) 统计的是已插入的比当前元素小的数，即逆序对。
     示例修正：

   • 初始 c 全 0。

   • i=3（a[3]=2）：pos=2，sum(1)=0，add(2,1) → c[2]=1。

   • i=2（a[2]=1）：pos=1，sum(0)=0，add(1,1) → c[1]=1。

   • i=1（a[1]=3）：pos=3，sum(2)=c[2]+c[1]=1+1=2（比 3 小的数有 1 和 2）。

   • 最终 ans=2（正确）。

   结论：代码逻辑正确，但需注意树状数组的 sum 实现是累加所有相关节点的值。

复杂度分析

1. 离散化：

   • 排序：O(n log n)。

   • 去重：O(n)。

2. 树状数组操作：

   • 每次 add 和 sum 是 O(log m)。

   • 遍历 n 次，总复杂度 O(n log m)（m ≤ n，故为 O(n log n)）。

3. 总复杂度：O(n log n)。

   离散化

   数组离散化详解

   离散化（Discretization） 是将连续或大范围的数值映射到较小的、离散的整数范围内的过程，常用于优化算法效率（如减少空间占用）或适应特定数据结构（如树状数组、线段树）。以下是离散化的核心步骤、代码实现及注意事项：

   ---

   1. 离散化的核心步骤

   1. 收集所有待离散化的值：将原数组中的所有元素（可能包含重复值）存入一个临时数组。

   2. 排序并去重：对临时数组排序，并去除重复元素，得到有序且唯一的值序列。

   3. 建立映射关系：为每个唯一值分配一个从0或1开始的连续整数（即离散化后的值）。

   4. 替换原数组：根据映射关系，将原数组中的每个元素替换为对应的离散化值。

   ---

   2. 代码实现（C++示例）

   xxxxxxxxxx
   #include <vector>
   #include <algorithm>
   #include <unordered_map>
   
   using namespace std;
   
   vector<int> discretize(vector<int>& nums) {
       if (nums.empty()) return {};
       
       // 步骤1：复制并排序去重
       vector<int> temp = nums;
       sort(temp.begin(), temp.end());
       temp.erase(unique(temp.begin(), temp.end()), temp.end());
       
       // 步骤2：建立映射（值 -> 离散化后的索引）
       unordered_map<int, int> map;
       for (int i = 0; i < temp.size(); ++i) {
           map[temp[i]] = i + 1; // 通常从1开始（根据需求调整）
       }
       
       // 步骤3：替换原数组
       vector<int> res;
       for (int num : nums) {
           res.push_back(map[num]);
       }
       
       return res;
   }
   
   // 示例用法
   int main() {
       vector<int> nums = {100, 200, 100, 50, 300};
       vector<int> discretized = discretize(nums);
       // 输出：假设映射为 {50:1, 100:2, 200:3, 300:4}，则结果为 [2,3,2,1,4]
       for (int num : discretized) cout << num << " ";
       return 0;
   }
   

   ---

   3. 关键注意事项

   • 去重必要性：离散化要求映射后的值唯一，因此必须去重。

   • 映射方向：

     • 值到索引：如上述代码，将原值映射为排名（适用于树状数组等）。

     • 索引到值：有时需要反向映射（如恢复原值），需额外存储排序后的唯一值数组。

   • 稳定性：离散化不改变元素的相对顺序，仅压缩数值范围。

   • 边界处理：

     • 空数组需直接返回。

     • 若原数组包含负数或零，排序和映射仍有效（离散化后的值从1或0开始均可）。

   ---

   4. 应用场景

   • 树状数组/线段树：这些数据结构要求操作的下标为连续整数，离散化可压缩大范围数值。

   • 坐标压缩：在二维平面问题中，将坐标映射到紧凑范围以减少内存使用。

   • 优化比较操作：将浮点数或大整数离散化为整数，便于哈希或排序。

   ---

   5. 扩展：离散化与排序的关系

   • 离散化通常依赖排序来去重和确定排名，但排序本身不改变数值范围，而离散化会。

   • 若原数组已有序且无重复，可直接建立映射（跳过排序和去重步骤）。

   ---

   6. 反向离散化（恢复原值）

   若需从离散化后的值恢复原值，可保存排序后的唯一值数组：

   xxxxxxxxxx
   vector<int> reverseDiscretize(const vector<int>& discretized, const vector<int>& uniqueSorted) {
       vector<int> res;
       for (int d : discretized) {
           res.push_back(uniqueSorted[d - 1]); // 假设离散化从1开始
       }
       return res;
   }
   

   ---

   通过离散化，可以高效处理大范围或稀疏数据，是算法优化中的常用技巧。理解其原理后，可根据具体问题调整实现细节（如映射起始值、是否保留原值等）。

质数筛

xxxxxxxxxx
#include<bits/stdc++.h>
using namespace std;
int main(){
         vector<int> v;
         v.push_back(1);
         int a[1000];
         memset(a,1,sizeof a);
         for(int i=2;i<=100;i++){
if(a[i])v.push_back(i);
for(int j=2*i;j<=100;j+=i){
         a[j]=0;
}
}
for(auto i:v)cout<<i<<" ";
return 0;
}

并查集

寻找父亲节点

xxxxxxxxxx
ll find(ll x) {
    if (x == f[x])       // 如果x是自己的父节点，直接返回x
        return x;
    return f[x] = find(f[x]); // 否则递归查找父节点，并进行路径压缩
}

合并两个节点

xxxxxxxxxx
void merge(ll x, ll y) {
    f[find(x)] = find(y); // 将x的根节点的父节点指向y的根节点
}

初始化

xxxxxxxxxx
 for (int i = 1; i <= n; i++) {
        f[i] = i;        // 初始化每个元素的父节点为自己
        string s;
        cin >> s;        // 输入字符串
        mp[s] = i;       // 将字符串映射到编号i
    }

总代码

x
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll n,m;
map<string , ll> mp;
ll f[100005];
ll find(ll x){
    if(x==f[x]) return x;
    return f[x] = find(f[x]);
}
void merge(ll x, ll y){
    f[find(x)] = find(y);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
    f[i] = i;
string s;
    cin>>s;
    mp[s] = i;
}
for(int i=1;i<=m;i++){
    string s1,s2;
    ll x;
    cin>>x>>s1>>s2;
    if(x==1)merge(mp[s1], mp[s2]);
    else if(find(mp[s1])==find(mp[s2]))cout<<"1"<<endl;
    else cout<<"0"<<endl;
}
}