CSP-J2021

发表于 2022-07-13 阅读次数：

游记

咕咕咕

T1

思路

显然当l与r整除n相同时，选择r个可以拿到最多的奖励，否则一定可以拿到n-1个奖励。

AC代码

code

#include <bits/stdc++.h> 
using namespace std;

#define uns unsigned
#define ll long long
#define use_cin_cout ios::sync_with_stdio(false)

const ll inf_ll = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;

int n, l, r;

int main() {
	use_cin_cout;
	// freopen("candy.in", "r", stdin);
	// freopen("candy.out", "w", stdout);

	cin >> n >> l >> r;
	if (l / n == r / n) cout << r % n << endl;
	else cout << n - 1 << endl;

	return 0;
}

T2

思路

复习第一轮的时候特地背过，插入排序是具有稳定性的，也就是如果两个元素值相等，排序后先后顺序不会对换。

我们可以用一个结构体存下每一个元素的值 \(v\) 以及它的初始位置 \(id\) ，最开始排一次序，然后用 \(ans[i]\) 记录排序前第i个元素在排序之后的id，也就是答案。那么对于查询操作，我们只需要 \(\theta (1)\) 输出 \(ans[i]\) 就行了。

然后来看修改操作。由于修改操作不超过5000次，所以必须在 \(O(n)\) 的时间内完成修改。修改操作给出的 \(i\) 对应了我们排序之后的 \(ans[i]\) ，在把这个元素的 \(v\) 修改之后，可以利用插排的思想，如果改小了就往前交换，否则往后交换，维护数组的单调性。最后再用 \(\theta (n)\) 的时间更新 \(ans\) 数组，完成修改。

讲的不是很清楚，看代码吧：

AC代码

code

#include <bits/stdc++.h>
using namespace std;

#define uns unsigned
#define ll long long
#define use_cin_cout ios::sync_with_stdio(false)

const ll inf_ll = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int maxn = 8e3 + 5;

struct node {
    int v, id;
};

int n, q;
node a[maxn];
int ans[maxn];

bool compare(node x, node y) {
    return x.v != y.v ? x.v < y.v : x.id < y.id; // 保证稳定性
}

int main() {
    use_cin_cout;
    // freopen("sort.in", "r", stdin);
    // freopen("sort.out", "w", stdout);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].v;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, compare);
    for (int i = 1; i <= n; i++) {
        ans[a[i].id] = i;
    }

    while (q--) {
        int mode, x;
        cin >> mode >> x;

        if (mode == 1) {
            int v;
            cin >> v;
            bool flag = (v > a[ans[x]].v); 
            a[ans[x]].v = v;

            if (flag) { //改大了
                for (int i = ans[x]; i <= n - 1; i++) {
                    if (!compare(a[i], a[i + 1])) {
                        swap(a[i], a[i + 1]);
                    }
                }
            }
            else { //改小了
                for (int i = ans[x]; i >= 2; i--) {
                    if (!compare(a[i - 1], a[i])) {
                        swap(a[i - 1], a[i]);
                    }
                }
            }
            for (int i = 1; i <= n; i++) {
                ans[a[i].id] = i;
            }
        }

        else {
            cout << ans[x] << endl;
        }
    }

    return 0;
}

T3

思路

看到题就知道是大模拟，显然无论是 Server 还是 Client ，就算 \(\theta (n)\) 暴力也可以过。难点只在 \(check()\) 上面。判断域名是否合法的代码没啥技术含量，但还是挺烦的。

开玩笑！STL大法帮我们节省了大量的代码长度。

string 切片操作（str的l到r）： string(str.begin() + l, str.begin() + r + 1)
string 的比较操作（两个 string 要长度一样）: str <= "255"

这样就很良心了。我们先扫一遍，记下三个 . 和一个 : 的位置，判一下个数以及先后顺序，然后把5个数字切片出来，一个一个判不存在、前导0以及>255，就写完了。

AC代码

code

#include <bits/stdc++.h>
using namespace std;

#define uns unsigned
#define ll long long
#define use_cin_cout ios::sync_with_stdio(false)

const ll inf_ll = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int maxn = 1e3 + 5;

struct computer {
    string address;
    int id;
};

vector<computer> server;

bool check(string s) {
    int cnt1 = 0, cnt2 = 0, id1[4], id2 = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '.') {
            id1[cnt1++] = i;
            if (cnt1 > 3) return true;
        }
        if (s[i] == ':') {
            id2 = i;
            cnt2++;
            if (cnt2 > 1) return true;
        } 
    }
    if (cnt1 < 3) return true;
    if (cnt2 < 1) return true;
    if (id1[2] >= id2) return true;

    string t = "";
    t = string(s.begin(), s.begin() + id1[0]);
    if (t.size() == 0 || t.size() > 3 || (t.size() > 1 && t[0] == '0') || (t.size() == 3 && t > "255")) return true;
    t = string(s.begin() + id1[0] + 1, s.begin() + id1[1]);
    if (t.size() == 0 || t.size() > 3 || (t.size() > 1 && t[0] == '0') || (t.size() == 3 && t > "255")) return true;
    t = string(s.begin() + id1[1] + 1, s.begin() + id1[2]);
    if (t.size() == 0 || t.size() > 3 || (t.size() > 1 && t[0] == '0') || (t.size() == 3 && t > "255")) return true;
    t = string(s.begin() + id1[2] + 1, s.begin() + id2);
    if (t.size() == 0 || t.size() > 3 || (t.size() > 1 && t[0] == '0') || (t.size() == 3 && t > "255")) return true;
    t = string(s.begin() + id2 + 1, s.end());
    if (t.size() == 0 || t.size() > 5 || (t.size() > 1 && t[0] == '0') || (t.size() == 5 && t > "65535")) return true;
    return false;
}

int n;

int main() {
    use_cin_cout;
    // freopen("network.in", "r", stdin);
    // freopen("network.out", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string mode;
        computer x;
        cin >> mode;
        cin >> x.address;
        x.id = i;
        if (check(x.address)) {
            cout << "ERR" << endl;
            continue;
        }

        if (mode == "Server") {
            bool flag = true;
            for (int j = 0; j < server.size(); j++) {
                if (x.address == server[j].address) {
                    flag = false;
                    cout << "FAIL" << endl;
                    break;
                }
            }

            if (flag) {
                server.push_back(x);
                cout << "OK" << endl;
            }
        }

        else {
            bool flag = false;
            for (int j = 0; j < server.size(); j++) {
                if (x.address == server[j].address) {
                    flag = true;
                    cout << server[j].id << endl;
                    break;
                }
            }
            
            if (!flag) {
                cout << "FAIL" << endl;
            }
        }
    }

    return 0;
}

T4

思路

看到题面感觉只能用模拟来做，所以考场上就打了一个 \(O(n^2)\) 的STL链表模拟。为什么想不到正解呢？考试的时候一直想不到合并操作怎么做，本来想的是用一个结构体存下来开始序号和结束序号，但是死活想不到怎么把已经被拿掉的水果筛掉，后来才知道拿一个 \(bool\) 数组筛掉就好了。。。

我~~真tm~~是个蒟蒻。

时间复杂度 \(O(n \log n)\) ，因为每一段水果最多被合并 \(\log n\) 次。

~~感觉拿链表有 \(O(n)\) 的做法啊，但是我的指针老是写挂~~

AC代码

code

#include <bits/stdc++.h>
using namespace std;

#define uns unsigned
#define ll long long
#define use_cin_cout ios::sync_with_stdio(false)
#define endl '\n'

const ll inf_ll = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int maxn = 2e5 + 5;

struct fruits {
    int l, r, f;
};

int n, cnt;
queue<fruits> q, q2;
int f[maxn];
bool book[maxn];

int main() {
    // use_cin_cout;

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &f[i]);
    }
    f[n + 1] = !f[n];
    for (int i = 2, si = 1; i <= n + 1; i++) {
        if (f[i] != f[i - 1]) {
            q.push((fruits){si, i - 1, f[i - 1]});
            si = i;
        }
    }
    while (cnt < n) {
        while (!q.empty()) {
            fruits top = q.front();
            q.pop();
            while (book[top.l] && top.l <= top.r) top.l++;
            if (top.l > top.r) continue;
            printf("%d ", top.l);
            cnt++;
            book[top.l] = true;
            if (top.l == top.r) continue;
            top.l++;
            q2.push(top);
        }
        printf("\n");
        while (!q2.empty()) {
            fruits add = q2.front();
            q2.pop();
            while (!q2.empty()) {
                if (add.f == q2.front().f) {
                    add.r = q2.front().r;
                    q2.pop();
                }
                else break;
            }
            q.push(add);
        }
    }
    return 0;
}