首页 > 其他分享 >暑假牛客多校第九场 2023-8-15(D、I)

暑假牛客多校第九场 2023-8-15(D、I)

时间:2023-08-17 18:00:24浏览次数:48  
标签:typedef 15 ve int 多校 long 牛客 区间 include

未补完


D. Non-Puzzle: Error Permutation


算法:差分

做法:
      考虑题目的数据,我们的做法可以先枚举出不合法的区间数,然后由区间总数减去不合法区间数。我们首先确定一个数,令这个数就是包含这个数的一段区间的不和法值,即这个数是第 \(i\) 小的数。一开始我们使这段区间大小为 \(1\),里面的数即为我们要确定的数。随后右边界向右移,找到第一个使这个区间中我们所确定的数是不和法的位置,然后右边界继续右移,直到使得这个区间中我们所确定的数是最后一个不合法的,这段不合法区间都要加起来。接着左边界左移,那么我们所确定的数变成了第 \(i - l + 1\) 个数,但是我们所确定的数不一定是第 \(i - l + 1\) 小的数,所以要继续右移边界,而且右移的边界是和上一次右边界结束的位置是一样的,因为上一次右边界确定的是我们所确定的数是第 \(i - (l - 1) + 1\),现在变成了这个数必须是第 \(i - l + 1\) 小,那么右边界就必须向右移来找比我们确定的数还要小的数使我们目前的数的排名加一(如果新加的左边界的数比我们确定的数大的话,我们就需要右移边界找比我们确定的数更小的数来使排名加一。如果新加的数比我们所确定的数还要小,那么我们所确定的数就是第 \(i - l + 1\) 小)。我们算不合法区间可能有重复,所以用差分维护。

code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define x first
#define y second
#define endl '\n'
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
typedef pair<int, string> PIS;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int N = 5010, M = 100100, INF = 0x3f3f3f3f, mod = 998244353, TIME = 50001;

int n;
int w[N];
int g[N][N];

void add(int p, int rst, int red)
{
    g[p][rst] += 1, g[p][red + 1] -= 1;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> w[i];
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            g[i][j] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int l = i, rst = i, red = i, cnt = 0; l >= 1; l--)
        {
            if (w[l] <= w[i])cnt++;
            while (cnt < i - l + 1 && red < n)
            {
                red++,  rst = red;
                if(w[red] < w[i])cnt++;
            }
            if (cnt == i - l + 1)
            {
                while (red < n && w[red + 1] > w[i])red++;
                add(l, rst, red);
            }
        }
    }

    LL ans = 0;
    for(int i = 1; i <= n ; i++)
        for (int j = 1; j <= n; j++)
        {
            g[i][j] += g[i][j - 1];
            if (i <= j && !g[i][j])ans++;
        }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

 

I. Non-Puzzle: Segment Pair


算法:排序

做法:我们定义一个数组 \(b\),\(b[0]\) 表示未覆盖这个点的区间个数,\(b[1]\) 表示一对区间只有一个区间覆盖这个点的区间个数,\(b[2]\) 表示一对区间两者都覆盖这个点的区间个数。我们再定义一个数组 \(a\),\(a[i]\) 表示编号为 \(i\) 的一对区间在数组 \(b\) 中的状态,那么 \(a[i]\) 的值就有0,1,2三种情况。由于我们考虑的是每个点的区间覆盖情况,因此必定有重复的情况出现,那么我们就按照一遇到区间的左边界我们就计算这个区间加入后的区间覆盖方案数。由于每一次都是在区间一加入后就计算方案数,这是不重不漏的。另外,每次遍历区间时我们会删去之前区间在数组 \(b\) 的状态,更新这个区间的状态和在数组 \(b\) 的状态。(看代码就懂了)

code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define x first
#define y second
#define endl '\n'
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int N = 500100, M = 100100, INF = 0x3f3f3f3f, mod = 1e9 + 7;

int n;
int p[N], a[N], b[4];

struct Node
{
    int x, v, id;
};

bool cmp(Node i, Node j)
{
    if (i.x != j.x)return i.x < j.x;
    return i.v < j.v;
}

void solve()
{
    cin >> n;
    p[0] = 1, b[0] = n;
    vector<Node> ve;
    for (int i = 1; i <= n; i++)p[i] = (LL)p[i - 1] * 2 % mod;
    for (int i = 0; i < n; i++)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        ve.push_back({ l1, 1, i });
        ve.push_back({ r1 + 1, -1, i });
        ve.push_back({ l2, 1, i });
        ve.push_back({ r2 + 1, -1, i });
    }

    sort(ve.begin(), ve.end(), cmp);
    LL ans = 0;
    for (auto t : ve)
    {
        b[a[t.id]]--;
        a[t.id] += t.v;
        if (t.v == 1 && b[0] == 0)
            ans = (ans + p[b[2]]) % mod;
        b[a[t.id]]++;
    }

    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

标签:typedef,15,ve,int,多校,long,牛客,区间,include
From: https://www.cnblogs.com/dkdklcx/p/17630887.html

相关文章

  • 15种实时uv实现方案系列(附源码)之一:Flink基于set实时uv统计
    UVStatMultiPlans(GitHub)项目持续收集各种高性能实时uv实现方案并对各种实现方案的优缺点进行对比分析!需求描述统计每分钟用户每个页面的uv访问量。Kafka数据格式{"userId":"c61b801e-22e7-4238-8f67-90968a40f2a7","page":"page_1","behaviorTime":1692247408129}{"userId......
  • CF1545B题解
    CF1545B题解题目描述你有一个长为\(n\)的棋盘,这个棋盘上有一些棋子,你可以进行如下操作:如果第\(i+2\)个位置是空的,且第\(i+1\)个位置非空,则可以将第\(i\)个位置的棋子挪到第\(i+2\)个位置(\(i+2\leqn\)).如果第\(i-2\)个位置是空的,且第\(i-1......
  • Apache HTTPd换行解析漏洞复现CVE-2017-15715
    ApacheHTTPd换行解析漏洞复现CVE-2017-15715漏洞利用漏洞利用条件Apache:2.4.0~2.4.29实际存到后端时的文件名可控漏洞利用方式bp中更改存放到后端的文件名假设原文件名为"evil.php"文件存放在网站根目录下evil.php的内容为:<?php@eval($_REQUEST[1]);?>操作:......
  • Linux 操作必备 150 个命令,速度收藏~
    nux命令是对Linux系统进行管理的命令。对于Linux系统来说,无论是中央处理器、内存、磁盘驱动器、键盘、鼠标,还是用户等都是文件,Linux系统管理的命令是它正常运行的核心,与之前的DOS命令类似。Linux命令功能说明线上查询及帮助命令(2个)man查看命令帮助,命令的词典,更复杂的......
  • 牛客多校赛第9场G Game
    黑板上有一些数字,Alice和Bob轮流操作,每次操作可以选择黑板上的两个数(两个数可以相同),然后在黑板上写下这两个数的异或。谁先写出k谁赢。首先重复的数字是没有用的,进而可以推出除整局游戏的第一步之外,都可以选择保持当前的局面不变.比如如果一个玩家面对的是一个必输的局面,他就......
  • 杭电多校赛第9场1002 Shortest path
    给定一个数字n,每次可以选择一项。令n=n-1令n=n/2,ifn%2==0令n=n/3,ifn%3==0求最少需要多少步可以让其变成1.减1操作可以看作是为了除法做准备,连续超过两次减1再除2是不优的,连续超过三次减1再除2也是不优的。可以根据下一步除2还是除3来分出两个分......
  • 牛客多校赛第9场D Error Permutaition
    给定一个长度为n的排列,计算满足条件的子区间的个数。对于子区间\([l,r]\)要求任意区间第k小,不在区间的第k个位置上。\(n<=5000\)从每个值入手,设这个值为先,寻找对于x来讲是不合法的区间,也就是x在这个区间中是第k小,并且在区间的第k个位置上。1.如果固定区间左端点l,那么右端......
  • 杭电23多校第九场Capoo on tree(二分+树链剖分+可持久化线段树)
    2023HDU多校9__Capooontree(二分+树链剖分+可持久化线段树)题目链接Solution\(Hint1\)考虑如何进行对某一相同点权的所有点进行点权\(+1\)操作,如果我们建立权值线段树,那只需要将权值为\(x\)的点并入权值\(x+1\)即可,但是这样就算我们建立以节点编号为版本的可持久化线段树,也是......
  • 15 模版方法模式 -- go语言设计模式
    15模版方法模式--go语言设计模式模板方法模式定义了一个算法的步骤,并允许子类别为一个或多个步骤提供其实践方式。让子类别在不改变算法架构的情况下,重新定义算法中的某些步骤模版方法模式的实现代码packagemainimport"fmt"//抽象类,制作饮料,包裹一个模板的全部实现......
  • ARC 157 F Sol
    嫌弃讲题人的我,准备好好写一篇题解。linktoproblem观察数据范围:\(1\leN\le50\)。如果是\(20\),想到\(2^{20}\);如果是\(40\),想到\(2^{40\div2}\);若果是\(50\)呢?\(2^{25}\)有点大,于是想到\(2^{50\div3}\)。但是如何去凑?Hint\(N\)\(S\)\(T\)\(res\)\(6......