可以做外链视频的网站,百度ai助手入口,磁县网站制作公司,高温热泵题目描述
给定一个长度为 n n n 的数组 a a a 和一个整数 m m m#xff0c;问数组中有多少个三元组 ( i , j , k ) (i,j,k) (i,j,k)#xff0c;满足#xff1a; i j k i j k ijk ( a i a j a k ) ( a i ⊕ a j ⊕ a k ) ≥ m (a_i a_j…题目描述
给定一个长度为 n n n 的数组 a a a 和一个整数 m m m问数组中有多少个三元组 ( i , j , k ) (i,j,k) (i,j,k)满足 i j k i j k ijk ( a i a j a k ) × ( a i ⊕ a j ⊕ a k ) ≥ m (a_i a_j a_k) \times (a_i \oplus a_j \oplus a_k) \ge m (aiajak)×(ai⊕aj⊕ak)≥m
输入格式
第一行两个整数 n , m n, m n,m。 ( 1 ≤ n ≤ 500 , 1 ≤ m ≤ 1 0 9 ) (1 \le n \le 500, 1 \le m \le 10^9) (1≤n≤500,1≤m≤109)
接下来一行 n n n 个整数第 i i i 个数字表示 a i a_i ai。 ( 1 ≤ a i ≤ 1 0 9 ) (1 \le a_i \le 10^9) (1≤ai≤109)
输出格式
一个整数表示满足条件的三元组个数。
样例输入1
4 10
1 3 2 5样例输出1
3解释
共有3个三元组满足条件 ( 1 , 2 , 4 ) (1,2,4) (1,2,4), ( 1 , 3 , 4 ) (1,3,4) (1,3,4), ( 2 , 3 , 4 ) (2,3,4) (2,3,4)
提示
记得开 longlong。 思路
计算满足特定条件的三元组的数量。这个特定条件是数组中任意三个元素的和乘以这三个元素的异或结果大于或等于给定的数值 m m m。 N N N 是数组的最大长度 n n n 和 m m m 是用户输入的值分别代表数组的实际长度和要比较的数值。 a a a 是存储用户输入数组的变量 a n s ans ans 用来记录满足条件的三元组的数量。
在 main 函数中程序首先通过 cin 读取用户输入的 n n n 和 m m m 的值然后读取 n n n 个数值存入数组 a a a 中。
数据范围不大直接暴力枚举。通过三层嵌套的 for 循环遍历数组中的所有可能的三元组。对于每一个三元组程序计算它们的和乘以它们的异或结果然后判断这个值是否大于或等于 m m m。如果满足条件就将 a n s ans ans 的值加一。
最后程序通过 cout 输出 a n s ans ans 的值这就是满足条件的三元组的数量。
这个算法的时间复杂度是 O ( n 3 ) O(n^3) O(n3)因为它需要遍历数组中所有可能的三元组。
注意记得开 long long不然会报答案错误 AC:17% AC代码
#include iostream
#define ll long long
#define AUTHOR HEX9CF
using namespace std;const int N 1e7 7;ll n, m;
ll a[N];
ll ans;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ans 0;cin n m;for (int i 1; i n; i) {cin a[i];}for (int i 1; i n; i) {for (int j i 1; j n; j) {for (int k j 1; k n; k) {if ((a[i] a[j] a[k]) * (a[i] ^ a[j] ^ a[k]) m) {ans;}}}}cout ans endl;return 0;
}
