Sun_AC-CSDN博客

原创 HDU 5407 CRB and Candies （2015多校第10场第一题）素数打表，除法取模（乘法逆元）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5407题意：求N个不同的糖果吃K个的所有情况的最小公倍数，并取模思路：简单一推，就知道结果为n的所有排列的LCM，但是直接这样做的话一定超时，所以得换种方式，因为每个n都有唯一解，所以求助于OEIS http://oeis.org/?language=english ，将给出的案例一一输入可得

2015-08-20 20:52:50 925

原创二分图匹配学习——KM算法

KM算法思路：KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[i]，顶点Yi的顶标为B [i]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[i]+B[j]>=w[i,j]始终成立。KM算法的正确性基于以下定理：　　若由二分图中所有满足A[i]+B[j]=w[i,j]的边

2015-08-10 20:45:10 794

原创二分图匹配学习——匈牙利算法模板

DFS(邻接矩阵)const int MAXN=1000;int p,n; //u,v数目int g[MAXN][MAXN];//左右集合连接情况int linker[MAXN];bool used[MAXN];bool dfs(int u){ int v; for(v=1; v<=n; v++) if(g[u][v]&&!used[v])

2015-08-10 20:36:32 685

原创 hdu 5363 Key Set （2015多校第六场第11题）找规律推公式

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5363题意：给你一个有1到n的n个数的集合，求这个集合的非空子集的子集所有元素的和为偶数的子集个数思路：因为和为偶数，所以一定是由2*x个奇数+y个偶数组成，从中就可以推出公式为2^(n-1)-1代码：#include #include #include #include #in

2015-08-07 18:41:19 871

原创 hdu 5358 First One （2015多校第六场第6题）尺取法枚举区间和

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5358题意：给你一个串数和一个公式，求这个公式的答案。思路：直接暴力一定会超时的，而且这道题很卡时间，交C++的都TLE了。怎么优化才能不超时，于是就有了尺取法，其实就相当于两个分别指向区间左右指针不断更新区间内容的过程。尺取法（two point）就是两个指针表示区间[l,r]的开始与结束

2015-08-07 16:12:50 795

原创 HDU 5351 MZL's Border(2015多校第五场第9题) 写长串找规律

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5351题意：求Fibn的前m位的LBorder思路：一开始完全没头绪，就开始一个个的写出来，最终就找出了规律，由于数据会很大用JAVA的大数会比较方便代码：import java.io.*;import java.util.*;import java.math.*;impo

2015-08-05 21:09:23 570

原创 hdu 5347 MZL's chemistry(2015多校第五场第5题)高中化学选修知识第一电离能

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5347题意：给你a,b两个原子序号（1思路：这是高中化学选修的知识，无语，具体根据电离能表可以看出结果，也可以打表，电离表看这个链接——http://wenku.baidu.com/link?url=re4QQP6VkbDGVhqpPaqgw4ifDRehbA7KbthcLGREkZoLbeuR

2015-08-05 14:06:59 622

原创 hdu 5349 MZL's simple problem (2015多校第五场第7题) multiset

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5349题意：用multiset进行操作添加，删除，查找。思路：直接用multiset代码：#include #include #include #define LL __int64#include using namespace std;int main(){ i

2015-08-05 10:59:12 540

原创 hdu 5344 MZL's xor (2015多校第五场第2题) 简单化简

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5344题意：求所有(Ai+Aj)（1《i，j《n）异或的值思路：由于当i不等于j时，(Ai+Aj)^(Aj+Ai)=0，所以只要考虑i=j的情况也就是所有（2*Ai）的异或就是答案，由于数据原因，可能会超int，所以用__int64代码：#include #include #inc

2015-08-04 22:30:16 608

原创 CF 121E - Lucky Array(树状数组裸题)

题目链接：http://codeforces.com/problemset/problem/121/E题意：幸运数是指只由4，7组成的数，例如4，7，47，74，447……，这道题先给你n个数的数组，再给你m个操作，操作有两种：1、count l r（计算[l,r]区间内幸运数的总数，并输出结果）；2、add l r d（区间内的每个数都加d）思路：由于数组中每个数都小于104，所以只

2015-08-01 21:35:49 985

原创 hdu 5326 Work (2015多校第三场第11题) 暴力

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5326题意：给你n个人和一个k，再给你n-1个关系a b，表示a是b直接上司，求有k个下属的上司有几个。思路：由于1 代码：#include #include #include #include #include #include #include using namesp

2015-07-30 22:03:48 424

原创 hdu 5319 Painter （2015多校第三场第4题）暴力模拟（瞎搞）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5319题意：用R颜色的笔只能画 \ ，用B颜色的笔只能画 / ，R颜色和B颜色的交点为G，给一幅画好的图，求最少画几笔。思路：一看到1代码：#include #include #include #include #include #include #include usin

2015-07-30 21:49:25 597

原创素数打表，质因数分解

const int X=1000010;bool isPrime[X+1];int total;//计数int prime[79000];void getPrime(){ total=0; memset(isPrime,true,sizeof(isPrime)); memset(prime,0,sizeof(prime)); for(int i=2;i<=

2015-07-30 21:12:03 703

原创 hdu 5317 RGCDQ （2015多校第三场第2题）素数打表+前缀和相减求后缀（DP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5317题意：F(x) 表示x的不同质因子的个数结果是求L，R区间中最大的gcd( F(i) , F(j) )，i、j在L，R区间内。思路：因为2F(x)代码：#include #include #include #include using namespace std;con

2015-07-30 20:50:09 583

原创 hdu 5316 Magician（2015多校第三场第1题）线段树单点更新+区间合并

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5316题意：给你n个点，m个操作，每次操作有3个整数t,a,b，t表示操作类型，当t=1时讲a点的值改成b；当t=0时，查询区间a，b之间最大的子序列和，这个子序列中的相邻的元素的原来的下标奇偶性都不同。思路：这道题难点就在查询，其余都是模板，而根据查询，你只要分别把下一个区间的奇偶最大的情况分

2015-07-29 16:26:01 601

原创 hdu 5305 Friends（2015多校第二场第6题）记忆化搜索

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5305题意：给你n个人，m条关系，关系可以是online也可以是offline，让你求在保证所有人online关系的朋友和offline关系的朋友相等的情况下，这样的情况有多少种。思路：因为online关系和offline关系的人数相等，而且m最多才28，所以只要枚举每个人的一半的关系是否符合要

2015-07-24 20:39:57 586

原创 hdu 5308 （2015多校第二场第9题）脑洞模拟题，无语

题目链接：http://acm.hdu.edu.cn/listproblem.php?vol=44题意：给你n个n，如果能在n-1次运算之后（加减乘除)结果为24的输出n-1次运算的过程，如果不能输出-1。思路：乍看起来，没什么规律，但是可以想象的是（n+n+n+n）/n=4，(n+n+n+n+n+n)/n=6，(n-n)*n*n*·····*n=0所以在n大于15的时候结果基本是固定的，

2015-07-24 19:07:03 711

原创 hdu 5301 Buildings (2015多校第二场第2题) 简单模拟

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5301题意：给你一个n*m的矩形，可以分成n*m个1*1的小矩形，再给你一个坐标（x,y），表示黑格子在n*m矩形中的位置，黑格子占一个1*1的小矩形的空间，用各种矩形去填充n*m矩形，（x,y）位置不能填，且每个去填充的小矩形都有一边是靠着n*m矩形的外框，求这些填充的小矩形在最小大小情况下的面积

2015-07-24 14:01:51 554

原创 hdu 4611 （2013多校第二场第1题）lcm+模拟

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4611题意：给你编号为0~N-1的N个球，先分别放入编号为0~A-1的盒子中，放球的规则为x%A=a%A(x为球编号，a为盒子编号)，再给你0~B-1个盒子，将A盒子中的求移到B盒子中，移动规则为 x%B=b%B(x为球编号，b为盒子编号)，求对于每个球自身放入的A、B盒子编号的差值之和，即每

2015-07-23 19:55:50 566

原创 hdu 5289 Assignment（2015多校第一场第2题）RMQ+二分（或者multiset模拟过程）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5289题意：给你n个数和k，求有多少的区间使得区间内部任意两个数的差值小于k，输出符合要求的区间个数思路：求出区间的最大最小值，只要他们的差值小于k，那么这个区间就符合要求，但是由于n较大，用暴力一定超时，所以就要用别的方法了；而RMQ是可以求区间的最值的，而且预处理的复杂度只有O(nlogn)

2015-07-22 21:24:53 532

原创 hdu 5288 OO’s Sequence（2015多校第一场第1题）枚举因子

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5288题意：在闭区间[l,r]内有一个数a[i]，a[i]不能整除除去自身以外的其他的数，f(l,r)表示在这区间内a[i]这样的数的个数，，现给你n个数，求所有区间的f(l,r)的和。思路：对于每个数a[i]求出他的左右侧最靠近他的且是他的因子的位置L、R，并记录，那么对于每

2015-07-22 16:03:07 440

原创 hdu 5294 Tricks Device（2015多校第一场第7题）最大流+最短路

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5294题意：给你n个墓室，m条路径，一个人在1号墓室（起点），另一个人在n号墓室（终点），起点的那个人只有通过最短路径才能追上终点的那个人，而终点的那个人能切断任意路径。第一问——终点那人要使起点那人不能追上的情况下可以切的最少的路径数，输出最少的路径数第二问——起点那人能追上终点那

2015-07-22 09:42:25 860

原创最大流模板（学习中）

1.EK/*poj 1273*/#include #include #include #include #include #include #include #include using namespace std;#define ll long long#define MAXN 205#define INF 0x3f3f3f3fint n,m;int flow

2015-07-20 15:01:36 412

原创 ZOJ 3872 Beauty of Array（模拟）

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3872题意：求每个连续子序列的和的总和（子序列的和为序列中不重复数字的和）思路：所有的子序列和（不管重复不重复）减去重复数字所重复的次数代码：#include #include #include #include #define LL lon

2015-04-30 21:46:46 527

原创 LightOJ 1005 - Rooks （组合数学dp模拟）

题目链接：http://lightoj.com/volume_showproblem.php?problem=1005题意：n*n的棋盘上放m个车，问有多少种放车的方式使得每个车都不会互相攻击到（即每个车都占有他所在的一行一竖两条直线）思路：这道dp模拟的是组合数学的算法（ n行中选出m行，C(n,m)，再在n列中选出m列随便放A(n,m)，答案为C(n,m)*A(n,m) ）

2014-11-30 13:18:59 1342

原创实验项目 4-06. 搜索树判断（25）

4-06. 搜索树判断（25）时间限制 400 ms内存限制 65536 kB代码长度限制 8000 B判题程序 Standard 对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。

2014-11-22 09:15:43 1051

原创 POJ 1651 Multiplication Puzzle（区间dp）

题目链接：http://poj.org/problem?id=1651题意：

2014-11-14 21:31:44 560

原创 HDU3699（POJ 3989）A hard Aoshu Problem（暴力模拟dfs）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3699http://poj.org/problem?id=3989

2014-11-14 21:24:18 1473

原创 HDU 2722（POJ 3653） Here We Go(relians) Again （建图，最短路Dijstra）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2722题意：给你

2014-10-29 22:49:31 966

原创 HDU 4791 Alice's Print Service（二分）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4791

2014-10-25 18:49:01 731

原创 HDU 4801 Pocket Cube（暴力模拟 dfs）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4801题意：求

2014-10-25 17:38:31 1140

原创实验项目 2-11. 两个有序链表序列的合并（15）

2-11. 两个有序链表序列的合并（15）时间限制 500 ms内存限制 80000 kB代码长度限制 8000 B判题程序 Standard 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的并集新非降序链表S3。输入格式说明：输入分2行，分别在每行给出由若干个正整数构成的非降序序列，

2014-10-23 19:28:10 1295

原创实验项目 7-05 魔法优惠券（25）

7-05. 魔法优惠券（25）时间限制 1000 ms内存限制 32000 kB代码长度限制 8000 B判题程序 Standard 在火星上有个魔法商店，提供魔法优惠券。每个优惠劵上印有一个整数面值K，表示若你在购买某商品时使用这张优惠劵，可以得到K倍该商品价值的回报！该商店还免费赠送一些有价值的商品，但

2014-10-22 22:14:42 1235

原创实验项目 2-12：两个有序链表序列的交集

2-12. 两个有序链表序列的交集（20）时间限制 400 ms内存限制 64000 kB代码长度限制 8000 B判题程序 Standard 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。输入格式说明：输入分2行，分别在每行给出由若干个正整数构成的非降序序列，用-1

2014-10-16 20:44:12 1679

原创 HDU 3102 Lawrence of Arabia（dp）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3102

2014-10-06 20:37:21 869

原创 HDU 5037 Frog（模拟跳石头的过程）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5037AC代码：

2014-09-23 19:52:37 882

原创 PAT 一元多项式的乘法与加法运算（20）（模拟计算过程）

一元多项式的乘法与加法运算（20）时间限制 400 ms内存限制 32000 kB代码长度限制 8000 B判题程序 Standard设计函数分别求两个一元多项式的乘积与和。输入格式说明：输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1

2014-09-22 19:50:27 1279 1

原创 HDU 5024 Wang Xifeng's Little Plot（暴力找点）

题目链接：AC代码：#include #include char ma[105][105];int n;int dfs1(int x,int y){ int i,a,b,ans=1; a=x+1; b=y; while(ma[a][b]!='#'){ a++; ans++; } a=x; b=y+1; while(ma[a][b]!='#'){ ans+

2014-09-20 18:07:46 823

原创 PAT QQ帐户的申请与登陆（25）（map的应用）

QQ帐户的申请与登陆（25）时间限制 800 ms内存限制 32000 kB代码长度限制 8000 B判题程序 Standard实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。输入格式说明：输入首先给出一个正整数N（5），随后给出N行指令。每行指令的格式为

2014-09-19 20:21:51 1253

原创 PAT 修理牧场（25）（Huffman问题，优先队列priority_queue）（与poj 3253 一模一样的思路）

题目链接：正确代码（1）：#include #include #include #include #include using namespace std;class cmp{ public: bool operator()(const int a,const int b) const{ return a>b; }};int main(){ int n,a,

2014-09-19 19:59:22 3500

STL算法入门ppt

空空如也