精华内容
下载资源
问答
  • HDU 3571 N-dimensional Sphere 高斯消元

    千次阅读 2011-06-01 16:20:00
    根据题目意思很容易得出式子,但难点在于数据较大,10^17,且输出为整数。   大数模板,java都会超时,可耻地去看了解题报告后发现是对中间过程取模。因为数据都在10^17范围以内,所以结果也在这...

    根据题目意思很容易得出式子,但难点在于数据较大,10^17,且输出为整数。

     

    大数模板,java都会超时,可耻地去看了解题报告后发现是对中间过程取模。因为数据都在10^17范围以内,所以结果也在这范围内,找个比它大的素数即可。

     

    起初还想不明白,消完元后等式右边的结果还要除以未知数的系数,怎么能用取模呢?又可耻地去看了代码后发现其实可以让系数乘以一个数使其取模后变为1,要求出乘以的那个数则用扩展欧几里得就可以了。这样就不需要除法操作了。思维差距啊……

     

    最后一直没搞明白为什么非要把数据都加上一个极大值使得负数变正数。取模等过程中正负应该都无所谓的啊,可改了后就WA。。。求解。

     

    展开全文
  • 题目意思:给出 1 * n field,编号从左至右依次为 1,2,...,n。问射 m 枪之后(第 i 次射中编号 xi,则 xi 这一点是不能放置船只!),能不能将 k 只 1 * a 小船放到这些没有经过被射中编号 field 中 。...

    题目链接:http://codeforces.com/problemset/problem/567/D

    题目意思:给出 1 * n 的 field,编号从左至右依次为 1,2,...,n。问射 m 枪之后(第 i 次射中编号 xi,则 xi 这一点是不能放置船只的!),能不能将 k 只 1 * a 的小船放到这些没有经过被射中编号的 field 中 。由于Alice 每次 shoot 的时候都会说 miss 的,即没有打中,你需要判断第几次shoot 使得整个field 不能放置 k 只 小船,如果都能放,最终输出 - 1.

      首先,外国人的题解真是好严谨,又好体~~~

     

      有几点需要解释下。事实上这几点也困惑了我好久 0.0

      (1)一开始整个区间 (n+1)/(a+1) 可能好多人还是不太明白。那么列条方程帮助理解吧。假设在[1, n] 中最多可以放置 x 只船,可以列出 x * a + (x - 1) = n,于是经若干合并同类项,就可以得到 x =  (n+1)/(a+1)。或者可以按题解者那样理解,由于最大放船数肯定是从最边边开始放的啦,然后间隔一个shoot之后随之放入另一只船。。。很容易知道,每只船占的空间至少为a+1(最尾那只可能不止又或者是a(可喜可贺啊)),那么我们可以虚拟多一个编号为 n+1 的 field。所以整个长度就为 (n+1)/ (a+1)了,很神奇哇~

      (2)(r-l+2)/(a+1) 是啥来的?!如果理解了第一点就很容易明白了。我们shoot完之后,这个 shoot 将空间一分为二了,选定的空间我们用集合set 的 upper_bound来找,返回的是 r ,前一个就是  l 。r-l+1很容易理解(不理解可以私聊我),再+1 就是虚拟的那个field。第(1)点已经说了,紧挨着边放置是最优解的条件!最后记得把shoot这个编号放入下一轮备选空间上。

      (3)空间中为什么要减完再加。因为有个shoot将空间一分为二嘛~~这个时候可以放置的船已经不是原来的[l, r] 这么多了。而是被分开的左区间[l, x-1] 和 [x+1, r] 之和这么多。

      

     1 #include <iostream>
     2 #include <cstring>
     3 #include <cstdio>
     4 #include <algorithm>
     5 #include <set>
     6 using namespace std;
     7 
     8 set<int> s;
     9 
    10 int main()
    11 {
    12     #ifndef ONLINE_JUDGE
    13         freopen("in.txt", "r", stdin);
    14     #endif // ONLINE_JUDGE
    15 
    16     int m, n, a, k, x;
    17     while (scanf("%d%d%d", &n, &k, &a) != EOF) {
    18         scanf("%d", &m);
    19         s.clear();
    20         s.insert(0), s.insert(n+1);   // 实现虚拟长度的小技巧
    21         int sum = (n+1) / (a+1); 
    22         int ans = -1, f = 0;
    23         for (int i = 1; i <= m; i++) {
    24             scanf("%d", &x);
    25             set<int>::iterator it = s.upper_bound(x);
    26             int r = *it;
    27             int l = *(--it);
    28             sum = sum - (r-l)/(a+1) +(x-l)/(a+1) + (r-x)/(a+1);
    29 
    30             if (sum < k && !f) {
    31                 ans = i;
    32                 f = 1;
    33             }
    34             s.insert(x);
    35         }
    36         printf("%d\n", ans);
    37     }
    38     return 0;
    39 }

      

      

    转载于:https://www.cnblogs.com/windysai/p/4714806.html

    展开全文
  • 题目的意思是: 现在有一个长度为n,宽为1的方格,在上面可以放大小为1*a船,然后输入为n,k,a;分别为平地的大小,船的数量,船的长度。 一个叫alice的人已经在地图上摆好了船的位置。 然后bob总共可以有m次...

    题目的意思是:

    现在有一个长度为n,宽为1的方格,在上面可以放大小为1*a船,然后输入为n,k,a;分别为平地的大小,船的数量,船的长度。

    一个叫alice的人已经在地图上摆好了船的位置。

    然后bob总共可以有m次攻击的机会,然后他每次攻击的点为xi,但是alice并不会告诉它有没有打中(也就是说每次都认为他是miss的),问你,bob可以在第几次攻击的时候推测出alice在撒谎,如果推测不出来则输出-1.

    这里每两条相邻的船不能相互接壤。

    思路:

    用set来维护每一段的区间。

    首先,我们最多可以放sum=(n+1)/(a+1)条船。

    这个公式是怎么来的呢? 我们可以这样想: 因为船不能接壤,所以当有k条船时,n最少为k*(a+1)-1;  然后反解就能得到答案了。

    然后我们每次攻击一个点t,就相当于把线段从中间隔开来了,我们要找到离点t最近的左右端点t1,t2,因为它们中间还插了一个t,所以就相当于t1,t2被分割开来了。

    然后当前船的数量可以由另一个公式得到: sum=sum-(t2-t1)/(a+1)+(t-t1)/(a+1)+(t2-t)/(a+1) ;这里的意思就相当于把原先的那个区间的部分减掉,然后再加上后来分开来后的区间所能容纳的船的最大数目。

    当sum<k的时候,就说明此时alice在撒谎。

    这里查找左右端点用的是二分查找。

    #include<stdio.h>
    #include<string.h>
    #include<iostream>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<set>
    #include<map>
    #include<stack>
    using namespace std;
    #define me rng_58
    #define maxn 200055
    set<int> st;
    set<int>::iterator it;
    int main(){
    	int n,k,a,m,i;
    	scanf("%d%d%d",&n,&k,&a);
    	scanf("%d",&m);
    	st.insert(0); 
    	st.insert(n+1);
    	int sum=(n+1)/(a+1);
    	int ans=-1;
    	for(i=1;i<=m;i++){
    		int t;
    		scanf("%d",&t);
    		it=st.upper_bound(t);
    		int t1=*it;
    		it--;				//这里为什么能减,学c++后再解答;
    		int t2=*it;
    		st.insert(t);		//这里只要把t压进去就好啦!!!小心!!! 
    		sum=sum-(t1-t2)/(a+1)+(t-t2)/(a+1)+(t1-t)/(a+1);
    		if(sum<k){
    			ans=i;
    			break;
    		}
    	}
    	printf("%d\n",ans);
    }
    /*
    5000 1660 2
    20
    1 100 18 102 300 81 19 25 44 88 1337 4999 1054 1203 91 16 164 914 1419 1487
    */

    佩服那些能够想出来的人。Wish I can become the same like U one day!
    展开全文
  • 所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。 简单来说就是:在样本空间(训练集)中,与待测样本最相邻(通过距离度量)的k个样本中,大多数属于某一个类别,则该待测...

    学习整理,部分描述来源于网络

    1. 概述

    1.1 定义

    k近邻法(k-nearest neighbor,k-NN)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。

    简单来说就是:在样本空间(训练集)中,与待测样本最相邻(通过距离度量)的k个样本中,大多数属于某一个类别,则该待测样本也属于这个类别,并具有这个类别上样本的特性。

    从上面的定义中可以提炼出k-NN的三个基本要素:

    1. “最相邻”-距离度量LpL_p距离 / Minkowski距离;
    2. “k个样本”-k值的选择:会决定模型的复杂程度;
    3. “大多数属于”-分类决策规则:k-NN中的分类决策规则往往是多数表决规则(majority voting rule)。

    1.2 示例

    引用百度百科中对k-NN的一个直观的例子来解释。

    在这里插入图片描述

    右图中,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?
    如果K=3,由于红色三角形所占比例为2/3(实线圈内),绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5(虚线圈内),因此绿色圆被赋予蓝色四方形类。

    2. k-NN实现:kd树

    实现k近邻法时,主要考虑的问题是如何对训练数据进行快速k近邻搜索,这点在特征空间的维数大及训练数据容量大时尤为必要。为了提高k近邻搜索的效率,可以考虑使用特殊的结构存储训练数据,以减少计算距离的次数。具体方法很多,下面介绍其中的kd树(kd-tree)方法。

    2.1 构造kd树

    有很多种方法可以选择轴垂直分割面( axis-aligned splitting planes ),所以有很多种创建k-d树的方法。 最典型的方法如下:

    • 随着树的深度轮流选择轴当作分割面。(例如:在三维空间中根节点是 x 轴垂直分割面,其子节点皆为 y 轴垂直分割面,其孙节点皆为 z 轴垂直分割面,其曾孙节点则皆为 x 轴垂直分割面,依此类推。);
    • 在该维度上选择中位数为划分点(pivot)对该数据集合进行划分,得到两个子集合,同时创建一个树节点node,用于存储;
    • 对两个子集合重复前面两个步骤的过程,直至所有子集合都不能再划分为止。

    此外,也有一些其它方法用来选择垂直分割面,如:在k维数据集合中选择具有最大方差的维度k等。

    这个方法产生一个平衡的k-d树。每个叶节点的高度都十分接近。然而,平衡的树不一定对每个应用都是最佳的。

    举个例子:

    假设有6个二维空间中的数据点(下图中黑点):(2,3),(5,4),(9,6),(4,7),(8,1),(7,2){(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
    在这里插入图片描述

    图 二维数据kd树空间划分示意图

    确定上图中分割线的过程就是构建kd树的过程,具体步骤如下:
    (1)分别计算x、y方向上数据的方差,得知x方向上的方差最大;
    (2)根据x轴方向数值2,5,9,4,8,7{2,5,9,4,8,7}得中位数为7,所以根节点的data为(7,2)(7,2),并确定超平面为图中x=7的竖线;
    (3)通过超平面x=7将原数据集分割为左子空间(x7x\leq 7的部分)和右子空间(剩余部分)。 (4)递归整个过程可完成kd树的构建。
    在这里插入图片描述

    图 上述实例生成的kd树

    2.2 搜索kd树(最邻近搜索)

    最邻近搜索用来找出在树中与输入点最接近的点。k-d树最邻近搜索的过程如下:

    1. 从根节点开始,递归的往下移。往左还是往右的决定方法与插入元素的方法一样(如果输入点在分区面的左边则进入左子节点,在右边则进入右子节点)。
    2. 一旦移动到叶节点,将该节点当作"当前最佳点"。
    3. 解开递归,并对每个经过的节点运行下列步骤:
      1. 如果当前所在点比当前最佳点更靠近输入点,则将其变为当前最佳点。
      2. 检查另一边子树有没有更近的点,如果有则从该节点往下找。
    4. 当根节点搜索完毕后完成最邻近搜索。

    举个例子:

    在前面例子中构建的kd树中搜索点(2.1,3.1)(2.1,3.1)

    为了找到真正的最近邻,还需要进行“回溯”操作:算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从(7,2)点开始进行二叉查找,然后到达(5,4),最后到达(2,3),此时搜索路径中的节点为<(7,2),(5,4),(2,3)>,首先以(2,3)作为当前最近邻点,计算其到查询点(2.1,3.1)的距离为0.1414,然后回溯到其父节点(5,4),并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以(2.1,3.1)为圆心,以0.1414为半径画圆,如图4所示。发现该圆并不和超平面y = 4交割,因此不用进入(5,4)节点右子空间中去搜索。
    在这里插入图片描述

    图 查找(2.1,3.1)点的两次回溯判断

    再回溯到(7,2),以(2.1,3.1)为圆心,以0.1414为半径的圆更不会与x = 7超平面交割,因此不用进入(7,2)右子空间进行查找。至此,搜索路径中的节点已经全部回溯完,结束整个搜索,返回最近邻点(2,3),最近距离为0.1414。

    一个复杂点的例子如查找点为(2,4.5)。

    同样先进行二叉查找,先从(7,2)查找到(5,4)节点,在进行查找时是由y = 4为分割超平面的,由于查找点为y值为4.5,因此进入右子空间查找到(4,7),形成搜索路径<(7,2),(5,4),(4,7)>,取(4,7)为当前最近邻点,计算其与目标查找点的距离为3.202。然后回溯到(5,4),计算其与查找点之间的距离为3.041。以(2,4.5)为圆心,以3.041为半径作圆,如图5所示。可见该圆和y = 4超平面交割,所以需要进入(5,4)左子空间进行查找。此时需将(2,3)节点加入搜索路径中得<(7,2),(2,3)>。回溯至(2,3)叶子节点,(2,3)距离(2,4.5)比(5,4)要近,所以最近邻点更新为(2,3),最近距离更新为1.5。回溯至(7,2),以(2,4.5)为圆心1.5为半径作圆,并不和x = 7分割超平面交割,如图6所示。至此,搜索路径回溯完。返回最近邻点(2,3),最近距离1.5。

    4. 代码实现(Python)

    可参考这里的实现,写得很棒。

    参考

    [1] 《统计学习方法》第三章. 李航
    [2] https://baike.baidu.com/item/kd-tree/2302515?fr=aladdin
    [3] https://www.jianshu.com/p/29b9dd354793

    展开全文
  • 图像隐写术中HUGO算法基本原理

    千次阅读 热门讨论 2018-11-01 17:47:40
    HUGO的意思是Highly Undetectable steGO,是一种当前常用的stegnography的方法。 文献出处 Tomas Pevny, Tomas Filler, Patrick Bas. Using High-Dimensional Image Models to Perform Highly Undetectable ...
  • ndarray含义是The N-dimensional array,意思就是N维数组 注:默认import numpy as np已经写在每段代码前,不再重复写入 1. 依据现有数据来创建 ndarray 【例1-1】通过array()函数进行创建。 def array(p_ob
  • 张量的意思是一个多维数组,它是标量、向量、矩阵的高维扩展。标量可以称为 0 维张量,向量可以称为1维张量,矩阵可以称为2维张量,RGB图像可以表示3维张量。你可以把张量看作多维数组 2. Tensor几种常见的形式有...
  • IE hasLayout

    2019-10-02 13:45:23
    John Gallant 和 Holly Bergevin 把这些问题归类为"尺寸臭虫(dimensional bugs)",意思是这些臭虫可以通过赋予相应元素某个宽度或高度解决。 “Layout"是一个 Internet Explorer for Windows...
  • TensorFlow中张量(tensor)理解

    千次阅读 2019-09-16 22:32:23
    TensorFlow字面意思——张量流动,即保持计算节点不变让数据以张量形式进行流动。张量tensor可以是一个变量/数组/多维数组等,可以想象成一个n维(n-dimensional数组、序列或列表。 tensor有三个属性:数据...
  • 题目意思是有一个螺旋存储正整数矩阵,求矩阵中任意数到数字1曼哈顿距离 矩阵如下图: 原题目:【再次吐槽。。】 Spiral Memory You come across an experimental new kind of memory stored on an infinite ...
  • 几句话之KNN和Kd-tree

    2019-11-12 13:36:45
    找一下周围的邻居们,看邻居们是什么,就大概知道自己是什么了,有点“物以类聚,人以群分”的意思。 kd-tree(k-dimensional树的简称) 分割k维空间的数据。找邻居的方法比KNN先进了一些,其余的都一样。 找邻居: ...
  • embedding_lookup从表面意思看就是一个查找单词对应词向量表, embeddings参数:词跟词向量对应表 train_inputs参数:需要转换文本(int类型) 类似下面操作:embeddings = np.random.random([1024, 64])...
  • IE layout

    2011-09-29 11:32:10
    介绍 Internet Explorer 中有很多奇怪渲染问题可以通过赋予其“layout”得到解决。John Gallant 和 Holly Bergevin 把这些问题归类为“尺寸bug(dimensional bugs)”,意思是这些 bug 可以通过赋予相应元
  • 因果分析,PC算法(PC Algorithm)

    千次阅读 2020-09-07 10:40:01
    PC Algorithm 理想情况(知道所有条件独立关系) Estimating High-Dimensional Directed Acyclic Graphs with the PC...校正其它变量后某一变量与另一变量的相关关系,校正的意思可以理解为假定其它变量都取值为均数 服
  • John Gallant 和 Holly Bergevin 把这些问题归类为”尺寸臭虫(dimensional bugs)”,意思是这些臭虫可以通过赋予相应元素某个宽度或高度解决。 元素是否具有”layout”可能会引发如下一些问题: [color...
  • [译文]On having layout

    2008-12-30 20:44:31
    Bergevin 把这些问题归类为“尺寸bug(dimensional bugs)”,意思是这些 bug 可以通过赋予相应元素某个宽度或高度解决。这便引出关于“layout”一个问题:为什么它会改变元素渲染特性,为什么它会影响到元素之间...
  • On having layout

    2010-03-06 20:25:00
    John Gallant 和 Holly Bergevin 把这些问题归类为“尺寸bug(dimensional bugs)”,意思是这些 bug 可以通过赋予相应元素某个宽度或高度解决。这便引出关于“layout”一个问题:为什么它会改变元素渲染特性,为....
  • IE layout详解

    2013-11-29 22:02:00
    Internet Explorer 中有很多奇怪渲染问题可以给他一个”layout”得到解决,John Gallant 和 Holly Bergevin把他归类为“dimensional bugs”(尺寸bug或者尺寸臭虫),意思是可以给对应元素赋予宽度和高度解决;...
  • 22222

    2011-11-09 11:19:42
    On having layout 本文修订中 当前版本:rev....Internet Explorer 中有很多奇怪渲染问题可以通过赋予其...John Gallant 和 Holly Bergevin 把这些问题归类为“尺寸bug(dimensional bugs)”,意思是这些 bu
  • IE中layout

    2016-11-19 20:47:56
    引言:Internet Explorer 中有很多奇怪渲染问题可以给他一个”layout”得到解决,John Gallant 和 Holly Bergevin把他归类为“dimensional bugs”(尺寸bug或者尺寸臭虫),意思是可以给对应元素赋予宽度和高度...
  • haslayout

    2015-03-02 23:55:00
    John Gallant 和 Holly Bergevin 把这些问题归类为”尺寸臭虫(dimensional bugs)”[32],意思是这些臭虫可以通过赋予相应元素某个宽度或高度解决。 “Layout”是一个 Internet Explorer for Win...
  • 首先2D,3D D 是什么意思?D 全称是Dimensional,翻译中文为维度。中文解译2D,3D 为二维,三维。 2. 2D 和3D 区别 如果从数学,物理角度出发考虑,大家就很容易理解,二维只有x,y 两个轴,比如一张画,一张相片。 ...

空空如也

空空如也

1 2
收藏数 28
精华内容 11
关键字:

dimensional的意思