异或笔记
一、 异或的基本性质（基石）记住这四条，其他大多可以推导： 归零律：a ⊕ a = 0 恒等律：a ⊕ 0 = a 自反性（交换律与结合律的推论）：a ⊕ b ⊕ a = b 交换律与结合律：运算顺序和分组不影响结果。这使得前缀异或成为可能。 二、 前缀异或：子数组问题的利器这是处理子数组异或和查询最核心的技巧，类似于前缀和。 定义：设 pre[i] = a[1] ⊕ a[2] ⊕ ... ⊕ a[i]，并约定 pre[0] = 0。 核心公式：a[l] ⊕ a[l+1] ⊕ ... ⊕ a[r] = pre[r] ⊕ pre[l-1] 原理：pre[r] ⊕ pre[l-1] = (前缀到r) ⊕ (前缀到l-1)，根据结合律和归零律，相同的部分（前l-1项）抵消，剩下就是区间 [l, r] 的异或和。 应用场景： 快速求任意子数组异或和。 将“子数组异或和为0”的条件转化为 pre[r] == pre[l-1]。这是解题的关键一步！ 问题转化为对前缀异或数组 pre 的分析，常结合哈希表（unordered_map）来统计次数、寻找配对。 三、 位运算的独特性...
ACM数字类题目
数字类题目 定义：通常有乘除法，或者时分解质因数之类的 重要观察 $2^{30} >= 10^9$所以一般不需要几个数就能乘到上界，除法的话同理，分解质因数实际上也算乘法。因此这类题目往往可以比较暴力的解决。因为只要枚举这几个位置即可。 重要例题： 1.题目传送门Strange Machine 重要观察：$log_2(10^9)=30$,所以除去全是1的情况，每次除2最多30次循环就结束了，因此可以暴力解决。除了有1的情况，因为n最大为20，所以最多$20*30$每个数据。 2.题目传送门Even Modulo Pair 重要观察，要塞大量数据来导致超时的话是不可能的，因为在30个数内必然能找到。理由：首先如果只有偶数，那么一定有解。（因为严格递增） 当只有奇数时： 因为当$y<2x$时，必然有$y \mod x \ = \ y-x \ = \text{偶数}$,因此要构造较大的数据的话，只能让$y \geq x 2$ 要让$y \mod x \ != \text{偶数}$，那么最小只能构造$y=x*2$那么和上一题就一样了。 3.题目传送门Add ...
计算机18讲题解
小技巧 在网页前面加上read有奇效例如： 1raed:https://www.reach-top.cn.com 这个是阅读器模式，开启以后就能获取里面原先不让复制的内容了 A题 题目描述每个整数都应输出一个各位数字和，并独占一行。 解题思路拿之前上课的程序自然是能解决的，直接一个循环算到底每一位的值是n%10，要取得下一位就n/=10再算就彳亍了但是注意到这节课的标题是函数，那么我们就编写一个递归程序来计算每一位的和边界条件：n<=10递推式子：n %10+solve(n/10) 参考代码 12345678910ll solve(ll n){ if(n<10) return n; return n%10+solve(n/10);}signed main(){ ll T; while(cin>>T) cout<<solve(T)<<endl; return 0;}//此处#define ll long long B题 题目描述给定若干个正整数，请你从这些整数中找到最小值和第二小的值...
模运算性质总结
说明感谢YuukiX和qinye_leaf大佬的指正,现已对部分内容进行了修改和补充 本文最后修改时间: 2026/1/23/15:08 模运算（Mod）性质总结定义对于任意实数 $( x, y )$，有： x \mod y = x - y \left\lfloor \frac{x}{y} \right\rfloor, \quad y \neq 0模运算（在一些场合使用符号 % 表示）是一个二元运算。$( x \mod y )$ 的值范围如下： 当 $( y > 0 )$ 时：$( 0 \leq x \mod y < y )$ 当 $( y < 0 )$ 时：$( 0 \geq x \mod y > y )$ 当 $( y = 0 )$ 时：为避免除以零，定义 $( x \mod 0 = x )$ 基本运算规则模运算与基本四则运算类似（除法除外）： 加法规则：$((a + b) \mod p = (a \mod p + b \mod p) \mod p)$ 减法规则：$((a - b) \mod p = (a \mod p - b \mod p + ...
算法挑战赛题解
算法挑战赛第二期题解题目 二进制小数的乘积~HC哥哥说这个很困！难！ Description HC哥哥今天又突发奇想，它依然定义一个数字为二进制小数，如果它是一个正整数，并且其十进制表示中的所有数字都是0或1。例如，110 是一个二进制小数，而 102 和 787 不是。 现在HC哥哥给定你一个数 n，你被要求判断是否可能将 n 表示为一些（不一定是不同的）二进制小数的乘积。 Input 第一行包含一个整数 t（1≤t≤5⋅10^4）— 测试用例的数量。 每个测试用例的唯一一行包含一个整数 n（1≤n≤10^5）。 Output 对于每个测试用例，如果 n 可以表示为一些二进制小数的乘积，则输出 “YES”（不带引号），否则输出 “NO”（不带引号）。 题目解释 （翻译成人话） 计算把01串强制转换为整数，再相乘得到的数就是合法的数字，其余都是不合法的。那么直接打表就行了，总共1e5个数，打表还是很容易实现的 接下来我们来学习一下该怎么打表 打表 定义 : 计算出所有情况，然后直接判断。 比如问你100以内的数是否是质数，你肯定能直接回答，因为你已...
算法挑战赛题解（11.2）
算法挑战赛题解（11.2）简单版本：题目大意：给定n个区间，判断这些区间能划分出几种不同的区域 性质不同的数字 题目分析：实际上是在讨论每个点被哪几个区包含，在样例中，数据是这样的，我们来分析一下这两个样例 123456789101112131415161718192021Sample Input 1 11 6Sample Output 12Sample Input 240 124 136 1312 13Sample Output 26 样例分析：12345678样例1: 0 1 1 1 1 1 1 0 0 … … 所以是两种区间样例2: 1 2 3 4 5 6 7 8 9 10 11 12 13 … … 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 ...
压行技巧
如何给你的代码压行？如果不会压行，你的代码看起来会是这样的： 12345678910int ml(vector<int> s, int n){ int m = s[0]; for (int i = 0; i <= n; i++) { if (s[i] > m) m = s[i]; } return m;} 整整用了9行！实际上其实根本不需用那么多行：1234567int ml(vector<int> s,int n){ int m=s[0]; for(int i=0;i<=n;i++){ if(s[i]>m)m=s[i]; } return m;} 当然也可以更短：12345int ml(vector<int> s,int n){ int m=s[0]; for(int i=0;i<=n;i++) if(s[i]...
过关考模拟考题解
过关考模拟考题解A签到题 分析: 要是这也不会那学习委员真没招了 参考代码: 12345#include<bits/stdc++.h>using namespace std;int main(){ cout<<"Help others voluntarily but never let them know they owe you a favor."<<endl;} B选择结构 分析: 按照要求逐个判断，然后取最小值就行了 参考代码: 123456789#include<bits/stdc++.h>using namespace std;int main(){ double x,y,n,p,ans=200; cin>>x>>y>>n>>p; if(p>=x) ans=min(ans,p-y); ans=min(ans,p/10*n); printf("%.2lf"...
全排列函数的应用
全排列函数什么是全排列？简单来说就是排列组合的所有情况，并按照字典顺序输出例如：123全排列的结果为 123456123132213231312321 而实际上全排列需要在代码中用复杂的深度搜索来写这实在是太复杂了！！！于是我就发现了全排列函数这个东西^__^现在我们就来学习一下这个高级函数————next_permutation 全排列函数123456789101112#include <iostream> #include <algorithm> using namespace std; int main() { int num[3]={1,2,3}; do { cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl; }while(next_permutation(num,num+3)); ...
广工月赛
ZestfulYK的战绩 比赛难度中等，以基础题为主，拼尽全力战胜少量难题 部分代码F 分析很不错的博弈题目，使我的大脑旋转，最后打表做出来了 题目链接 代码:1234567891011121314151617181920212223#include<bits/stdc++.h>using namespace std;#define ll long longint main(){ ll n,m; cin>>n>>m; if(n==0&&m==0) cout<<"Bob"<<endl; else if(n==1&m==0) cout<<"Alice"<<endl; else if(n==2&m==0) cout<<"Bob"<<endl; else if(n==3&m==0) cout<<"Bob"...
