链接 信息提取: 学生有n名,他们要考m个科目,每个人都有希望所有成绩出分的天数 这里给出的学生的不满意度C,只要出分成绩晚了k天,学生就会产生k x C的不满意度 题目还给出两种调整出分方式 1.将X科目的老师调到Y科目,X延迟出分一天,Y提前一天,产生A点老师不满意度 2.增加老师到Z科目,Z科目提前一天,产生B点老师不满意度 我们需要做的,就是找到最佳调整方式,是总不满意度最小 首先,我们不妨思考,最佳调整方式是调整什么 应该是最晚所有科目的出分天数 假设最晚所有出分科目的天数为T,那么T的范围应在学生希望出分天数的值域内 设总不满意度为f(T),应该能想到f(T)是先减后增的,就可以使...

链接 emm,写两棵树? #include<iostream> #include<vector> #include<algorithm> #include<climits> using namespace std; class min_node { public: vector<int>tree; vector<int>lazy; int n; void build(vector<int>& data, int left, int right, int root) { if (left == right...

链接 不想说了,典型的线段树,之前已经写过,就不赘述了 #include<iostream> #include<vector> #include<algorithm> #include<climits> using namespace std; class node { public: vector<int>tree; vector<int>lazy; int n; void build(vector<int>& data, int left, int right, int root) { if (le...

链接 题目看上去挺吓人的,尤其是这个F(x),乍一看F(x)是一个相当复杂的函数, 但实际上我们拿笔画一下会发现这个函数是一个先减后增的函数,类似于一个大的凹二次函数 那么这题就好些多了 #include<bits/stdc++.h> using namespace std; double f(double a[], double x) { double res = 0; for (int i = 0;i <3;i++) { res = res * x + a[i]; } return res; } struct coefficient { double a[3]; }; d...

链接 这题可以使用直接求导,然后不断用二分法压缩即可 #include<bits/stdc++.h> using namespace std; double f(vector<double>&ss,double x){ double y=0; for(int i=0;i<ss.size();i++){ y+=ss[i]*pow(x,i); } return y; } int main(){ int N;double l,r; cin>>N>>l>>r; vector<double>s(N+1); vector...

链接 题目最终只关心第M个数的大小,那么,我们也就没必要把数组B给找出来了 我们不妨假设最终答案是x,那么数组B就有M个数大于等于x 而数组B是由数组A得来的,数组A给出的值要想在前M个,就必须满足前K个数大于或等于x 我们只需要找到M个满足前K个数大于或等于x的子序列即可 这题就可以采用二分法解决 如果最终得出满足条件的子序列达到了M(一旦达到,为节省时间,直接退出) 说明x可能偏小,那么答案就暂时定为x,我们把左边界扩大到x+1 相反,如果遍历完之后满足条件的子序列小于M个,那就说明x偏大了,右边界就缩小为x-1 (x=(left+right)/2) 通过这种方法,最终左边界会超出右边界,...

链接 信息提取:首先给出n天(也就是数据长度),和m个订单(也就是操作次数) 接下来有一行是n个数据 d1 d2 d3 ... dn 在接下来m行,每行有三个数据,分别为教室数量 val, 初始时间l(左区间),归还时间r(右区间) 题目的要求就是让我们判断dl~dr的数据是否大于每每行val,如果某一行时小于val,让我们输出-1和订单编号 否则输出0 这题的思路很简单,就是直接让给出的n个数据在执行订单时减去val,如果出现负数,直接返回 但是,由于数据量很大,直接暴力做减法会超时 因此,我们可以用线段树来解决这个问题 线段树的优势就是对某一数据进行操控(增大或减小)时,能快速得到某区间的...

链接 题目给出终点L(最大数),和距起点1~L的各石头(数字),要求我们拿走M个石头(数字),使各石头间的距离最小值最大 例如给出一段序列 0 1 11 22 26 31 37 47(0代表起点,47代表终点),拿走三块石头,使各石头间的距离最小值最大 我们可以拿走 1 26 31,得出的结果为10 这题我们可以采用二分法+贪心的思想 最终结果肯定介于[ 1 , L ] ,我们先假设这个最大值为(1+L)/2,如果偏小,那么结果就介于 [ ( 1 + L ) / 2 , L ],依次不断对区间缩小,直到左区间超过右区间 怎么判定偏大偏小呢,我们不妨思考,如果p成立,那么p-1肯定成立,最大值肯...

链接 题目给出一串数据,比如 2 -23 44 124 -51 32 34 5 并给出目标数据t(t>0),要求我们找到一个子序列(或者一个区间),使得这个子序列的和的绝对值最接近t,并输出和的绝对值和 左区间和右区间 我们假设t为89,我们可以找到最接近的数为94,从2到5,也就是 94 2 5 这题乍一看是滑动窗口,但似乎又不太好滑,主要还是因为窗口大小未知,如果直接滑要n!次,非常大。所以我们需要找到一方法,排好序(因为原序列是乱的,往右加总和不确定),如果单调增加或单调减少,那么我们就可以减少遍历次数了 但如果直接排序的话,我们会发现得到的结果不连续(即最终区间是断开的) 解决该...

链接 这题需要我们寻找不重复的最长序列 比如一串序列 1 2 3 4 2 4 5 6 7 最长序列是1 2 3 4或4 5 6 7,也就是4 这题可以采用类似滑动窗口的方法(一次可能滑过多个元素,且不遍历) 用unordered_map记录每个元素的位置,为了方便我们从一开始 比如 1 2 3 4 5 1 2 1 4 6 未创建时,编号为0 创建时,编号为对应数字,也就是右窗口 #include<unordered_map> #include<vector> using namespace std; #define ll long long int main() { i...

链接 题目会给出一串数字,我们需要对这些连续数字进行相加,直到其大于或等于给出的值,我们需要找到最短的连续数字 比如 s=15 3 4 5 6 7 8 9 显然最短的连续数字长度为2,7 8或者8 9 这题和滑动窗口很像,应该说就是滑动窗口(不定长)? using namespace std; #include<vector> #define ll long long int main() { int T; cin >> T; while (T--) { int N; ll S; cin >> N >> S; vector<ll> n...

链接 这题给出二叉树的中序序列和后序序列,要我们写出前序序列 我们可以通过递归调用中序序列和后序序列来构建完整的二叉树 接着直接输出前序序列,根据后序序列的特点,我们在中序序列中找到某一个根节点时,它对应的位置左边的子节点和后续序列位置相同,右节点同样相同 比如中序:BGDHAEFC 后序:GHDBFECA A为根节点,在中序序列里,A的左边元素和后序前四个完全一样,A的右边和后序也完全一样(只有顺序不一样) 这是因为中序是左根右,而后序是左右根,也就是说,中序如果把根放在最后,元素就一样了,位置除外 #include<iostream> #include<string&gt...

链接 这题要求我们对WPL(带全路径长度)进行计算,而WPL就等于每个子节点相加后形成的加权节点的总和,比如有四组数据出现的频率分别是1 2 3 4 那么加权节点的值分别为1+2=3,3+3=6,6+4=10,总和为19 直接计算WPL=3x(1+2)+2x3+1x4=19 二者相等,依据这个就好处理了 考虑使用map统计频率,用优先队列来进行计算 #include<bits/stdc++.h> using namespace std; int main() { int n;cin >> n; for (int i = 0;i < n;i++) { int set...

链接 这题会输入一段表达式,要求我们判断括号能不能匹配 比如2+(23-1*7)) 这个肯定是不匹配的,我们所需要做的就是判断这些括号能不能对应上 因此,我们不必在意其他无关变量 我们可以设置一个计数器,当我们遇到左括号时,计数器加一,遇到右括号但计数器为0时,说明 此刻的右括号多了(可能整体相等但此时多了,就像")("这样) 那直接就返回NO了 如果最后计数器不等于0,说明左右括号数量不相等,那也是NO #include<bits/stdc++.h> using namespace std; int main(){ string str; cin>&gt...