首页 > 其他分享 >CSP模拟 21

CSP模拟 21

时间:2023-08-14 21:24:31浏览次数:31  
标签:right 21 int long dp 交点 CSP 模拟 Mod

Get On Your Way.

木偶戏 你看

台上台下 角色跟着反转

大红的衣衫 配上滑稽妆扮

一唱一和 多少人在围观

乌鸦跟着鼓掌 笑风水轮流转

两语三言 拉扯我的五感

衣带要系紧 不得有碍观瞻

木偶提线 怪事又成一桩美谈

A. [CEOI2016] kangaroo

神奇的 DP,从未涉及的领域。

观察题意,一个合法序列中,一个数两边的两个数要么都比它大,要么都比它小。

我们可以发现,合法的跳的顺序一定是这样的:

我们把每一个符合这种形式的片段看作一个块。

对于这样一个块来说,有三种操作:

  1. 将某个块的元素加一
  2. 添加一个新的块
  3. 将两个相邻的块合并

我们记 \(dp_{i,j}\) 表示放了 \(i\) 个元素,形成了 \(j\) 个块的方案数。

那么考虑转移,即上面对于块的三种操作。

1. 将某个块的元素加一

块的数量没有发生变化,放的元素多了 \(1\) 个,对于 \(j\) 个块,可以任选其中一个块放入,有

\[dp_{i,j}=j \times dp_{i-1,j} \]

考虑加元素之前的值一定是小于该元素的,以后加入的值一定是大于该元素的。

2. 添加一个新的块

原先有 \(j-1\) 个块,即有 \(j\) 个空,选择任意一个空插入块。

\[dp_{i,j}=j \times dp_{i-1,j-1} \]

3. 合并两个相邻的块

与添加新块的方式类似。考虑不可能选择第 \(0\) 个块和第 \(n + 1\) 个块与其他块进行合并,所以我们仍然只有 \(j\) 个空。

\[dp_{i,j}=j\times dp_{i-1,j+1} \]

添加的用于合并的块的值一定是大于两边的值的。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 2050;
const int Mod = 1e9 + 7;

int n,s,t;

long long dp[N][N];

int main() {
    cin >> n >> s >> t;
    dp[1][1] = 1;

    for(int i = 2;i <= n; i++) {
        for(int j = 1;j <= i; j++) {
            if(i == s || i == t)
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] + dp[i - 1][j]) % Mod;
            else {
                dp[i][j] = (dp[i - 1][j - 1] * (j - (i > s) - (i > t)) + dp[i - 1][j + 1] * j) % Mod;
            }
        }
    }
    cout << dp[n][1] << "\n";
    return 0;
}

B. [JOI 2023 Final] Advertisement 2

题目大意

在一个数轴上有 \(n\) 个人,第 \(i\) 个人位于坐标 \(X_i\),权值为 \(E_i\)。我们要送给一些人书,当 \(i\) 收到了一本书,那么对于所有 \(j\),满足 \(\left | X_i-X_j \right | \le E_i-E_j\),那么 \(j\) 会去买一本书。问最少送几个人书会使得所有人都有一本书。

思路

我们可以考虑把题目中给出的限制转化一下。

\[\begin{aligned} \left | X_i-X_j \right | \le E_i-E_j & \Longleftrightarrow X_i-X_j\leq E_i - E_j \land X_j - X_i \leq E_i-E_j \\ & \Longleftrightarrow E_j-X_j\leq E_i - X_i \land X_j+E_j\leq X_i+E_i \end{aligned} \]

那么我们考虑把每个居民转化成平面直角坐标系中的一个点。

我们用 \(E-X\) 当作横坐标,\(E+X\) 当作纵坐标,显然我们可以发现,从原点到这个居民所在点形成的矩形是该居民影响的范围。

我们还可以发现,从左到右看,选取的点的纵坐标是单调递减的,因为如果某个点右上方还有一个点,我们会直接选择那个点而放弃当前点。

按照纵坐标从上往下扫,如果一个点的横坐标大于目前扫过的最大的横坐标时,会对答案产生贡献。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 705000;

int n;

long long ans = 0;

struct Resident{
    long long x,y;
}t[N];

bool cmp(Resident a,Resident b) {
    if(a.y == b.y)
        return a.x > b.x;
    return a.y > b.y;
}

int main() {
    cin >> n;

    long long X,E;
    for(int i = 1;i <= n; i++) {
        cin >> X >> E;

        t[i].x = E - X;
        t[i].y = E + X;
    }

    sort(t + 1,t + n + 1,cmp);

    long long Max = LLONG_MIN >> 4;
    for(int i = 1;i <= n; i++) {
        if(t[i].x > Max)
            ans ++;
        
        Max = max(Max,t[i].x);
    }

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

C. Your

一道合成题。

第一问

对于一个 \(n\) 个顶点的凸多边形,它的任何三条对角线都不会交于一点,它的对角线交点的个数是 \(\dfrac{n(n-1)(n-2)(n-3)}{24}\)。

考虑以下几点:

  1. 每两个顶点连一条对角线;
  2. 每两条对角线有一个顶点;
  3. 所以每一个交点对应 \(4\) 个顶点。

那么我们就可以把问题转化为:

从 \(n\) 个顶点中选出 \(4\) 个的方案数。

所以答案为 \({n \choose 4}\),可以转化为 \(\dfrac{n(n-1)(n-2)(n-3)}{24}\)。

第二问

欧拉公式:令 \(G\) 为一个连通的平面图,其中 \(V\) 是顶点的集合,\(E\) 是边的集合,并令 \(F\) 为面的集合,那么有 \(\left | V \right | - \left | E \right |+\left | F \right |=2\)。这里的 \(\left | F \right |\) 包含所有边之外的无穷平面。

明显这不是一个平面图,我们需要将其转化。

转化成平面图后,考虑第二问让我们求的区域数实际上就是除去无穷平面外的平面数,那么问题就转化为求边数和点数。

我们将相交的线段全部拆开,把交点处转化成新的点。

假如原本一条线上有 \(3\) 个交点,现在就把这 \(3\) 个交点变成 \(3\) 个点,一条线段被分割成了 \(4\) 条短线段。

那么转化后的点数包含圆上的点和圆内的交点,即 \(n+{n \choose 4}\)。

考虑转化后的边数,原来的 \({n \choose 2} + 2{n \choose 4} + n\) 个交点每个交点会让边的个数增加 \(2\)。

最后用欧拉公式计算一下,去掉无穷平面,答案为 \({n \choose 4} + {n \choose 2} + 1\)。

Code

#include <bits/stdc++.h>

using namespace std;

const long long Mod = 998244353;

int n;

long long ans1,ans2;

long long Inv(long long x) {
    if(x == 4)
        return 748683265;
    if(x == 6)
        return 166374059;
    if(x == 2)
        return 499122177;
}

const long long INV = Pow(24,Mod - 2) % Mod;

int main() {
    cin >> n;

    ans1 = 1ll * n * (n - 1) % Mod * (n - 2) % Mod * (n - 3) % Mod * INV % Mod;
    ans2 = 1ll * n * (n - 1) % Mod * (n - 2) % Mod * (n - 3) % Mod * INV % Mod + 1ll * n * (n - 1) / 2 + 1;
    ans2 %= Mod;

    cout << ans1 << "\n" << ans2;
    return 0;
}

D. [ARC141F] Well-defined Abbreviation

AC 自动机,咕咕咕。

\[\text{END} \]

标签:right,21,int,long,dp,交点,CSP,模拟,Mod
From: https://www.cnblogs.com/baijian0212/p/csp-21.html

相关文章

  • [ABC215D] Coprime 2 题解
    题意给定数列\(A_N\)和一个正整数\(M\),求出所有的\(1\lek\leM\)满足\(\foralli\in\left[1,N\right],\gcd(k,A_i)=1\)。题解本题存在线性复杂度算法。记\(\operatorname{lpf}(n)=[1<n]\min\{p:p\midn\}+[1=n]\),即\(n\)的最小质因数。特别地,\(n......
  • LeetCode 213.打家劫舍II
    1.题目:你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。给定一个代表每个房屋存......
  • PCIe卡设计方案:631-单路12Gsps 3G 带宽模拟信号源PCIe卡
     一、板卡概述    单路3G带宽模拟信号源卡由DA子卡和PCIe底板组成,二者通过标准FMC连接器互联,可以实现将PCIe总线数据转换为一路高速的模拟量输出。北京太速科技该板可广泛用于雷达、通信、光电领域的噪声信号、毛刺、脉冲信号模拟产生等领域。 二、性能指标 板卡功能......
  • 2023年CSPM-3国标项目管理中级认证报名推荐这家
    CSPM-3中级项目管理专业人员评价,是中国标准化协会(全国项目管理标准化技术委员会秘书处),面向社会开展项目管理专业人员能力的等级证书。旨在构建多层次从业人员培养培训体系,建立健全人才职业能力评价和激励机制的要求,培养我国项目管理领域复合型人才。  【证书含金量】 ·竞聘优先......
  • 在安卓模拟器上如何实现HTTP代理自动切换
    在开发和测试应用程序时,有时需要在安卓模拟器上实现HTTP代理的自动切换以方便调试。本文将介绍如何在安卓模拟器上实现HTTP代理的自动切换。1.使用脚本文件使用脚本文件是一种实现HTTP代理自动切换的简单方法。以下是一个示例脚本文件:这个脚本定义了一个代理服务器地址和端口号数组......
  • 华为数通方向HCIP-DataCom H12-821题库(单选题:81-100)
    第81题某公司新购入一台网络设备,作为网络管理员,初次配置该设备通常通过什么方式?A、FTPB、TelnetC、SNMPD、Console口登录答案:D解析:通常情况下,初次配置网络设备会通过Console口登录的方式进行。Console口是一种串口接口,可以直接连接到设备的控制台端口。通过Console口登录设备......
  • 【刷题笔记】21. Merge Two Sorted Lists
    题目Mergetwosortedlinkedlistsandreturnitasanewlist.Thenewlistshouldbemadebysplicingtogetherthenodesofthefirsttwolists.Example:Input:1->2->4,1->3->4Output:1->1->2->3->4->4题目大意合并2个有序链表解题思路按照......
  • Nexpose v6.6.210 for Linux & Windows - 漏洞扫描
    Nexposev6.6.210forLinux&Windows-漏洞扫描Rapid7VulnerabilityManagement,ReleaseAug09,2023请访问原文链接:https://sysin.org/blog/nexpose-6/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org您的本地漏洞扫描程序搜集通过实时覆盖整个网络,随......
  • 水果编曲软件FL Studio 21.1.0.3267音频工作站2023电脑配置要求详解
    FL全称为FruityLoops,FLStudio更倾向于DJ混音和编辑。但这并不意味着它缺乏功能!FLStudio21是一个受欢迎的插件,如果购买了制作版本,那么这个软件就可以终身更新。为音乐制作和音频编辑选择硬件FLStudio21Win-安装包:https://souurl.cn/ZIwzHsFLStudio21Mac-安装包:https://sou......
  • FL Studio 21.1.0.3267中文解锁版功能介绍
    FLStudio21简称FL21,全称FruityLoopsStudio21,因此国人习惯叫它"水果"。目前最新版本是FLStudio21,它让你的计算机就像是全功能的录音室,大混音盘,非常先进的制作工具,让你的音乐突破想象力的限制。FLStudio21官方汉化激活解锁版提供了音符编辑器,编辑器可以针对作曲者的要求编辑......