题目链接
A. Cubes Sorting
思路：
根据可交换的次数可以看出：直接判断数组是否是递减的即可。
代码：
const int N = 1e5 + 10;
int a[N];
int main(){
int t; cin >> t;
while(t --){
int n; cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
int mark = 0;
for(int i = 1; i < n; i ++) if(a[i] <= a[i + 1]) { mark = 1; break; }
if(mark) puts("YES");
else puts("NO");
}
return 0;
}
B. Rock and Lever
思路：
以二进制来看 (a) 和 (b)。
要 (a) (&) (b ge a ⊕ b)，那么 (a) 和 (b) 的最高位的 (1) 一定是对齐的。
直接预处理出每一个数的最高位 (1) 的位置。那么 (ans = ans + frac{cnt[i] imes (cnt[i]-1)}{2})。
代码：
const int N = 1e5 + 10;
int a[N];
int main(){
int t; cin >> t;
while(t --){
int n; cin >> n;
int cnt1[50];
memset(cnt1, 0, sizeof cnt1);
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++){
for(int j = 31; j >= 0; j --){
if((a[i] >> j) & 1){
cnt1[j] ++;
break;
}
}
}
ll ans = 0;
for(int i = 0; i < 32; i ++) ans += 1ll * cnt1[i] * (cnt1[i] - 1) / 2;
cout << ans << endl;
}
return 0;
}
C1. Pokémon Army (easy version)
思路：
把 ((a_{bi} - b_{bj})) 看作一个选择的点对。那么必然有 (a_{bi} > a_{bj})。由于 (b_i < b_j) 的，那么我们从左往右遍历一遍，记录出每一个有贡献的点对即可。
考虑：(a > b < c > d，a > d)。那么对于答案的贡献一定是：((a - b + c - d) > (a - d))。
所以对于上述做法是可行的。
代码：
const int N = 3e5 + 10;
int a[N];
int main(){
int t; cin >> t;
while(t --){
int n, q; cin >> n >> q;
for(int i = 1; i <= n; i ++) cin >> a[i];
int l = 0, r = 0;
ll ans = 0;
for(int i = 1; i <= n; i ++){
if(i == 1) l = a[i];
else {
if(a[i] > a[i - 1]){
if(l && r) ans += l - r;
l = a[i];
r = 0;
} else r = a[i];
}
}
ans += l;
cout << ans << endl;
}
return 0;
}