传送门  题目：  input：  9 3 -1997 94 -1591 -1211 -439 -1951 917 -1777 1845 -771 1909 594 1080 1682 -253 1983 -1469 1356 1000 0 -499 866 -500 -866  output: 36  样例对应的图：   思路： 红点组成七边形，可以从一个顶点将这七边形划分为6个三角形，每个三角形内的蓝点数之和=3即满足七星阵的要求。 根绝这个思路，首先要求出由n个红点构成的所有三角形内的蓝点数，由于题目保证不存在三点共线，所以蓝点不会出现在三角形的边（由两个红点连接而成）和顶点上，只会出现...

传送门  题目： 思路： 先获取每两个相邻办公楼之间的距离。      D   i     D_i   Di​（1≤i≤n-1）   当k=1时，选择最小的      D   i     D_i   Di​  当k=2时  方案一：选择最小的      D   i     D_i   Di​和除了      D    i   −   1     ,    D   i    ,    D    i   +   1      D_{i-1},D_i,D_{i+1}   Di−1​,Di​,Di+1​之外的其他数中的最小值 方案二：选择最小的      D   i     D_i   Di​旁边的 ...

传送门  题目： 思路： 如果一个数     x    x   x有三个不同的质约数      p   1    ,    p   2    ,    p   3     p_1, p_2, p_3   p1​,p2​,p3​，那么这个数至少有8个约数。 这是因为     g   c   d   (    p   1    ,    p   3    )   =   1   ,   g   c   d   (    p   2    ,    p   3    )   =   1    gcd(p_1,p_3)=1, gcd(p_2, p_3)=1   gcd(p1​,p3​)=1,gcd(p...

传送门  题目： 思路： h用处不大，因为上次睡的时间和下次醒的时间是一样的，每次都面临两种选择。      d   p   [   i   ]   [   j   ]    dp[i][j]   dp[i][j]表示前     i    i   i次选择     j    j   j次“      a   i    −   1    a_i-1   ai​−1”这种方案能够获得的最大good sleeping数（     0   ≤   j   ≤   I    0≤j≤I   0≤j≤I）      s   u   m   [   i   ]   =    ∑    k   =   1  ...

传送门  题目： 思路： 数组中的某些数可以通过执行多次题目中的操作最终归为1个数。 先确定每个     r   (   1   ≤   r   ≤   n   )    r(1≤r≤n)   r(1≤r≤n)有哪些     l   (   1   ≤   l   ≤   r   )    l(1≤l≤r)   l(1≤l≤r)满足     [   l   ,   r   ]    [l,r]   [l,r]内的数可以归为1个数。在处理的时候可以先枚举     l    l   l，这样     r    r   r每次都只增加1。且     [   l   ,   o   l   d   r...

传送门  题目： 思路：  n个元素有一对相同的，那么n个数***有n-1个不同的数，从m个数中选n-1，方法数：      C   m    n   −   1      C_m^{n-1}   Cmn−1​ 从n-1个不同的数中选择一个数使其在要构造的数组中出现两次，最大的数是唯一的，不能选它，所以方法数为：n-2 除了重复出现的数一个在最大数的左边，一个在右边外，其他n-3个数可以出现在最大数的左边/右边，方法数为：      2    n   −   3      2^{n-3}   2n−3 故     a   n   s   =    C   m    n   −   1     ...

电子科技大学《linux操作系统编程》实验2：https://www.icourse163.org/learn/UESTC-1003040002?tid=1206878228#/learn/content?type=detail&id=1211971805&cid=1215051733  实现效果：  上述两个 命令参数缺失给出错误提示信息 源文件为目录时给出错误提示信息 目的文件为目录时将源文件在目的目录中复制一份（默认同名） 目的文件已经存在时提供追写/重写选项  实现代码：  #include <sys/types.h> #include <sys/st...

A 签到 B 签到 C dp  题意：n道题，第i道题做对的概率为      p   i     p_i   pi​，问分别做对n道题中分别做对0,1,2,3,…n道的概率。 思路：     d   p   [   i   ]   [   j   ]   表   示   前   i   道   题   中   对   了   j   道   的   概   率    dp[i][j]表示前i道题中对了j道的概率   dp[i][j]表示前i道题中对了j道的概率      d   p   [   i   ]   [   0   ]   =   d   p   [   i   −   1   ] ...

A 签到  题意： 迷宫遇到D只能向下，遇到R只能向右，遇到B既可以向下也可以向右，问从左上走到右下有多少种方案。 思路：dp或者记忆化dfs  B 构造  题意：A的逆过程，即知道方案数，构造这样一个迷宫 思路：若以方案数为20为例  根据上面的构造过程可以从二进制考虑，先将1,2,4,8,16等构造出来，最后一列填D还是B取决于该位上是0还是1，是1则填B，否则填D。所以1e9+7以内的数肯定能由此方法构造出来，注意特判方法数是0的情况。 ac代码：   #include <bits/stdc++.h> using namespace std; char s[50][50]; ...

A 签到 B 签到 括号匹配 栈 C 子段乘积 注意不能除0 D  题意：给出序列，求多少个区间异或值为0 思路：遍历序列的同时记录当前前缀异或值，用map统计当前前缀异或值之前出现次数，用这个次数更新答案。初始mp[0]=1。  E 贪心  思路：给出一串加号和1-9的数字组成的字符串，如：23984692+238752+2+34+，求重组后表达式的结果的最小值是多少 思路：有n个加号就有n+1个数字相加(记最终要进行相加数字为V)，要想使最后的结果最小，那么这些数字就应该尽量均匀的分配到V中，且V的低位数值大，高位数值小。故对所有的数字降序排列，每n+1个为一组从低位到高位分配给V，并计算...

A 签到 B  题意：在x轴上找一个点，使得它到给定的点之间的最大距离最小，输出最大距离的最小值 思路：答案点的左/右侧，得到的最大距离都比答案大，所以答案所在的点是一个极小值点。可以对在x轴上找的这个点三分，或者对最大距离二分，找到第一个满足答案的最大距离（该距离最小） ac代码：   //三分法 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; struct node{ int x, y; }a[maxn]; int n; double maxdis(double x) { double...

爆炸的一场，脑子已经放弃我了。。  A -思维  题意：数组a、b，可对数组重排，令c[i]=a[i]+b[i]，求c中第k大的数的最大值。 思路：a中的前k大和b中的前k大倒序组合，取最小值  B-图论  题意： 1e6个点的有向图，每个点只有一条指出的边，问图中最长的简单路径包含的点数 思路：图中一定会出现环。对于环，从环内所有点出发的最长简单路径的点数=该环内包含的点数，可以先把能够直接统计的答案处理出来。注意每个点只能访问一次，避免复杂度退化，再以每个点为起点记忆化dfs求答案。 ac代码：   #include <bits/stdc++.h> using namespac...

很早之前就学过了，现在系统的再学习下，做个汇总。 原理  deque实现，队头存最大值/最小值，从队头到队尾使之单调减/增。 以队头存最小值为例：  队列为空，直接入队 依次将队列中大于(等于也可以)当前值的数从队尾出队，最后再将当前值入队尾  deque<int> q; for(int i = 0; i < n; i++) { while(!q.empty() && q.back()>a[i]) q.pop_back(); q.push_back(a[i]); }  练习   洛谷P1886-滑动窗口-模版题 传送门 解题思路： 因为有长度k的限制，所...

传送门 题目：  给定一个整数 M，对于任意一个整数集合 S，定义“校验值”如下: 从集合 S 中取出 M 对数(即 2∗M 个数，不能重复使用集合中的数，如果 S 中的整 数不够 M 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值 就称为集合 S 的“校验值”。 现在给定一个长度为 N 的数列 A 以及一个整数 T。我们要把 A 分成若干段，使得 每一段的“校验值”都不超过 T。求最少需要分成几段。  input 2 5 1 49 8 2 1 7 9 5 1 64 8 2 1 7 9  output 2 1  解题思路：  枚举每一个分块[L,R]的L，在L一定的情况下...