首页 > 其他分享 >2023 xjtupc 西交校赛

2023 xjtupc 西交校赛

时间：2023-05-08 11:13:46浏览次数：41  
标签：std int 西交校 cin xjtupc ++ long 2023 using

A

签到，\(O(1)\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

    int n;
    cin >> n;
    cout << (n <= 6 ? "water" : "dry") << '\n';

    return 0;
}

B

签到, \(O(1)\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    i64 a, b;
    cin >> a >> b;
    cout << fixed << setprecision(15) << (1.0 * a) / (1.0 * b) << '\n';

    return 0;
}

C

签到,\(O(1)\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

    i64 x, y, z;
    cin >> x >> y >> z;
    cout << fixed << setprecision(6) << (1.0 / x) * (1.0 / y) * z << '\n';

    return 0;
}

D

没有 \((0,0)\) 就不行，发现每次操作都在一个矩形里，\(O(n)\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }

    bool ok = 0;
    for (int i = 0; i < n; i++) {
        if (x[i] == 0 && y[i] == 0) {
            ok = 1;
        }
    }

    if (!ok) {
        cout << -1 << '\n';
        return 0;
    }

    int xmx = *max_element(x.begin(), x.end());
    int xmn = *min_element(x.begin(), x.end());
    int ymx = *max_element(y.begin(), y.end());
    int ymn = *min_element(y.begin(), y.end());

    int a = xmx - xmn, b = ymx - ymn;
    if (n != (a + 1) * (b + 1)) {
        cout << -1 << '\n';
        return 0;
    }
    cout << a + b << '\n';

    return 0;
}

E

最后必须形成 \(k\) 个大小大于 \(1\) 的环，\(O(n^{2})\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    double b;
    cin >> n >> b;
    vector<vector<double>> a(n, vector<double>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    if (n == 1) {
        cout << "kono jinsei, imi ga nai!\n";
        return;
    }

    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        int k = -1;
        double mx = -1E9;
        for (int j = 0; j < n; j++) {
            if (i == j) {
                continue;
            }
            if (a[i][j] < b) {
                continue;
            }
            if (a[i][j] > mx) {
                mx = a[i][j];
                k = j;
            }
        }
        if (k == -1) {
            cout << "hbxql\n";
            return;
        }
        p[i] = k;
    }

    vector<int> vis(n);
    for (int i = 0; i < n; i++) {
        int j = i;
        int cnt = 0;
        while (!vis[j]) {
            vis[j] = 1;
            j = p[j];
            cnt++;
        }
        if (cnt == 1 || j != i) {
            cout << "hbxql\n";
            return;
        }
    }

    cout << "wish you the best in your search\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

F

同层剩一个且不为 \(2\) 就平衡打破，\(O(3\cdot n-3)\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

    int n;
    cin >> n;

    vector<bitset<3>> a(n);
    for (int i = 0; i < n; i++) {
        a[i].set();
    }

    vector<array<int, 3>> b(3 * n - 3);
    for (int i = 0; i < 3 * n - 3; i++) {
        auto &[u, v, w] = b[i];
        cin >> u >> v >> w;
    }

    for (int i = 0; i < 3 * n - 3; i++) {
        auto &[u, v, w] = b[i];
        u--;
        v--;
        w--;
        a[u][v] = 0;
        if ((a[u].count() == 1 && a[u][1] == 0) || a[u].count() == 0) {
            cout << ((i % 2) ? "Sheauhaw" : "Nocriz") << '\n';
            return 0;
        }
    }
    return 0;
}

G

\(k\) 为边权上界。

输出 \(k,k-1,k-2,\cdots,k-n+2\) 的一条链，\(O(n)\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

    vector<array<int, 3>> ans;
    int k = (n + 1) * (n + 1) / 4;
    for (int i = 1; i <= n - 1; i++) {
        ans.push_back({i, i + 1, k--});
    }
    
    cout << (int)ans.size() << '\n';
    for (auto &[u, v, w] : ans) {
        cout << u << ' ' << v << ' ' << w << '\n';
    }

    return 0;
}

H

找一个字母在每条串中出现次数不同，把他留到最后操作就行，\(O(26\cdot n)\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int vis[1001];

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

    int n;
    cin >> n;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<vector<int>> c(26, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (auto &si : a[i]) {
            c[si - 'a'][i]++;
        }
    }

    int b = -1;
    for (int i = 0; i < 26; i++) {

        int cnt = 0;
        for (int j = 0; j < n; j++) {
            vis[c[i][j]]++;
            if (vis[c[i][j]] == 1) {
                cnt++;
            } else {
                cnt--;
            }
        }

        for (int j = 0; j < n; j++) {
            vis[c[i][j]]--;
        }
        
        if (cnt == n) {
            b = i;
            break;
        }
    }

    if (b == -1) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";
    for (int i = 0; i < 26; i++) {
        if (i != b) {
            cout << char(i + 'a');
        }
    }

    cout << char(b + 'a');

    return 0;
}

J

莫队，\(O(m\cdot \sqrt{m})\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using u32 = unsigned int;

constexpr int N = 2E6;
int cnt[N + 1];

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

    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }

    vector<int> p(n, -1);
    vector<int> pre(n, -1);
    for (int i = 0; i < n; i++) {
        pre[i] = p[a[i]];
        p[a[i]] = i;
    }

    p.assign(n, n);
    vector<int> nex(n, n);
    for (int i = n - 1; i >= 0; i--) {
        nex[i] = p[a[i]];
        p[a[i]] = i;
    }

    struct node {
        int l, r, id;
    };
    vector<node> q(m);
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        q[i] = { l, r, i };
    }

    int bk = sqrt(m);
    sort(q.begin(), q.end(), [&](node a, node b) {
        return ((a.l / bk) ^ (b.l / bk)) ? a.l < b.l : (((a.l / bk) & 1) ? a.r < b.r : a.r > b.r);
    });

    int l = 0, r = -1;
    u32 res = 0;
    u32 Lres = 0, Rres = 0;
    u32 Cnt = 0;

    vector<u32> ans(m);
    auto add = [&](int pos, bool flag) {
        int num = a[pos];
        ++cnt[num];
        if (cnt[num] == 1) {
            ++Cnt;
        }
        if (flag) {
            Rres += pos - max(pre[pos], l - 1);
            res += Rres;
            Lres += Cnt;
        } else {
            Lres += min(r, nex[pos] - 1) - pos + 1;
            res += Lres;
            Rres += Cnt;
        }
    };
    auto del = [&](int pos, bool flag) {
        int num = a[pos];
        if (flag) {
            res -= Rres;
            Lres -= Cnt;
            Rres -= pos - max(pre[pos], l - 1);
        } else {
            res -= Lres;
            Rres -= Cnt;
            Lres -= min(r, nex[pos] - 1) - pos + 1;
        }
        --cnt[num];
        if (cnt[num] == 0) {
            --Cnt;
        }
    };

    for (int i = 0; i < m; i++) {
        auto &[ql, qr, qid] = q[i];
        while (r < qr) add(++r, 1);
        while (l > ql) add(--l, 0);
        while (l < ql) del(l++, 0);
        while (r > qr) del(r--, 1);
        ans[qid] = res;
    }

    for (int i = 0; i < m; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

M

考虑离线，考虑每个点在哪个时间段满足条件，然后差分前缀和，\(O(n)\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 1; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }

    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        g[a[i]].push_back(i);
    }

    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }

    vector<int> k(n);
    for (int i = 0; i < n; i++) {
        k[p[i]] = i;
    }
    vector<int> ans(n);
    function<pair<int, int>(int, int)> dfs = [&](int cur, int pre) {
        vector<pair<int, int>> t;
        for (auto &nex : g[cur]) {
            if (nex != pre) {
                t.push_back(dfs(nex, cur));
            }
        }
        int L = k[cur], R = k[cur];
        for (auto &[u, v] : t) {
            L = min(L, u);
            R = max(R, v);
        }
        ans[L]++;
        if (R < n) {
            ans[R]--;
        }
        return pair(L, R);
    };

    dfs(0, -1);
    for (int i = 1; i < n; i++) {
        ans[i] += ans[i - 1];
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }
    
    return 0;
}

N

两种情况，一开始就执行切换操作，不执行操作的话必须是连续的一段，\(O(n)\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

    vector<int> x(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }

    auto get1 = [&]() {
        i64 res = c;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                res += 1LL * x[i] * (a + b);
                res += a;
                continue;
            } 

            res += 1LL * (x[i] - x[i - 1] + m - 1) % m * (a + b);
            res += a;
        }

        return res;
    };

    i64 inf = 9E18;

    auto get2 = [&]() {
        bool ok = 1;
        for (int i = 1; i < n; i++) {
            if (x[i] != (x[i - 1] + 1) % m) {
                ok = 0;
            }
        }
        if (!ok) {
            return inf;
        }
        return 1LL * x[0] * (a + b) + n * a;
    };

    cout << min(get1(), get2()) << '\n';

    return 0;
}

O

\(n!\)。QAQ

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int P = 19961;

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

    int ans = 1;
    for (int i = 1; i <= n; i++) {
        ans = ans * i;
        ans %= P;
    }

    cout << ans << '\n';
    
    return 0;
}

标签：std,int,西交校,cin,xjtupc,++,long,2023,using
From： https://www.cnblogs.com/kiddingma/p/17381093.html

相关文章

  • 【2023-05-03】连岳摘抄
    23:59人们若是一心一意地做某一件事，总是会碰到偶然的机会的。                                                 ——巴尔扎克真正聪明的孩子，知道参加工作后的十多年......
  • 【2023-05-02】连岳摘抄
    23:59不要简单地相信直觉判断——无论是你自己的还是他人的——但也不要完全抛开它。                                                 ——丹尼尔·卡尼曼从小聪明......
  • 产品原型21-20230507
            ......
  • 2023前端面试题
    1.什么是重绘和回流，有哪些措施可以避免回流，从而提高页面性能重绘（repaint）和回流（reflow）是浏览器渲染页面时的两个重要的步骤。重绘是指当一个元素的样式（如颜色、背景等）发生变化，但没有影响其布局（如位置、大小等）时，浏览器会将这个元素的新样式重新画到页面上。回流则是指当一个元素......
  • [20230508]crack oracle执行文件.txt
    [20230508]crackoracle执行文件.txt--//昨天看了链接:https://www.xifenfei.com/2023/04/ora-07445-kglsget.html--//提到open阶段执行如下:-----CurrentSQLStatementforthissession(sql_id=gtf6tgc2ycgxx)-----selectcount(*)fromXDB.XDB$SCHEMAswheres.xmldata.s......
  • PKUSC2023
    还是写一下，发现我都忘记去年的分数了，所以不写游记的话我肯定明年又忘掉了。面到了好几个以前没见过的群友，lgdswnmonstersqwq云浅知处breezeender都非常猛啊。拍了个照。PKU的食堂很多，感觉挺便宜，味道还行吧。Day1Day1看到这个串串很兴奋啊，结果搞了一个逆天假做法，大概是......
  • PKUSC2023 邮寄
    $\text{Day-1}$\(5.5\)提前从一中出发，集合时不出所料的又是所有人等ysu。高铁上很无聊，ry不一起来打florr，在高铁上打了一会就不想打了。然后就是漫长的刷视频时间。下午\(13:30\)下车，去汉庭酒店，和ry一间房。下午去圆明园参观。脚都要断了。晚上wfy来打跑得快，输......
  • THUSC2023 游记
    THUSC2023游记Day1试机，试机题是A+B，一个交互，一个提答。提答是几何，瞬间不想认真做了。键盘的下键是坏的，按下去弹不起来，左键也是，但没下键那么严重。喊工作人员换键盘，工作人员说明天作为随机打乱，不管了。交互写了个暴力，发现分数给错了，除以了100（试了下各种错误，比如越界，sqrt(-......
  • 录屏界鼻祖Camtasia 2023中文版功能介绍/下载安装激活教程
    随着网络科技的迅速发展，所以对于电脑的使用率也就越来越高了！然而，也可能跟这有关系，目前各种类型的软件层出不穷，当然也就包括了电脑录屏软件。这给我们造成了一些困难，究竟哪一款适合自己呢？Camtasia2023是TechSmith公司出品的一款屏幕录像和编辑的软件，可轻松录制和分享高质量的截屏视......
  • PKUSC2023游记
    旅游，不慌.jpgDay0人生中第一次来北京.jpg下午在北大外面走了大半圈，感觉很壮观啊！不过校园这么大，想必明后天要迷路了（不是然后回酒店摆。想面积但是社恐又犯了/ngDay1上午开幕式+试机，试机题只有一题，据说去年也是这题。面到了Nz/tyt然后试机完直接被教练带去家园食堂了？？食......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99