首页 > 其他分享 >NOIP模拟赛记录

NOIP模拟赛记录

时间：2023-10-23 16:35:36浏览次数：25  
标签：ch return NOIP 记录 int long push 模拟 define

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;
}

2023.10.23模拟赛总结

T2赛场做法假了，没对拍

T3没有注意到重要的 \(a_i \neq a_j\) 的条件

T4注意线段树常数很大，不如暴力，\(10^6\) 应该优先考虑 \(\mathcal{O(n)}\) 做法

标签：ch,return,NOIP,记录,int,long,push,模拟,define
From： https://www.cnblogs.com/xiaruize/p/17782596.html

相关文章

  • Unity3D学习记录03——Navigation智能导航地图烘焙
    首先还是在PackageManager中安装AINavigation接着选择我们场景的地面，右键，找到AI的NavMeshSurface，它会为我们的Ground添加一个叫NavMeshSurface的子物体在Inspector窗口中可以看到它的详细的参数：图中的R，H为你人物的参数，45°为你的人物可以爬行的最大角度AgentType里面可......
  • 模拟赛总结合集
    20231023:NOIP2023-div2模拟赛24A.公园题意给一个无向图\(G=(V,E)\),求一个\(X\),使得\(D\timesX+\sum\limits_{e\inG,dist(1,e.u)>Xordist(1,e.v)>X}cost(e)\)最小,求最小值赛时思路非常的简单啊算法概述处理出一号点到所有点的最短路,按最短路从大到小排序依......
  • Netsuite Oauth1.0 C# 项目对接 踩坑记录
    参考Github项目地址：https://github.com/ancpetras/asp.net-netsuite-oauth-1.0-starter注意点：1、Realm这个参数在Authorization请求头中，但是它不需要参与签名，不要将Realm丢进去一起签名了。2、参与签名的还包括URL传参中的参数，比如：?script=152&deploy=1中的script与deploy。3、......
  • 漏洞记录
    记录分享一下工作上遇到的一个洞进入根域名，404目录扫描，发现/conf/catalina.properties路径，catalina.properties是配置tomcat的安全设置、类加载设置、不需要扫描的类设置、字符缓存设置四大块。既然是访问到tomcat的配置文件了，那么就尝试访问/logs/路径下的日志文件。通过log......
  • 模拟集成电路设计系列博客——3.3.1 带隙电压基准概念
    3.3.1带隙电压基准概念在模拟电路模块，尤其是数据转换模块中，一个非常重要的组件是电压参考。理想情况下，这个模块输出一个固定的已知幅度的直流电压，并且不随温度发生变化。通过这个模块再结合一个精确的电阻可以提供一个稳定的直流电流。有一系列手段可以产生集成电路中的电压参考......
  • IPV6问题处理-双栈环境IPv6网络不通模拟测试
    1.1网络拓扑环境描述测试是在公司现有的环境下进行测试的，IPv4网络全通无故障，没有IPv6网络外网线路。主机是自己的电脑，支持双栈。1.3验证问题验证在双栈网络中，主机会优先请求DNS的AAAA记录，如果ipv6网络故障了，还是否会根据向DNS请求来的AAAA记录去访问网站，从而导致断网。设备配置2.1H......
  • 自动化交易程序开发记录-23年10月22日
    陷入停滞的自动化交易项目从十月份上半月开始，自动化程序开发陷入了停滞，现在主要是有了以下成果：自动交易基于binance的行情接口和现货交易接口，能够根据行情和预先编写的策略进行判定并执行交易回测框架在binance上下载历史行情数据，导入到mysql，来验证策略的收益从实际效果上......
  • CAN协议信号位-大小端学习记录
    CAN协议信号位-大小端学习进入汽车行业虽然是软件开发但是对底层的信号传递还是很感兴趣的，深入的学习了一下CAN协议中提到的大小端内容。还挺有意思的。我抽几个信号进行学习推断。有很多信号的推断我直接附上手绘图片仅记录一下分析过程。前提条件：了解DBC数据库文件能看懂了......
  • 报错：java: -source 8 中不支持 记录
    修改项目的字节码版本|Settings|Build,Execution,Deployment|Compiler|JavaCompiler修改项目的LanguageLevel修改Modules的LanguageLevel......
  • laravel:捕捉异常记录到日志(10.27.0)
    一，相关文档:https://learnku.com/docs/laravel/10.x/errors/14857#9e8f93二，php代码:1，代码:12345678910111213141516171819202122232425262728classNewsControllerextendsController{    //启用事务    publicfuncti......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99