WORIA

数学   大整数    加减乘除，取模，逻辑运算符，输入，输出，绝对值，幂   1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891 ...

https://acm.ecnu.edu.cn/contest/448/ E. Effective Gradient   题意：给定 p,qp, qp,q，以及平面上 nnn 个点，求一条至少过两个点的直线，斜率与 p/qp / qp/q 的差的绝对值最小。 几何 把所有点按照与直线 y=pqxy=\frac{p}{q}xy=qp​x 的有向距离的大小排序。即按照 pqxi−yi\frac{p}{q}x_i-y_iqp​xi​−yi​ 排序。 最终答案的两个点一定相邻。否则选择它们中间的一个点，一定与这两点之一能够组成更优的直线。 之所以是有向距离是因为在直线两侧的点不同。 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 2e6 + 10;const ll ...

http://codeforces.com/gym/103202 H. The Boomsday Project   题意：共享单车，每次骑要花费 rrr 元。另外还有 nnn 种租赁方式，每种方式在购买后 did_idi​ 天内有效，在有效期内能免费骑 kik_iki​ 次，购买需要花费 cic_ici​ 元。给出 mmm 条骑车记录，在第 pip_ipi​ 天骑了 qiq_iqi​ 次，问最少花费。1≤n≤500,1≤m≤105,1≤r≤109,1≤di,ki,ci≤109,0≤pi≤109,0≤qi≤3×105,∑i=1mqi≤3×1051\leq n \leq 500, 1 \leq m \leq 10^5, 1 \leq r \leq 10^9,1 \leq d_i, k_i, c_i \leq 10^9,0 \leq p_i \leq 10^9, 0 \leq q_i \leq 3 \times 10^5, \sum_{i=1}^m q_i \leq 3 \times 10^51≤n≤500,1≤m≤105,1≤r≤109,1≤di​,ki​,ci​≤109,0≤pi​≤1 ...

https://github.com/woriazzc/beiyouCV/tree/master/02 任务 编写一个图像分类系统，能够对输入图像进行类别预测。具体的说，利用数据库的2250张训练样本进行训练；对测试集中的2235张样本进行预测。 数据库说明：scene_categories数据集包含15个类别（文件夹名就是类别名），每个类中编号前150号的样本作为训练样本，15个类一共2250张训练样本；剩下的样本构成测试集合。 数据集详情可参阅： https://qixianbiao.github.io/Scene.html 数据集下载地址： https://figshare.com/articles/15-Scene_Image_Dataset/7007177 使用知识点: SIFT特征、Kmeans、词袋表示、支撑向量机 算法流程 提取数据集中的样本，并划分训练集和测试集 -----------------------特征提取与词典生成----------------------- 对于训练集的所有图片，提取图片的SIFT 特征点，并对SIFT 特征点向量归一化 对所有SIF ...

https://github.com/woriazzc/beiyouCV/tree/master/01 任务 编写一个钱币定位系统，其不仅能够检测出输入图像中各个钱币的边缘，同时，还能给出各个 钱币的圆心坐标与半径 。 算法流程 步骤1 ：使用 Canny 算法 提取图像边缘 使用高斯滤波器滤波 计算图像的梯度图并获得梯度方向 对梯度图进行非极大化抑制 使用双阈值法获得最终的边缘图 步骤2：在边缘图上利用Hough变换计算圆心与半径 建立参数空间 依据边缘点的梯度方向对参数空间进行投票 依据预设定的投票阈值筛选出初步结果 对已筛选出的结果进行非极大化抑制，得到精确的参数（圆心和半径） 算法简介 Canny 算法 高斯滤波器可以针对服从高斯分布的噪声进行平滑。 图像在 xxx 方向的偏导数可以用核 (−11)\begin{pmatrix} -1 & 1 \\ \end{pmatrix}(−1​1​) 卷积以近似求解，在 yyy 方向的偏导数可以用核 (−11)\begin{pmatrix} -1 \\ 1 \\ \end{pmatrix}(−11​) 卷积以近似求解。也就 ...

https://ac.nowcoder.com/acm/contest/17148 C - Alice and Bob   题意：给定数组 aaa，常数 KKK，多次询问，每次问区间 [L,R][L,R][L,R] 中有几个连续子区间中不同的数的个数大于等于 KKK。 尺取+二分/主席树 首先尺取求出以每个位置为右端点时满足条件的最右的左端点。 查询时只要找到最靠左的完整在 [L,R][L,R][L,R] 中的区间。可以二分做到。 但这里脑子一热写了个主席树，就当是实现下上次浙江省赛的那道主席树了。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include <bits/stdc++.h>bool dbg = true;#define debug(x) if (dbg) cout & ...

https://codeforces.com/gym/103055 F. Fair Distribution   题意：给定 n,mn,mn,m，nnn 只能减少，mmm 只能增加，问要使得 mmm 是 nnn 的倍数，两者变化量的绝对值之和最小是多少？1≤n,m≤1081 \le n, m \le 10^81≤n,m≤108 整除分块 暴力的做法是枚举 nnn，再计算 mmm 的最少改变量。这其中会有很多无效的枚举。 对于 ⌊mx⌋\lfloor\frac{m}{x}\rfloor⌊xm​⌋ 相同的这一段 xxx，这一段的最小值或最大值处一定存在这一段的最优解（虽然其它位置可能也有）。所以其实整除分块后，每一块只需要计算两个端点处即可。 1234567891011121314151617181920212223242526272829303132333435363738394041#include <bits/stdc++.h>bool dbg = true;#define debug(x) if (dbg) cout << #x << " ...

http://codeforces.com/gym/103104 I. Sequence 题意：mmm 个限制条件：pindex≠valuep_{index}\neq valuepindex​=value。问有多少个四元组 (A,B,L,R)(A,B,L,R)(A,B,L,R) 满足 ∀i∈[A,B]\forall i\in [A,B]∀i∈[A,B]，pip_ipi​ 可以取 [L,R][L,R][L,R] 中任意数。1≤A,B,L,R≤N1 \le A,B,L,R \le N1≤A,B,L,R≤N 单调栈 问题转化为二维网格上有 mmm 个坏点，问有几个只包含好点的矩形。 dp[i][j]dp[i][j]dp[i][j] 表示以 (i,j)(i,j)(i,j) 为右下端点的矩形的个数。 遍历行，遍历列，对每一行维护一个递增的单调栈，左上端点的取法等于栈顶的左上位置取法数+当前位置到栈顶位置构成的矩形中的点数。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#in ...

http://codeforces.com/gym/103102 I. Modulo Permutations 题意：给定 nnn，问满足 pi mod pi+1≤2p_i \text{ mod } p_{i+1} \le 2pi​ mod pi+1​≤2，（pn+1=p1p_{n+1}=p_1pn+1​=p1​），的排列 ppp 的个数。 dp 首先 1 和 2 可以放在任意位置。 由于这个题目要的其实是个环，所以可以从 1 的位置切开，变成 1,x,x,x,2,x,x,x,x。1 和 2 把整个排列分成两段。每一段内一定是递减的，因为如果有递增，则 pi mod pi+1=pi>2p_i \text{ mod } p_{i+1}=p_{i}>2pi​ mod pi+1​=pi​>2。 从小到大遍历，每一轮在上一轮的基础上插入数 iii，考虑把 iii 放在第一段还是第二段。 假设现在枚举到 iii，数组 dp[j]dp[j]dp[j] 表示与 iii 处于不同段的数中最大的数为 jjj 时的方案数。sum[j]sum[j]sum[j] 表示 jjj 的所有因数的 ...

https://ac.nowcoder.com/acm/contest/11174 D - 牛客推荐系统开发之动态特征获取   题意：每个特征有有时间戳，且保质期都为 yyy，在时间戳+ yyy 秒后会失效，每个特征都有优先级，越近使用的特征的优先级越高，内存中只能存放优先级最高的 mmm 个特征，问 nnn 次交互中各次是否需要重新取特征。 双端队列 在内存中需要两个条件：未过期，且优先级在前 mmm 个。 因此维护两个双端队列：时间戳队列，队列中的特征都未过期；优先级队列，队列中的特征的优先级都在前 mmm。 可以直接把按照时间排序后的交互队列作为，优先级队列，只需要记录门槛，保证门槛右侧的都是前 mmm。记录每个特征最近被使用的时间，只要判断这个时间是否位于门槛右侧就能判断优先级是否满足条件。 在维护时间戳队列时需要记录每个特征在队列中的次数，因为一个特征可能先由于优先级不够而离开内存，但由于没有过期，所以在时间戳队列中仍然存在，当再次交互时需要重新取，因此又放进了时间戳队列中，导致在时间戳队列中有两个这个特征。 因此仅当一个特征在时间戳队列中出现次数为 0 时才能视为过期。 1 ...