发表于 | 分类于 | 阅读次数:
阅读全文 »

发表于 | 分类于 | 阅读次数:

1. 题目链接

[loj 6226. 「网络流 24 题」骑士共存问题]

2. 题目描述

Problem Description

3. 解题思路

题目中要求如果一个顶点被选择，那么8个方向上的顶点就不能被选择。显然，这很像二分图的染色问题。
将每个非障碍的顶点与其8个方向上的非障碍顶点连一条边，那么本题就是一个求最大独立集的问题，而且是一个求二分图的最大独立集的问题。
为什么是二分图呢？可以从下面两条性质来分析：

  • 对于任意节点$u$，不可能经过奇数步回到节点$u$，实际上，这就是 匈牙利算法 Hungary 的进行二分图的判断的主要思想；
  • 按照题目中那个图，将所有顶点划分成红色、黄色两类节点，可以发现同色的节点之间没有边。

而二分图上有很好的性质，比如：

  • 最大匹配数 = 最小点覆盖；
  • 最大独立集 = 最小边覆盖 = 顶点数 $\lvert V \lvert$ - 最大匹配数；
  • DAG 的最小路径覆盖数 = DAG 图中的节点数 - 相应二分图中的最大匹配数。
    • DAG 的最小路径覆盖是指找最小数目的互相不相交的有向路径，满足 DAG 的所有顶点都被覆盖。
    • DAG 对应的二分图这样构造：对于 DAG 中的一个顶点 $p$，二分图中有两个顶点 $p$ 和 $p’$，对应 DAG 中的一条有向边 $p\to q$，二分图中有 $p\to q’$ 的一条无向边。二分图中 $p$ 属于 $S$ 集合，$p’$ 属于 $T$ 集合.
  • ……

求二分图的最大匹配数的方法有 匈牙利算法（复杂度$\mathcal O(VE)$） 和 网络流（代表算法就是Dinic/Hopcroft-carp 算法，复杂度$\mathcal O(\sqrt{V}E)$）。

阅读全文 »

发表于 | 分类于 | 阅读次数:

1. 题目链接

[hdu 5988. Coding Contest]

2. 题目描述

有 $N$ 个点，$M$ 条边的有向图 $(N\le 100, M\le 5000)$。任意一个点 $i$ 上有$s_i$ 个人，$b_i$ 份食物$(s_i, b_i\le 200)$。

任意一条边 $i$ 有几个属性 $u_i, v_i, c_i, p_i$ $(c_i\le 100, 0\lt p_i\lt 1)$。$u_i, v_i$ 分别表示有向边的两个顶点编号；$c_i$ 表示这条边的最大容量（最多允许几个人通过）；点$u_i$ 中的每个人可以沿着这条有向边移动到点 $v_i$，但是除了第一个经过这条边的人不会破坏这条边，剩下的人都会有 $p_i$ 的概率把这条边破坏。图中只要有一条边被破坏了，就认为图被破坏了。

现在需要保证所有人都能拿到一份食物的情况下，求出图被破坏的最小概率。

数据范围：

3. 解题思路

主要思路：拆边 + 对数函数将积性函数转为和性函数 + zkw 最小费用最大流。

阅读全文 »

发表于 | 分类于 | 阅读次数:

Overview

搜索/广告-徐

  • 置信度、支持度
  • 决策树
  • 监督学习评价指标：Accuracy/Precision/Recall/F1
  • SVD 分解
    • Fold-in 算法
  • AdaBoost算法
  • BM25
  • 语言模型Language Model for IR(LM4IR)、平滑化
  • 排序学习：基于有序对
  • 排序学习评价方法：MAP、NDCG(Normalized Discounted Cumulative Gain)
  • TF-IDF计算公式
  • 线性感知器
  • SVM
    • 硬边距：
    • 软边距: 松弛变量$\xi$、参数$C$

图数据挖掘-沈

  • 无标度网络：数据分布
  • 复杂网络的小世界特性
  • 连边关系的结构平衡
  • 影响最大化问题
  • PageRank
  • 图聚类算法：Normalized Cut、模块度优化、InfoMap、非负矩阵分解等

推荐系统-罗

  • 矩阵分解的核心思想
  • 矩阵分解和U-U CF、I-I CF的区别
  • U-U CF 的评分
  • 相关度的度量：Pearson Correlation
阅读全文 »

发表于 | 分类于 | 阅读次数:
Nearest Neighbors# 无监督最近邻： 返回每个数据样本点的$k$近邻节点或者距离，无训练集 应用：流行学习(manifold learning)、谱聚类(spectral clustering) 有监督最近邻 返回训练集中的$k$近邻 应用：数据分类/回归 VC-Dimen ...
阅读全文 »

发表于 | 分类于 | 阅读次数:

Github 大文件删除之后依旧push不上

Counting objects: 24, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (23/23), done.
Writing objects: 100% (24/24), 201.06 MiB | 1.36 MiB/s, done.
Total 24 (delta 5), reused 0 (delta 0)
remote: Resolving deltas: 100% (5/5), completed with 2 local objects.
remote: warning: File model/news.model is 73.08 MB; this is larger than GitHub’s recommended maximum file size of 50.00 MB
remote: warning: File data/user_click_data.tar.gz is 74.27 MB; this is larger than GitHub’s recommended maximum file size of 50.00 MB
remote: error: GH001: Large files detected. You may want to try Git Large File Storage - https://git-lfs.github.com.
remote: error: Trace: a092a0b034ec52cbdd5c6fda7852c00c
remote: error: See http://git.io/iEPt8g for more information.
remote: error: File src/data-utils/train_original.csv is 155.62 MB; this exceeds GitHub’s file size limit of 100.00 MB
To github.com:XingwXiong/NewsRS.git
! [remote rejected] master -> master (pre-receive hook declined)
error: failed to push some refs to ‘git@github.com:XingwXiong/NewsRS.git’

解决办法:

1
2
3
$ git filter-branch --index-filter \
    'git rm -r --cached --ignore-unmatch src/data-utils/train_original.csv' HEAD
$ git push origin master

阅读全文 »