AC_jie-CSDN博客

原创洛谷 P2181 对角线

洛谷 P2181 对角线目标：求解点的数量思路分析：一开始在思考边和交点的关系。应该是最终考虑顶点和交点的关系。思路：两条对角线确定一个交点，两条对角线牵扯到4个顶点。从所有顶点选择4个组合数Cn4转化成组合数学问题因为数据量的问题直接乘会超有一个技巧n * （n -1）/ 2 * (n - 2) / 3 * (n - 3) / 4原因：n*(n - 1)必定是 2 的倍数n * (n - 1 ) * （n - 2）必定是 3的倍数n * (n -1) * (n

2021-04-28 19:55:11 152

原创剑指offer 剑指 Offer 04. 二维数组中的查找

public boolean findNumberIn2DArray(int[][] matrix, int target) { if(matrix.length == 0) return false; int x = matrix[0].length - 1; int y = 0; boolean flag = false; while(check(x,y,matrix)){ if(matrix[y][x] > target){

2020-08-06 17:28:27 184

原创剑指offer 05

class Solution { public String replaceSpace(String s) { char[] c = s.toCharArray(); char[] ans = new char[30010]; int k = 0; for(int i = 0;i < c.length;i++){ if(c[i] == 32){ ans[k++] = '%';

2020-08-06 17:27:16 210

原创重拾旧山河之快速排序

void quick_sort(int l,int r){    int k = a[l];    if(l < r)    {        int i = l, j = r; 

2018-12-06 21:55:10 257

原创收拾旧山河之归并排序

模板#include<cstdio>#include<iostream>using namespace std;const int MAXN = 100;int a[MAXN];void Merge(int left,int mid,int right){    int i = left; int j = mid + 1; in...

2018-12-06 16:28:01 186

原创 hdu5976 Detachment思维数学（贪心+逆元）

这个题，比赛的时候分析出来了，但是最后时间不够了，就没有做出来，GG了，最后补题的时候有因为自己地粗心开始不断debug，不过也发现问题了。先来说一下思路，将这个数分解后使其乘积最大，且因子各不相同，我就想到了阶乘，但是一个数不一定可以分解的彻底，所以可以将其从后向前均分到每一个数上，可以想一下，前面的数每增加1其实就是相比于原乘积增加一倍的后面数的乘积。然后分析一下时间复杂度，发现必须直接计算...

2018-10-04 20:04:39 266

原创 2016大连区域赛 HDU5974 (数论）

昨天开始国庆的区域赛训练，体验还不算太差，也终于知道了心怡师哥为什么可以区域赛拿牌了，想到了一句话，只有经历了才能真正懂。这个题我推了半天，没有思路，队友换了一种思路，打表找规律，真的是很佩服。看来就是自己平时没有用心做题。以后加油。先来说一下正确的推理。题目给力 X+Y = a,lcm(x,y) = b;这样的话，就可以将式子变形一下，X+Y = aX * Y = b * gcd(x...

2018-10-02 11:22:53 321

原创杜教筛

51nod1244-------杜教筛入门这几天开始学习杜教筛，前前后后看了大约一周，现在终于看懂了，感受到了自己的弱小，哈哈。这里不详细写了就，等区域赛回来给我的大一小孩讲一下。这里先贴上我学习的博客，感觉对数学要求和抽象思维能力要求很高感谢一下各位大佬传送门 http://jiruyi910387714.is-programmer.com/posts/195270.html ht...

2018-09-25 18:23:53 267

原创多校9 Rikka with Badminton（容斥原理）

今天开始和机油打比赛，开始做多校，真鸡儿难，我太菜了。这个题不是很难，开始就是没想到。等临走的那一周，开始做概率。题目是若有至少2个球拍和至少一个球就满足条件，求的是不满足条件的情况数。记事件A 为来的人都没有球。事件B 为来的人都没有球拍。事件C 为来的人只有一个球拍。以上就是构不成满足条件的事件数，因为d这类人既有球也有球拍，所以A B C ...

2018-09-14 21:40:10 309

原创 51nod 1204 莫比乌斯函数之和

今天来做莫比乌斯，这个题就是裸的莫比乌斯，但是由于如果想打表做的话，并不是网上写的那样就做不了，虽然说不能完全打出素数表，但是仔细想一个的话，我们可以先做一个1e6的素数表，然后进行素数分解，如果不断进行分解后，N的值还是不为1的话，这就说明N是一个很大的素数，因为在给定的数据范围内每个数都被它的最小素因子筛去，如果一个合数的最小素因子是1e6这个级别的，那样这个数就超出了数据范围，综上，肯定存...

2018-09-12 08:42:00 195

原创容斥原理——CodeForces 1017B

今天来不昨天的题，这个题想到了思路，但是去重出了问题，一开始拿set去重，直接爆掉，GG。忽然发现自己真正会的东西真少，从今天开始就要脚踏实地的一步一步地将自己的基础打牢。一会儿整理stl的用法。先来说一下这个题，本质是一个容斥原理，整天给师弟们讲，自己还是不会用QAQ.#include&lt;cstdio&gt;#include&lt;iostream&gt;#include...

2018-08-10 21:58:14 539

原创 CodeForces 1017D MAP统计的数量

我是真的菜，嗯，这是题解开篇辟邪的。今天又开始做CF,一开始看题没明白题意，后来就是思路错了，演绎法用的太差，没有考察到足够的例子。就开始形成算法，或者没有论证自己的算法。再就是思考的方向不对。当思考的方向更正时，发现自己又被技术所限制，唉，真是菜。先来说一下，我认为的问题的第一个关键所在，就是统计a[i],b[i],b[n - 1 - i],a[n - 1 - i]的关系，具体来说先统计...

2018-08-10 21:49:17 210

原创 CodeForces 1006B

我是真的菜，开始进行回复性训练。做了一个水题，敲了好长时间，反思一下就是没有思考成熟就开始干了。结合最近看的书，一定要认清思维的表象。思考成熟后，在开始写。#include&lt;cstdio&gt;#include&lt;iostream&gt;#include&lt;utility&gt;#include&lt;algorithm&gt;using namesp

2018-08-01 18:47:06 249

转载动态规划的意义

https://www.zhihu.com/question/23995189/answer/35429905 转载自知乎王勐的回答. 这个解释感觉很不错,分享一下给大家共享,同时感谢大佬的指点. orz !!!作者：王勐链接：https://www.zhihu.com/question/23995189/answer/35429905 来源：知乎著作权归作者所有。商业转载...

2018-04-20 09:30:04 479

原创 The King’s Ups and Downs

今天又开始做DP，今天这个题是一个组合递推DP,一开始在思考加入一个新的人后，会对前面的数列有什么影响，但是卡在了，这个新加入的人的高度，就直接看了题解。才发现状态的划分是按照从小到大的顺序来进行的，这样也很符合状态的设计，因为递推性，当有n - 1个不同身高的人已经排好时，再加入一个更高的，其实也复合逻辑，并且之所以这样设计状态对于问题来说也是便于处理和正确的。接着就是加入这个新的人后，...

2018-04-17 11:12:34 480

原创（zoj3747) Attack on Titans

今天开始做DP,今天的这个DP是带有限制条件的，并且和组合数学有关。首先这个题第一个突破点是将至少条件转化为至多的条件，这个很重要，决定了解题的方向。因为在规划问题状态的时候很难对至少进行处理，并且不易进行状态的划分。这样的话，将问题就转化成了，至多连续n个G,至多连续k个R 减去至多连续 m-1 个G,至多连续K个R,现在问题的状态就转换成了求至多上面两个状态的方法数。然后考虑...

2018-04-14 22:06:10 650 2

原创 Working out 三维DP

今天开始研究DP,今天是4.10 离省赛开始还有25天。先来说一下这个题，一开始把题意看错了，没有看到必须在一个位置相遇。菜啊这个题一开始想到了将问题转化成计算从相遇点到起点和终点的距离。但是还是不知道怎么划分状态，看完题解后，想到了一个点就是”累积性”。联想到了概率上的分布函数，可能这就是“递推的本质”。说一下这个题的思路。先来说一下为什么将问题转化成相遇点到各个角的最大...

2018-04-10 20:08:10 235

转载 United Kingdom and Ireland Programming Contest 2017 B

codeforces.com/gym/222400 题意是有一个饼干，这个饼干是标准的一个多边形，然后给这个饼干上的顶点，然后问要是将他放入一个杯子中的话，这个杯子的最小直径是多少？一开始的第一反应是两点之间的最远距离，但是TD说了可以将饼干竖起来之后的想法，就想到了旋转卡壳算法，然而并不知道旋转卡壳是干什么的，计算几何这块太差了。一定赶紧补起来。那就先拿今天的这几个题来练一练。因为...

2018-04-07 10:26:00 596

转载抽象能力

https://blog.csdn.net/ljc3046/article/details/1600426有天和朋友聊天，朋友是国内一家大型互联网企业的一位技术主管，朋友把他将近十年研发工作积累的心血总结成两点，这两点朋友刚一提出来我并没有马上明白，只是大约有这么一个概念，我还没达到朋友在技术领域的那种高度，不能彻底领悟他深刻的思想。但我想与众多刚刚踏入IT技术研发领域的新人们分享一下这位朋友...

2018-04-03 10:41:42 380

原创 Thrall’s Dream 搜索算法山东省第四届省赛

题意就是判断任意两点是否联通,因为是有向图,就要求任意两点之间至少有一条单向路,一开始没什么思路,在没有思路的时候暴力搜索就是最好的思路. 因为暴力出奇迹. 但还是先算一下时间复杂度. 搜索的话,就是对每一个点进行广搜,记录每一个点可以到达的点,这样的话时间复杂度就为 N * M = 2e7 . 所以这是可以暴力的.不过广搜的时候,发现的一个问题,因为一个点可以出现出队后在入队的情况...

2018-03-26 17:36:02 260

原创求割点和点联通分量

今天又开始搞图论，今天的这个算法是用来求割点的算法。以及将这个点去掉后可以形成的强联通分量数。先来解释一下原理：先来思考一下最朴素的算法，就是将每个点进行标记，意为将其去掉，然后进行深搜遍历，统计联通分量的个数。这个时间复杂度为 n (这个是n个被去掉的点)* n （判断n个点）* n（搜索）？？？这个宝宝也不是很清楚的拉略略略~先来说一下Tarjan(塔尔杨) 算法的原理，...

2018-03-25 16:39:32 260

原创母函数生成函数初步

母函数简单来说就是用于组合计数的函数，利用同底数乘法的性质，来模拟组合问题。用其指数描述情况种类，其系数描述组合数。今天先来讲一下模板这个是hdu1398 一个模板题‘ #include<cstdio> #include<iostream> using namespace std; const int MAXN = 300 ...

2018-03-22 16:15:31 210

原创山东省第四届省赛 A^X mod P (连续求多个高次幂) 哈希思想

今天开始训练难题,这个题常规思路超时,因为算法复杂度为 T (40)* 1e6 * log 1e9 (30)大约等于1.2 * 1e9 无论怎么样优化快速冪的操作都会超时,而递推式的(1e6)很难优化,这是可以考虑降低一个快速冪的时间复杂度,假设如果可以在o(1)的时间内算出冪,但是如何算呢? 其实算一个数的快速冪的时间复杂度是log(N),但是在算多个的时候显得没有优势了, 再来想一下,如果...

2018-03-22 16:13:37 223

原创蓝桥杯水题矩形面积交

一开始以为是扫描线算法,但是仔细一看基础题出扫描线?,想了一下一直卡在两个矩形的左右关系上,看了题解才发现,原来矩形的面积交与坐标的相对位置有关,其实就是位置第二大的x与位置第三大的x可以组成矩形,y同理.#include<cstdio>#include<iostream>#include<iomanip>using namespace std;...

2018-03-20 15:26:51 336

原创 proxy 逆向建图 dijkstra算法山东省第七届省赛

这个题的思路就是先逆向建图这点不容易想到,逆向建图的原因是便于枚举与0临接的边,如果正向建图的话是没有办法实现的, 一直在WA,后来看了题解也知道自己对题目的挖掘还不够,而且对dijkstra的理解也还不够. 这个题的思路就是先逆向建图求出最短路之后,枚举与0临接的边. 坑点在于这个图不一定是联通图. ACcode#include<cstdio>#include&...

2018-03-15 16:44:25 226

原创第六届省赛J题 single round math

解题的逻辑在于先判断相等,然后就是判断这个数是否可以被11整除. 由于这个数很大,很容易就想到了同余定理.就是怎么样用的问题了. 第一首先想到的是我之前看过一个结论就是关于可以被11 整除的数,每位数之间是有关系的按照这个经验了一下就发现了,奇数位上之和和偶数位上之和之差可以被11整除第二大数取模的思想.这个实在网上看的.来说一下. 类似于秦九召算法,的原理就是递归的思想利用同余...

2018-03-11 15:06:39 219

原创第四届山东省赛A题 Rescue The Princess

三角定位法:已知两点和角度,求以这两点为向量转过逆时针转过给定角度后的新点坐标. 以给定向量和与其逆时针垂直的向量建立基向量,根据角度分解求解之#include<cstdio>#include<iostream>#include<cmath>#include<iomanip>using namespace std;int main...

2018-03-11 14:05:11 189

转载优先队列的用法

优先队列的使用 http://www.cnblogs.com/void/archive/2012/02/01/2335224.html优先队列是队列的一种，不过它可以按照自定义的一种方式（数据的优先级）来对队列中的数据进行动态的排序每次的push和pop操作，队列都会动态的调整，以达到我们预期的方式来存储。例如：我们常用的操作就是对数据排序，优先队列默认的是数据大的优先级高所以我...

2018-03-04 09:44:59 418

原创 poj 3255 松弛思想求次短路

#include <cstdio>#include <cstring>#include <queue>#include <algorithm>#define MAXN (5000 + 10)#define INF (5000*5000*2)using namespace std;struct edge{ // 临界表 int ...

2018-03-04 09:24:47 209

转载图论500题

=============================以下是最小生成树+并查集======================================【HDU】1213 How Many Tables 基础并查集★1272 小希的迷宫基础并查集★1325&&poj1308 Is It A Tree...

2018-02-27 15:22:41 213

原创 poj 1014 多重背包

就是判断弹珠是否可以平分，一开始想到了背包模型。一开始转画成了01背包。wa了。那是就一直在纠结物品的cost是什么，假设成了1，后来一直不对，看了题解他们将cost 设定等于就是将cost等同于weight.就是在寻找也可以转化这样想，将所给的标准就是cost，也就是体积的话，问题就转化成了在不考虑价值的情况下。怎么分配可以放满容积为 sum / 2 的背包。 #include&l...

2018-02-26 21:04:42 313

原创给定区间整数分解 by kuangbin模板

#include<cstdio>#include<iostream>using namespace std;typedef long long LL;const int MAXN = 1e4;int prime[MAXN + 10];void getprime(){ fill(prime,prime + MAXN,0); for(int i =...

2018-02-24 17:18:36 158

原创 1.1.3 Friday the Thirteenth 黑色星期五

#include<cstdio>#include<iostream>#include<cstring>using namespace std;int a[10];int time1[18] = {0,31,28,31,30,31,30,31,31,30,31,30,31};int time2[18] = {0,31,29,31,30,31,30,31...

2018-02-20 19:24:48 360

原创有向图的欧拉回路判定问题 poj1386

这个题也卡卡卡，发现自己好粗心，唉.。有向图的判定:统计每个点的出度和入度，前提是有向图是连通图。 1. 如果每个点的出度 = 入度则存在欧拉回路。 2. 如果有且仅有两点出度、入度不想等，且这两个点的出度 - 入度差为1 或 -1.差为1的那个点是欧拉图的起点，为 -1 的是重点。这个题先来判断图的连通性，用并查集的方法，值得注意的一点是并查集是以点为元素的，所以

2018-02-05 09:53:57 875

原创欧拉回路的判定 poj 1300

这个题卡了一上午卡到心态爆炸，卡到欲仙欲死。各种bug蜜汁出现。一边一遍的调试，忽然发现思考成熟是多么的重要！最后是一个短路效应的问题，怀疑人生！这个题就是统计出度和入度，就是建图有点麻烦，其实也不算太麻烦了。对于无向图而言就是判断是否满足没有奇度顶点，或者奇度定点只有两个，并且这两个奇度顶点其中一个是0，另一个是起点。#include#include#include#inc

2018-02-04 15:18:41 204

转载剪枝之奇偶剪枝 zoj 2110

今天学了下剪枝，简单来说一下剪枝是什么，在深搜过程中，如果标记其点，会生成一颗搜索树，但是有一些“枝”是无效的，所以可将其“剪去”。奇偶剪枝转载自 http://blog.csdn.net/chyshnu/article/details/6171758/ 什么是奇偶剪枝？把矩阵看成如下形式： 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1

2018-02-03 11:09:09 262

原创 hdu 1242 Rescue

bfs的拓展应用就是搜索无论是形式，关键在于状态的转移，和动态规划一样，如何划分状态是解决问题的关键。这个题是寻求最少的时间，由于有坑点r可能有多个，就要反向搜索，将a点作为起点进行搜索，再将r点的坐标记录，利用动态规划的思想将每个点的可达最小值记录，然后求个最小值就可以了。#include#include#includeusing namespace std;const i

2018-02-02 16:40:48 196

原创 zoj 2770 Burn the Linked Camp(火烧连营) 差分约束

今天学了一个东西叫差分约束，简单来说就是用最短路知识的三角不等式来解多元不等式组。假设 Xv - Xu 但是难点在于如何根据已知条件构造不等式组，这是难点，也是解决问题的关键。#include#include#include#includeusing namespace std;const int MAXN = 1000 + 10; // 点数const int MAX =

2018-02-02 16:03:17 381

原创 poj 2570 Fiber Network floyd 传递闭包与二进制压缩

题意就是每个段光缆被一些公司掌握，询问所给定的一段上的光缆所有可以掌握它的公司，如果有字典序输出，没有的话输出‘-’。思路：看完题意不难想到就是个传递闭包将所有点对路径上的公共字符找出来，如果是处理字符串有点麻烦，就引出了一种新的方法和思想，二进制压缩。就是将有限字符集映射到一段二进制数上，这个忽然想起了真值函数的思想，二者本质相同，都是将难以处理的集合元素根据性质映射到01序列上。

2018-01-31 10:07:49 256

原创 poj 3268 Silver Cow Party

求所有奶牛往返的最短时间中最长的，将问题转化为两部分，一是求去时，这部分是将目标点作为起点，将每个点的出边作为数据建立邻接表，二是求回来时，这部分是将目标点作为起点，将每个点的入边作为数据建立邻接表。将上述求得的数据求和找最大。注意图有可能不是连通图。#include#include#include#include#includeusing namespace std;const

2018-01-30 16:33:24 154

空空如也

空空如也