首页 > 其他分享 >SMU 2024 winter round1

SMU 2024 winter round1

时间：2024-01-26 18:25:00浏览次数：25  
标签：ldb winter int SMU back long 2024 using define

7-1 最好的文档

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << "Good code is its own best documentation.";
    return 0;
}

7-2 自动编程

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using ldb = long double;

const int mod = 998244353;
#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string s;
    cin >> s;
    cout << "print(" << s << ")\n";
    return 0;
}

7-3 程序员买包子

n , x , m , k = input().split(" ")
if k == n :
    print("mei you mai {} de".format(x))
elif k == m :
    print("kan dao le mai {} de".format(x))
else :
    print("wang le zhao mai {} de".format(x))

7-4 猜数字-交互版

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using ldb = long double;

const int mod = 998244353;
#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    int l = 1, r = n, res = -1;
    string s;
    for (int mid; l <= r;) {
        mid = (l + r) / 2;
        cout << mid << endl;
        cin >> s;
        if (s == ">=") res = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << "! " << res << endl;
    return 0;
}

7-5 斯德哥尔摩火车上的题

def f(a):
    s = ""
    for i in range( 1 , len(a) ):
        if int(a[i]) % 2  == int(a[i-1]) % 2 :
            s += max( a[i] , a[i-1] )
    return s

a = input()
b = input()
a = f(a)
b = f(b)
if a == b :
    print(a)
else :
    print(a)
    print(b)

7-6 剪切粘贴

模拟题

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using ldb = long double;

const int mod = 998244353;
#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string s;
    int n;
    cin >> s >> n;
    int l, r;
    string a, b, x, y, z;
    for (; n; n--) {
        cerr << s << "\n";
        cin >> l >> r >> a >> b, l--, r--;
        cerr << " " << l << " " << r << " " << a << " " << b << "\n";
        for (int i = 0; i < s.size(); i++) {
            if (i < l) x += s[i];
            else if (i <= r) y += s[i];
            else z += s[i];
        }
        cerr << x << " " << y << " " << z << "\n";
        s = x + z, x = "", z = "";
        cerr << s << "\n";
        int p = a.size(), q = b.size();
        for (int i = p; i < s.size(); i++) {
            if (s.substr(i - p, p) != a or s.substr(i, q) != b) continue;

            for (int j = 0; j < i; j++)
                x += s[j];
            for (int j = i; j < s.size(); j++)
                z += s[j];
            cerr << x << " " << y << " " << z << "\n";
            s = x + y + z, x = y = z = "";
            break;
        }
        if (y != "") s = s + y , y = "";
        cerr << s << "\n\n";
    }
    cout << s << "\n";
    return 0;
}

7-7 天梯赛的善良

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using ldb = long double;

const int mod = 998244353;
#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    map<int, int> cnt;
    for (int x; n; n--) cin >> x, cnt[x]++;
    cout << cnt.begin()->first << " " << cnt.begin()->second << "\n";
    cout << cnt.rbegin()->first << " " << cnt.rbegin()->second << "\n";
    return 0;
}

7-8 谷歌的招聘

把每个字串截取出来，然后判断质数就行

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using ldb = long double;

const int mod = 998244353;
#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";


bool is_prime(int x) {
    if (x < 3) return x == 2;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    for (int l = 0, r = k - 1, x; r < n; l++, r++) {
        x = 0;
        for (int i = l; i <= r; i++) x = x * 10 + s[i] - '0';
        if (is_prime(x)) {
            cout << setw(k) << setfill('0')<< x << "\n";
            return 0;
        }
    }
    cout << "404\n";
    return 0;
}

7-9 锦标赛

把比赛过程想象成一个满二叉树

第一行全部放在每一对的左侧。

然后开始逐行判断，其实每一个结点都有两个位置可以选择，但是当前节点必须大于左子树或右子树的最大值，所以逐个判断，如果都不满足就是No Solution

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using ldb = long double;

const int mod = 998244353;
const ldb eps = 1e-9;
const ldb g = 9.8;
#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int k;
    cin >> k;
    vi res(1 << k), a, b;

    for (int i = 0; i < res.size(); i += 2)
        cin >> res[i], a.push_back(i + 1), b.push_back(res[i]);
    while (a.size() > 1) {
        vi c, d;
        for (int i = 0, x; i < a.size(); i += 2) {
            cin >> x;
            if (x >= b[i]) res[a[i]] = x, c.push_back(a[i + 1]), d.push_back(max({b[i], b[i + 1], x}));
            else if (x >= b[i + 1]) res[a[i + 1]] = x, c.push_back(a[i]), d.push_back(max({b[i], b[i + 1], x}));
            else cout << "No Solution\n", exit(0);
        }
        a = c, b = d;
    }
    cin >> res[a.back()];
    if (res[a.back()] != *max_element(res.begin(), res.end()))
        cout << "No Solution\n", exit(0);
    for (auto i: res) cout << i << " ";
    return 0;
}

7-10 插松枝

模拟题，认真读题

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using ldb = long double;

const int mod = 998244353;
#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vi pusher(n), box;
    vector<vi> ans;
    for (auto &i: pusher) cin >> i;
    reverse(pusher.begin(), pusher.end());
    while (!pusher.empty() || !box.empty()) {
        vector<int> cur;
        if (!box.empty()) cur.push_back(box.back()), box.pop_back();
        else cur.push_back(pusher.back()), pusher.pop_back();
        while (cur.size() < k) {
            if (!box.empty() && box.back() <= cur.back())
                cur.push_back(box.back()), box.pop_back();
            else {
                while (!pusher.empty() && pusher.back() > cur.back() && box.size() < m)
                    box.push_back(pusher.back()), pusher.pop_back();
                if (!pusher.empty() && pusher.back() <= cur.back())
                    cur.push_back(pusher.back()), pusher.pop_back();
                else break;
            }
        }
        ans.push_back(cur);
    }
    for (const auto &it: ans) {
        cout << it.front();
        for (int i = 1; i < it.size(); i++)
            cout << " " << it[i];
        cout << "\n";
    }
    return 0;
}

7-11 拯救007

特判起点终点，然后宽搜索即可。

但是说直径15，所以起点应该是到原点距离小于\(k+7.5\)的点，但是亲测数据是\(k+15\)，所以鉴定为垃圾题

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using pii = pair<int, int>;
using ldb = long double;

const int mod = 998244353;
const ldb eps = 1e-9;
const ldb g = 9.8;
#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<pii> node;
    vi ed, vis(n);
    queue<int> q;
    for (int i = 0, d = (15 + k) * (15 + k) , x , y; i < n ; i ++ ) {
        cin >> x >> y;
        node.emplace_back( x,  y);
        if (abs(x - 50) <= k) ed.push_back(i);
        else if (abs(x + 50) <= k) ed.push_back(i);
        else if (abs(y - 50) <= k) ed.push_back(i);
        else if (abs(y + 50) <= k) ed.push_back(i);
        if (x * x + y * y <= d) q.push(i);
    }

    for (int x, d = k * k; not q.empty();) {
        x = q.front();
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int y = 0; y < n; y++) {
            if (vis[y]) continue;
            if ((node[x].first - node[y].first) * (node[x].first - node[y].first) +
                (node[x].second - node[y].second) * (node[x].second - node[y].second) <= d)
                q.push(y);
        }
    }
    for( auto i : ed )
        if( vis[i] ) cout << "Yes\n" , exit(0);
    cout << "No\n";
    return 0;
}

7-12 寻宝图

直接进行暴搜就行，在搜索过程中判断有没有经过宝藏

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using pii = pair<int, int>;
using ldb = long double;

#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;

    vector<string> g(n);
    for (auto &i: g) cin >> i;
    int res = 0, ans = 0;
    auto vis = vector(n, vi(m));
    for (int sx = 0, flag; sx < n; sx++)
        for (int sy = 0; sy < m; sy++) {
            if (vis[sx][sy] or g[sx][sy] == '0') continue;
            res++, flag = 0;
            queue<pii> q;
            q.emplace(sx, sy);
            while (not q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                if (vis[x][y]) continue;
                vis[x][y] = 1;
                if (g[x][y] != '1') flag = 1;
                for (int i = 0, fx, fy; i < 4; i++) {
                    fx = x + dx[i], fy = y + dy[i];
                    if (fx < 0 or fy < 0 or fx >= n or fy >= m) continue;
                    if (vis[fx][fy] or g[fx][fy] == '0') continue;

                    q.emplace(fx, fy);
                }
            }
            ans += flag;
        }
    cout << res << " " << ans << "\n";
    return 0;
}

7-13 垃圾箱分布

从每个垃圾箱开始做一次最短路，然后按照题目要求求出最优解

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using pii = pair<int, int>;
using ldb = long double;

#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
const int inf = 1e9;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, k, ds;
    cin >> n >> m >> k >> ds;
    vector <vector<pii>> e(n + m + 1);
    string us, vs;
    for (int u, v, w; k; k--) {
        cin >> us >> vs >> w;
        if (us[0] == 'G') u = n + atoi(us.substr(1).c_str());
        else u = atoi(us.c_str());
        if (vs[0] == 'G') v = n + atoi(vs.substr(1).c_str());
        else v = atoi(vs.c_str());
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
    }
    auto dij = [e, n, m](int s) -> vi {
        vi dis(n + m + 1, inf), vis(n + m + 1);
        priority_queue<pii, vector<pii>, greater<pii>> q;
        dis[s] = 0, q.emplace(0, s);
        while (not q.empty()) {
            auto [d, x] = q.top();
            q.pop();
            if (vis[x]) continue;
            vis[x] = 1;
            for (auto [y, w]: e[x]) {
                if (vis[y] or dis[y] <= d + w) continue;
                dis[y] = d + w;
                q.emplace(dis[y], y);
            }
        }

        return dis;
    };
    int res = -1, resMin = 0, resSum = inf;
    for (int i = 1, ansMin, ansSum; i <= m; i++) {
        auto dis = dij(n + i);
        ansMin = inf, ansSum = 0;
        for (int j = 1; j <= n; j++) {
            if (dis[j] > ds) ansMin = -1, ansSum = inf;
            ansMin = min(ansMin, dis[j]), ansSum += dis[j];
        }
        if (ansMin > resMin) res = i, resMin = ansMin, resSum = ansSum;
        else if (ansMin == resMin and ansSum < resSum)res = i, resMin = ansMin, resSum = ansSum;
    }
    if (res == -1) cout << "No Solution\n";
    else cout << "G" << res << "\n" << fixed << setprecision(1) << (ldb)resMin << " " << (ldb) resSum / n << "\n";
    return 0;
}

7-14 非常弹的球

高中物理，斜上抛运动，初速度一定是45度角水平移动距离最远。

在起始位置做正交分解

\[m = \frac{w}{1000} \\ E_x=E_y=\frac E 2\\ E_x=\frac 12 m v_x^2 \rightarrow v_x = \sqrt{\frac{E}{m}}\\ t = \frac {E_y}{g}\\ x = v_xt \]

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using ldb = long double;

const int mod = 998244353;
const ldb eps = 1e-9;
const ldb g = 9.8;
#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ldb m, p;
    cin >> m >> p, m /= 100.0, p = (100.0 - p) / 100.0;
    ldb E = 1000;
    ldb v, t, res = 0;
    while (E > eps) {
        v = sqrt(E / m), t = v / g * 2;
        res += v * t, E = E * p;
    }
    cout << fixed << setprecision(3) << res << "\n";
    return 0;
}

7-15 拯救007（升级版）

这里还是利用bfs，然后顺便统计下距离和路径就好

#include <bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;
using i32 = int32_t;
using pii = pair<int, int>;
using ldb = long double;

const int mod = 998244353;
const ldb eps = 1e-9;
const ldb g = 9.8;
const int inf = 1e9;
#define DEBUG(x) cerr <<(#x) << " = " << x  << "\n";
int n, k;

struct Node {
    ldb x, y;

    Node(ldb x = 0, ldb y = 0) : x(x), y(y) {};
} o;

vector<Node> nodes;

ldb dis(Node a, Node b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

ldb dis(int a, int b) {
    return dis(nodes[a], nodes[b]);
}

ldb dis(Node a, int b) {
    return dis(a, nodes[b]);
}

ostream &operator<<(ostream &os, Node x) {
    return os << x.x << " " << x.y;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    cin >> n >> k;
    if (k + 7.5 >= 50) {
        cout << "1\n";
        return 0;
    }
    vi ed, d(n, inf), fa(n, -1), vis(n);
    queue<int> q;
    for (int i = 0, x, y; i < n; i++) {
        cin >> x >> y, nodes.emplace_back(x, y);
        if (max(abs(x), abs(y)) + k >= 50) ed.push_back(i);
        if (dis(o, i) <= 7.5 + k) d[i] = 1, q.push(i);
    }
    for (int x; not q.empty();) {
        x = q.front(), q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int y = 0; y < n; y++) {
            if (vis[y] or d[y] <= d[x] + 1) continue;
            if (dis(x, y) > k) continue;
            d[y] = d[x] + 1, fa[y] = x, q.push(y);
        }
    }
    int res = inf;
    vi resPath;
    for (auto i: ed) {
        if (d[i] > res or d[i] == inf) continue;
        vi path;
        for (int x = i; x != -1; x = fa[x]) path.push_back(x);
        reverse(path.begin(), path.end());
        if (d[i] < res) res = d[i], resPath = path;
        else if (dis(o, path[0]) < dis(o, resPath[0])) resPath = path;
    }
    if (res == inf) cout << "0\n", exit(0);
    cout << res + 1 << "\n";
    for (auto i: resPath) cout << nodes[i] << "\n";
    return 0;
}

标签：ldb,winter,int,SMU,back,long,2024,using,define
From： https://www.cnblogs.com/PHarr/p/17990419

相关文章

  • 2024年可以提高工作效率的待办事项提醒软件
    对于上班族来说，追求升职加薪始终是一个不断努力的目标，而提升工作效率则成为必备的一环。在繁忙的工作生活中，一个可靠的待办事项提醒软件就成了事业成功的得力助手。那么2024年口碑很好的待办事项提醒软件是哪个呢？在2024年，备受好评的待办事项提醒软件中，敬业签成为许多上班族的选择......
  • 20240126打卡——《构建之法》第5~8章
    第五章团队和流程5.2软件团队的模式主治医师模式、明星模式、社区模式、业余剧团模式、秘密团队、特工团队、交响乐团模式、爵士乐模式、功能团队模式、官僚模式5.3开发流程①写了再改模式②瀑布模型（WaterfallModel）是一个项目开发架构，开发过程是通过设计一系列阶段顺序......
  • P10083 [GDKOI2024 提高组] 不休陀螺
    前置题目：石头剪刀布大赛很经典的问题，可以参考一个比这个简单容易想的*2500的做法。先想判定条件再考虑怎么计数。因为少写了一个case导致Au\(\to\)Ag，有点难评。不难想到记录\(c_i=b_i-a_i\)。我们考虑怎样才能无限下去：卡牌打完之后的费用变化是正的，不然会一直......
  • THUWC2024 游记
    已经是老年选手了。Day0从成都坐车到重庆。到酒店就四点多了，打了个车去巴蜀，车上学弟问师傅有什么火锅店推荐，然后司机直接给我们送过去了（？）火速签到，火速试机，然后监考下班了（？）后来又说加班半个小时，登了下OJ写了个A+B就run了。见到了清华学长cxy哥哥！！！晚上把路上口胡的题写......
  • 2024-01-26 yarn证书源过期 ==》 yarn切换的镜像源为https，实际上该链接的证书已过期，应
    如，我给一个项目用yarn装依赖，这时候报错：yarninstallv1.22.21infoNolockfilefound.[1/4]Resolvingpackages...errorError:certificatehasexpiredatTLSSocket.onConnectSecure(node:_tls_wrap:1539:34)atTLSSocket.emit(node:events:513:28)atTLSSocket._fin......
  • Premiere Pro 2024：用故事触动人心，让视频更精彩 mac/win版
    PremierePro2024是一款专业的视频剪辑软件，被广泛应用于电影、电视、广告和网络媒体等领域。它能够帮助用户快速高效地将原始素材转化为精美的视频作品，是视频制作人员的必备工具之一。→→↓↓载PremierePromac/win版 在PremierePro2024中，用户可以导入各种视频、音频和......
  • 2024年值得关注的几款开源或免费的web应用防火墙
    2024年，随着ChatGPT的强势崛起，人工智能必将改造各行业并且成为新一轮经济发展的动力，所以无论私有服务器还是云厂商如Cloudflare、阿里云、腾讯云等都把web应用防火墙（WAF）向智能化方向发展，并闷声发大财。但市场上商业web应用防火墙（WAF）基本都是闭源，开源WAF虽多，但能免费部署的极少，笔者......
  • 2024年1月Java项目开发指南13：登录注册实现
    创建文件，如上图创建好文件后去router.index.js配置路由import{createRouter,createWebHistory}from'vue-router';//定义路由constroutes=[{path:'/',name:'ControlCenter',component:()=>import('../vi......
  • 2024年1月Java项目开发指南12：前后端分离项目跨域问题解决
    创建config文件夹，创建WebConfig文件代码如下（可以直接抄）packagecc.xrilang.serversystem.config;importorg.springframework.context.annotation.Configuration;importorg.springframework.web.servlet.config.annotation.CorsRegistry;importorg.springframework.web.se......
  • 2024年展望
    前言本来这个2024年展望是想跟2023年总结写到一起的。（https://www.cnblogs.com/bee0060/p/17971435）本来都写完了，但是过了几天，想着想着，感觉又有更多的内容想写，还是单独拆出来吧。低头看看自己光阴似箭，岁月如梭，老掉牙的开场白，却写在了第二段。过去我们会憧憬遥远的将来，想着以......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99