A-Shuffle Party

题意

对一个数组，起初是 $a_i=i$

对操作swap(k)：

设 $d$ 是不等于 $k$ 本身的 $k$ 的最大除数，然后交换元素 $a_d$ 和 $a_k$ 。

按顺序对每一个 $i=2,3,..,n$ 进行 $swap(i)$ 之后，找出 $1$ 在数组中的位置。

数据范围

$t(1≤t≤10^4)$

$n(1≤n≤10^9)$

思路

简单模拟之后可以发现， $a_1=1$ 最后会挪到不大于 $n$ 的最大2的次幂处。

参考代码

1
void solve() {
2
    vector<ll>p;
3
    ll x = 1;
4
    while (x <= 1e9) {
5
        p.push_back(x);
6
        x *= 2;
7
    }
8
    int t;cin >> t;
9
    while(t--){
10
        ll n;cin >> n;
11
        ll ans = upper_bound(p.begin(), p.end(), n) - p.begin();
12
        cout << p[ans - 1] << endl;
13
    }
14
}

B-Binary Path

题意

一个 $2\times n$ 网格，网格充满 $0,1$ ，找一条从 $(1,1)$ 走到 $(2,n)$ 的路径，要求找到字典序最小的路径并找到这个最小路径的路径数。

数据范围

$t(1≤t≤10^4)$

$n(2≤n≤2\times 10^5)$

思路

路径的组成是第一行的前部分+第二行的后部分，长度是 $n+1$ 。对从第一行到第二行的转折的位置进行枚举，假设往后一位可以获得字典序更小的则重新计数，若相同则累计路径数，若不同则代表没有更好的路径。

参考代码

1
void solve() {
2
    int n;cin >> n;
3
    vector<string>s(2);
4
    cin >> s[0] >> s[1];
5
    string st = s[0] + s[1];
6
    ll cnt = 1;
7
    ll ix = 2;
8
    for (int i = 2;i + n - 2 < 2 * n - 1;i++) {
9
        ll j = i + n - 2;//[i,j]
10
        if (st[i - 1] == '0' && st[j] == '1') {
11
            cnt = 1;
12
            ix = i;
13
        }
14
        else if (st[i - 1] == st[j]) {
15
            cnt++;
16
        }
17
        else {
18
            break;
19
        }
20
    }
21

22
    string res = st.substr(0, ix) + st.substr(ix + n - 1);
23
    string res1 = s[0][0] + s[1];
24
    if (res1 < res)res = res1;
25

26
    cout << res << '\n';
27
    cout << cnt << '\n';
28
}

C-Bitwise Operation Wizard

题意

交互题。

对一个神秘序列 $p_0,p_1,...,p_{n-1}$ （是 $\{0,1,...,n-1\}$ 的排列组合）。我们通过询问需要获得 $p_i\oplus p_j$ 最大的一个 $(i,j)$ 对。

每次询问任意索引 $(a,b,c,d)$ 评审团计算 $x=(p_a|p_b)$ 和 $y=(p_c|p_d)$ ，并告知是 $x\lt y,x\gt y$ 还是 $x=y$ 。最多使用 $3n$ 个查询。

数据范围

$t(1≤t≤1000)$

$n(2≤n≤10^4)$

思路

先两两比较找到最大的数，再找到与最大的数异或的结果最大的另一个数。

参考代码

1
char r;
2
char ask(int a, int b, int c, int d) {
3
    cout << "? " << a << ' ' << b << ' ' << c << ' ' << d << endl;
4
    cin >> r;
5
    return r;
6
}
7

8
void solve() {
9
    int n;cin >> n;
10
    int pm = 0;
11
    // 找n-1
12
    for (int i = 1;i < n;i++) {
13
        if (ask(pm, pm, i, i) == '<') {
14
            pm = i;
15
        }
16
    }
17
    // 另一个数pn：与pm取或大于pm的最小值
18
    int pn = 0;
19
    for (int i = 1;i < n;i++) {
20
        ask(pm, i, pm, pn);
21
        if (r == '>') {
22
            pn = i;
23
        }
24
        else if (r == '=' && ask(i, i, pn, pn) == '<') {
25
            pn = i;
26
        }
27
    }
28
    cout << "! " << pm << " " << pn << endl;
29
}