NOI 2023 春季测试游记

• 03.03｜踩点
• 03.04｜测试
  • T1｜涂色游戏（paint）
  • T2｜幂次（power）
  • T3｜圣诞树（tree）
  • T4｜密码锁（lock）
• 03.05｜自测

03.03｜踩点

上午停课练题。

中午左臂变成矿泉水跟叶子姐 say hello.

大巴车上张老师发了巧克力但是没买够两人一块第二天考场上都化成酱了。

面基了 jltxsfl。

大巴车上偷拍沐纭。

回来刚好体活课打球。

zgr一帮人商量战术不带我不管他。

03.04｜测试

06:18起床，但是没起来。

将近八点到新大。

T1｜涂色游戏（paint）

签到题。

直接模拟肯定不行。

记录行和列的修改内容及时间进行比较后输出即可。

【提示】

数据千万条，清空第一条。多测不清空，爆零两行泪。

#include <iostream>
#include <cstring>

void promote() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    return;
}

const int maxN = 1e5;
const int maxM = 1e5;
const int maxQ = 1e5;

int T;
int n, m, q;
int op, x, c;
int rc[maxN + 10];
int rt[maxN + 10];
int cc[maxN + 10];
int ct[maxN + 10];

void init() {
    std::memset(rt, 0, sizeof(rt));
    std::memset(ct, 0, sizeof(ct));
    return;
}

void mian() {
    std::cin >> n >> m >> q; init();
    for (int i = 1; i <= q; i++) {
        std::cin >> op >> x >> c;
        if (op == 0) {
            rc[x] = c;
            rt[x] = i;
        } else if (op == 1) {
            cc[x] = c;
            ct[x] = i;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (rt[i] || ct[j]) {
                if (rt[i] > ct[j]) {
                    std::cout << rc[i] << ' ';
                } else {
                    std::cout << cc[j] << ' ';
                }
            } else {
                std::cout << 0 << ' ';
            }
        }
        std::cout << '\n';
    }
    return;
}

int main() {
    freopen("paint.in", "r", stdin);
    freopen("paint.out", "w", stdout);
    promote();
    std::cin >> T;
    while (T--) mian();
    return 0;
}

T2｜幂次（power）

昨天早上 10:35 用 Lucyna VP Educational Codeforces Round 144 (Rated for Div. 2)。

其中C题给了我灵感就是整除然后取 $\log$。

然后再加个换底公式可以过 $10^6$ 的 30pts。

考完听说是容斥。

可我数学是真的一点不会阿。

有 Emiya 家的饭那意思了是吧？。

LHQing 发犇犇说是 CF955C。

好像没弱化也没强化。

#include <iostream>
#include <map>
#include <cmath>

void promote() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    return;
}

typedef unsigned long long lxl;
typedef double dbl;

lxl n, k;

std::map<lxl, bool> vis;
std::map<lxl, bool> ban;
void init() {
    for (lxl i = 2; i <= n; i++) {
        //if (vis[i] == false) {
        //    for (lxl j = 2; i * j <= n; j++) vis[i * j] = true;
        if (ban[i] == false) for (lxl j = i * i; j <= n; j *= i) ban[j] = true;//, printf("ban %d\n", j);
        //}
    }
    return;
}

bool check(lxl v, lxl &p) {
    if (ban[v]) return false;
    lxl x = v;
    lxl y = k;
    while (y) {
        if (y & 1) p = p * x;
        if (p > n) return false;
        x = x * x;
        y = y / 2;
    }
    return true;
}

lxl ans = 1;

int main() {
    freopen("power.in", "r", stdin);
    freopen("power.out", "w", stdout);
    promote();
    std::cin >> n >> k; init();
    for (lxl i = 2; i <= n; i++) {
        lxl p = 1;
        if (check(i, p)) {
            ans += std::log(n / p) / std::log(i) + 1;
            //printf("%d, pow = %d: %d\n", i, p, ans);
        }
    }
    std::cout << ans;
    return 0;
}

T3｜圣诞树（tree）

一眼凸多边形以为凸包。

考前面基 lyx_lyx 讨论暴力时提了一嘴 A_star。

然后用它冲了60。

快说谢谢lyx_lyx！

但是性质 $\text{A}$ 写假了。

zyh 说就是个贪心但我感觉不对。

吐槽一句死机重启了不下十回但是监考阿姨真的还不错。

#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <cmath>

void promote() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    return;
}

typedef long double dbl;
typedef std::set<int> sit;
typedef std::vector<int> vic;

const int maxN = 1e3;
const dbl inf = 3e18;

int n; int k;
dbl x[maxN + 10], y[maxN + 10];
dbl d[maxN + 10][maxN + 10];
dbl D = inf;
int N = 5;

dbl dis(dbl x1, dbl y1, dbl x2, dbl y2) {
    dbl dx = x1 - x2;
    dbl dy = y1 - y2;
    return std::sqrt(dx * dx + dy * dy);
}

struct Pro {
    int u;
    dbl w;

    bool operator<(const Pro &other) const {
        return w < other.w;
    }
};

std::vector<Pro> pro[maxN + 10];

void init() {
    N = std::min(N, n - 1);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            dbl t = dis(x[i], y[i], x[j], y[j]);
            d[i][j] = t;
            d[j][i] = t;
            D = std::min(D, t);
        }
        for (int j = 1; j <= n; j++) {
            pro[i].push_back((Pro) {j, d[i][j]});
        }
        std::sort(pro[i].begin(), pro[i].end());
    }
    for (int i = 1; i <= n; i++) {
        if (k == 0 || y[i] > y[k] || y[i] == y[k] && i < k) {
            k = i;
        }
    }
    return;
}

struct Node {
    dbl g;
    dbl h;
    sit s;
    vic v;

    bool operator<(const Node &other) const {
        return g + h > other.g + other.h;
    }
} ans;

void Astar() {
    ans.g = inf;
    Node node;
    node.g = 0;
    node.h = D * (n - 1);
    node.s.insert(k);
    node.v.push_back(k);
    std::priority_queue<Node> q;
    q.push(node);
    while (q.size()) {
        Node node = q.top(); q.pop();
        if (node.g + node.h > ans.g) break;
        //printf("%d, %d, %d\n", node.g, node.h, node.v.size());
        if (node.v.size() == n) {
            //std::cout << node.g << '\n';
            if (node.g < ans.g || ans.v.size() == 0) {
                ans = node;
            }
            continue;
        }
        int u = node.v.back();
        for (int i = 1; i <= N; i++) {
            int v = pro[u][i].u;
            int w = pro[u][i].w;
            if (node.s.count(v)) continue;
            Node n0de = node;
            n0de.g += w;
            n0de.h -= D;
            n0de.s.insert(v);
            n0de.v.push_back(v);
            if (n0de.g + n0de.h <= ans.g) q.push(n0de);
        }
    }
    for (auto i : ans.v) std::cout << i << ' ';
    return;
}

void A() {
    if (k == n) {
        for (int i = n; i >= 1; i--) std::cout << i << ' ';
        return;
    }
    dbl ld = std::fabs(y[k] - y[k - 1]);
    dbl rd = std::fabs(y[k] - y[k + 1]);
    std::cout << k << ' ';
    if (ld < rd) {
        for (int i = k - 1; i >= 1; i--) std::cout << i << ' ';
        for (int i = n; i >= k + 1; i--) std::cout << i << ' ';
    } else {
        for (int i = k + 1; i <= n; i++) std::cout << i << ' ';
        for (int i = 1; i <= k - 1; i++) std::cout << i << ' ';
    }
    return;
}

void B() {
    for (int i = 1; i <= n; i++) std::cout << i << ' ';
    return;
}

void Subtask() {
    if (k == 1) B();
    else A();
    return;
}

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    promote();
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> x[i] >> y[i]; init();
    if (n <= 18) Astar();
    else Subtask();
    //std::cout << ans.g;
    return 0;
}

T4｜密码锁（lock）

Hello, Luogu 2 群里评的下紫。

爆搜应该能艹个 $n \le 20$。

也就4个点。

【后记】

你花了九牛二虎之力算出 $C$ 的值之后，小 $\text{I}$ 却告诉你他已经找开锁师傅用锤子暴力破解了。在你的百般劝说下，小 $\text{I}$ 承诺以后锁车不用大于等于一万个拨圈的密码锁。

u1s1 红湖这边好康的小姐姐是真的多。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

void promote() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    return;
}

const int maxK = 4;
const int maxN = 5e5;
const int maxA = 3e4;

int T, k;
int n;
int a[maxK * 2 + 5][maxN + 10];
int s[maxN + 10];
int mn[maxK + 10];
int mx[maxK + 10];

void init() {
    std::memset(mn, 0x3f, sizeof(mn));
    std::memset(mx, 0xcf, sizeof(mx));
    std::memset(s, 1, sizeof(s));
    return;
}

bool DFS(int id, int lim) {
    if (id > n) return true;
    for (int S = 1; S <= k; S++) {
        bool ok = true;
        for (int j = 1; j <= k; j++) {
            int tn = mn[j];
            int tx = mx[j];
            tn = std::min(tn, a[S + j - 1][id]);
            tx = std::max(tx, a[S + j - 1][id]);
            if (tx - tn > lim) {
                ok = false;
                break;
            }
        }
        if (ok == false) continue;
        int bn[maxK + 10];
        int bx[maxK + 10];
        for (int j = 1; j <= k; j++) {
            bn[j] = mn[j];
            bx[j] = mx[j];
        }
        for (int j = 1; j <= k; j++) {
            mn[j] = std::min(mn[j], a[S + j - 1][id]);
            mx[j] = std::max(mx[j], a[S + j - 1][id]);
        }
        int sb = s[id];
        s[id] = S;
        if (DFS(id + 1, lim)) return true;
        for (int j = 1; j <= k; j++) {
            mn[j] = bn[j];
            mx[j] = bx[j];
        }
        s[id] = sb;
    }
    return false;
}

void mian() {
    std::cin >> n;
    for (int i = 1; i <= k; i++) for (int j = 1; j <= n; j++) std::cin >> a[i][j];
    for (int i = 1; i <= k; i++) for (int j = 1; j <= n; j++) a[i + k][j] = a[i][j];
    int l = 0;
    int r = maxA;
    while (l < r) {
        int mid = (l + r) / 2;
        init();
        if (DFS(1, mid)) r = mid;
        else l = mid + 1;
    }
    std::cout << l << '\n';
    return;
}

int main() {
    freopen("lock.in", "r", stdin);
    freopen("lock.out", "w", stdout);
    promote();
    std::cin >> T >> k;
    while (T--) mian();
    return 0;
}

03.05｜自测

InfOJ 测的。

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间
#57178	#252. 密码锁	Lyccrius	30	216ms	7920kb	C++14	2.0kb	2023-03-05 08:04:02
#57175	#251. 圣诞树	Lyccrius	65	2125ms	78912kb	C++14	3.4kb	2023-03-05 08:03:29
#57173	#250. 幂次	Lyccrius	30	353ms	66064kb	C++14	1.1kb	2023-03-05 08:02:59
#57172	#249. 涂色游戏	Lyccrius	100	2366ms	5112kb	C++14	1.2kb	2023-03-05 08:02:37