原创 洛谷 P2312 解方程

题目首先，可以确定的是这题的做法就是暴力枚举x，然后去计算方程左边与右边是否相等。但是noip的D2T3怎么会真的这么简单呢？卡常卡的真是熟练 你需要一些优化方法。首先可以用秦九韶公式优化一下方程左边的计算方法：左边=(((..(a[n]*x)+a[n-1])*x+..+a[1])*x+a[0]然后我就试着直接去算：#includetypedef long long

原创 233

转载 欢迎使用CSDN-markdown编辑器

欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit修改而来，用它写博客，将会带来全新的体验哦：Markdown和扩展Markdown简洁的语法代码块高亮图片链接和图片上传LaTex数学公式UML序列图和流程图离线写博客导入导出Markdown文件丰富的快捷键快捷键加粗 Ctrl + B 斜体 Ctrl + I 引用 Ctrl

转载 网络流 增广路 入门很好的文章

转自点击打开链接网络流基础篇–Edmond-Karp算法BY纳米黑客这是我的一个初学者教程系列的一部分，也是这个系列的第一篇文章，这个系列计划中将包括网络流，线段树，树状数组等一些初学者比较难以入门的内容。因为是初学教程，所以我会尽量避免繁杂的数学公式和证明。也尽量给出了较为完整的代码。本文的目标群体是网络流的初学者，尤其是看了各种NB的教程也没看懂怎么

转载 超大整数开方&&灯

引用：点击打开链接T4607 灯·重回江湖收五杀【提高】题目描述N盏灯和N个人，最开始N盏灯都是灭的，第i个人会按下第ki(ki≤N且k>0)的开关，试问N个人操作之后有多少盏灯是亮着的。输入输出格式输入格式：输入共一个正整数N输出格式：输出共一个正整数，即N个人操作之后亮着的灯的数量。输入输出样例输入样例#1：2输出样例#1：1说明te

转载 Color Length UVA - 1625

Color Length UVA - 1625题意：输入两个长度分别为n和m(n,m<=5000)的颜色序列，要求按顺序合并成一个序列，也就是每次从n或者m的开头取一个颜色，将这个颜色从原序列去掉并放入新序列的尾端。对于每个颜色C来说，L(C)表示合并后的序列中C最后出现的位置与最前出现的位置之差。现在要使得L(C)的总和最小。

原创 从一个n位数中选出m位按顺序组成新数并使其最大 || Erasing and Winning UVA - 11491

就是从n位数中取出n-d个数字按顺序排成一排组成一个新数使得其最大算法：从前往后确定每一位。找第i位时，要求后面留下d-i位的空间，因此第i位应该从第i-1位原来位置+1到第d+i位寻找用线段树确定区间最大值(其实直接用优先队列就行了，可能会多一些多余的出队操作)更好的算法：***引用后来看到一个博客写的特别巧妙，每读取一个字符，如果ans中有字符，且如果删除一个字

原创 Bits Equalizer UVA - 12545

点击打开链接#include#include/*别看错了：0能变1,1不能变0能完成的条件是，s与t长度相等且s中0数量和?数量之和大于等于t中0数量首先，对于相等的字符显然不应修改然后：***抄的主要就是要注意0能变1,1不能变0因此，优先满足1->0的情况****/char s[110];char t[110];int a1;//0->1int a2;//1->0

转载 Party Games UVA - 1610

点击打开链接

原创 笔记 树状数组--区间查询+区间修改

参考：点击打开链接区间修改+区间查询的树状数组，实际上是用两个树状数组来表示一个数组用a[i]表示原数组，d[i]=a[i]-a[i-1](a[i]视为0)关于的说明：a[1]+a[2]+...+a[x]=d[1]+(d[1]+d[2])+(d[1]+d[2]+d[3])+...+(d[1]+d[2]+...+d[x])=d[1]*x+d[2]*(x-1)+..

原创 算法竞赛入门经典 笔记(1)

P144 UVa12657 移动盒子 Boxes in a LineP138 UVa212 医院设备利用 Use of Hospital FacilitiesP148 UVa 679 小球下落 Dropping BallsP160 UVa 297 四分树 Quadtrees

原创 Database UVA - 1592

对于每组数据，首先通过一个map将每个字符串由一个数字代替，相同的字符串由相同数字代替，不同的字符串由不同数字代替。那么题目就变为了询问是否存在行r1,r2以及列c1,c2使得str[r1][c1]=str[r2][c1]且str[r1][c2]=str[r2][c2]（此时所有单元格内都是数字，str[i][j]表示第i行第j列的数字）。也就是寻找两行和两列，它们相交所在的四个单元格中上面的两个

原创 set有关的函数的用法（The SetStack Computer UVA - 12096）

#includeusing namespace std;typedef set Set;map IDcache;vector Setcache;stack s;int ID(Set x){ if(IDcache.count(x)) return IDcache[x]; Setcache.push_back(x); return IDcache[x]=Setcache.size(

原创 指针杂谈

#include//http://blog.csdn.net/solomon1558/article/details/40798901 double do1(){ printf("uses do1\n"); return 122.6546564;}int main(){ double (*do2)()=do1;//函数指针 int (*do3)()=(int(*) ())do1

原创 UVa 11889 最小公倍数

vjudge

原创 求数轴上一点到数轴上一些点距离之和最小

也就是求|x-a1|+|x-a2|+...+|x-an|的最小值。可以证明，当x为a1,a2,...,an的中位数时该式有最小值。第一个：绝对值不等式：||a|-|b|| ≤|a±b|≤|a|+|b|这里要用的是|a|+|b|≥|a+b|可以推出如|a|+|b|+|c|≥|a+b+c|以及更多未知数时的情况，对于这样的形式，取等号时要求a、b等字母代表的数字同号。剩下看

原创 算法竞赛入门经典--训练指南 笔记

P1（贪心）自己想的糟糕的算法：#include//从大到小排序龙头和骑士，每个龙头由“恰好”能砍掉的骑士来砍#include//貌似没问题，但是又难写又慢#include//就当复习stl了#includeusing namespace std;int n=1,m=1;int a[30000];vector b;vector::iterator iter;bool bo

原创 洛谷 P2279 [HNOI2003]消防局的设立

P2279 [HNOI2003]消防局的设立法一：某贪心方法（摘自洛谷题解）：一般的，对于深度最大的结点u,选择u的k级祖先是最划算的（意思是说这个题目的2改成了k我们都是可以做的，至于这个结论，详见刘汝佳的《***入门经典》（蓝书P35），还有一个例题，不过和本题不一样）法二：//树形dp/*状态的设计：f[i][0]: 表示选了自己以后...f[i][1]:

原创 洛谷 P1273 有线电视网

P1273 有线电视网//ans[i][j]表示第i个结点以下共j个用户观看时最大的赚钱量 //（仍然没有想到）ans[u][i]=max{ans[u][i-j]+ans[v][j]-w}//具体解释：/*ans[i][j][k]表示第i个结点以下前k个子结点中有j个用户观看时最大的赚钱量ye[v]为v及以下叶节点数量则对于边(u,v,w)，ans[i][j][k]=max{ans

原创 洛谷 P1040 加分二叉树

P1040 加分二叉树树形dp，用记忆化搜索即可//树形dp P1040 //http://www.cnblogs.com/mhpp/p/6628528.html #include#includeusing namespace std;int ans[31][31];//从l到r的结点构成的子树的最高加分int n;int root[31][31];//记录从l到r的结点构成

原创 洛谷 P1892 团伙

P1892 团伙并查集#includeint fa[2500];//fa[i]表示i的朋友所在集合，fa[i+n]表示i的敌人所在集合bool boo[2500];int ans,n,m;int find(int x){ if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x];}void union1(int x,int y)

原创 洛谷 P2024 食物链

P2024 食物链法一：种类并查集法二：加权并查集加权并查集的做法并非将同类放入同一个并查集，而是将所有有关系的动物都放入同一个并查集。这一点跟上面的做法不同。r[i]表示i结点与父亲结点的关系，r[i]=0 表示father[i]与i同类；1表示father[i]吃i；2表示i吃father[i]。#include#includeusing namespace std

原创 洛谷 P1196 银河英雄传说

P1196 银河英雄传说加权并查集，简介见点击打开链接，具体方法见代码及注释//P1196 银河英雄传说#includeint fa[30010];int r[30010];//r[i]表示第i号战舰在其父亲之后的第r[i]个位置int r2[30010];//r2[i]表示以第i号战舰为队首的队列有r2[i]辆战舰//本来只想到了记录战舰i后面的战舰数量，但是操作量太大，这

原创 并查集--算法，优化，变种

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

原创 洛谷 P1801 黑匣子_NOI导刊2010提高（06）

P1801 黑匣子_NOI导刊2010提高（06）法一：算法思想较精妙--两个堆先将数字放入大根堆，然后取出堆顶元素，放入小根堆，如果要求输出，则取出小根堆堆顶元素，输出并放入大根堆。#include#includeusing namespace std;priority_queue q1;//大根堆 priority_queue,greater > q2;//小根

原创 洛谷 P3370 【模板】字符串哈希

P3370 【模板】字符串哈希字符串哈希就是根据一个字符串s通过某种方法计算得到一个数字x，这样如果字符串s对应一个值y的话，可以把y保存在数组a[x]中，这样如果告诉你字符串，要得到或者修改对应的值，就比较方便。因为这个数字通常有大小限制，字符串却是无限的，所以哈希通常会有冲突，也就是多个不同的串计算出相同的数字。因此，哈希算法需要某些措施来减少冲突的可能，例如使算法更复杂，对同

原创 洛谷 P1219 八皇后

搜索+打点type ar=array[0..25] of integer;var arr:ar;i,j,n,p,q,ans:longint;function ok(x,y:integer):boolean;var k,m,i:integer;begin k:=abs(x-y); for i:=1 to p-1 do begin if arr[

原创 洛谷 P1090 合并果子

大佬的做法var n,i,ans,a1,k,temp:longint;a:array[1..10001] of longint;procedure qsort(l,r:longint);var i,j,k,p,temp:longint;begin i:=l; j:=r; k:=a[l]; repeat while a[i]>k do

原创 洛谷 P1972 [SDOI2009]HH的项链

首先读入贝壳颜色，并建立#include#includeusing namespace std;typedef long long LL;LL a[51000];LL c[400100];LL next1[51000];LL ans[201000];LL boo[1001000];//jiLL n,m,x,k=1,lastk;struct query1{ LL

原创 洛谷 P1908 逆序对

P1908 逆序对法一：归并排序求逆序对（记一下）#includeint a[40001];int a1[40001];int num,n;void merge(int start,int mid,int end){ int k=start,k1=start,k2=mid+1; while(k1<=mid&&k2<=end) { i

原创 洛谷 P1010 幂次方

P1010 幂次方#includeusing namespace std;int ans2[15];//ans2[i]=2^iint ans1[50001];//如ans1[i]=k，则表示2^(k-1)=ivoid work(int a){ int b=ans1[a]; if(a==1)//a为1,2,3则直接输出 cout<<"2(0)";

原创 洛谷 P1032 字串变换

P1032 字串变换#include#include#includeusing namespace std;map map1;string s1,s2;int n,l=1,r=0;int deep[500000];string que[500000];string sa[7];string sb[7];void in(string s,int deep1){ q

原创 洛谷 P1060 开心的金明

P1060 开心的金明ans[i][j]表示前i件物品用j元时最大结果则ans[i][j]=max(ans[i-1][j-v[i]+v[i]*w[i],ans[i-1][j])显然，ans[i][j]只会用到ans[i-1][p](j-v[i]可依据此降掉一维：ans[j]=max(ans[j-v[i]]+v[i]*w[i],ans[j])（此时第二重循环的j需要从大到小，

原创 洛谷 P1019 单词接龙

P1019 单词接龙var a:array[1..21] of string; b:array[1..21] of integer;i,n,x,max:longint; ch:char;function min(a,b:longint):longint;begin if a>b then exit(b) else exit(a);end;function f(a,b:str

原创 洛谷 P1094 纪念品分组

P1094 纪念品分组先按价格对纪念品排序（这里是从大到小），然后从两端向中心开始配对，有两个变量i和j，表示正在处理的两个纪念品编号，开始时i=1，j=n，如果a[i]+a[j]>w则第i贵的纪念品无法与任何较小的纪念品配对，那么该纪念品单独一组，i++，否则第i贵的纪念品可以和第j便宜的纪念品一组，因此i++,j--，两种情况都使ans++，而i=j时说明纪念品分组完成，于是退出。

原创 洛谷 P1086 花生采摘

P1086 花生采摘说白了就是将植株按花生数从大到小排序，然后按排序后的顺序摘，每次摘前计算能否在摘后回到路边，如果能就将ans加上该植株花生数，如果不能就直接输出dangvar a:array[1..405,1..3] of integer;i,j,x,y,m,n,k,n1,t1,ans,time:longint;procedure sort(l,r:longint);var i,

原创 洛谷 P1042 乒乓球

P1042 乒乓球var s:string; a1:array[1..50000] of char;i,n,x,y:longint;procedure f1;begin while not eof do begin readln(s); for i:=1 to length(s) do begin if s[i]='E' then exit;

原创 洛谷 P1031 均分纸牌

P1031 均分纸牌这道题告诉我们，对于实在想不出算法的题，可以大胆按照直觉用贪心，而且在考试中永远不要试着去证明贪心算法，因为非常难证，会浪费大量时间。（这就是你们都不去证的理由？？）这道题贪心算法就是，计算牌的平均数，然后除了最后一堆以外，每堆都通过把多余牌移到下一堆或从下一堆取牌来使其达到平均值，并且假设牌堆内牌数量可以为负。var a:array[1..110] of in

原创 洛谷 P1067 多项式输出

P1067 多项式输出模拟，很坑的那种var i,n:longint; a:array[1..105] of integer;begin readln(n); for i:=1 to n+1 do read(a[i]); if a[1]=-1 then write('-'); if a[1]<-1 then write(a[1]); i

原创 洛谷 P1017 进制转换

P1017 进制转换const sz:array[0..20] of char=('0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J','K');var a:array[1..1000] of integer;i,i1,j,n1,n,r,t1,t2:longint;begin