Von Brank

对拍，即将相同的数据输入两个不同程序，比对其输出结果。可以用于在ACM/OI等比赛中用暴力算法检测标算的正确性，寻找使程序出错的样例数据。 随机数生成器 要编写好用的对拍程序，首要的是要编写一个随机数生成器，便于产生多样化的数据。 朴素随机数生成器 相信很多人都见过下面这种写法： 1234567891011121314151617181920//DataGenerator_naive.cpp#include <iostream>#include <cstdio>#include <ctime>using namespace std;int main(int argc, char *argv[]){ int seed = time(NULL); srand(seed); //以下代码可以生成10个随机整数 int n = 10; for (int i = 1; i <= n; i++) { printf("%d ", rand()); } retu ...

本文合作者：laybxc 赛事信息 名称 出题人 开始时间 时长 官方题解 Codeforces Round #706 (Div. 2) Daniel_yuanImakfsmg23333waaitg Mar/10/202120:05 (UTC+8) 02:00 Tutorial (en) A. Split it! 题目 题目描述 给出一个长度为 nnn 的字符串 sss 和一个整数 kkk ，问其能否划分为如下形式： s=a1+a2+⋯+ak+ak+1+R(ak)+R(ak−1)+⋯+R(a1)s=a_1+a_2+\dots+a_k+a_{k+1}+R(a_k)+R(a_{k-1})+\dots+R(a_1)s=a1​+a2​+⋯+ak​+ak+1​+R(ak​)+R(ak−1​)+⋯+R(a1​) 其中， R(x)R(x)R(x) 表示将 xxx 反转得到的字符串。 输入格式 第一行是一个整数 t(1≤t≤100)t(1≤t≤100)t(1≤t≤100) ，表示数据组数。 每组数据第一行有两个整数 n,k(1≤n≤100,0≤k≤⌊n2⌋)n,k(1≤n≤100, ...

本文合作者：laybxc 赛事信息 名称 出题人 开始时间 时长 官方题解 Codeforces Round #705 (Div. 2) 74TrAkToRAlFlen Mar/06/202122:05 (UTC+8) 02:15 Tutorial A. Anti-knapsack 题目 题目描述 给定 n,kn,kn,k ，请选择 1−n1-n1−n 的若干个整数，使得这些整数的和的子集都不等于 kkk ，问最多能选出几个整数且分别是多少。 输入格式 第一行是一个整数 t(1≤t≤100)t(1≤t≤100)t(1≤t≤100) ，表示数据组数。 每组数据有两个整数 n,k(1≤k≤n≤1000)n,k(1≤k≤n≤1000)n,k(1≤k≤n≤1000) 输出格式 对于每组数据 第一行输出一个整数 mmm ，表示最多能选出的整数数量。 第二行输出这些选出的整数，顺序任意。 解决方案： 思路： 显然对 i∈[1,n]i ∈[1,n]i∈[1,n] ， i>ki>ki>k 时 iii 这个数肯定可以直接选 i=ki=ki=k 显然不行 ...

动态规划（Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 最长上升子序列（LIS） 给出一个序列 a1,a2,...,an−1,ana_1, a_2, ...,a_{n-1}, a_na1​,a2​,...,an−1​,an​ ，求其最长不下降（或上升）子序列。 求最长上升子序列（LIS）的算法是Yukko介绍给我的第一个算法。 解决方案（ O(n2)O(n^2)O(n2) ） 状态设计： dp[i]dp[i]dp[i] 表示以第 iii 个数结尾的最长上升子序列的最长长度。 状态转移方程： dp[i]=max(dp[j])+1(1≤j＜i，且a[i]>a[j])dp[i]= max(dp[j])+1 \quad (1≤j＜i， 且a[i]>a[j])dp[i]=max(dp[j])+1(1≤j＜i，且a[i]>a[j]) 1234567891 ...

解决单源最短路径问题的几种算法，是Yukko最早给我介绍的几类算法之一。 最短路算法的基本功能，是求解带边权的有向或无向图中任意两点之间最短或最长的路径及其距离。 模板题：洛谷 P4779 | [模板]单源最短路径（标准版） 题目描述 给定一个 nnn 个点， mmm 条有向边的带非负权图，请你计算从 sss 出发，到每个点的距离。 数据保证你能从 sss 出发到任意点。 输入格式 第一行为三个正整数 n,m,sn, m, sn,m,s 。 第二行起 mmm 行，每行三个非负整数 ui,vi,wiu_i, v_i, w_iui​,vi​,wi​ ，表示从 uiu_iui​ 到 viv_ivi​ 有一条权值为 wiw_iwi​ 的有向边。 输出格式 输出一行 nnn 个空格分隔的非负整数，表示 sss 到每个点的距离。 输入输出样例 输入 #1 12345674 6 11 2 22 3 22 4 11 3 53 4 31 4 4 输出 #1 10 2 4 3 说明/提示 1≤n≤1051≤n≤10^51≤n≤105 ； 1≤m≤2×1051 \leq m \leq 2\times 10^ ...

KKK 近邻算法（k-Nearest Neighbor）是CS231n课程介绍的第一个算法，此算法和神经网络没有任何关系，实际中也极少使用，但学习使用KNN算法可以获得对图像分类方法的基本认知。 先决条件 在开始写作业前，你需要做一些准备工作。 Jupyter Notebook先决条件 你可以在这里下载官方提供的CS231n Assignment1的 Jupyter笔记本。 在Anaconda Prompt Powershell中输入conda activate cs231，接着cd到assignment1目录下，输入jupyter notebook开启Ipython笔记本，打开knn.ipynb即可开始本次作业。 在开始之前，需要注意，由于Jupyter Notebook的某种bug，CIFAR-10的路径变量cifar10_dir需要赋值为绝对路径，同时在路径前加上r来忽略转义，像下面这样： 12# Load the raw CIFAR-10 data.cifar10_dir = r'D:\Users\VonBrank\Documents\GitHub\code-lear ...

快速幂 以 a=2,n=10a = 2, n = 10a=2,n=10 的情况为例，注意到 10=21+2310 = 2^1 + 2^310=21+23 ，则 2102^{10}210 可表示为 221×2232^{2^1}\times2^{2^3}221×223 ，利用二进制拆分，可以实现在 O(log⁡n)O(\log_{}{n})O(log​n) 时间范围内计算出 ana^nan 的值。 模板题：洛谷 P1226 | [模板]快速幂||取余运算 题目描述 给你三个整数 b,p,kb,p,kb,p,k ，求 bpmodkb^p mod kbpmodk 。 输入格式 输入只有一行三个整数，分别代表 b,p,kb,p,kb,p,k 输出格式 输出一行一个字符串 b^p mod k=s，其中 b,p,kb, p, kb,p,k 分别为题目给定的值， sss 为运算结果。 输入输出样例 输入 #1 12 10 9 输出 #1 12^10 mod 9=7 说明/提示 样例输入输出 1 解释 210=1024，1024 mod 9=72^{10} = 1024， 1024\ mod\ ...

近期在和朋友做计算机视觉相关的年度项目，根据导师的建议，我们选择了Stanford的CS231n课程作为计算机视觉的入门课程。然而由于某些原因， 初期的学习线路出了一些偏差， 临近中期才发现CS231n官方提供了非常完善的笔记和作业文档，免去了大面积重复造轮子的工作，只需要编写部分核心代码。因此我决定重修CS231n课程，写下这一系列文章记录学习过程。 本文提供开始学习前CS231n的准备步骤，主要翻译自官方提供的Software Setup文档，供日后查询。 使用Google Colaboratory工作 在本地设备上工作 配置Anaconda虚拟环境 CS231n官方推荐使用Anaconda搭建Python编程环境并管理Numpy等包及其依赖项。这样做的好处之一在于，其自带MKL优化，这可以加速numpy与scipy代码的执行。 Anaconda虚拟环境的搭建在其他文章中已做介绍，在此不再赘述。 安装完Anaconda后，需创建名为cs231n的虚拟环境，可以在终端中运行以下指令创建： 123# 这将在'path/to/anaconda3/envs/'下创建# ...

排序算法（Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。 几种排序算法的比较： 模板题：洛谷 P1177 | [模板]快速排序 题目描述 利用快速排序算法将读入的 NNN 个数从小到大排序后输出。 输入格式 第 111 行为一个正整数 NNN，第 222 行包含 NNN 个空格隔开的正整数 aia_iai​ ，为你需要进行排序的数，数据保证了 aia_iai​ 不超过 10910^9109 。 输出格式 将给定的 NNN 个数从小到大输出，数之间空格隔开，行末换行且无空格。 输入输出样例 输入 #1 1254 2 4 5 1 输出 #1 11 2 4 4 5 说明/提示 对于 20%20\%20% 的数据，有 N≤103N\leq 10^3N≤103 ； 对于 100%100\%100% 的数据，有 N≤105N\leq 10^5N≤105 。 快速排序 快速排序（Quicksort），又称分区交换排序（partition-exchange sort），简称快排，是一种被广泛运用的排序算法。 解决方案 12345 ...

搜索，是Yukko首先给我介绍的几类算法之一，其对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。 搜索有很多优化方式，如减小状态空间，更改搜索顺序，剪枝等。 搜索是一些高级算法的基础。在 OI 中，纯粹的搜索往往也是得到部分分的手段，但可以通过纯粹的搜索拿到满分的题目非常少。 DFS（深度优先搜索） DFS 本是图论概念，在搜索算法中，该词常常指利用递归函数方便地实现暴力枚举的算法，与图论中的 DFS 算法有一定相似之处，但并不完全相同。 DFS 框架 123456789101112131415161718192021222324252627282930313233#include <cstdio>using namespace std;const int maxn = 100;int n;bool vst[];bool CheckEdge(...) // 边界条件和约束条件的判断{ if (...) // 满足条件 return 1; else // 与约束条件冲突 return 0;} ...