跳转至

10.30算法学习打卡

今日打卡牛客每日一题

已经连续打卡第九天
不多说直接上代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
    int n;
    cin>>n;
    ll a[n];
    stack<int>st;
    ll sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;++i){
        while(!st.empty()&&a[st.top()]<=a[i]){
            sum ^=st.top();
            st.pop();
        }
        st.push(i);
        sum ^= i;
        cout<<sum<<endl;
    }
    return 0;
}

异或运算（XOR）是一种基础的二进制运算，它在计算机科学和编程中有广泛的应用。下面我们通过一个表格来快速了解其核心规则，然后逐步解析其运算方法和实用技巧：

输入 a 输入 b 输出 (a ⊕ b)
0 0 0
0 1 1
1 0 1
1 1 0

🔢 运算步骤详解

异或运算遵循“相同为0，不同为1”的原则。我们以计算 5 ⊕ 3 为例，来看看具体的运算过程：

  1. 转换为二进制 将两个数转换为二进制表示。如果位数不同，通常在较短二进制数的前面补零，使两者位数一致。

    • 5 的二进制是 101
    • 3 的二进制是 011

  2. 按位进行异或运算 根据异或规则，从右向左（从最低位到最高位）对每一位进行计算：

    • 最低位（最右边）：1 ⊕ 1 = 0
    • 中间位：0 ⊕ 1 = 1
    • 最高位（最左边）：1 ⊕ 0 = 1 所以，得到的结果二进制为 110。

  3. 将结果转换回十进制 二进制 110 对应的十进制数是 6。 因此，5 ⊕ 3 = 6。

你可以把异或运算理解为一种 不带进位的二进制加法。比如在二进制中，1 + 1 = 10（需要进位），但在异或运算中，我们忽略进位，只保留个位的 0。

📐 运算性质与应用

异或运算有一些非常重要的数学性质，这些性质使得它在编程中非常有用：

  • 归零律：a ⊕ a = 0（任何数与自身异或结果为0）
  • 恒等律：a ⊕ 0 = a（任何数与0异或结果为其本身）
  • 交换律：a ⊕ b = b ⊕ a
  • 结合律：a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
  • 自反性：a ⊕ b ⊕ a = b（这是由以上性质推导出的）

一个经典的应用是利用自反性 在不使用临时变量的情况下交换两个变量的值：

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
a = 5
b = 3
# 交换 a 和 b
<div markdown="1" style="margin-top: -30px; font-size: 0.75em; opacity: 0.7;">
:material-circle-edit-outline: 约 660 个字 :fontawesome-solid-code: 32 行代码 :material-clock-time-two-outline: 预计阅读时间 3 分钟
</div>
a = a ^ b  # Step 1
b = a ^ b  # Step 2: 此时 b 得到了原来 a 的值
a = a ^ b  # Step 3: 此时 a 得到了原来 b 的值
print(a) # 输出 3
print(b) # 输出 5

请注意：这种交换方法虽然巧妙，但如果两个变量指向内存中的同一个地址（例如，对同一个数组的不同索引进行操作），可能会导致错误（结果为0）。在实际编程中，通常更推荐使用临时变量法，因为其可读性更好。

💡 实用提示

  • 在大多数编程语言（如C、C++、Java、Python）中，异或运算符是 ^。
  • 异或运算还在奇偶校验、密码学和一些算法（如寻找只出现一次的数字）中扮演关键角色。

评论