Codeforces Hello 2022 题解(A-C)

有段时间不打手生+读错题导致掉大分。

A.Stable Arrangement of Rooks

题意

给一个n*n的棋盘和k个车,我们知道象棋中车是能横着或竖着走的,求是否有一种摆法,使得任意一个车执行任意一次移动后是否会与其他车相邻,如果不能,输出摆法。

题解

按照类似这种摆法就行,在对角线上隔一个放一个,放不下就-1:
R….
…..
..R..
…..
….R

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
using namespace std;
int iceil(int a, int b) {
    if (a % b == 0) return a / b;
    return a / b + 1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        string s="";
        for (int i = 0; i < n; i++) {
            s += '.';
        }
        //cout << s << endl;
        if (iceil(n , 2) < k) {
            cout << -1 << endl;
        }
        else {
            int j = 0;
            for (int i = 0; i < n; i++) {
                string kk = s;
                if (i % 2 == 0&&k>0) {
                    kk[j] = 'R';
                    k--;
                    j += 2;
                }
                cout << kk << endl;
            }

        }
    }
    return 0;
}

B. Integers Shop

题意

商店里面出售n个正整数区间,我们可以获赠任意个数x当满足以下条件时:
x没有被购买
x>购买的最小的数
x<购买的最大的数
求当只能购买前1-n个区间时,使得获得数最多的最小花费。

题解

此处参考了tourist的做法。
维护五个值:最小的数,最大的数,最小左区间花费,最小右区间花费,最小单个区间花费。
然后求最小值,详见代码。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        n--;
        ll l, r, c;
        cin >> l >> r >> c;
        cout << c << endl;//第一次,特殊处理
        ll tl = l, tr=r, tcl=c,tcr=c,tclr=c;//分别为最小的数,最大的数,最小左区间花费,最小右区间花费,最小单个区间花费
        while (n--) {
            cin >> l >> r >> c;
            if (l < tl) {
                tl = l;//如果左区间可以更新,因为比之前的数多,所以将之前的值置为一个很大的数
                tcl = linf;
                tclr = linf;
            }
            if (r > tr) {
                tr = r;//同理,右区间可以更新,置为最大
                tcr = linf;
                tclr = linf;
            }
            if (l == tl) tcl = min(tcl,c);//如果和之前的左区间相等,则取最小,如果比之前的左区间大,那么之前已经将花费置为最大,这里相当于更新
            if (r == tr) tcr = min(tcr, c);//右区间同理
            if (l == tl && r == tr) tclr = min(tclr, c);//这里是当只购买一个区间的时候,因为如果发生左右任意的更新,则相当于更新值。否则相当于和之前的区间取min

            cout << min(tcl + tcr, tclr) << endl;//为什么很大的值用0x3f3f3f3f3f3f3f3f而不用0x7fffffffffffffff,因为0x3f3f3f3f3f3f3f3f在执行tcl + tcr的时候最坏情况(相当于乘2)不会溢出,而0x7fffffffffffffff会。
        }
    }
    return 0;
}

C. Hidden Permutations

题意

这是一道交互题。
有一个排列p。
数组q最初是1 2 3 4…..n
每次询问后,都令${q’}i=q{pi},然后把{q’}复制给q$。
在2n次对q的询问中求出p。

题解

对于样例4 1 2 3
我们列举出8次询问所在的q
1 2 3 4
4 2 1 3
3 2 4 1
1 2 3 4
4 2 1 3
3 2 4 1
1 2 3 4
4 2 1 3
我们竖着取观察,发现满足条件{p}_ {q[i-1][j]}=q[i][j]
例如,我们只观察第一列,能得出p_1=4p_4=3p_3=1
我们只需要标记所有已经取过的下标,然后遍历1-n,找好每一次循环(当询问到的值=首次询问的值,就可以判定循环终止),即可得出所有数。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
using namespace std;
void ask(int i) {
    cout << "? " << i << endl;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T;
    cin >> T;
    while (T--) {
        int n;
        int t,t1;
        cin >> n;
        int re[10005];
        memset(re, 0, sizeof(re));
        set<int> se;
        for (int i = 1; i <= n; i++) {
            se.insert(i);
        }
        int j = 1;
        int k = 0;
        int startt1;
        bool f = 0;
        for (int i = 1; i <=n; i++) {
            ask(i);
            int t;
            cin >> t;
            if (se.count(t) == 1) {
                vector<int> num;
                num.push_back(t);
                do {
                    ask(i);
                    cin >> t;
                    num.push_back(t);
                } while (t!=num[0]);

                for (int i = 0; i < num.size()-1; i++) {
                    re[num[i]] = num[i + 1];
                    se.erase(num[i]);
                }
            }
        }

        cout << "! ";
        for (int i = 1; i <= n; i++) {
            cout << re[i] << " ";
        }
        cout << endl;
    }

    return 0;
}
知识共享许可协议
Text is available under CC BY-NC-SA 4.0 unless otherwise stated.

除非特殊声明,本站所有内容均以 CC BY-NC-SA 4.0协议授权。
上一篇
下一篇