首页 > 其他分享 >2022牛客国庆集训派对day1

2022牛客国庆集训派对day1

时间:2022-10-12 15:36:08浏览次数:36  
标签:pre int cin stk 牛客 second mp 2022 day1

B

题意:

给定一个01字符串,你需要找到最长的一个子串和最长的一个子序列,分别使得其中01的个数相同。

做法:

子序列很好算 2×min(cnt0,cnt1)

子串可以考虑前缀和

将0与1的个数差前缀和 每次询问当前的前缀和x 如果之前出现前缀和为y 使得x+y=0即成立

最后取个最大值就好

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    s = " " + s;
    int ans = 0, cnt = 0;
    map<int,int> mp;
    mp[0] = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '1') cnt++;
        else cnt--;
        if(mp.count(cnt)) ans = max(ans, i - mp[cnt]);
        else mp[cnt] = i;
    }
    cout << ans << " ";
    int cnt1 = 0, cnt0 = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '0') cnt0++;
        else cnt1++;
    }
    cout << min(cnt1, cnt0) * 2 << endl;
}

很神奇的做法:

假设开始线是水平的 然后我们可以找到第一条使得过线和线上方的点大于总点数的线

然后使得这条线倾斜一丢丢就好

map<int, vector<int>>mp;
int n;
void slove() {
    cin >> n;
    mp.clear();
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        mp[y].push_back(x);
    }
    int pre = 0;
    for (auto p : mp) {
        sort(p.second.begin(), p.second.end());
        pre += p.second.size();
        if (pre >= n / 2) {
            pre -= p.second.size();
            for (int x : p.second) {
                pre++;
                if (pre == n / 2) {//找到中间点
                    //x   y 
                    int y = p.first;
                    cout << int(x + 1e8) + 1<<" " << y - 1 << " " << int(x - 1e8) <<" " << y + 1 << endl;
                    break;
                }
            }
            break;
        }
    }    
}

G

题意:

给你n个数,问你有多少个长度不小于2的连续子序列,使得其中最大元素不大于所有元素和的一半。

做法

还是用到容斥原理

int a[N], n, pre[N];
int sum(int L, int R) {
    if (L > R)return 0;
    return pre[R] - pre[L - 1];
}
int LL[N], RR[N];
void slove() {
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++)pre[i] = pre[i - 1] + a[i];
    a[0] = 1e18, a[n + 1] = 1e18;
    stack<int>stk; stk.push(0);
    for (int i = 1; i <= n; i++) {
        while (a[stk.top()] < a[i])stk.pop();
        LL[i] = stk.top();
        stk.push(i);
    }
    while (stk.size())stk.pop();
    stk.push(n + 1);
    for (int i = n; i >= 1; i--) {
        while (a[stk.top()] < a[i])stk.pop();
        RR[i] = stk.top();
        stk.push(i);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int L_len = i - LL[i], R_len = RR[i] - i;
        if (L_len <= R_len) {
            int mx = a[i];
            for (int j = LL[i] + 1; j <= i; j++) {
                auto k = lower_bound(pre + i, pre + RR[i], 2 * mx + pre[j - 1]) - pre;
                ans += (k - i);
            }
        }
        else {
            int mx = a[i];
            for (int j = i; j < RR[i]; j++) {
                auto k = lower_bound(pre + LL[i], pre + i, pre[j] - 2 * mx + 1) - pre;
                ans += i - k;
            }
        }
    }
    cout << n * (n + 1) / 2 - ans << endl;
}

标签:pre,int,cin,stk,牛客,second,mp,2022,day1
From: https://www.cnblogs.com/wzxbeliever/p/16784648.html

相关文章

  • 活动预告 | Feature Store Summit 2022
    10月12日北京时间上午7:05-7:15 (10.1116:05-16:15GMT-7),OpenMLDBPMC、第四范式系统架构师卢冕,将在FeatureStoreSummit2022活动中为大家带来议题为《OpenMLDB:......
  • 【算法训练营day1】LeetCode704. 二分查找 LeetCode27. 移除元素
    【算法训练营day1】LeetCode704.二分查找LeetCode27.移除元素LeetCode704.二分查找题目链接:704.二分查找初次尝试看到题目标题是二分查找,所以尝试使用二分查找的......
  • 数字政务发展得如何?来看看2022年各地移动政务服务新变化
    2021年11月,国务院办公厅印发《全国一体化政务服务平台移动端建设指南》(以下简称《建设指南》),就进一步加强政务服务平台移动端标准化、规范化建设和互联互通,创新服务方式、增......
  • 2022上海赛(A,E,H)
    Dashboard-2022ShanghaiCollegiateProgrammingContest-CodeforcesA.AnotherA+BProblem题意:给出一个表达式xx+xx=xx的格式,然后每个位置有三种字母表示三种状......
  • 2022 CSP-S 游记
    死去的我又回来了因为某浏览器使得我写不了博客(一直时间错误)今年打提高((普及都没打利索的我又来霍霍提高了今年不拿奖我可能就AFO了……一群高二学长学姐中夹杂的一名......
  • 【2022-10-05】回趟老家
    20:00即使生活还相当艰难,爱情还隐隐约约,学习还道路方长,社会还明明暗暗,人间还有许多不平,你也要投入,你也要尽力尽情尽兴尽一切可能,努力争取一切可以争取到也应该争取到的,以......
  • 【2022-10-04】连岳摘抄
    23:59我觉得个人的态度最好的一方面了解到自己的渺小,一方面尽量地希望这个渺小的生命还是有点意义。                     ......
  • [20221012]TNS-12543 TNSdestination host unreachable.txt
    [20221012]TNS-12543TNSdestinationhostunreachable.txt--//今天尝试本机连接测试库,出现如下问题.sqlplus报ORA-12543:TNS:destinationhostunreachable错误.R:\>tns......
  • 即用型UI组件库Kendo UI R3 2022,让应用主题开发更容易
    KendoUI是带有 jQuery、Angular、React和Vue库的JavaScriptUI组件的最终集合,无论选择哪种JavaScript框架,都可以快速构建高性能响应式Web应用程序。通过可自定义的UI组件......
  • 2022/10/12线程核心概念
    线程核心概念线程就是独立的执行路径。在程序运行时,即使自己没有创建线程,后台也会有多个线程,如主线程,gc线程。main()称之为主线程,为系统的入口,用于执行整个程序。......