发表于   |   分类于
from numpy import * def loadDataSet(filename): dataMat = [] fr = open(filename) for line in fr.readlines(): curLine = line.strip().split('\t') fltLine = list(map(float, curLine)) dataMat.append(fltLine) return dataMat #根据阈值分割数据集 def binSplitDataSet(dataSet, feature, value): mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0], :] mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0], :] return mat0, mat1 #叶子结点的平均值 def regLea ...
阅读全文 »

发表于   |   分类于
from numpy import * import matplotlib.pyplot as plt def loadDataSet(filename): numFeat = len(open(filename).readline().split('\t')) - 1 dataMat = []; labelMat = [] fr = open(filename) for line in fr.readlines(): lineArr = [] curLine = line.strip().split('\t') for i in range(numFeat): lineArr.append(float(curLine[i])) dataMat.append(lineArr) labelMat.append(float(curLine[-1])) return dataMat, labelMat #最 ...
阅读全文 »

发表于   |   分类于
原题：Finite Encyclopedia of Integer Sequences 原题大意给出两个数K，N， 表示数列的取值范围为1~K，N表示数列长度的取值范围为1~N，问这样的所有序列按照字典序排序，第（X/2）个序列是什么 算法分析如果是K是偶数，该序列一定是这样的：第一个数是（K/2），然后跟着(N-1)个K。如果是奇数，先看到这样一个序列B：n个（K+1）/2构成，排在这个序列之前的序列和排在这个序列之后的序列，他们的关系是满足函数(K+1-Xi)的（比如K=5时， 1234，4321），但是个数却不是相等的（比如K=5时， 3333只有一个，在前半段），所以前后序列差为(N-1)，从B开始往前数(N-1)/2个。 程序代码#include <bits/stdc++.h> using namespace std; const int maxn = 3e5+10; int n, k; void solve(int num){ stack<int> s; int t = (k+1)/2; for(int i = 0; i & ...
阅读全文 »

发表于   |   分类于
原题：Small Multiple 原题大意给一个数K，在K的整数倍里，找出数位和最小的，并输出和 算法分析首先引入图论，求一个数的数位和，可以看成一张有向图求最短路，图上的每个顶点都是整数，起点是1，数字v到数字v+1之间的值为1，数字v到数字v*10的值为0，求x的数位和就是求1到x的最短路的距离加上1。 这里求K的整数倍，可以把图压缩到K个点，因为如果两个数mod K的值相同，我们可以认为是同一个点（如2 和 20 mod 6），所以就是求从1到0的最短路。因为只含有1和0，所以可以用双端队列来优化（每个值取出来要么不变，要么加1，不变的放到队首，加1的放到队尾，队列里的值一定是非递减的）。 程序代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+50; typedef pair<int, int> ii; int solve(int K){ deque<ii> dq; vector<int&g ...
阅读全文 »

发表于   |   分类于
原题：Snuke Festival 原题大意给出长度为n的三个数组A，B，C，从A中取出a， 从B中取出b， 从C中取出c，使得a < b < c，问有多少种取法？ 算法分析把A，C 排序，对于B中的每一个元素，在A中找小于它的和在C中大于它的个数相乘，然后记录总和 程序代码//lower_bound是大于等于，upper_bound是大于 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+50; int a[maxn], b[maxn], c[maxn]; int n; int main(){ while(cin >> n){ for(int i = 0; i < n; i++)cin >> a[i]; for(int i = 0; i < n; i++)cin >> b[i]; for(int i = 0; i < n; ...
阅读全文 »