发表于   |   分类于
from numpy import * import operator def createDataSet(): group = array([[1.0,1.1], [1.0, 1.0], [0,0], [0, 0.1]]) labels = ['A', 'A', 'B', 'B'] return group, labels def classify0(inX, dataSet, labels, k): #inX是输入值，dataset是训练集，labels是标签，k是前k个 dataSetSize = dataSet.shape[0] #shape[0]表示数据集的行数 diffMat = tile(inX, (dataSetSize,1)) - dataSet #tile是延展复制，将inX按 dataSetSize * 1 延展 sqDiffMat = diffMat**2 #方差中的平方差 sqDistance ...
阅读全文 »

发表于   |   分类于
原题：Sandglass 原题大意给一个沙漏，一半叫A，另一边叫B，初始A在上B在下，A+B的沙子一共为X，每秒钟走一滴沙，再给出k个时刻，每个时刻都将沙漏倒置，现在有Q个询问，每个询问（t，a）代表若起始A中有a滴沙，t时刻时A中还有多少沙子，每个询问的时刻t是递增的给出。 算法分析ft(x)表示若A中初始沙数量为x，在t时刻A中剩余的沙的数量。举几个例子之后会发现，ft(x)的函数都是这样的 （x前面的斜率也可以为-1），同时函数上限不会超过X，下限不会低于0，模拟即可 程序代码#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+5; int X, K, Q, r[maxn], t[maxn], a[maxn], ub, lb, b, t1, t2, add, tmp, diff, sgn; void Add(int &n, int num){ n+=num; n = max(0, min(X, n)); } int main(){ ios::sync_wi ...
阅读全文 »

发表于   |   分类于
原题：ConvexScore 原题大意给出N个点，这N个点可以形成若干个子集S，每个S满足如下条件：S里的所有点正好形成一个凸多边形，每个点都是凸多边形的顶点。对于任意一个S，n是N个点散布在S的凸包内的个数（包括边界和顶点），S相对应的得分为2^(n-|s|)。求所有得分和，结果模998244353。 算法分析令Ts = n - |S|,Ts即为集合S的凸包内的点组成的集合（除顶点以外），则题目要求的是合法的Ts子集的种数，Ts最多为2^n，然后减去不合格的集合个数。首先，减去一个空集，再减去n个单点集，然后减去共线的情况（集合全在一条线段上）。 程序代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 998244353; const int maxn = 200 + 50; int n; ll p[maxn]; ll x[maxn], y[maxn]; map<pair<ll, ll>, ll> mp; void pre(){ ...
阅读全文 »

发表于   |   分类于
图论的几个重要细节和思路 分析原图建新图 是否可以转化为DAG来dp解决 用板子时端点从0开始而不是1 加边的时候注意重边的处理 注意输入一条边时，起点终点应该不一样（u != v） 无向图的边具有双向性，如果涉及具体枚举某条边的时候，要注意u->v 和 v->u都枚举一遍 Airport Express原题：Airport Express 原题大意有两种车票，商务车票和经济车票。由于经济原因，商务车票只能买一张，经济车票可以买多张。车票都是双向的。现在问从起点到终点，的最短路径，以及商务车票在哪个站点用最划算和最后花费的总时间。 算法分析对于每个给出的起点终点a，b；分别求出到a和到b的单源最短路f(x), g(X)，然后枚举商业线的边T，答案就是f(a) + T(a,b) + g(b)，如果不做商业线就是f(b)或者g(a)；维护最大值即可。注意每条边要枚举两次。 程序代码#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define pb push_back using n ...
阅读全文 »

发表于   |   分类于
原题：Uva 658 程序代码/* ①判定某些位置是否为1，如判定2、4位置为1，则转化为判断x|0101是否等于x。 ②判定某些位置是否为0，如判定2、4位置为0，则转化为判断x&1010是否等于x。 ③将某些位置转化为1，如2、4位置转化为1，则令x=x|0101。 ④将某些位置转化为0，如2、4位置转化为0，则令x=x&1010。 */ #include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int N = (1<<20)+5,K=105,INF = 1<<30; int d[N], s[K][2], t[K][2], w[K]; int n, m; char s1[K], s2[K]; bool inque[N]; void spfa(int ss){ mem(inque,false); queue<int> q; q.push( ...
阅读全文 »