gwq5210-CSDN博客

原创舞蹈链(Dancing Links) 解决精确覆盖问题 hustoj 1017 Exact cover zoj 3209 Treasure Map

一，舞蹈链简介（参考这里）舞蹈链是Donald Knuth提出的技术，也叫做DLX，目的是快速实现

2015-09-17 00:17:33 1143

原创 poj 1085 Triangle War 1568 Find the Winning Move 极大极小搜索 alpha-beta剪枝

一，极大极小搜索及alpha-beta剪枝

2015-09-14 16:29:25 1090

原创 uvaoj 1600 Patrol Robot 10603 Fill BFS

uvaoj 1600 Patrol Robot一个巡逻机器人在一个n*m的网格上从左上角(1,1)走到右下角(n,m)。格子中有的地方是空地，用0表示，有的地方是障碍，用1表示。机器人每次可以往相邻的四个方向走，每次这个机器人不能连续穿越k个障碍，也就是说，能连续穿越障碍的最大个数是k，求从起点到终点的最短路径长度。起点和终点保证是空地。在每一个格子，需要用一个三元组(x,y,k)来表示，即在位置(

2015-09-01 10:48:10 2552

原创 poj 2286 The Rotation Game IDA*算法

一，算法思路(参考这里) 迭代加深算法：总体上按照深度优先方法进行，对搜索深度需要给出一个限制dm，当深度达到了dm的时候，如果还没有找到解答，就停止对改分支的搜索。dm从1开始，从小到大一次增大（因此称为迭代加深）。迭代加深搜索是最优的也是完备的。IDA*算法：迭代加深的A*算法其实就是将A*和迭代加深算法结合起来。优先将初始状态结点的估价函数H值设置为阈值maxH，然后进行深度优先

2015-09-01 10:34:06 833

原创 poj 2449Remmarguts' Date uvaoj 10740 not the best dijkstra或spfa或bellman-ford k短路 A*

一，基础知识图的前向星和链式前向星表示（参考这里）前向星是一种特殊的边集数组，我们把边集数组中每一条边的起点按照从小到大排序，如果起点相同就按照终点从小到大排序，并记录下以某个点为起点的所有边在数组中的起始位置和存储长度，那么前向星就构造好了。用len[i]和head[i]分别表示以点i为起点的边的个数和起始位置。因为前向星有排序动作，所以最快是nlogn级别的。但是用链式前向星就可以避免排

2015-08-31 15:07:28 742

原创 poj 1729 Jack and Jill 1376 Robot 1324 Holedox Moving 1475 Pushing Boxes bfs + a*

poj 1729 Jack and JillJack和Jill要从各自的家走到各自的学校，但是他们俩各自不喜欢对方，因此，需要你找到两个人行走的路线，使得他们路线中两个人最近的直线距离最长。单位时间内，每个人都可以走到相邻的四个格子中。只考虑移动过后两个人所在位置的直线距离。走过的路可以来回走，到达学校之后就不能离开学校了。其中H，S分别表示Jack的家和学校；h，s分别表示jill的家和学校；

2015-08-29 20:53:26 2138

原创 poj 1077 hdu 1043 Eight 八数码问题 DBFS（双向广度优先搜索）a*算法康拓展开

一，八数码问题简介编号为1到8的8个正方形滑块被摆成3行3列（有一个格子留空），可以每次把与空格相邻（有公共边）的滑块移动到空格中，而它原来的位置就成了新的空格。给定局面，计算出从当前状态移动到目标状态的最少步数。如将八数码从左到有从上到下的数字列出来，没有空格用0表示（其实也可以用9表示），可以表示为： 2 6 4 1 3 7 0 5 8 -> 8 1 5 7 3 6 4 0 2 在这里我们

2015-08-29 20:40:28 1638

原创 hdu 3068 manacher算法

manacher算法可以在O(n)的时间里找出最长回文子串。具体的manacher算法可以看这里：manacher算法/************************************************************************* > File Name: 3068.cpp > Author: gwq > Mail: gwq5210@q

2015-07-26 20:58:28 531

原创 NBUT 1583 贪心

NBUT 1583 贪心暑期集训实在太热了，机房里的空调有时还不给力。所以有些新生想出去买饮料，又有些新生出去上厕所，有些新生出去洗把脸等等等等…Zyvas坐在自己的座位上就这样看着他们走进来走出去，他突然想知道这个机房里原先至少有多少新生。输入第一行输入一个数 N(0 < N < 10,000). 接下来N行，每行有2个数 P(P == 0 || P == 1)和 M(0 < M < 100

2015-05-03 21:57:24 635

原创 NBUT 1582 比赛吃鸡腿 wythoff博弈

NBUT 1582 比赛吃鸡腿 wythoff博弈关于博弈的可以看这里。这是裸的wythoff，没啥意思，不过当时知道结论，就是想了好久不知道怎么判定，在这里记录一下。代码：/************************************************************************* > File Name: f.cpp > Author

2015-05-03 21:51:19 659

原创 BNUT 1581 233333333 数位dp

BNUT 1581 233333333 数位dp求n到m之间的搞笑数字，包含23或5的数字是搞笑数字，一个裸的数位dp。 dp[i][j][k]dp[i][j][k]表示i位数最高位上为j时，是搞笑数字的个数(k=1)(k=1)，不是搞笑数字的个数(k=0)(k=0)。代码：/*************************************************************

2015-05-03 21:38:35 579

原创 NBUT 1579 小青蛙找妈妈 dijkstra,flody最短路

NBUT 1579 小青蛙找妈妈 dijkstra，flody最短路一个坐标系上有n个点，青蛙在第一个点，青蛙妈妈在第二个点，青蛙只能在n个点之间跳来跳去，青蛙最少需要多少弹跳能力才能跳到青蛙妈妈所在的点。其实是将青蛙跳的路径上两点之间的最大距离最小化。最开始想的时候写的flody，交上去超时了，后来想到因为求的只是两点之间的，可以用dijkstra。后来学长说用的flody，不用stl就过了。代码

2015-05-03 20:53:20 636

原创 NBUT 1586 买票回家啦区间dp

NBUT 1586 买票回家啦 dp给定一个字符串，问最少删除多少个字符串可以将字符串变成一个回文串。使用区间dp。dp[i][j]dp[i][j]表示字符串s[i],⋯,s[j]s[i],\cdots ,s[j]删除最少多少个字符可以变成回文串。当s[i]==s[j]s[i]==s[j]时，dp[i][j]=min(dp[i][j],dp[i+1][j−1])dp[i][j]=min(dp[i][

2015-05-03 20:51:05 662

原创 hduoj 5223 GCD 构造检查

hduoj 5223 GCD 构造检查有一个数组A1⋯ANA_1 \cdots A_N，数组中每一个元素是在区间[1,109][1,10^9]之间。现在有Q个问题，每一个问题是GCD(ALi, ALi+1, ALi+2, ..., ARiA_{L_i},~A_{L_i + 1},~A_{L_i + 2},~...,~A_{R_i})，即给定区间的所有数的最大公约数，现在知道了每个问题和问题的答案。要

2015-05-03 11:07:27 768

翻译 mathjax简单教程（翻译）

mathjax简单教程（翻译）原文地址：mathjax basic tutorial and quick reference在任何的mathjax公式上，都可以使用右键点击公式选择”Show Math As > TeX Commands”来查看公式是怎么写出来的（包括这里）。使用$…$来产生行内公式，使用$$…$$来产生多行公式。公式∑ni=0i2=(n2+n)(2n+1)6\sum_

2015-05-02 22:54:18 4226

原创 hduoj 5214 Movie 暴力

hduoj 5214 Movie 暴力给定了n，l1，r1，a，b，c，d，按照如下公式生成一个区间，区间全部生成完成后，如果li>ri，那么将这两者交换（做的时候这里坑了）。 L i = ( L i − 1 ∗ a + b

2015-05-02 22:38:39 588

原创 hduoj 1973 Prime Path bfs

hduoj 1973 Prime Path bfs四位数的素数，改变其中一位变成另外一个素数，问最少需要多少次变换，才能将给定的一个素数变成另一个素数。思路是利用bfs，将原始素数入队，枚举改变的数字，判断是否是素数，是的话入队，直到遇到目标素数，如果到队列为空也没有变换成目标素数，那么就是不能变换到，输出Impossible。判断素数我写的是使用素数筛法，因为数据量小，也可以写一个函数来判断。代码

2015-05-02 22:12:42 611

原创 2015年腾讯阿里实习生招聘面试经历

每年毕业生找工作都是一个问题，对于个人来说，无非就是笔试和面试的问题。对于应届生来说，最头疼的或许不是笔试而是面试。对于笔试，只要自身实力过硬，一般都没有问题（退一步讲，万一笔试没过，还可以在面试的时候霸面）；对于面试，就不一样了，应届生没有接触过面试，所以对于面试可能有些害怕，面试之前会在网上搜一些面试注意事项之类的，而这些都是对所有面试的一般概括，没有什么针对性，无非就是提醒面试者注意着装、礼貌

2015-04-30 19:59:39 2394 4

原创 codeforces round 299 div2 题解

A. Tavas and Nafas 将0到99的数字变成英文的表示。处理好特殊情况就行了。#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <cstring>#include <queue>#include <stack>#include <map>#includ

2015-04-28 16:22:48 581

原创 codeforces round 291 div2 题解

A. Chewbaсca and Number对于给定的一个正整数n(1<=n<=10^18)，我们可以将这个数的某些位翻转，所谓翻转是，将数字t用数字9-t替代。经过某些替换后，我们所能得到的最小正整数是多少。题目还说数字不能以0开头，所以当9为第一个数字时，是不能进行替换的。当然，也可能有其他的理解，不过命题者的意思是这样的。其他的情况就让数字尽可能小就行了。/***************

2015-04-28 16:09:45 454

原创 2015年4月25日浙江省ACM比赛题解

A、Ace of Aces#include <stdio.h>#include <string.h>#define N 1010int num[N];int main(void){ int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); mems

2015-04-25 21:43:40 1865

原创 2015年郑州大学首届“玲珑杯”ACM新生选拔赛题解

C（C++）编译器判断给定的字符串在不在集合中，用字符串比较函数就行了。代码：/************************************************************************* > File Name: a.cpp > Author: gwq > Mail: [email protected] > Created Ti

2015-04-12 21:51:32 1554

原创 C语言笔记

C语言笔记C语言笔记参数传递机制优先级和求值顺序分支和跳转函数数组指针字符串作用域类型限定符文件IO结构联合和枚举变量相关：C99以前的C要求在一个代码块的开始处声明变量。声明语句为变量创建，标定存储空间并为其制定初始值。C99引入_Bool类型表示布尔值。它还提供stdbool.h头文件，包含这个头文件可以使用bool来代替_Bool，并把true和false定义为1

2015-04-07 10:43:03 596

原创蓝桥杯算法训练题解

1.区间k大数查询可以先排序，也可以使用快排的思想。/************************************************************************* > File Name: algo_1.cpp > Author: gwq > Mail: [email protected] > Created Time: 2014年11月08日星

2015-03-26 19:15:49 1186

原创组合数C(n,m)的求法总结，卢卡斯定理

组合数C(n,k)的求法总结与组合数有关的两个最重要内容是杨辉三角和二项式定理。杨辉三角前10行如下所示：另一方面，将(a+b)^n展开，系数正好和杨辉三角一致。一般有(a+b)^n=C(n,0)a^n+C(n,1)a^(n-1)b+...+C(n,n)b^n。给定n，如何求出(a+b)^n所有项的系数呢？方法一，递推，利用杨辉三角的性质，当前数等于上方两个数的和，

2015-01-27 19:21:20 2232

原创 uvaoj 12169 Disgruntled Judge 扩展欧几里得算法

uvaoj 12169 Disgruntled Judge 扩展欧几里得算法一个裁判，找了3个整数x1,a和b，按照递推公式xi=(axi-1+b)%10001，计算出了一个长度为2n的序列，n是测试数据的组数，然后他把n和x1，x3，。。。，x2n-1写到输入文件中，x2，x4，。。。，x2n写到输出文件中。你的任务是找出对应的x2，x4，。。。，x2n。任意输出一个合法的。如果知道了a

2015-01-27 14:15:14 569

转载欧几里得算法与扩展欧几里得算法

欧几里得算法与扩展欧几里得算法一，欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。基本算法：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。第一种证明：a可以表示成a = kb + r，则r = a mod b。假设d是a,b的一个公约数，则有d|a,

2015-01-25 11:59:50 522

原创 uvaoj 10375 Choose and divide 唯一分解定理

uvaoj 10375 Choose and divide 唯一分解定理已知C(m,n)=m!/(n!(m-n)!)，输入整数p,q,r,s（p>=q,r>=s,p,q,r,s可以使用唯一分解定理来做，用一个数组表示唯一分解式中各个素数的指数，可正可负。每乘上一个整数，就把相应的素因子指数上加上相应指数，除也一样。代码如下：/****************************

2015-01-25 10:55:55 569

原创 uvaoj 11582 Colossal Fibonacci Numbers! 求周期

uvaoj 11582 Colossal Fibonacci Numbers! 求周期输入两个非负整数a，b和正整数n（0=0。因为是对n取模，设F(i)=f(i)%n，那么当（F(i),f(i+1))重复时，整个序列就开始重复，因为余数最多有n种，所以最多n^2项就会出现重复。设周期为T，那么F(n)=F(n%T)。只需计算出0-T就可以了。代码如下：/*************

2015-01-22 12:49:30 526

原创 uvaoj 12716 GCD XOR 打表

uvaoj 12716 GCD XOR 打表输入整数n（1对于异或运算，有a^b^b=a，所以可以推出，若a^b=c，则a^c=b，可以枚举a和c，算出b，验证是否有gcd(a,b)=c，注意到c是a的约数，所以，可以使用素数筛法的方法，复杂度为nlogn。进一步可以发现，c=a-b，因为a-b=c，假设存在c使得a-b>c，那么c代码如下：/*****************

2015-01-21 21:59:56 474

原创 uvaoj 136 Ugly Numbers 优先队列使用

uvaoj 136 Ugly Numbers 优先队列使用丑数是不能被除2,3,5以外的其他素数整除的数，把丑数从小到大排列，1,2,3,4,5，6,8,9,10,12,15.......，求第1500个丑数。对于丑数x，2x，3x，5x，都是丑数，我们可以从小到大生成丑数，将生成的丑数保存起来，每次取出来最小的一个，然后生成三个丑数，但这个会重复，可以使用set去重。代码如下：/

2015-01-21 16:45:15 700

原创 uvaoj 540 Team Queue 队列模拟

uvaoj 540 Team Queue 队列模拟t个团队的人在排队，每新来一个人时，如果它有队友在排队，那么这个人就排在最后一个队友的后边，如果没有任何队友排队，那么这个人排到长队的队尾，我们可以将这个队列看做两级，一级是团队队列，一个是团队自身的队列。模拟一下就行了。代码如下：/****************************************************

2015-01-21 16:20:00 588

原创 uvaoj 12096 The SetStack Computer 集合操作用法

uvaoj 12096 The SetStack Computer 集合操作用法有一个初始为空的栈，有好多类型的操作，PUSH,DUP,UNION,INTERSECT,ADD，因为是集合的集合，所以使用STL中的set，和对set的操作函数，set_union和set_intersection，和函数inserter。代码如下：/****************************

2015-01-21 15:31:11 612

原创 uvaoj 156 Ananagrams map的基本使用

uvaoj 156 Ananagrams map的基本使用给定一些单词，找出满足如下条件的单词：该单词不能通过字母重排，得到文本中的另外其他单词，在判断满足条件时，不区分大小写，但输出时应该保留输入中的大小写。我们可以将单词都变成小写，然后将单词中的字母按照大小排列，那些不满足条件的单词就会出现多次，而满足条件的单词只会出现一次，因为要记录之前的单词，可以通过map集合来映射。代码如下

2015-01-20 15:27:03 781

原创 uvaoj 10815 Andy's First Dictionary set的基本使用

uvaoj 10815 Andy's First Dictionary set的基本使用将单词去重后按照字典序输出。代码如下：/************************************************************************* > File Name: 10815.cpp > Author: gwq > Mail: gwq5210@

2015-01-20 14:51:54 619

转载 c++中关于结构体长度的计算问题

说明：结构体的sizeof值,并不是简单的将其中各元素所占字节相加，而是要考虑到存储空间的字节对齐问题。这些问题在平时编程的时候也确实不怎么用到，但在一些笔试面试题目中出是常常出现，对sizeof我们将在另一篇文章中总结，这篇文章我们只总结结构体的sizeof，报着不到黄河心不死的决心，终于完成了总结，也算是小有收获，拿出来于大家分享，如果有什么错误或者没有理解透的地方还望能得到提点，也不

2015-01-20 13:13:43 3878

转载 c/c++中的三字符

今天看书看到这个词,书上没给解释,上网查了下,意思很"隐讳",不过总算是搞明白怎么回事了,呵呵,写下来~~~ 先用简单的话讲一下什么是trigraph吧,这样不会一上来就是没人看得懂的话,trigraph是三字母词,又叫三连字,实在搞不懂翻译>的人是怎么想的,居然翻译成"三个图形字符",搞得我想了老半天... 言归正传,总得来说,thrgraph是C/C

2015-01-18 22:42:50 706

转载 c语言解析json

c语言解析json一，json简介JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。易于人阅读和编写。同时也易于机器解析和生成。它基于JavaScript Programming Language, Standard ECMA-262 3rd Edition - December 1999的一个子集。 JSON采用完全独立于语言的文本格式，但

2015-01-14 13:48:15 1063

转载 fcntl的使用

fcntl的使用功能描述：根据文件描述词来操作文件的特性。#include #include int fcntl(int fd, int cmd, ... /* arg */ );描述fcntl()针对(文件)描述符提供控制。参数fd是被参数cmd操作(如下面的描述)的描述符。针对cmd的值，fcntl能够接受第三个参数int arg。返回值fcntl()的

2015-01-10 13:23:02 439

原创 uvaoj 11029 Leading and Trailing 取log和快速幂

uvaoj 11029 Leading and Trailing 取log和快速幂给定n和k,求n^k的最低三位和最高三位，数字很大，不能直接求出来。最低三位可以使用快速幂在logk的复杂度下解决。对于最高三位，设log为以10为底的对数，那么log(n^k)=klogn，这个值很容易算出来，我们设n^k用科学计数法表示为d*10^p，其中d为大于等于1小于10的实数，p为整数。那么log

2015-01-09 19:19:52 467

pro git 中文版

空空如也