- 浏览: 120708 次
- 性别:
- 来自: 北京
最新评论
“精确覆盖”问题
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #define out(v) cout << #v << ": " << (v) << endl using namespace std; typedef long long LL; const int max_size = 1005 * 105; const int maxint = 0x3f3f3f3f; int L[max_size], R[max_size], U[max_size], D[max_size], CH[max_size], RH[max_size]; int S[1005], O[1005]; int head, size; void remove(const int &c) { //remove column c and all row i that A[i][c] == 1 L[R[c]] = L[c]; R[L[c]] = R[c]; //remove column c; for (int i = D[c]; i != c; i = D[i]) { //remove i that A[i][c] == 1 for (int j = R[i]; j != i; j = R[j]) { U[D[j]] = U[j]; D[U[j]] = D[j]; --S[CH[j]]; //decrease the count of column C[j]; } } } void resume(const int &c) { for (int i = U[c]; i != c; i = U[i]) { for (int j = L[i]; j != i; j = L[j]) { ++S[CH[j]]; U[D[j]] = j; D[U[j]] = j; } } L[R[c]] = c; R[L[c]] = c; } int len; bool dfs(const int &k) { //cout << "new DFS" << endl; if (R[head] == head) { //One of the answers has been found. return true; } int s(maxint), c; //out(head); for (int t = R[head]; t != head; t = R[t]) { //out(t); out(R[t]); //select the column c which has the fewest number of element. if (S[t] < s) { s = S[t]; c = t; } } //cout << "remove " << c << endl; remove(c); for (int i = D[c]; i != c; i = D[i]) { O[k] = i; //record the answer. len = k; for (int j = R[i]; j != i; j = R[j]) { remove(CH[j]); } if (dfs(k + 1)) { return true; } for (int j = L[i]; j != i; j = L[j]) { resume(CH[j]); } } resume(c); return false; } int node(int up, int down, int left, int right) { U[size] = up, D[size] = down; L[size] = left, R[size] = right; D[up] = U[down] = R[left] = L[right] = size; return size++; } void init(int M) { size = 0; head = node(0, 0, 0, 0); for (int j = 1; j <= M; ++j) { node(j, j, L[head], head); CH[j] = j, S[j] = 0; } } int main() { int N, M, cnt; while (scanf("%d%d", &N, &M) != EOF) { init(M); for (int i = 1; i <= N; ++i) { scanf("%d", &cnt); int row = -1; while (cnt--) { int j; scanf("%d", &j); CH[size] = j, ++S[j]; if (row == -1) { row = node(U[CH[j]], CH[j], size, size); RH[row] = i; } else { int k = node(U[CH[j]], CH[j], L[row], row); RH[k] = i; } } } //out("DFS"); bool ans = dfs(1); if (ans) { printf("%d", len); for (int i = 1; i <= len; ++i) printf(" %d", RH[O[i]]); printf("\n"); } else { printf("NO\n"); } } return 0; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1188/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 867线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 890线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 944写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 1012转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1223封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 828终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 649写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1175源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 837import java.util.*; import j ... -
整数划分
2010-10-07 10:38 860#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 1011// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1073typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1168最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1338Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 810static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 921标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hdu 3498
2010-08-11 16:48 1079“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1028推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ... -
RMQ模板
2010-07-28 11:04 1222/* * Author: rush * Creat ...
相关推荐
3. hust-1017.cpp:这个文件名暗示它可能是华中科技大学(HUST)在线评测系统的一个问题的解决方案。尽管具体问题内容未知,但根据文件名,我们可以推测这同样是一个需要用到高效搜索的题目,DLX算法的引入可能是...
DLX是一种32位精简指令集计算机(RISC)架构,其特点是可以仅用三种指令格式来管理。DLX的核心是一个固定的定点单元(FXU),并且它还包括一个浮点数扩展。DLX指令集架构主要由以下几个知识点组成: 1. DLX架构基础...
标题中的"dlx.zip_DLX_cpu dlx_dlx c++_vhdl_vhdl dlx"表明这个压缩包主要涉及的是DLX处理器相关的项目,其中包括CPU的设计、编程以及VHDL代码实现。DLX是一种简单的RISC(精简指令集计算机)架构,常用于教学和实验...
**DLX汇编器模拟器**是一款专为学习和测试DLX指令集设计的实用工具。DLX(Davis Little eXtended)是RISC(精简指令集计算机)架构的一种,由计算机科学家David A. Patterson教授提出,常用于教学目的,让学生了解...
"MIPS-DLX模拟器"是一款基于Java编程语言开发的计算机体系结构教学工具,主要用于模拟DLX处理器的工作原理。DLX(Dense Logic eXtended)是计算机体系结构领域中一个简化的RISC(Reduced Instruction Set Computer)...
【LPE-DLX 经典】是一款深受IT专业人员喜爱的工具集合,它主要用于系统维护、故障排查和性能优化。LPE-DLX的名字来源于“Linux Penetration and Exploitation Deluxe”的缩写,虽然其名称暗示了它可能与黑客攻击和...
DLX是一种特定的指令集架构(ISA),它主要用于教学和研究目的,以帮助理解计算机系统设计的基本原理。DLX是由计算机科学家David A. Patterson和John L. Hennessy设计的,作为他们教材《计算机体系结构:量化方法》...
标题“比较好用的DLX模拟器”指的是一个针对MIPS DLX架构设计的模拟器,该模拟器在功能性和易用性上具有一定的优势。描述中的“大作业写的”可能意味着这是一个学术项目或者课程作业,表明作者在完成这个模拟器时...
**DLX算法详解** DLX( Dancing Links )算法,由计算机科学家Donald Knuth提出,是一种在图论中用于解决完全多对一匹配问题的高效算法。它在回溯搜索中展现出优秀的性能,尤其适用于解决0-1背包、 Exact Cover 和...
**DLX模拟器DlxSimulator** DLX模拟器DlxSimulator是一款专门用于执行基于DLX指令集架构的汇编程序的软件工具。DLX是计算机体系结构中的一种简化模型,由计算机科学家David A. Patterson教授设计,常用于教学和研究...
用于修改H1、H2步步高学习机内部DLX文件内的图片,从而达到修改学习机内部程序图片显示的效果
在研究计算机体系结构的实验中,DLX(Digital-Logic eXperiment)实验报告为我们提供了一系列关于使用DLX汇编语言编程的实践内容和分析。DLX是一种教学用的简化精简指令集计算机(RISC)处理器的架构,常用于计算机...
标题中的“dlx.zip_DLX_MIPS_dlx cpu pipelin”指的是一个关于DLX处理器的MIPS流水线实现的压缩包文件。这个压缩包可能包含了罗晓华同学完成的一个DLX处理器模拟器,用于理解MIPS架构下的指令流水线工作原理。 首先...
《DLX体系仿真与开发详解》 在计算机科学领域,体系结构仿真是一种重要的技术,它允许我们模拟和分析特定的处理器架构,以便于理解和优化其性能。本文将深入探讨DLX处理器的实现,以及如何利用Visual C++进行体系...
《DLX模拟器及教程》是一份专注于计算机系统结构、体系设计和实验模拟技术的教育资源。DLX是一种简化版的RISC(精简指令集计算机)架构,常用于教学和研究,让学生能深入理解计算机底层的工作原理。TMS320F2812是一...
"DLX指令集(汇编)" DLX指令集是computer science中非常重要的一部分,深入了解DLX指令集对了解汇编语言有很大的帮助。本文档将对DLX指令集进行详细的介绍,包括指令集的组成、寄存器的使用、立即数的表示方式等。...
### DLX处理器浮点数流水线性能的研究 #### 一、引言 DLX处理器作为一种虚拟的32位微处理机系统结构,在计算机系统结构的教学和研究领域具有重要的地位。由John L. Hennessy(斯坦福大学)和David A. Patterson...
dlx语言写的求和运算,计算机系统结构试验
标题中的"DLX_Links_DLX_"暗示了我们讨论的主题是关于一种名为"Dancing Links"(跳舞链)的算法,通常简称为DLX。这个算法是由Donald Knuth提出的一种高效解决完全背包问题、数独问题和其他一系列组合优化问题的方法...
《风铃DX(WindLX)模拟器与DLX处理器实验指南》 本文将深入探讨风铃DX(WindLX)模拟器以及与其相关的DLX处理器实验。DLX处理器是一种教学用的精简指令集计算机(RISC)架构,由计算机科学家David A. Patterson...