首页 > 其他分享 >The 3rd Universal Cup. Stage 1: St. Petersburg Finalized Standings

The 3rd Universal Cup. Stage 1: St. Petersburg Finalized Standings

时间:2024-08-21 15:07:07浏览次数:10  
标签:Standings cur 3rd Cup int cnt len tag using

C. Cherry Picking

这道题用了一个类似 ODT 的题思路。

首先我们可以想到是,如果删除某些选手,只有可能会导致区间的合并,不会导致区间的分裂。所以我们可以枚举一下$x $的值,然后找到需要删除的点。用set​维护相同且相邻区间,找到删除点所在的区间后,给区间长度减一。如果区间长度为空后,就将该区间两侧的区间进行合并。同时在维护一下当前所有为 1 的区间长度。

#include <bits/stdc++.h>

using namespace std;


using ldb = long double;
using ll = long long;

using vi = vector<int>;


const int inf = 1e9;

struct Seg {
    int l, r, tag;
    mutable int len;

    Seg(int l = 0, int r = 0, int tag = 0, int len = 0)
            : l(l), r(r), tag(tag), len(len) {};

    bool operator<(const Seg &b) const {
        return l < b.l;
    }
};


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

    int n, k;
    cin >> n >> k;
    vector<array<int, 3>> a(n);// {val, idx, tag}
    for (int i = 0; i < n; i++)
        cin >> a[i][0], a[i][1] = i;

    string s;
    cin >> s;
    for (int i = 0; i < n; i++)
        a[i][2] = (s[i] == '1');


    set<Seg> seg;
    multiset<int> cnt;

    for (int i = 1, l = 0, tag = a[l][2]; i <= n; i++) {
        if (i == n) {
            seg.emplace(l, i - 1, tag, i - l);
            if (tag == 1) cnt.insert(i - l);
        } else if (a[i][2] != tag) {
            seg.emplace(l, i - 1, tag, i - l);
            if (tag == 1) cnt.insert(i - l);
            l = i, tag = a[l][2];
        }
    }

    sort(a.begin(), a.end());

    int res = 0;
    for (int x = 1, i = 0; x <= 2e5; x++) {
        if (cnt.empty() or seg.empty()) break;
        while (i < n and a[i][0] < x) {
            auto [val, idx, tag] = a[i];
            auto it = prev(seg.upper_bound(Seg(idx)));
            assert(it->l <= idx and idx <= it->r and it->tag == tag);
            if (tag == 1)
                cnt.erase(cnt.find(it->len));
            it->len--;
            if (tag == 1 and it->len > 0)
                cnt.insert(it->len);

            if (it->len == 0) {
                Seg cur(inf, -inf, -1, 0);
                if (it != seg.begin()) {
                    auto L = prev(it);
                    cur.l = min(cur.l, L->l);
                    cur.r = max(cur.r, L->r);
                    cur.len += L->len;
                    cur.tag = L->tag;

                    if (L->tag == 1) cnt.erase(cnt.find(L->len));
                    seg.erase(L);
                }
                if (next(it) != seg.end()) {
                    auto R = next(it);
                    cur.l = min(cur.l, R->l);
                    cur.r = max(cur.r, R->r);
                    cur.len += R->len;
                    cur.tag = R->tag;

                    if (R->tag == 1) cnt.erase(cnt.find(R->len));
                    seg.erase(R);
                }
                seg.erase(it);
                if (cur.tag != -1) {
                    seg.insert(cur);
                    if (cur.tag == 1) cnt.insert(cur.len);
                }
            }
            i++;
        }

        if (not cnt.empty() and *cnt.rbegin() >= k)
            res = max(res, x);
    }

    cout << res << "\n";

    return 0;
}

H. Page on vdome.com

签到题

#include <bits/stdc++.h>

using namespace std;

#define ll long long

using vi = vector<int>;


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

	int n;
	cin >> n;
	if(n < 10) cout << n + 1;
	else cout << 10;
	return 0;
}

K. Tasks and Bugs

简单模拟题

#include <bits/stdc++.h>

using namespace std;


using ldb = long double;
using ll = long long;

using vi = vector<int>;


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

    string s;
    map<int, vector<int>> e;

    while (getline(cin, s)) {
        s += "@";
        vector<int> a;
        int cnt = 0, f = 0;
        for (auto i: s) {
            if (isdigit(i)) {
                f = 1;
                cnt = cnt * 10 + i - '0';
            } else {
                if (f) a.push_back(cnt);
                cnt = f = 0;
            }
        }
        for (int i = 1; i < a.size(); i++)
            e[a[i]].push_back(a.front());
    }
  
    for (auto [id, v]: e) {
        cout << "CS-" << id << ": ";
        for (int f = 0; auto y: v) {
            if (f) cout << ", ";
            cout << "CS-" << y, f = 1;
        }
        cout << "\n";
    }
    return 0;
}

O. Mysterious Sequence

首先通过二维 dp,求出$X_n = a X_1 + b X_2 \(中的\)a,b\(然后解方程求出\)X_2 $,然后再重新递推出整个序列。

#include <bits/stdc++.h>

using namespace std;


using ldb = long double;
using ll = long long;
using vi = vector<int>;


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

	cout << fixed << setprecision(20);

	ldb A, B;
	cin >> A >> B;

	int n;
	cin >> n;

	vector<ldb> a(n + 1);
	cin >> a[1] >> a[n];


	if(n == 2){
		for(int i = 1; i <= n; i ++)
			cout  << a[i] << "\n";
		return 0;
	}

	vector<array<ldb,2>> k(n + 1);
	k[1] = {1, 0};
	k[2] = {0, 1};
	for(int i = 3; i <= n; i ++){
		k[i][0] = k[i - 1][0] * A + k[i - 2][0] * B;
		k[i][1] = k[i - 1][1] * A + k[i - 2][1] * B;
	}

	a[2] = (a[n] - k[n][0] * a[1]) / k[n][1];

	for(int i = 3; i < n ; i ++)
		a[i] = A * a[i - 1] + B * a[i - 2];

	for(int i = 1; i <= n; i ++)
		cout << a[i] << "\n";
	return 0;
}

标签:Standings,cur,3rd,Cup,int,cnt,len,tag,using
From: https://www.cnblogs.com/PHarr/p/18371649

相关文章

  • 题解:CF1032B Personalized Cup
    本题题意给一个字符串,将其分成等长度的字符串,但是分的行数不能超过\(5\)行,每行的长度不得超过\(20\)。如果无法等分的,则用*来补足长度。输出在行数最小的前提下,列数最少的一种方案。思路由于字符串范围最多也就\(20\times5\),直接分类讨论即可。ACcode#include<bits/st......
  • 【WCET 户厕】2nd Qingbai Cup
    T1考虑二分,然后怎么check。我们随便选一个点开始BFS地移动,如果以它为左上角的正方形可以覆盖整个局面中的所有空格子,那么整个边长就是可行的。容易证明随便选一个点开始是正确的。T2抽象题。看到数据范围容易有一个状压状物,然而\(2^n\)怎么都去不掉。根据某年NOI或W......
  • 第三届机械、航天技术与材料应用国际学术会议 (MATMA 2024) 2024 3rd International C
    文章目录一、会议详情二、重要信息三、大会简介四、主讲嘉宾五、征稿主题六、咨询一、会议详情二、重要信息末轮征稿:2024年8月26日23:59,不再延期!收录检索:EI(核心),Scopus均稳定检索会议官网:https://ais.cn/u/vEbMBz会议地点:内蒙古工业大学新城校区三、......
  • XXI Open Cup, Grand Prix of Tokyo
    Preface神秘沟槽Counting大赛,十个题全是模\(998244353\)有点逆天了开场发现G是去年暑假前集训的原,然后坐牢了大半天看榜发现包大爷切了B,然后跟了一手接下来慢慢把所有题都看了一遍,每个题都属于有点思路但不多中间和祁神把诈骗题I玩出来了,然后对着H硬套「PKUWC2018......
  • SMU Summer 2024 div2 3rd
    文章目录TheThirdWeek一、前言二、算法1.KMP算法2.线性DP<1>(最长上升子序列II)3.背包DP<1>(「木」迷雾森林)4.其它<1>(Ubiquity)三、总结TheThirdWeek战略上藐视敌人,战术上重视敌人————毛泽东主席一、前言周六打了场cf,只过了俩题而且比较慢,给我的id上......
  • 【待做】【AI+安全】数据集:KDD CUP99
    https://mp.weixin.qq.com/s?__biz=Mzg5MTM5ODU2Mg==&mid=2247494059&idx=1&sn=fdbfa26d8a3fc53596e5c8fe061f22a6&chksm=cfcf5966f8b8d0709e0992983b7ea9ebfc4f0331758b732394515e75eda99f82cd4829128144&scene=21#wechat_redirect[当人工智能遇上安全]6.基于机器学习......
  • Python数据预处理+正态性检验+异常值处理+Q-Q图-K-S检验+相关性分析(2024MathorCup A题
    #数据预处理#正态性检验、Q-Q图、箱线图、直方图、相关性分析#Q-Q图importnumpyasnpimportpandasaspdimportmatplotlib.pyplotaspltfromscipy.statsimportnormfromscipy.statsimportprobplota=pd.read_excel('附件1:小区基本信息.xlsx',engine='openpyxl'......
  • 【待做】【AI+安全】数据集:KDD CUP 99
    KDDCUP99KDDCUP99dataset是KDD竞赛在1999年举行时采用的数据集。1998年美国国防部高级规划署(DARPA)在MIT林肯实验室进行了一项入侵检测评估项目收集而来的数据,其竞争任务是建立一个网络入侵检测器,这是一种能够区分称为入侵或攻击的“不良”连接和“良好”的正常连接的预测模......
  • Picovoice Porcupine 自定义唤醒词不起作用,文件路径问题
    我在picovoice网站上训练了自定义唤醒词并下载了ZIP文件。然后我将其解压并复制文件路径。这是我的代码:importstructimportpyaudioimportpvporcupineporcupine=Nonepaud=Noneaudio_stream=Nonetry:porcupine=pvporcupine.create(access_key="blahblah",keyw......
  • Sleeping Cup #1 Editorials
    A-Sleepingpairs很明显,能删的要立刻删,它们会阻碍交换。一共要删除\(n\)列,这需要\(n\)点体力。由于删除时总要保证两列字符一致,故两列X的个数要相等。设两列X的个数原来相差\(b\)个,则交换一行XZ(或ZX)会使得某一列减少一个X,而另一列增加一个X,差值减少\(2\),故这......