语音评测系统 2019 计蒜之道 初赛 第六场 多个特殊二次函数(同样形状)的最小值 它与多条直线最小值的互换...

本文主要是介绍语音评测系统 2019 计蒜之道 初赛 第六场 多个特殊二次函数(同样形状)的最小值 它与多条直线最小值的互换...,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

https://nanti.jisuanke.com/t/39458

 

n个函数的形状是一致的,只是大小不同

 

a按照从小到大排序,

设当前最小值的区间段为

(u1,u2) ai1

(u2,u3) ai2

……

[其中i1<i2<...]

 

加上一个新的函数,若它与函数ik交于点ur,则它必大于段(u1,u2),...,(uk-1,uk),必小于段(uk+1,uk+2),(uk+2,uk+3),...。

 

经过修改过,段变为(u1,u2),...,(uk-1,uk),(uk,ur),(ur,inf)

使用单调栈处理,每个段最多被加入或删除一次

 同理,对于函数(x+a)^2+b,它可以转变x^2+2ax+b,在进行函数比较时,都有x^2,则可以转变为直线的比较,

对于直线,同样满足凸包性质

如题目[JSOI2008]Blue Mary开公司,可以像本题一样,使用排序+单调栈

当然如果修改为线段,李超树大法好,https://i.cnblogs.com/PostDone.aspx?postid=11156309&actiontip=%e4%bf%9d%e5%ad%98%e4%bf%ae%e6%94%b9%e6%88%90%e5%8a%9f

 

https://nanti.jisuanke.com/t/39458代码

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 
11 const int maxn=1e6+10;
12 const double eps=1e-8;
13 
14 ll a[maxn],b[maxn],c[maxn],d[maxn];
15 int u[maxn];
16 double v[maxn];
17 
18 double cal(int i,int j)
19 {
20     return (c[i]+c[j]+1.0*(d[i]-d[j])/(c[i]-c[j]))/2;
21 }
22 
23 int main()
24 {
25     bool vis=0;
26     int n,m=0,q,i,g;
27     ll r,y;
28     double x;
29     scanf("%d",&n);
30     for (i=1;i<=n;i++)
31         scanf("%lld",&a[i]);
32     for (i=1;i<=n;i++)
33         scanf("%lld",&b[i]);
34 
35     a[n+1]=a[n]+1;
36     r=1e18;
37     for (i=1;i<=n;i++)
38     {
39         r=min(r,b[i]);
40         if (a[i]!=a[i+1])
41         {
42             c[++m]=a[i];
43             d[m]=r;
44             r=1e18;
45         }
46     }
47 
48     g=0;
49     for (i=1;i<=m;i++)
50     {
51         while (g>=2 && cal(i,u[g])<v[g])
52             g--;
53 
54         g++;
55         u[g]=i;
56         if (g>=2)
57             v[g]=cal(u[g],u[g-1]);
58     }
59 
60 //    for (i=1;i<=g;i++)
61 //        printf("%d %.5f\n",u[i],v[i]);
62 
63     i=2;
64     scanf("%d",&q);
65     while (q--)
66     {
67         scanf("%lf",&x);
68         while (i!=g+1 && v[i]<x)
69             i++;
70         if (!vis)
71             vis=1;
72         else
73             printf(" ");
74         y=(ll)x;
75         printf("%lld",(y-c[u[i-1]])*(y-c[u[i-1]])+d[u[i-1]]);
76     }
77     return 0;
78 }
79 /*
80 3
81 1 3 5
82 0 1 2
83 9
84 -1000000 -1 0 1 2 3 4 5 1000000
85 1000002000001 4 1 0 1 1 2 2 999990000027
86 
87 3
88 1 3 5
89 0 1 -10
90 9
91 -1000000 -1 0 1 2 3 4 5 1000000
92 
93 4
94 1 1 2 2
95 0 -3 1000 -5
96 5
97 1 2 3 4 5
98 -4 -5 -4 -1 4
99 */

 

转载于:https://www.cnblogs.com/cmyg/p/11160344.html

这篇关于语音评测系统 2019 计蒜之道 初赛 第六场 多个特殊二次函数(同样形状)的最小值 它与多条直线最小值的互换...的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/214831

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务,目标是自动识别图像中的对象类别。通过卷积神经网络(CNN)等深度学习技术,我们可以构建高效的图像分类系统,广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统,包括环境

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

嵌入式QT开发:构建高效智能的嵌入式系统

摘要: 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发,详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程,包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发,涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用,以及嵌入式 QT 与硬件设备的交互,包括输入输出设

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

阿里开源语音识别SenseVoiceWindows环境部署

SenseVoice介绍 SenseVoice 专注于高精度多语言语音识别、情感辨识和音频事件检测多语言识别: 采用超过 40 万小时数据训练,支持超过 50 种语言,识别效果上优于 Whisper 模型。富文本识别:具备优秀的情感识别,能够在测试数据上达到和超过目前最佳情感识别模型的效果。支持声音事件检测能力,支持音乐、掌声、笑声、哭声、咳嗽、喷嚏等多种常见人机交互事件进行检测。高效推

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

【区块链 + 人才服务】可信教育区块链治理系统 | FISCO BCOS应用案例

伴随着区块链技术的不断完善,其在教育信息化中的应用也在持续发展。利用区块链数据共识、不可篡改的特性, 将与教育相关的数据要素在区块链上进行存证确权,在确保数据可信的前提下,促进教育的公平、透明、开放,为教育教学质量提升赋能,实现教育数据的安全共享、高等教育体系的智慧治理。 可信教育区块链治理系统的顶层治理架构由教育部、高校、企业、学生等多方角色共同参与建设、维护,支撑教育资源共享、教学质量评估、

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同