526互联

NOIP模拟赛记录

发布时间 2023-10-23 16:27:16作者: xiaruize

NOIP模拟赛记录

2023.10.23 比赛记录

A. 公园

直接dijkstra即可

可爱的code捏 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e5 + 10;

// bool st;
int n, m, c;
vector<pii> g[N];
int dis[N];
bool vis[N];
int sum = 0;
int res, cnt = 0;
// bool en;

void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({ 0, 1 });
    dis[1] = 0;
    while (!q.empty()) {
        auto [ds, x] = q.top();
        q.pop();
        if (ds != dis[x])
            continue;
        for (auto [v, w] : g[x])
            if (vis[v])
                sum -= w;
        vis[x] = true;
        cnt++;
        // cerr << x << ' ' << ds << ' ' << cnt << ' ' << sum << ' ' << ds * cnt + sum << endl;
        res = min(res, ds * c + sum);
        for (auto [v, w] : g[x]) {
            if (dis[v] > dis[x] + w) {
                dis[v] = dis[x] + w;
                q.push({ dis[v], v });
            }
        }
    }
}

void solve() {
    cin >> n >> m >> c;
    rep(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
        sum += w;
    }
    res = sum;
    dijkstra();
    cout << res << endl;
}

signed main() {
    freopen("park.in", "r", stdin);
    freopen("park.out", "w", stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--) solve();
    return 0;
}

B. 括号

考虑这样的贡献，每个右括号，考虑先找到一个左括号与它匹配，

此时考虑在这个匹配左侧加上一个括号序列

可以用一个stack记录剩下 \(x\) 个时的贡献

可爱的code捏 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e7 + 10;

// bool st;
int n, x, y, z, m[2], c[N];
int cnt = 0;
int sum = 0;
ull res = 0;
stack<pii> st;
// bool en;

void solve() {
    cin >> n >> x >> y >> z >> m[0] >> m[1] >> c[1] >> c[2];
    // // cerr << c[1] << ' ' << c[2] << ' ';
    rep(i, 3, n) {
        c[i] = (c[i - 1] * x + c[i - 2] * y + z) % m[(i & 1) ^ 1] + 1;
        // cerr << c[i] << ' ';
    }
    cnt = 0;
    rep(i, 1, n) {
        if (i & 1) {
            cnt += c[i];
            continue;
        }
        res += min(cnt, c[i]);
        while (!st.empty() && st.top().first > cnt - c[i]) {
            res += st.top().second;
            st.pop();
        }
        if (cnt < c[i])
            cnt = 0;
        else {
            cnt -= c[i];
            if (st.empty() || st.top().first != cnt)
                st.push({ cnt, 1 });
            else {
                res += st.top().second;
                st.top().second++;
            }
        }
    }
    // cerr << endl;
    cout << res << endl;
}

signed main() {
    freopen("brackets.in", "r", stdin);
    freopen("brackets.out", "w", stdout);
    // cerr << (&en - &st) / 1024.0 / 1024.0 << endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--) solve();
    return 0;
}

C. 学校

注意到一个重要的条件 \(a_i \neq a_j\)

考虑 \(dp_i\) 表示选择第 \(i\) 位且 \(i\) 选择的方案数

枚举 \(i,j\) 表示最后两个选中的位置，考虑如何 \(O(1)\) 的算剩下的 \(2\) 个

可以用前缀和做，即 \(sum_{i,j}\) 表示到 \(i\) 位， 选择 \(2\) 个的 \(\oplus\) 值为 \(j\) 的方案数

可爱的code捏 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 998244353;
const int N = 5e3 + 10;

// bool st;
int n, m, s;
int a[N];
int dp[N], sum[N][N];
int res = 0;
// bool en;

void solve() {
    cin >> n >> m >> s;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) {
        dp[i] = 1;
        rep(j, 0, (1 << m)) sum[i][j] = sum[i - 1][j];
        rep(j, 1, i - 1) {
            int val = ((dp[j] - sum[j - 1][s ^ a[i] ^ a[j]]) % MOD + MOD) % MOD;
            (dp[i] += val) %= MOD;
            (sum[i][a[i] ^ a[j]] += val) %= MOD;
        }
        (res += dp[i]) %= MOD;
    }
    cout << res << endl;
}

signed main() {
    freopen("school.in", "r", stdin);
    freopen("school.out", "w", stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--) solve();
    return 0;
}

D. 运算

考场想了个线段树优化建图，其实没必要，因为常数过大，在大多数数据下不如暴力

明显应该把操作逆过来，即从 \(0\) 倒推

可以将第一次操作算成加法，然后每次除一下再减一下

除法可以在一开始预处理，即 \((i\times d)\mod{n} \rightarrow i\) 建边

每个点的答案在第一次访问时就确定了，而且只会在第一次访问时向别的点贡献

此时，其实就是一个区间删除，区间查询剩下的数

就可以并查集维护每个点右边的第一个还没被访问的点，暴力扩展即可

有一点点卡常 加个快读就过了

可爱的code捏 
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e6 + 10;

// #define DEBUG 1  // 调试开关
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
    IO() : p1(buf), p2(buf), pp(pbuf) {}

    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
    char gc() {
#if DEBUG  // 调试，可显示字符
        return getchar();
#endif
        if (p1 == p2)
            p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
        return p1 == p2 ? ' ' : *p1++;
    }

    bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }

    template <class T>
    void read(T &x) {
        double tmp = 1;
        bool sign = 0;
        x = 0;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-')
                sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
        if (ch == '.')
            for (ch = gc(); isdigit(ch); ch = gc()) tmp /= 10.0, x += tmp * (ch - '0');
        if (sign)
            x = -x;
    }

    void read(char *s) {
        char ch = gc();
        for (; blank(ch); ch = gc())
            ;
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
    }

    void read(char &c) {
        for (c = gc(); blank(c); c = gc())
            ;
    }

    void push(const char &c) {
#if DEBUG  // 调试，可显示字符
        putchar(c);
#else
        if (pp - pbuf == MAXSIZE)
            fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
#endif
    }

    template <class T>
    void write(T x) {
        if (x < 0)
            x = -x, push('-');  // 负数输出
        static T sta[35];
        T top = 0;
        do {
            sta[top++] = x % 10, x /= 10;
        } while (x);
        while (top) push(sta[--top] + '0');
    }

    template <class T>
    void write(T x, char lastChar) {
        write(x), push(lastChar);
    }
} io;

// bool st;
int n, d, l, r, q;
vector<int> g[N];
int dis[N];
queue<int> que;
// bool en;

struct Union {
    int fa[N];

    void init() { rep(i, 0, n) fa[i] = i; }

    int get(int x) {
        if (fa[x] == x)
            return x;
        return fa[x] = get(fa[x]);
    }

    void merge(int x, int y) { fa[get(x)] = get(y); }

    void tag(int x) { merge(x, x + 1); }
} uni;

void solve() {
    memset(dis, 0x3f, sizeof(dis));
    io.read(n);
    io.read(d);
    io.read(l);
    io.read(r);
    io.read(q);
    uni.init();
    rep(i, 0, n - 1) g[i].clear();
    rep(i, 0, n - 1) g[1ll * i * d % n].push_back(i);
    rep(i, n - r, n - l) {
        dis[i] = 0;
        uni.tag(i);
        que.push(i);
    }
    while (!que.empty()) {
        int x = que.front();
        que.pop();
        for (auto v : g[x]) {
            int st = (v - r + n) % n, en = (v - l + n) % n;
            if (st <= en) {
                for (int i = uni.get(st); i <= en; i = uni.get(i)) {
                    dis[i] = dis[x] + 1;
                    uni.tag(i);
                    que.push(i);
                }
            } else {
                for (int i = uni.get(0); i <= en; i = uni.get(i)) {
                    dis[i] = dis[x] + 1;
                    uni.tag(i);
                    que.push(i);
                }
                for (int i = uni.get(st); i < n; i = uni.get(i)) {
                    dis[i] = dis[x] + 1;
                    uni.tag(i);
                    que.push(i);
                }
            }
        }
    }
    while (q--) {
        int x;
        io.read(x);
        if (dis[x] >= INF) {
            io.push('-');
            io.push('1');
            io.push('\n');
        } else {
            io.write(dis[x], '\n');
        }
    }
}

signed main() {
    freopen("calculator.in", "r", stdin);
    freopen("calculator.out", "w", stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    io.read(testcase);
    while (testcase--) solve();
    return 0;
}