完整源代码:https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces/Hello%202022
前排提示:本场的题十分之恶心人,不建议做

A. Stable Arrangement of Rooks

题目大意:给你一个大小n * n的板子 让你放k个棋子,任意一个棋子的同行同列无其他棋子,而且它向上下左右移动一格也满足,判断是否存在方案,存在则输出,否则输出-1
思路:很容易联想到n皇后问题,不过这个跟n皇后没什么关系,我们可以轻松构造出这种情况,沿对角线分布隔一个的方式放棋子,不难证明出这种方式是放的最多的,而在这种方式之下,一个n*n的板子可以放(n+1)/2个棋子,我们只需要简单判断+输出即可
代码:

void work()
{
    cin >> n >> k;
    if ((n + 1) / 2 < k)
    {
        cout << -1 << endl;
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j && i % 2 == 1 && ((i+1)/2 <= k))
                cout << "R";
            else
                cout << ".";
        }
        cout << endl;
    }
}

B. Integers Shop

(这是一道非常恶心的分类讨论)
题目大意:给你n个区间让你选择,每个区间都有它的价格,如果你选择过了一个数l,r,那么l-r之间的数可以免费给你,问前1,2,3,..,n个区间中,求能选择到最大数的个数的最小花费
思路:起初看到这道题,可以很自信的写出一个记录并替换左右端点位置和花费的贪心,我们知道它要最大的选择长度,所以就要选最左边最便宜和最右边最便宜的,但此时少考虑了一个大区间覆盖所有的情况
于是你有额外写了一个判断,如果大区间可取则抛弃左右端点区间取大区间,交了上去 wa2
我们来考虑这样一种情况
红蓝是之前的最小左右端点区间,紫色是更便宜的大区间,下面那个深蓝是新区间
当我们为了紫色抛弃红蓝后再判断深蓝区间,我们需要取深蓝和紫,但实际上,深蓝和蓝是最优的,所以我们不能抛弃左右端点区间
我们需要再记录左右端点区间的同时记录大区间,如果大区间是全部且更优,才选择大区间
代码:

void work()
{
    cin >> n;
    ll lCost, rCost;
    lCost = rCost = 1e12;
    ll cntLen = 0;
    ll lenCost = 1e12;
    cntL = 1e12;
    cntR = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> l[i] >> r[i] >> c[i];
        // cout << cntL << " " << cntR << endl;
        // cout << l[i] << " " << r[i] << endl;
        if (cntL > l[i])
        {
            cntL = l[i];
            lCost = c[i];
        }
        if (cntR < r[i])
        {
            cntR = r[i];
            rCost = c[i];
        }
        if (cntL == l[i])
            lCost = min(lCost, c[i]);
        if (cntR == r[i])
            rCost = min(rCost, c[i]);
        cntC = lCost + rCost;
        if (r[i] - l[i] + 1 > cntLen)
            cntLen = r[i] - l[i] + 1,lenCost = c[i];
        if (cntLen == r[i] - l[i] + 1)
            lenCost = min(lenCost,c[i]);
        
        // cout << cntL << " " << cntR << " " << cntLen << endl;
        if (cntLen == cntR - cntL + 1)
            cntC = min(lenCost, cntC);

        cout << cntC << endl;
    }
}

C. Hidden Permutations

题目大意:给你一个数组p,和一个数组q,p的内容不知道,q的初始是qi = i,即1,2,3,4...n,你可以询问qi的数值,但你每次询问后
Q[i] 会被替换成 Q[Pi]
你需要再2*n次询问内给你原有的数组p
思路:
观察样例,不难发现Q[1]的变化:1-4-3-1,由于Q初始已知,我们发现p[1] = 4,p[4] = 3,p[3] = 1不难证明P[Q[X]] = Q[Q[X]],我们用并查集的方式统计是否被选择过,对每一个都这样循环求解,即可在2*n次内找到p.(因为最坏情况就是2次询问找到一个,且不可能全为最坏)
代码:

int find(int x)
{
    if (x == father[x])
        return x;
    father[x] = find(father[x]);
    return father[x];
}

int query(int pos)
{
    cout << "? " << pos << endl;
    int targetVal;
    cin >> targetVal;
    return targetVal;
}

void work()
{
    cin >> n;
    M.clear();
    cnt = 0;
    for (int i = 1; i <= n; i++)
        father[i] = i;
    for (int k = 1; k <= n; k++)
    {
        if (cnt == n)
            break;
        if (M[find(k)] != 0)
            continue;
        int nowNum = query(k);
        while (M[nowNum] == 0)
        {
            int newNum = query(k);
            M[nowNum] = newNum;
            father[find(nowNum)] = find(newNum);
            nowNum = newNum;
            cnt++;
            if (cnt == n)
                break;
        }
    }
    // ll tot = 0;
    // for (int i = 1; i <= n; i++)
    //     tot += M[i];
    cout << "! ";
    for (int i = 1; i <= n; i++)
        cout << M[i] << " ";
    cout << endl;
}