A_Happyer-CSDN博客

原创 +-*、（）表达式转逆波兰

#include#include#include#include#include#include#include#includeusing namespace std;typedef long long LL;typedef pair pii;const int maxn=10005;const int maxlen=12;char s[maxn][maxlen];

2016-09-19 22:54:27 443

原创 HDU5225 Tom and permutation(排列组合)

题意：Tom学会了通过写程序求出一个1-n的排列的逆序对数，但他的老师给了他一个难题：给出一个1-n的排列，求所有字典序比它小的1-n的排列的逆序对数之和。Tom一时不知道该怎么做，所以他来找你帮他解决这个问题。因为数可能很大，答案对109+7取模。从前往后推，先计算1-k的所有排列可以产生逆序总数，先假设db[2]为1-2的结果，那么我们来看3的排列，他是由1[2,3]

2015-05-10 08:54:16 1050

原创 NPY and shot（三分）

直接三分求解。#include#include#include#include#include#include#include#include#include#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i,a,b) for(int i=(a);i>=(b);i--)#define clr(a,x) mems

2015-03-14 15:56:01 847

原创 HDU1043:Eight HDU3567:Eight II(康拓展开+bfs搜索）

HDU1043:Eight这个题还算好过，用我刚整理的康拓展开的模板直接就ok的，需要注意的是对于这种终态唯一的题目，一般用终态来反搜初态，就是一边bfs记录下所有答案，如此如此，看下AC程序的主函数就能理解的。代码：#include#include#include#include#include#include#include#include#include#def

2015-03-07 00:46:28 872

原创最大网络最小流

const int maxn=805;const int maxm=2000005;int first[maxn],dis[maxn],vis[maxn],pre[maxn];int u[maxm],v[maxm],w[maxm],cost[maxm],flow[maxm],nex[maxm];int n,m,vcnt,ecnt,vcnt1,vcnt2;void add_(int a,i

2015-02-15 14:46:30 542

原创 HDU 5171 GTY's birthday gift （矩阵快速幂）

GTY's birthday giftTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 408 Accepted Submission(s): 154Problem DescriptionFFZ'

2015-02-14 11:05:02 490

原创 CentOS安装后常见的一些应做工作（恢复引导。ntfs支持，）

记录双系统CentOS安装后所做的一些工作。以下工作需要root权限1.电脑上原本有win7，我又装上了CentOS7，电脑启动就进入CentOS7，找不到win7引导。注意正常安装情况win7引导并没有被覆盖，只是不能被识别而已。解决办法（前提：win7装在sda1上面，一般来说win7都是在sda1上的）：在终端输入vi /etc/grub2.cfg在“###END

2015-01-03 20:04:39 948

原创 codeforces Good Bye 2014题解(A、B、C)

codeforces Good Bye 2014(A、B、C)A. New Year Transportationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputSo, user tncks0121 has made a transportation system to move between these cells, to celebr

2014-12-31 09:43:12 1461

原创 UVA 796 - Critical Links （求桥按序输出）

tanjar求图中的桥，然后排序输出。代码：#include#include#include#include#include#include#include#include#include#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i,a,b) for(int i=(a);i>=(b);i--)#def

2014-12-28 14:12:10 825

原创 poj 3694 Network（桥+lca）

给定一个无向无环图，保证连通，求每加入一条给定的边图中还剩下多少桥。双联通缩点重新建图后，再用lca在线算法解。lca算法参考斌神http://www.cnblogs.com/kuangbin/p/3184884.html这个版本的lca思路大致是先topsort，再用并查集分别从查询的两点向根节点回溯，直到两个点碰撞。效率我分析不出来，但看得出效率很高，每次查询都对后面查询做

2014-12-28 11:34:18 779

原创数据结构实验总览及相关代码

实验1链表的插入和删除【实验目的】1、了解单链表、循环链表和双链表的基本知识；2、掌握算法思想和数据结构的描述；3、掌握链表的插入、删除的相关语句及基本方法。【实验步骤与要求】1、实验前的准备（1）了解C语言的基本概念；（2）了解C语言的基本段落。2、上机操作（1）了解链表的基本知识；（2）掌握算法思想和数据结构的描述；（3）掌握

2014-12-24 09:09:14 1089

原创康拓展开与逆康拓展开原理及实现

1.康托展开的解释康托展开就是一种特殊的哈希函数　　把一个整数X展开成如下形式：　　X=a[n]*n!+a[n-1]*(n-1)!+...+a[2]*2!+a[1]*1!　　其中，a为整数，并且0　　{1,2,3,4,...,n}表示1,2,3,...,n的排列如 {1,2,3} 按从小到大排列一共6个。123 132 213 231 312 321 。

2014-12-23 23:49:52 1213

转载图的割点、桥与双连通分支（知识点）

图的割点、桥与双连通分支转自https://www.byvoid.com/blog/biconnect[点连通度与边连通度]在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。一个图的点连通度的定义为，最小割点集合中的顶点数。类似的，如果有一个边集合，删除这个边集合以后，原图变成多个

2014-12-23 12:35:33 551

原创非齐次方程组代码（C++）

/*先输入未知数个数。然后输入n*(n+1)的行列式。*/#include #include int hanglieshi(int a[],int n){ int j,s; if(n==1) s=a[0]; else { for(s=0,j=0; j<n; j++) { int yuzishi(

2014-12-22 22:21:45 1986

原创 POJ3177 Redundant Paths (双联通缩点)

求对于给定一个连通图，加多少条边可以变成边双连通图。一个有桥的连通图要变成边双连通图的话，把双连通子图收缩为一个点，形成一颗树。需要加的边为(leaf+1)/2 (leaf为叶子结点个数)。对于此题，有重边但重边不加入计算。重边的话，要么在开始去掉，要么用桥来计算入度。因为桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。对于重边而言，只有一对

2014-12-22 20:06:05 705

原创 hdu4612（双联通缩点+求树的直径）

求在给定图中添加一条边最多能是多少条桥消失。双联通缩点，成为一棵树，然后求树的直径。此图中两点之间可能会有重边，也按双联通，而不能按桥处理。其他的就没什么特别的代码：#pragma comment(linker, "/STACK:1024000000,1024000000")#include#include#include#include#include#include

2014-12-22 16:52:54 632

原创 poj1804(归并排序求逆序数)

逆序数，也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。我们移动元素的次数转化为，假如对每个数da[i]来说前面比他大的数的数目为c[i]的话，那么移动元素总次数就应该是c[0]+c[1]+……+

2014-12-22 12:46:43 1493

原创 poj2299(离散化+树状数组求逆序)

数据范围比较大，先用离散化将数据映射到可控的范围，然后应用树状数组求逆序求解。总共有N个数，如何判断第i+1个数到最后一个数之间有多少个数小于第i个数呢？不妨假设有一个区间 [1,N]，只需要判断区间[i+1,N]之间有多少个数小于第i个数。如果我们把总区间初始化为0，然后把第i个数之前出现过的数都在相应的区间把它的值定为1，那么问题就转换成了[i+1,N]值的总和。再仔细想一下，区间

2014-12-21 16:28:21 626

原创 HDU4685 Prince and Princess 完美匹配+强连通

题意：现在有n个王子，m个公主。现在要给他们配对，王子会和他喜欢的一个人结婚，而公主不能做选择。这题啃得好费劲，有个类似的题目poj1904，那个题目也是给王子与公主配对，但那个是王子公主各n个，且给定了一个完美匹配，然后求每个王子可以做出的选择且不影响最大匹配数目。那题是先建各条喜欢关系的边，然后在由被选择的公主连一条边到与之配对的王子，强连通之后如果一个王子和一个公主在一个强连通分量中，那

2014-12-18 23:26:15 976

原创 HDU4738 Caocao's Bridges(桥)

http://acm.hdu.edu.cn/showproblem.php?pid=4738题意：给定一张无向图，求其中权值最小的一座桥，派最少的士兵去炸掉它！！思路：直接用tarjan计算出桥并且取其中权值最小者。此题坑点甚多，1、有可能桥本来就不联通，输出-1。2、桥最小者为0，输出1（至少排一个人去炸桥）。3、不要去重边，两个岛之间允许有多座桥，tarjan忽略返回边只忽略一次，

2014-12-16 20:44:16 1582

原创 POJ-3207-Ikki's Story IV - Panda's Trick（2-sat模板）

2-sat模板提。代码：#include#include#include#include#include#include#include#include#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i,a,b) for(int i=(a);i>=(b);i--)#define clr(a,x) memset

2014-12-02 13:54:36 638

原创 ZOJ Problem Set - 3795(缩点拓补)

题意：每条信息说明了两个一定不在一个集合里的人，求最少情况集合可以划分为多少子集。一看就是拓补树的最高层数，但题意中隐含了可能有环（>=关系偏序），所以要先缩点，再拓补。当然，缩点之后图中没有环，直接dfs记忆化也是ok的。代码：#include#include#include#include#include#include#include#include#define

2014-12-02 12:49:00 677

原创 poj1184 聪明的打字员（双向搜索）

双向搜索，同时从起点和终点开始搜索，当if(mark[s.sta][s.site][s.fl] == -1)时就代表从两端的搜索范围开始出现交叉点，即得到最小值。代码：#include #include #include #include #include #include #include #include #include using namespace std;

2014-11-30 16:02:42 1140

原创 HDU1560:DNA sequence(IDA*)

求一DNA串包含所有给定字串。ida*剪枝，预测函数为个匹配串为匹配部分最大长度。代码：#include#include#include#include#include#include#include#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i,a,b) for(int i=(a);i>=(b);i--)

2014-11-30 15:43:51 511

原创 poj 1190(dfs剪枝)

先初始化算出n层蛋糕所需的最小体积，用其剪枝，可以大大提升速度。代码：#include#include#include#include#include#include#include#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i,a,b) for(int i=(a);i>=(b);i--)#define c

2014-11-30 15:36:35 549

原创 POJ 3687 Labeling Balls（逆向拓扑）

正向每次取最小并不能保证为最优解，反向建边每次取最大可得正解。代码：#include#include#include#include#include#include#include#include#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i,a,b) for(int i=(a);i>=(b);i--)#

2014-11-30 15:21:13 630

原创 POJ 1236 Network Of Schools (强连通分量模板题）

代码：#include#include#include#include#include#include#include#include#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i,a,b) for(int i=(a);i>=(b);i--)#define clr(a,x) memset(a,x,sizeof

2014-11-30 15:11:06 725

原创 poj 2728 Desert King最小比例生成树

问题可以转化为：给定一个rate，z(rate)=∑xi×ci-rate*∑xi×disi，xi为一棵生成树使(∑xi×ci-rate*∑xi×disi)的值最小(下面会介绍求此生成树的方法)，则rate=(∑xi×ci-z(rate))/( ∑xi×disi)，令rateNex=(∑xi×ci)/( ∑xi×disi)。求解生成树xi使(∑xi×ci-rate*∑xi×disi)

2014-11-30 15:08:57 687

原创 poj 3635(搜索)

我刚开始用dp做，超时了，看了别人博客重写ac的。个人觉得此题更偏向搜索，dp数组只是记录最佳状态的标记。#include#include#include#include#include#include#include#include#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i,a,b) for(int

2014-11-30 14:31:05 584

原创最短路及次短路

#include#include#include#include#include#include#include#include#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i,a,b) for(int i=(a);i>=(b);i--)#define clr(a,x) memset(a,x,sizeof a)#

2014-11-30 14:20:17 578

原创 Codeforces Round #277.5 (Div. 2)-D

题意：求该死的菱形数目。直接枚举两端的点，平均意义每个点连接20条边，用邻接表暴力计算中间节点数目，那么中间节点任选两个与两端可组成的菱形数目有r*（r-1）/2.代码：#include#include#include#include#include#include#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i

2014-11-18 12:34:27 976

原创 Codeforces Round #277.5 (Div. 2)-A

分析：这题很像Codefoces 432 C. Prime Swaps（水），我就直接处理数据

2014-11-18 11:55:30 510

原创 Codeforces Round #277.5 (Div. 2)-B

一看就是贪心，想了个策略，

2014-11-18 11:50:32 527

原创 Codeforces Round #277.5 (Div. 2)-C

简单细节题：#include#include#include#include#include#include#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i,a,b) for(int i=(a);i>=(b);i--)#define clr(a,x) memset(a,x,sizeof a)typedef lon

2014-11-18 11:47:43 772

原创 Codefoces 432 C. Prime Swaps（水）

思路：从前往后想将1调整好，在调整2。。。。这样平均每次有五次机会调整，而且有相当一部分可能都用不到五次，可以一试。ac代码：#include#include#include#include#include#include#includeusing namespace std;const int maxn=600005;const int maxm=100005;in

2014-11-17 22:21:22 799

原创 ZOJ3622 Magic Number(水题)

分析：举个例子xxx(三位数)为魔力数，则xxx|(xxx+1000*y),那么xxx|1000,这个就是结论同理：四位数xxxx|10000,五位数xxxxx|100000代码：#include#include#include#include#include#include#includetypedef long long LL;using namespace s

2014-11-17 08:40:52 727

原创 POJ 1012 Joseph(打表题)

题意：约瑟夫环的变形，要求寻找到一个杀人循环节m使后半节的坏人先被全部杀光。直接链表模拟出结果，再打表就行；代码：（注释的是打表码）#include#include#include#include#include#include#include#includeusing namespace std;/*int l[30],r[30];int main(){

2014-11-10 12:22:09 862

原创 HDU 1143 Tri Tiling（递推）

题意：现有一些1*2的小方块，求拼成3*n的矩形有多少种拼法。思路：既然是递推式，肯定要遇上一层发生关系。仔细观察，发现每一层应该设为2层，（奇数层不可能是矩形）而从上一次拼好的图形中的最后一层可以发现，只有两种结果（对称的也先算一种）。即：。结果二可以==上一层的结果一和结果二两种结果（很明显，不多说，用笔画一下便知）。结果一可以==2*（上一层的结果一和结果二）以及结果一。为什么呢

2014-11-10 09:23:24 882

原创 202 - Repeating Decimals

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=830&problem=138&mosmsg=Submission+received+with+ID+14498728

2014-11-09 11:13:39 588