网站关键词添加后的后果,前端开发入门薪水,wordpress 搜索排除,阿里免费域名申请Problem - 7359
题目大意#xff1a;给出一个n个数的排列#xff0c;可以将任意区间内的所有数头尾翻转#xff0c;每次操作的费用等于区间长度#xff0c;要求将其变成一个递增排列#xff0c;求消耗费用的异或和的最小值和最大值
1n1e5
思路#xff1a;操作…Problem - 7359
题目大意给出一个n个数的排列可以将任意区间内的所有数头尾翻转每次操作的费用等于区间长度要求将其变成一个递增排列求消耗费用的异或和的最小值和最大值
1n1e5
思路操作的最小费用就是翻转相邻两个数费用为2而这样翻转的最小操作次数就是排列的逆序对数量而这样任意操作的操作数的奇偶性也与逆序对的数量的奇偶性相同所以最小的异或和要么是0要么是2与逆序对的数量的奇偶性有关。
考察如何使异或和最大异或和最大也就是在与n的二进制位数相同时每一位都为1这样就需要分别翻转一次肠胃所有2的幂的区间然后我们发现翻转了一个长为x的区间后可以用x*(x-1)/2次翻转相邻两数的操作将区间还原因为x是2的幂所以x*(x-1)/2一定是偶数也就是i1是所有2的i次方且小于等于n的数都能加到答案上然后因为区间长度可以为1所以也可以1那么最大值也就是在最小值基础上将n的二进制表达的其他位都变成1
#include__msvc_all_public_headers.hpp
//#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 1e5 5;
ll tree[N];
int n;
ll a[N];
ll lowbit(ll x)
{return x -x;
}
void add(ll x)
{//树状数组的建立while (x n){tree[x];x lowbit(x);}
}
ll summ(ll x)
{//树状数组求前缀和ll ans 0;while (x){ans tree[x];x - lowbit(x);}return ans;
}
void solve()
{cin n;for (int i 1; i n; i){//初始化树状数组tree[i] 0;}ll inv 0;for (ll i 1; i n; i){cin a[i];add(a[i]);inv i - summ(a[i]);}int ans1 inv 1 ? 2 : 0;ll ans2 log2l(n);if (1 ans2 ! log2l(n)){ans2;}ans2 (1 ans2) - 1;//将n的二进制表达都填满1ans2 !ans1 n 1 ? -2 : 0;//如果n!1且an1等于0就要把2减掉cout ans1 ans2 endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin t;while (t--){solve();}
}
