西部数码个人网站,铜陵58同城做网站,华军软件园下载中心,广东网页空间网站题目链接#xff1a;Problem - G - Codeforces
题目大意#xff1a;给你一个n长的序列#xff0c; 其中你可以将a[i] XOR a[j] 的值 严格小于4的数对进行交换。 你可以操作任何几次#xff0c; 让最后的数列最小。如果在 x 和 y 不同的第一个位置#xff0c; xiyi Problem - G - Codeforces
题目大意给你一个n长的序列 其中你可以将a[i] XOR a[j] 的值 严格小于4的数对进行交换。 你可以操作任何几次 让最后的数列最小。如果在 x 和 y 不同的第一个位置 xiyi 那么数组 x 在词法上比数组 y 小。 具体题目见链接。
输入
第一行包含一个整数 t ( 1≤t≤1e4 ) - 测试用例数。
每个测试用例的第一行包含一个整数 n (1≤n≤2⋅1e5 ) - 数组的长度。
每个测试用例的第二行包含 n 个整数 ai ( 0≤ai≤1e9 ) - 数组的元素。
保证所有测试用例中 n 的总和不超过 2⋅1e5
考察知识点 并查集 容器map的使用位运算a^bc c^ba。
1.首先可以交换的条件可以看出 我们可以将 可以交换的数字放在一起有此功能的算法不难想到并查集 然后为了方便使用 并 可以方便取出数据 采用map, 收集。
2.可以合并的条件两数 XOR 4 , 此处 暴力枚举 0123 XOR回取在map里查找是否出现了该数 如果出现将该数的下标与次数合并。 最后在到map里标记次数记录下标。
3. 在并查集使用完过后 又采用 mapint, multisetint q 收集每一个下标上的值 方便在于最后的重新赋值。 利用了multiset的自动排序不去重。 q的键实质上就是每个联通块的根。
#includebits/stdc.h
using namespace std;using i64 long long;
using i128 __int128;const int N 2e59;
int tr[N];
int n;
void innt(){for(int i0; in; i) tr[i] i;
}//并查集
int find(int x) {if(tr[x] ! x) {tr[x] find(tr[x]);}return tr[x];
}
void mger_(int a, int b){a find(a);b find(b);if(ab)return;tr[b] a;
}
mapint,int mp;
mapint, multisetint q;
void solve(){cin n;vectorint a(n);for(int i0; in; i) {cin a[i];}innt();mp.clear();//初始化q.clear();for(int i0; in; i) {for(int k0; k4; k) { //枚举0,1,2,3int u a[i] ^ k;if(mp.count(u)) {mger_(i, mp[u]);}//有就连起来}mp[a[i]] i;//标记} for(int i0; in; i) {q[find(i)].insert(a[i]); //分组到q}for(int i0; in; i) {int u find(i);a[i] *q[u].begin();q[u].erase(q[u].begin());//使用过后删除}for(int i0; in; i) {cout a[i] ;}cout \n;
}int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t 1;cin t;while(t--) {solve();}
}
感谢收看与点赞 欢迎大佬指正。
