首页 > 其他分享 >10 月 16 日模拟赛总结

10 月 16 日模拟赛总结

时间：2023-10-16 23:15:53浏览次数：39  
标签：10 return 16 int kMaxN ++ BigInt 模拟 size

Before

本文章在洛谷博客同步发布

Contest-Link

预期 \(30 + 0 + 0 + 20 = 50\)。

实际 \(30 + 0 +100+ 60 = 190\)。

挂分 \(-140\)。

rk2/totrk7，行。

看 T1，单调栈，不会，写暴力溜。看 T2，挺线段树的，但好像维护不了，写暴力溜。看 T3，不会怎么还不会啊，挺 K 的一个树形 DP，没拿暴力 30 分是最大的失误。然后就只有 1h 了，感觉今天要爆零啊。然后开 T4，啊啊这不板子题吗，怎么最简单啊，这么牛。你直接坐坐坐坐坐坐坐下！结果被坐下了，剩下 15min 还没调出来，我恼恼恼恼恼恼恼。然后本来想输出样例的，但不能放弃，然后我调调调调调调，然后是并查集写错了，看了半小时，哈哈。只剩 5min 了大样例还是错的，我急急急急急急急。哈哈。我当场感觉今天寄了啊，垫底了啊。哈哈哈哈哈哈哈。

结果非常炸裂，我 T4 过了。经典西西弗数据啊。而且初一组就我一人 AC 了。原来是我样例复制少了，最后 3min 惊险调出来了，哈哈哈哈哈哈哈。

然后就寄了。

T1

Description

给定一个排列，每一轮对于每个数，如果它左边相邻的数比它大则删除，求几轮后不会再删除数。

\(1 \le n\le 10^6\)。

Solution

这不显然的单调栈吗我考试时怎么没想出来啊。

只要不是逆序对塞进去然后答案计数即可。

考场想法：暴力。

考场寄因：暴力。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。

Code

\(\text{100pts:}\)

// 2023/10/16 PikachuQAQ

#include <iostream>

using namespace std;

const int kMaxN = 1e6 + 7;

int n, a[kMaxN], ans;
int stk[kMaxN], top;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = n, cnt; i; i--) {
        for (cnt = 0; top && stk[top] < a[i]; ) {
            top--, cnt++;
        }
        stk[++top] = a[i], ans = max(ans, cnt);
    }
    cout << ans;

    return 0;
}

T2

Description

给定 \(1\) 到 \(n\) 的数轴上每个点最多能够被覆盖的次数 \(a_i\)，以及 \(m\) 个区间，求最多可以选择几个区间。

\(1 \le n,m,a_i \le 10^5\)，\(1 \le l_i, r_i \le n\)。

Solution

可以证明，按右端点排序来覆盖是最优的。

于是我们使用线段树贪心的覆盖，能塞就塞。

时间复杂度 \(O(n\log n)\)，空间复杂度 \(O(n)\)。

Code

\(\text{100pts:}\)

// 2023/10/16 PikachuQAQ

#include <iostream>
#include <algorithm>

using namespace std;

const int kMaxN = 1e6 + 7, kMaxM = 4e6 + 7, INF = 1e9;

struct E {
    int l, r;
} a[kMaxN];

bool cmp(E x, E y) {
    return x.r < y.r;
}

int n, m, ans;
int seg[kMaxM], add[kMaxM];

int M(int l, int r) { return l + r >> 1; } 
int L(int p) { return p << 1; } 
int R(int p) { return p << 1 | 1; } 
void tag(int p, int d) { seg[p] += d, add[p] += d; } 
void pushup(int p) { seg[p] = min(seg[L(p)], seg[R(p)]); }
void pushdown(int p) { 
    tag(L(p), add[p]), tag(R(p), add[p]);
    add[p] = 0;
}

void Update(int s, int t, int l, int r, int p, int d) {
    if (s <= l && r <= t) {
        tag(p, d);
    } else {
        pushdown(p);
        if (s <= M(l, r)) {
            Update(s, t, l, M(l, r), L(p), d);
        }
        if (t >= M(l, r) + 1) {
            Update(s, t, M(l, r) + 1, r, R(p), d);
        }
        pushup(p);        
    }
}


int Query(int s, int t, int l, int r, int p) {
    int res = INF;
    if (s <= l && r <= t) {
        return seg[p];
    }
    pushdown(p);
    if (s <= M(l, r)) {
        res = min(Query(s, t, l, M(l, r), L(p)), res);
    } 
    if (t >= M(l, r) + 1) {
        res = min(res, Query(s, t, M(l, r) + 1, r, R(p)));
    }
    return res;
}


int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        Update(i, i, 1, n, 1, x);
    }
    for (int i = 1; i <= m; i++) {
        cin >> a[i].l >> a[i].r;
    }
    sort(a + 1, a + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        if (Query(a[i].l, a[i].r, 1, n, 1)) {
            ans++;
            Update(a[i].l, a[i].r, 1, n, 1, -1);
        }
    }
    cout << ans;

    return 0;
}

T3

Description

给定一棵树，对边进行黑白染色，不能有两条黑边相邻，求最多黑边数量以及对应的方案数。

\(1 \le n \le 1000\)。

Solution

有 \(f_{i,0/1}\) 表示 \(i\) 不选择或选择时的能匹配的最多点，\(g_{i,0/1}\) 表示 \(f_i\) 匹配点的方案数，\(p_i\) 表示 \(i\) 不匹配的状况下，\(j\) 匹配的方案数。

当这个点不连接时，能匹配的点自然是它儿子最多能选雨最多不选中的最大值，也就是：

\[f_{u,0}=\sum^m_{v=1} \max(f_{v,0},f_{v,1}) \]

然后我们考虑选择。对于当前的能匹配的点，我们减去重复的 \(\max(f_{v,0},f_{v,1})\)，也有可能下面的儿子直接不匹配了，所以点加上 \(f_{v,0}+1\)。也就是：

\[f_{u,1}=\max^m_{i=1}(f_{u,0} - \max(f_{v,0}, f_{v,1})+f_{v,0}+1) \]

然后我们统计方案数。我们只考虑转移合法的，从下往上转移即可。

令 \(x=[f_{v,0}\ge f_{v,1}],y=[f_{v,0}\le f_{v,1}]\)，有 \(g_{u,0}\) 转移：

\[g_{u,0}=\prod^m_{j=1}(g_{v,0} \times x + g_{v,1}) \]

然后就有了选择的 \(g_{u,1}\) 转移：

\[g_{u,1}=\dfrac{g_{u,0}}{h_j}\times g_{v,0} \]

然后 DP 数组会炸，高精度一下，就做完了。

时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。

Code

\(\text{100pts:}\)

// 2023/10/16 PikachuQAQ

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

using namespace std;

const int kMaxN = 1007, INF = 1e9;

typedef long long ll;

struct BigInt {
    static const int BASE = 100000000, WIDTH = 8; 
    vector<ll> s;

    BigInt() {
        *this = 0;
    }

    BigInt(const int& num) {
        *this = num;
    }

    BigInt operator = (int num) {
        s.clear();
        do {
            s.push_back(num % BASE);
            num /= BASE;
        } while (num > 0);
        return *this;
    }

    BigInt operator = (const string& str) {
        s.clear();
        int x, len = (str.length() - 1) / WIDTH + 1;
        for (int i = 0; i < len; i++) {
            int end = str.length() - i * WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start, end - start).c_str(), "%lld", &x);
            s.push_back(x);
        }
        return *this;
    }
    bool operator<(const BigInt& b) {
        if (s.size() < b.s.size()) return true;
        if (s.size() > b.s.size()) return false;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] < b.s[i]) return true;
            if (s[i] > b.s[i]) return false;
        }
        return false;
    }

    bool operator >= (const BigInt& b) {
        return !(*this < b);
    }

    bool operator == (const BigInt& b) {
        if (s.size() != b.s.size()) return 0;
        for (int i = 0; i < s.size(); i++)
            if (s[i] != b.s[i]) return 0;
        return 1;
    }

    BigInt operator + (const BigInt& b) {
        BigInt c;
        c.s.clear();
        for (int i = 0, g = 0;; i++) {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = g;
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x += b.s[i];
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c;
    }

    BigInt operator - (const BigInt& b) {
        BigInt c;
        c = *this;
        for (int i = 0; i < c.s.size(); i++) {
            int tmp;
            if (i >= b.s.size())
                tmp = 0;
            else
                tmp = b.s[i];
            if (c.s[i] < tmp) {
                c.s[i + 1] -= 1;
                c.s[i] += BASE;
            }
            c.s[i] -= tmp;
        }
        while (c.s.back() == 0 && c.s.size() > 1) c.s.pop_back();
        return c;
    }

    void operator -= (const BigInt& b) {
        *this = *this - b;
    }

    BigInt operator * (const BigInt& b) {
        BigInt c;
        c.s.resize(s.size() + b.s.size());
        for (int i = 0; i < s.size(); i++)
        for (int j = 0; j < b.s.size(); j++) c.s[i + j] += s[i] * b.s[j];
        for (int i = 0; i < c.s.size() - 1; i++) {
            c.s[i + 1] += c.s[i] / BASE;
            c.s[i] %= BASE;
        }
        while (c.s.back() == 0 && c.s.size() > 1) c.s.pop_back();
        return c;
    }

    void operator *= (const BigInt& b) {
        *this = *this * b;
    }

    friend istream& operator >> (istream& input, BigInt& x) {
        string s;
        if (!(input >> s)) return input;
        x = s;
        return input;
    }

    friend ostream& operator << (ostream& output, const BigInt& x) {
        output << x.s.back();
        for (int i = x.s.size() - 2; i >= 0; i--) {
            char buf[20];
            sprintf(buf, "%08d", x.s[i]);
            for (int j = 0; j < strlen(buf); j++) output << buf[j];
        }
        return output;
    }
} mod = 2, ans;

BigInt Copy(const BigInt& b, int x) {
    BigInt t;
    t.s.resize(b.s.size() + x);
    for (int i = 0; i < b.s.size(); i++) t.s[i + x] = b.s[i];
    return t;
}

BigInt Divide(const BigInt& a, const BigInt& b, BigInt& mod) {
    BigInt c;
    c.s.resize(a.s.size() - b.s.size() + 1);
    mod = a;
    int Pow[(int)log2(BigInt::BASE) + 5];
    Pow[0] = 1;
    for (int i = 1; i <= log2(BigInt::BASE); i++) Pow[i] = Pow[i - 1] * 2;
    for (int i = c.s.size() - 1; i >= 0; i--) {
        BigInt t;
        t = Copy(b, i);
        for (int j = log2(BigInt::BASE); j >= 0; j--)
        if (mod >= t * Pow[j]) {
            c.s[i] += Pow[j];
            mod -= t * Pow[j];
        }
    }
    while (c.s.back() == 0 && c.s.size() > 1) c.s.pop_back();
    return c;
}

int n;
vector<int> a[kMaxN];
BigInt g[kMaxN][2], h[kMaxN];
ll f[kMaxN][2];

void DFS(int u, int fa) {
    BigInt res = 1;
    f[u][0] = 0, f[u][1] = -INF;
    g[u][0] = 1;
    for (int v : a[u]) {
        if (v ^ fa) {
            DFS(v, u);
            h[v] = g[v][0] * (f[v][0] >= f[v][1]) + g[v][1] * (f[v][0] <= f[v][1]);
            res *= h[v];
            f[u][0] += f[v][1] * (f[v][0] < f[v][1]) + f[v][0] * (f[v][0] < f[v][1] == 0);
        }
    }
    g[u][0] = res, f[u][1] = -INF;
    for (int v : a[u]) {
        if (v ^ fa) {
            int val = f[u][0] - max(f[v][1] - f[v][0], 0ll) + 1;
            if (f[u][1] < val) {
                f[u][1] = val;
                g[u][1] = Divide(res, h[v], mod) * g[v][0];
            } else if (f[u][1] == val) {
                g[u][1] = Divide(res, h[v], mod) * g[v][0] + g[u][1];
            }
        }
    }
}

int main() {
    for (int i = 1; i <= 1005; i++) {
        mod *= 2;
    }
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1, u, m; i <= n; i++) {
        cin >> u >> m;
        for (int j = 1, v; j <= m; j++) {
            cin >> v;
            a[u].push_back(v);
        }
    }
    DFS(1, 0);
    ans = g[1][0] * (f[1][0] >= f[1][1]) + g[1][1] * (f[1][0] <= f[1][1]);
    cout << max(f[1][0], f[1][1]) << '\n' << ans << '\n';

    return 0;
}

T4

Description

给定 \(n\) 个数之间的一些大于、小于、等于关系，关系数为 \(m\)，按照数值第一编号第二排序，求是否唯一。

多组数据。

\(0 \le n \le 10000, 0 \le m \le 20000, T \le 30\)。

Solution

很显然，当 \(a\) 比 \(b\) 大时，我们建一条从 \(a\) 到 \(b\) 的变，\(a\) 比 \(b\) 小同理。

然后这个等于处理比较麻烦，我们想到一个点数值一样，那么大小关系也是一样的，我们可以把这些互相等于的连通块缩到一个点在和其他点连边，然后进行操作。这一部分可以用并查集处理。

首先想想 no enough 怎么处理。

我们知道，当一个点的入度为零时，我们不知道还有哪些数比他更大，那么当入度为零的点数大于一时，这几个点因为没有比他们互相关系更大的了，我们判断不了他们之间的互相关系，所以这种情况就是条件缺失，并且当出度为零的点数大于一时，我们也互相判断不了这些点的大小关系，同样条件不足。这一部分可以统计缩点后的图的点入出度。

然后想想 contradiction，冲突怎么处理。

很显然，一个合法的大小关系一定是一个 DAG，不可能出现以下情况：

A > B and B > A

A > B and B > C and C > A

也就是说，不可能图中会有环。一旦有环就会冲突。这一部分可以拓扑排序处理。注意是对缩点后的图进行。

最后，以上两种情况都不是，那么就是 yes 了。

考场想法：并查集拓扑排序。

考场寄因：没寄。

时间复杂度 \(O(n+m)\)，空间复杂度 \(O(n+m)\)。

Code

\(\text{100pts:}\)

// 2023/10/16 PikachuQAQ

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int kMaxN = 10007;

int n, m, cnt1, cnt2, tot;
vector<int> g[kMaxN], a[kMaxN];
int in[kMaxN], out[kMaxN];
int fa[kMaxN], siz[kMaxN];
char laugh_my_axx_off;
bool ne, co;
queue<int> q;

int findfa(int x) {
    return (fa[x] == x) ? x : (fa[x] = findfa(fa[x]));
}

void uni(int x, int y) {
    int u = findfa(x), v = findfa(y);
    if (siz[u] > siz[v]) {
        swap(u, v);
    }
    fa[u] = v, siz[v] += siz[u];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    while (cin >> n >> m) {
        for (int i = 0; i <= n; i++) {
            fa[i] = i, siz[i] = 1;
        }
        for (int i = 0, u, v; i < m; i++) {
            cin >> u >> laugh_my_axx_off >> v;
            if (laugh_my_axx_off == '<') {
                g[v].push_back(u);
            }
            if (laugh_my_axx_off == '>') {
                g[u].push_back(v);
            }
            if (laugh_my_axx_off == '=') {
                uni(u, v);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j : g[i]) {
                a[findfa(i)].push_back(findfa(j));
                in[findfa(j)]++, out[findfa(i)]++;  
            }
        }
        for (int i = 0; i < n; i++) {
            cnt1 += (in[i] == 0 && fa[i] == i);
            cnt2 += (out[i] == 0 && fa[i] == i);
        }
        ne = (cnt1 > 1 || cnt2 > 1);
        for (int i = 0; i < n; i++) {
            if (in[i] == 0 && fa[i] == i) {
                q.push(i);
            }
        }
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int v : a[u]) {
                --in[v];
                if (in[v] == 0) {
                    q.push(v);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (in[i] > 0 && fa[i] == i) {
                co = 1;
            }
        }
        if (co) {
            cout << "contradiction\n";
        } else if (ne) {
            cout << "not enough\n";
        } else {
            cout << "yes\n";
        }
        co = ne = cnt1 = cnt2 = 0;
        for (int i = 0; i < n; i++) {
            in[i] = out[i] = 0;
            g[i].clear(), a[i].clear();
        }
    }

    return 0;
}

Summary

需要掌握的：规划时间。

标签：10,return,16,int,kMaxN,++,BigInt,模拟,size
From： https://www.cnblogs.com/PikachuQAQ/p/10-16-contest-ji-yin.html

相关文章

  • CSP模拟赛记录
    CSP模拟赛记录落下了好多慢慢补qwq2023.10.16A.魔力子串直接vector扔map里面没什么好说的警示后人:能用map就不要哈希B.吃树结论题当正好存在\(\frac{n}{k}\)个节点的子树大小为\(k\)的倍数时,\(k\)作为块的大小是合法的对于每种合法的块的大小，有且仅有......
  • 2023.10.16——每日总结
    学习所花时间（包括上课）：9h代码量（行）：0行博客量（篇）：1篇今天，上午学习，下午学习；我了解到的知识点：1.DIV+CSS明日计划：学习......
  • 有趣的大玩具之N4100，小主机也来玩群辉
    这款小主机很有趣。先来看看图。当时忘记备份图片，找咸鱼把图片下载回来。正面背面当时拿这个机器安装的群晖测试了一下局域网+2.5G网卡跑群晖的网速，速度还是非常不错的。晒完图啦。我先来说说优缺点。优点：1、支持type-c一线通，插一根连接显示器就可以开机显示，省去一根电......
  • 生活随笔-20231016
        早起，叫醒小非，为他制作了”可颂滑蛋香肠沙拉“，自己准备的可颂未加香肠，非常美味，我俩都吃的津津有味。        小非上学后，按计划完成书本第三章思维导图第一节。    中午继续观看【大明王朝1566】-20~21集晚上下班到家，按计划带小齐来到楼下，让他练......
  • 16 class 绑定
    初学阶段，这玩意看得懂就行了目的：操作class属性对象绑定：单个对象：：class={}多个对象：：class="ObjectClass"数组绑定：class=[]对象与数组的结合使用只能数组嵌套对象，不能反着来......
  • 2023/10/16 辞职当天 自由身
    曾许人间第一流   须知少时凌云志本想和领导争取一下一个月的缓冲期 没想到最后成了我自己的归途还是试用期被辞退了 感性一下：也许来上海就是个错 错误的一面直接就给了offer  错误的选择了上海错误的将自己压注在这家公司上违约来的上海天真的以为早来早学......
  • 每日总结20231016
    代码时间（包括上课）3h代码量（行）：20行博客数量（篇）：1篇相关事项：1、今天是周一，一周里面最容易犯困的一天，但是这次没有那么困，这次还算是学了不少的，今天上的是软件设计模式和人机交互技术。2、软件设计模式这次讲了三种模式，中介者模式、备忘录模式、观察者模式，人机交互技术讲的是盒子模......
  • 每日总结1016
    代码时间（包括上课）3h代码量（行）：20行博客数量（篇）：1篇相关事项：1、今天是周一，一周里面最容易犯困的一天，但是这次没有那么困，这次还算是学了不少的，今天上的是软件设计模式和人机交互技术。2、软件设计模式这次讲了三种模式，中介者模式、备忘录模式、观察者模式，人机交互技术讲的是盒子模......
  • 2023.10.16
    今天本来都忘了学习网安的东西，结果晚上突然发现今天还没学，去看了一些堆的东西发现ctfwiki堆的知识概述的内容好多，距离真正的应用还有好多感觉是不是应该每天一边刷题一边学堆，这样更有效率一点？ ......
  • pytorch(10.2) 注意力汇聚理论
     https://zh.d2l.ai/chapter_attention-mechanisms/nadaraya-waston.html  https://zhuanlan.zhihu.com/p/265108616 Attention注意力机制与self-attention自注意力机制 Attention注意力机制与self-attention自注意力机制1.为什么要因为注意力机制在Attention诞......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99