Codeforces Round 930 (Div. 2)

Codeforces Round 930 (Div. 2)

Codeforces Round 930 (Div. 2)

A. Shuffle Party

题意：

给出长度为n的整数数组a，$a_i$= i，对于k>=2的下标进行运算，设d为k除本身外最大的除数，

操作为交换($a_k$, $a_d$)，从小到大交换操作后数组元素1的位置。

思路：

从前往后元素1下标的移动：1->2->4->…->x

最终x为小于n的最大二次幂。

AC code：

void solve() {cin >> n;for (int i = 32; i >= 0; i --) {if (pow(2, i) <= n) {cout << (int)pow(2, i) << endl;return;}}
}

B. Binary Path

题意：

略，这构造。。。

思路：

• 首先是找到最小字典序的路径字符串，保证长度最短则有且只能换行一次，只有第一次遇到对角线右上大于左下的时候进行换行，可以同时保证路径长度最短和字典序最小。
• 然后对于相同的最佳路径，从换行的列开始向前找，遇到对角线相等则相同路线+1，否则结束寻找。

​ 可以通过画二叉树路径来模拟可能的结果。

• 注意不需要提前进行换行的情况。

AC code：

void solve() {cin >> n;for (int i = 0; i < 2; i ++) {string s; cin >> s;for (int j = 0; j < n; j ++) {a[i][j] = s[j];}}int ans = 1;string s = "";int x = 0, y = 0, pos = n - 1;for (int i = 1; i < n; i ++) {s += a[0][i - 1];if (a[0][i] > a[1][i - 1]) {pos = i - 1;break;}}if (pos == n - 1) {s += a[0][n - 1];s += a[1][n - 1];for (int i = pos; i >= 0; i --) {if ((a[0][i] == a[1][i - 1])) ans += 1;else break;}}else {for (int i = pos; i < n; i ++) s += a[1][i];for (int i = pos; i >= 0; i --) {if ((a[0][i] == a[1][i - 1])) ans += 1;else break;}}cout << s << endl;cout << ans << endl;
}

C. Bitwise Operation Wizard

题意：

难得补交互。。。

现在有一组长度为n的p隐藏序列，为0到n-1的排列组合，我们的目的是找到两个索引使$p_i$^$p_j$最大化。

我们可以进行的询问为：选择任意a, b, c, d四个下标元素进行查询；

每次查询可以得到一个字符：表示(pa | pb) 与 (pc | pd) 的大小关系。

最多可以进行3*n次询问，在有限次数内找出最大异或对的两个下标。

思路：

• 首先进行(n - 1)次查询，每次选择的四个下标，a=b, c=d，则可以判断两个元素的大小关系，遍历完所有元素则可以找到最大元素的下标mx；
• 然后考虑如何通过询问，得到异或最大元素：
  • 对每个p元素进行询问，通过查询与mx进行或运算，找出可以通过与mx进行或运算所能得最大元素的下标；
  • 注意，查询可能出现重复的或运算结果，此时再进行比较大小的查询选择较小的元素。

AC code：

void solve() {cin >> n;int mx = 0;for (int i = 1; i < n; i ++) {cout << '?' << " " << mx << " " << mx << " " << i << " " << i << endl;cout.flush();char pos; cin >> pos;if (pos == '<') mx = i;}if (n == 2) {cout << "! 0 1" << endl;cout.flush();return;}int mn = 0;for (int i = 1; i < n; i ++) {cout << '?' << " " << mx << " " << mn << " " << mx << " " << i << endl;cout.flush();char pos; cin >> pos;if (pos == '<') mn = i;if (pos == '=') {cout << '?' << " " << mn << " " << mn << " " << i << " " << i << endl;cout.flush();char pos1; cin >> pos1;if (pos1 == '>') mn = i;}}cout << '!' << " " << mx << " " << mn << endl;cout.flush();
}