首页 > 其他分享 >SMU Summer 2024 Contest Round 6

SMU Summer 2024 Contest Round 6

时间：2024-07-22 20:42:10浏览次数：16  
标签：Summer ++ SMU tr 2024 int vector include void

A Many Formulas

思路：二进制枚举


void solve() {
    string s;
    cin >> s;
    int n = s.size();
    int m = pow(2, n - 1);
    int ans = 0;
    for (int i = 0; i < m; ++i) {
        int now = 0, sum = 0;
        for (int j = 0; j < n; ++j) {
            now = now * 10 + (s[j] - '0');
            if ((i >> j) & 1) {
                sum += now;
                now = 0;
            }
        }
        sum += now;
        ans += sum;
    }
    cout << ans;
}

B Tak and Cards

思路：将数分为大于A和小于A的两部分，只去与A的差值，分别对两部分用背包求和的个数，统计答案即可

void print(__int128 num)
{
    if(num>9)
        print(num/10);
    putchar(num%10+'0');
}
void solve() {
    int n, a;
    cin >> n >> a;
    vector<int> b(n + 1);
    vector<int> x, y;
    __int128 cnt = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        int c = abs(b[i] - a);
        if (b[i] < a) x.push_back(c);
        else if (b[i] > a) y.push_back(c);
        else cnt ++;
    }
    cnt = pow(2, (int)cnt);
    int nx = x.size(), ny = y.size();
    int m = 2500;

    vector<__int128> fx(m + 5);
    vector<__int128> fy(m + 5);
    fx[0] = fy[0] = 1;
    for (int i = 0; i < nx; ++i) {
        for (int j = m; j >= x[i]; --j) {
            fx[j] = fx[j] + fx[j - x[i]];
        }
    }
    for (int i = 0; i < ny; ++i) {
        for (int j = m; j >= y[i]; --j) {
            fy[j] = fy[j] + fy[j - y[i]];
        }
    }
    __int128 ans = 0;
    for (int i = 1; i <= m; ++i) {
        ans += (fx[i] * fy[i] * cnt);
    }
    ans += cnt - 1;
    print(ans);
}

C Wall

思路：floyd求最短路

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > g(10, vector<int> (10));
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            cin >> g[i][j];
        }
    }
    for (int k = 0; k < 10; ++k) {
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < 10; ++j) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int x;
            cin >> x;
            if (x != -1) {
                ans += g[x][1];
            }
        }
    }
    cout << ans;
}

D Coloring Edges on Tree

思路：最大的颜色数为最大度数，首先标记度最大的点的边，bfs继续标记每条表，跳过已经标记过得颜色

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e5 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;

struct E {
    int x, y;
};

void solve() {
    int n;
    cin >> n;
    vector<E> g(n - 1);
    vector<int> st(n + 1), d(n + 1);
    vector<vector<int> > ve(n + 1);
    map<PII, int> mp;
    int ma = -1, p;
    for (int i = 0; i < n - 1; ++i) {
        cin >> g[i].x >> g[i].y;
        mp[{g[i].x, g[i].y}] = -1;
        ve[g[i].x].push_back(g[i].y), ve[g[i].y].push_back(g[i].x);
        d[g[i].x] ++, d[g[i].y] ++;
        if (d[g[i].x] > ma) {
            ma = d[g[i].x], p = g[i].x;
        }
        if (d[g[i].y] > ma) {
            ma = d[g[i].y], p = g[i].y;
        }
    }
    vector<int> col(n - 1);
    queue<int> q;
//    cout << p << '\n';
    st[p] = 1e9;
    q.push(p);
    while (q.size()) {
        auto t = q.front();
        q.pop();
        int idx = 1;
        for (auto v:ve[t]) {
            if (st[v]) continue;
            if (idx == st[t]) idx ++;
            mp[{t, v}] = mp[{v, t}] = idx;
            st[v] = idx ++;
            q.push(v);
        }
    }
    cout << ma << '\n';
    for (int i = 0; i < n - 1; ++i) {
        cout << mp[{g[i].x, g[i].y}] << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

E Fault-tolerant Network

思路：实际上就是要将a1、an、b1、bn都连上边，求出与它们差最小的数，分别考虑每种连接情况

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <climits>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e5 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0,1, 0, -1};


void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    int ans = LLONG_MAX;
    int x1, x2, x3, x4;
    x1 = x2 = x3 = x4 = LLONG_MAX;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        x1 = min(x1, abs(a[1] - b[i]));
        x2 = min(x2, abs(a[n] - b[i]));
    }
    for (int i = 1; i <= n; ++i) {
        x3 = min(x3, abs(b[1] - a[i]));
        x4 = min(x4, abs(b[n] - a[i]));
    }
    ans = min(ans, abs(a[1] - b[1]) + abs(a[n] - b[n]));
    ans = min(ans, abs(a[1] - b[n]) + abs(a[n] - b[1]));
    ans = min(ans, abs(a[1] - b[1]) + x2 + x4);
    ans = min(ans, abs(a[1] - b[n]) + x2 + x3);
    ans = min(ans, abs(a[n] - b[1]) + x1 + x4);
    ans = min(ans, abs(a[n] - b[n]) + x1 + x3);
    ans = min(ans, x1 + x2 + x3 + x4);
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

F Nearest Excluded Points

思路：

点数不多，若距离一个点为1的位置不存在点，说明该位置可以为该点的答案，考虑用已经标记过答案的点去bfs没有标记过的点，更新答案

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <climits>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e5 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0,1, 0, -1};

struct E {
    int x, y;
};
void solve() {
    int n;
    cin >> n;
    vector<E> ve(n + 1), ans(n + 1, {LLONG_MAX, LLONG_MAX});
    map<PII, int> id;
    for (int i = 1; i <= n; ++i) {
        cin >> ve[i].x >> ve[i].y;
        id[{ve[i].x, ve[i].y}] = i;
    }
    queue<E> q;
    for (int i = 1; i <= n; ++i) {
        for (int k = 0; k < 4; ++k) {
            int x = ve[i].x + dx[k], y = ve[i].y + dy[k];
            if (!id.count({x, y})) {
//                cout << ve[i].x << ' ' << ve[i].y << "|" << x << ' ' << y << '\n';
                ans[i] = {x, y};
                q.push({ve[i].x, ve[i].y});
                break;
            }
        }
    }
    while (q.size()) {
        auto [x, y] = q.front();
        q.pop();
        int fa = id[{x, y}];
        int fx = ans[fa].x, fy = ans[fa].y;
        for (int k = 0; k < 4; ++k) {
            int xx = x + dx[k], yy = y + dy[k];
            if (id.count({xx, yy}) && ans[id[{xx, yy}]].x == LLONG_MAX) {
                ans[id[{xx, yy}]] = {fx, fy};
                q.push({xx, yy});
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i].x << ' ' << ans[i].y << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

G Vacation Query

思路：

线段树维护0和1的最大连续区间长度，若为修改操作，交换0和1维护的线段树即可

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 5e5 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;
#define lc k << 1
#define rc k << 1 | 1
string a;
struct tree {
    int l, r;
    int ans[2], lmx[2], rmx[2];
    int lz;
}tr[N * 4];

void pushup(tree & u, tree ll, tree rr) {
    u.ans[0] = max({ll.ans[0], rr.ans[0], ll.rmx[0] + rr.lmx[0]});
    u.ans[1] = max({ll.ans[1], rr.ans[1], ll.rmx[1] + rr.lmx[1]});

    u.lmx[0] = ll.lmx[0];
    if (ll.lmx[0] == ll.r - ll.l + 1) u.lmx[0] += rr.lmx[0];
    u.lmx[1] = ll.lmx[1];
    if (ll.lmx[1] == ll.r - ll.l + 1) u.lmx[1] += rr.lmx[1];

    u.rmx[0] = rr.rmx[0];
    if (rr.rmx[0] == rr.r - rr.l + 1) u.rmx[0] += ll.rmx[0];
    u.rmx[1] = rr.rmx[1];
    if (rr.rmx[1] == rr.r - rr.l + 1) u.rmx[1] += ll.rmx[1];
}

void build (int k, int l, int r) {
    tr[k] = {l, r};
    if (l == r) {
        if (a[l] == '0') tr[k].rmx[0] = tr[k].lmx[0] = tr[k].ans[0] = 1;
        else tr[k].rmx[1] = tr[k].lmx[1] = tr[k].ans[1] = 1;
        return ;
    }
    int mid = l + r >> 1;
    build (lc, l, mid), build(rc, mid + 1, r);
    pushup(tr[k], tr[lc], tr[rc]);
}

void swap_(int k) {
    swap(tr[k].ans[0], tr[k].ans[1]);
    swap(tr[k].lmx[0], tr[k].lmx[1]);
    swap(tr[k].rmx[0], tr[k].rmx[1]);
}

void pushdown(int k) {
    if (tr[k].lz) {
        swap_(lc), swap_(rc);
        tr[lc].lz ^= 1;
        tr[rc].lz ^= 1;
        tr[k].lz ^= 1;
    }
}

void modify(int k, int l, int r) {
    if (tr[k].l >= l && tr[k].r <= r) {
        swap_(k);
        tr[k].lz ^= 1;
        return ;
    }
    pushdown(k);
    int mid = tr[k].l + tr[k].r >> 1;
    if (l <= mid) modify(lc, l, r);
    if (r > mid) modify(rc, l, r);
    pushup(tr[k], tr[lc], tr[rc]);
}

tree query(int k, int l, int r) {
    if (tr[k].l >= l && tr[k].r <= r) return tr[k];
    pushdown(k);
    int mid = tr[k].l + tr[k].r >> 1;
    if (mid >= r) return query(lc, l, r);
    if (mid < l) return query(rc, l, r);
    tree T;
    pushup(T, query(lc, l, mid), query(rc, mid + 1, r));
    return T;
}

void solve() {
    int n, q;
    cin >> n >> q;
    cin >> a;
    a = ' ' + a;
    build(1, 1, n);
    while (q --) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            modify(1, l, r);
        } else {
            cout << query(1, l, r).ans[1] << '\n';
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

 

标签：Summer,++,SMU,tr,2024,int,vector,include,void
From： https://www.cnblogs.com/bible-/p/18316850

相关文章

  • 2024 Selenium10个替代品
     随着自动化测试需求的不断增长，Selenium作为广泛使用的自动化测试工具，虽然功能强大，但也存在一些限制和挑战。在2024年，越来越多的替代工具涌现，它们提供了更高效、更易用的解决方案。那么，哪些替代品值得我们关注呢？  在自动化测试领域，除了Selenium，还有哪些工具能够满足我们的......
  • 2024信友队蓝润暑期集训提高1班②Day7
    知识总结Tarjan算法Tarjan算法是一种用于计算有向图中强连通分量的算法。Tarjan算法的基本思想是：首先，将图中每个节点标记为未访问。然后，从某个节点开始，对该节点进行DFS，并记录该节点的入度（即该节点的邻居个数）。对于每个节点，如果其入度为0，则说明它是一个根节点，将它标记......
  • Camtasia2024苹果mac+win电脑破解版安装包下载！附带激活码许可证号
    在视频创作和教学内容制作领域，CamtasiaStudio一直是备受青睐的工具。随着2024版本的推出，CamtasiaStudio带来了更多强大的功能和优化，为用户提供了更高效、更便捷的创作体验。接下来，让我们详细了解一下CamtasiaStudio2024的新功能，并深入学习它的使用教程。camtasia202......
  • 2024钉钉杯及2023钉钉杯ABC题分析
    钉钉杯，通常指的是钉钉杯大数据挑战赛，这是一场由阿里巴巴旗下钉钉举办的全国性大数据竞赛。以下是对钉钉杯的详细解析：一、竞赛背景与目的钉钉杯大数据挑战赛旨在通过大数据竞赛的形式，激发学生对大数据技术的兴趣，提升他们的数据分析和数据挖掘能力。同时，该竞赛也为学生提供了一......
  • 【ACM出版】2024年云计算与大数据国际学术会议（ICCBD 2024，7月26-28)
    2024年云计算与大数据国际学术会议(ICCBD2024)将于2024年7月26-28日在中国大理召开。ICCBD2024将围绕“云计算与大数据”的最新研究领域,旨在为从事研究的专家、学者、工程师和技术人员提供一个国际平台，分享科研成果和尖端技术，了解学术发展趋势，拓宽研究思路，加强学术研......
  • 2024/7/22 模拟赛记录
    这次的模拟赛比较简单。150T1:100T2:30T3:0T4:20T1:【题目描述】给定两个字符串a,b，从a中选一段前缀，b中选一段后缀（前后缀都可以为空），并将选出的后缀拼在选出的前缀后面。你需要求出有多少种本质不同的串（可以为空）场上思路：上来直接敲了个扩展kmp，仔细读题后发现这道题和kmp......
  • 2024“钉耙编程”中国大学生算法设计超级联赛（2）
    Preface最唐氏的一集，前中期被A卡得数次破防红温，后期经典不知道在干嘛摆着摆着就结束了可惜的是徐神最后1h写的B因为两个数组搞反了一直没过，赛后看了眼就过了，这下狠狠地掉Rating了鸡爪丁真构造题，但有人连WA三发怎么回事呢首先不难想到最大化和\(1\)连边的数量，首......
  • 2024 ICPC ShaanXi Provincial Contest 换座位 sol
    \(\text{Link}\)自然地想到\(i\)向\(a_i\)连边。随便造一组强一点的数据：103121010892082图大概长这样容易发现每个\(i\)有且仅有\(1\)条出边。发现图中\(1,2,3\)这\(3\)个点组成了一个环。在这个环上，每个人都能做到自己心仪的位置上，所以这个环对......
  • NOI2024 翻盘记
    前排提示：这里的“翻盘”指的不是Day1寄了Day2翻盘（虽然也有一点？），而是Day2单场比赛的翻盘。2024.7.12（UNR笔试）没看到与题库相比改了答案，喜提\(99\)，正赛可不能这么粗心！2024.7.13（UNRDay1）唐完了。上来A结论假了，浪费了一个小时。B式子推错了，改对后以为单次复杂度是\(O(......
  • 2024护网行动可能要用的一些工具（非常详细）零基础入门到精通，收藏这一篇就够了
    前言通用工具工具类型工具地址内网扫描https://github.com/shadow1ng/fscan哥斯拉Webshell管理https://github.com/BeichenDream/GodzillaARL资产侦察灯塔https://github.com/TophantTechnology/ARLaliyun-accesskey-Toolshttps://github.com/mrknow001/aliyun-access......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99