- 博客(79)
- 收藏
- 关注
RSS订阅原创 容斥定理+鸽巢原理
容斥定理+鸽巢原理容斥定理要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。容斥原理：在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研...
2019-08-14 20:27:36
2150
2
原创 F
题意：问n个点中是否存在两对不同的点的曼哈顿距离相等。题解：有的同学可能会想，直接算出每两个点之间的曼哈顿距离，然后看看有没有重复的就可以了，不过这个题上给的n是 1e5那样算的话一定超时，那么应该怎么办呢，想一下，这个题上还给了一个 m，m最多是1e5，所以曼哈多距离最多是2*1e5，根据鸽巢原理，只要我们算的点超过了2*m（m是题上说的m），就一定有距离相等的。所以判断的时候我们...
2019-08-14 15:32:30
183
原创 A
题意：就是把一个数字分成一个奇数和一个偶数相乘，题解：水题：代码：#include<stdio.h>typedef long long ll;int main(){ ll i,n,t,cnt,sum,m; scanf("%lld",&t); cnt=0; while(t--) { cnt++; scanf("%lld",&n); ...
2019-08-14 11:00:49
189
原创 B
题意：给你一个集合M，里面最多有10个非负数，问1~n-1中一共有多少个数可以被其中一个整除。题解：容斥定理，这个题和C题几乎一样，我们只要在C的基础上求个LCM就行了代码：#include<bits/stdc++.h>using namespace std;#define ll long longll gcd(ll a,ll b){ return b==...
2019-08-14 10:49:24
320
原创 E
题意：题上说的很明白了。题解：只要最大值能够被隔开，那么其他的所有的值就都能够被隔开了，所以只要sum-max+1>=max 就是YES，否则就是NO；代码：#include<bits/stdc++.h>using namespace std;#define ll long longint main(){ ll t,n,A; scanf("%...
2019-08-14 10:34:36
144
原创 CODE[VS]-1332
CODE[VS]-1332基本上算是强；连通分量的板子题吧，只需要对最后的拓扑序稍微的操作一下就行了，下面给出代码。#include<bits/stdc++.h>using namespace std;#define met(Q,QQ) memset(Q,QQ,sizeof(Q))const int maxn=5007;vector<int > G[m...
2019-08-07 20:17:15
338
原创 POJ-2186(强连通分量)
poj-2186题意：每头牛都想成为牛群中的红人。给定N头牛的牛群和M个有序对(A, B)。(A, B)表示牛A认为牛B是红人。该关系具有传递性，所以如果牛A认为牛B是红人，牛B认为牛C是红人，那么牛A也认为牛C是红人。不过,给定的有序对中可能包含(A, B)和(B, C),但不包含(A,C)。求被其他所有牛认为是红人的牛的总数。比较暴力的思路：假如我们直接暴力就是我们直接建图，然后再对每...
2019-08-07 16:50:03
235
原创 强联通分量算法入门
强联通分量，听着名字挺高大上的，一直听别人说但是自己也不知道是什么东西，昨天晚上，看见别人在学习这个东西，闲来无事的无就也学了学。强连通分量在图论问题中得到广泛的应用，往往可以将有向图缩点，得到一个 DAG，于是避免了原图中可能有环造成后效性，可以在上面进行动态规划求解。强联通分量究竟是干什么用的呢？我感觉吧他就是为了节约时间，因为有的题图给的会比较大，如果我们按正常的方法去写，一般...
2019-08-07 16:40:25
169
原创 大数模板
//大数相加#include <stdio.h>#include <string.h>#define MAXN 100int an1[MAXN+10];int an2[MAXN+10];char str1[MAXN+10];char str2[MAXN+10];int main(){ memset(an1,0,sizeof(an1)); ...
2019-08-05 16:21:08
78
原创 矩阵快速幂-构造矩阵
参考博文：https://blog.csdn.net/Akatsuki__Itachi/article/details/80443939感觉矩阵快速幂也不是太难吗，矩阵的乘法基本上都会吧，还有快速幂这也没有啥难度，所以矩阵快速幂的板子其实挺简单的。关键都是矩阵的构造，假如矩阵快速幂的题，如果你能够把矩阵给构造出来，那你这道题就已经出来了。所以说矩阵快速幂的关键就是构造矩阵，这篇文章就说一下矩阵...
2019-08-02 19:41:54
376
原创 hdu-5667（矩阵快速幂）
前两天就已经学习了矩阵快速幂，当时的我就学了个矩阵快速幂的模板，而且我还以为我自己学会了，实在是太搞笑了，矩阵快速幂最难的地方就是构造矩阵，而我根本一点都不会构造矩阵，没办法，从新学呗，hdu-5667这个题，我个人感觉也挺难的，因为矩阵好构造，这就是这个题的难点吧，思路：发现a^b，和f[i-1]^c之类的东西，我们很明显吧这个幂变成乘，很自然的想到对数。问题是对什么取对数，最后发现...
2019-08-02 15:53:23
252
原创 RMQ算法入门（dp）
在开始学LCA的时候，看别人的博客，知道了RMQ这个算法，在学LCA的时候会用的到，于是我就先把这个算法给学了，一百度，原来RMQ算法实现的功能，和线段树差不多，还有这个算法也是dp，dp无处不在啊，RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在...
2019-08-01 12:10:16
338
1
原创 洛谷P1706（dfs）
学dfs一年了，但是感觉还是不会，没办法，只有在学了，关键是我不能理解它的递归的思想，每次只要递归我就有点不太懂了，可能是自己太笨了吧，没事，熟能生巧，既然不会，那我就在多刷几道题就行了。洛谷P1706这个题的意思很简单，大致意思就是给你一个n输出1~n的全排列，直接dfs搜索就行了，感觉也没有啥好说的，直接给出代码吧，并附上详细的注释。#include<bits/stdc...
2019-07-31 15:18:35
201
原创 矩阵快速幂模板
#include<stdio.h>#include<string.h>using namespace std;#define ll long long#define met(d,dd) memset(d,dd,sizeof(d))const ll mod=10000;struct stu{ int a[3][3];};stu cheng(stu...
2019-07-31 10:03:47
146
原创 poj1463（树形dp）
刚简单了学习了一下树形dp，我们再来做一道题联系一下吧，poj1463题意：大致意思就是现在给你一个树，然后让你再每个节点上放士兵，每个节点的士兵都可以管辖与这个节点相连的所有的边，让你放置最小的士兵来使这个树的每条边都可以被管辖，求最小放置的士兵数。思路：这个题大致一看就是一个dp，又是因为这是一个树。所以就是树形dp了，（这样解释是不是有点那个啥啊，哈哈）首先我们先找状态转移方...
2019-07-30 15:21:09
411
原创 树形dp（入门）
今天我们来简单了解一下树形dp，树形dp，顾名思义就是在树上进行动态规划，其实这和其他的动态规划中心思想是一样的，不过这个难点之处就是在树上进行的，因为树有其特殊的结构特点，一般对树的处理用的都是递归的思想，这就是其难点所在吧，其实学树形dp，HIA有助于帮助我们增强我们对树的处理，对于树形dp感觉也没有什么可以 说的，还是直接给题去训练吧，在做题中慢慢的理解树形dp的精髓。poj2342...
2019-07-30 10:21:21
278
原创 区间dp（入门）
这个区间dp学完dp就先告一段落了。虽然感觉dp还是啥都不会吧，但是比以前强了那么一点点，至少现在听见那希望名字知道是干什么用的了，这次我们简单的说一下区间dp。顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，...
2019-07-29 16:26:19
363
原创 数位dp（入门）
这一周一直在学dp，先学了一些简单的dp，然后又学了状压dp，这次又学了数位dp，唉，感觉这dp是真的难，可能是我太菜了吧，没办法，慢慢学吧，本来准备一周把dp学完是不太可能了，因为今天已经周六了，还是进入正题，说我们的数位dp吧。数位dp是一种计数用的dp，一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp，字面意思就是在数位上进行dp咯。数位还算是比较好听的名字，数位...
2019-07-27 08:38:13
361
2
原创 poj- 3254（状压dp）
poj-3254【题目大意】一个矩阵里有很多格子，每个格子有两种状态，可以放牧和不可以放牧，可以放牧用1表示，否则用0表示，在这块牧场放牛，要求两个相邻的方格不能同时放牛，即牛与牛不能相邻。问有多少种放牛方案(一头牛都不放也是一种方案)#include<stdio.h>#include<string.h>using namespace std;cons...
2019-07-25 18:49:21
327
原创 【ZOJ4257】MostPowerful （状压dp）
【ZOJ4257】MostPowerful这个题从早饭看到晚饭，真的是，看到快吐了，题意：这个题的大致意思就是，现在有很多的原子，然后这些原子之间可以互相碰撞，碰撞后会有一个原子消失，而且碰撞后悔释放一定的能量，求可以获得的能量的最大值，这个题吧，用的就是状压dp，我们可以用0表示这个原子还在，1表示这个原子不在。为什么很多的题都是用0表示有的意思而不是用1 呢，这是因为这样用的话...
2019-07-25 18:26:01
182
原创 状态dp入门
状压dp，很早我就听说过这个算法的名字，感觉这个算法就是可厉害的那种，从昨天起开始了学习状压dp的道路，然后被虐的很惨，真的感觉好难啊，首先我先大致看了看状压的概念，然后便开始看题，看那些经典的题，自己肯定是不会做的，就看别人的代码，可能因为别人都比较厉害的缘故吧，写的代码都不没有太详细的解释，我看起来是真的费力，昨天下午加晚上看懂了一道题，然后今天从早上到现在又看懂了一道题，真的是心累，经过这两...
2019-07-25 18:07:59
486
原创 最大子段和
N个整数组成的序列a11,a22,a33,…,ann，求该序列如aii+ai+1i+1+…+ajj的连续子段和的最大值。当所给的整数均为负数时和为0。例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。Input第1行：整数序列的长度N（2 <= N <= 50000)第2 - N + 1行：N个整数（-10^9 <= Aii...
2019-07-24 10:11:42
79
原创 HDU1284：钱币兑换问题(完全背包)
Problem Description 在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。 Input 每行只有一个正整数N，N小于32768。 Output 对应每个输入，输出兑换方法数。 Sample Input ...
2019-07-24 09:49:08
356
原创 CF-D. Polycarp and Div 3
D. Polycarp and Div 3time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputPolycarp likes numbers that are divisible by 3.He has a ...
2019-07-24 08:36:28
176
1
原创 cf-C. Array Splitting
C. Array Splittingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given asortedarraya1,a2,…,ana1,a2,…,an(for each i...
2019-07-23 09:29:06
212
原创 hdu-6570
Wave Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 237Accepted Submission(s): 110 Problem Description Avin is st...
2019-07-23 09:12:26
430
原创 hdu-6573
Traffic Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 267Accepted Submission(s): 116 Problem Description Avin is...
2019-07-23 08:46:23
344
原创 hdu-6577
Class Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 229Accepted Submission(s): 161 Problem Description Avin has ...
2019-07-23 08:33:23
153
原创 逆元
时隔一年了，又重新学了逆元。首先来说一下逆元的概念，逆元，什么是逆元呢，设c是b的逆元，那么b*c%m=1，一个数字是另一个数字的逆元是在另一个数字的前题下的，就是一说谁是谁的逆元，必须是在一个数字的前提下的，逆元和倒数差不多，但是又不是倒数，再说一下逆元的作用，逆元是用来干什么的，怎么说呢，下想一个问题吧，求 (a/b)%m这个式子的结果，是不是无从下手，我们假如c是b的逆元，那么b*...
2019-07-22 18:55:29
288
原创 hdu-1160 LIS记录路径
2019暑期集训的第一篇博客这次写一下LIS记录路径的问题，当你学会了LIS后有没有想过把路径给记录下来，就是最长递增子序列是有哪几个数字组成的，怎么记录呢，其实很简单，就是用递归的方法，首先你可以每个点的上一个点是谁，意思就是说知道此时这个点的LIS是在哪个点的基础上转变过来的，我们只要开一个数组，记录每个点的上一个点，然后逆序递归输出就行了，下面给一个例题，来详细的说一下LIS记录路径...
2019-07-20 11:26:43
137
原创 123
#include<bits/stdc++.h>using namespace std;vector<pair<int,int> > vec[10005];pair<int,int> p;int pre[10005];queue<int> que;int B[10005];int C[10005];int n,m;s...
2019-07-18 16:26:02
71
原创 被一些数字整除的数字的特征
一些数字能不能被一些数字整除，这都是有规律的。下面就来说一说能被一些比较小的数字整除的数的特征。能被2整除：数字应是偶数。能被3整除：各位数字之能被3整除。能被4整除：最后两位数字组成的两位数能被4整除。能被5整除：最后一个数字为0或5.能被6整除：同时满足能被2整除和能被3整除的两个特征。能被7整除：设一个数为abc def , 则def - abc 能被7整除 ,又...
2019-04-09 16:33:14
2073
原创 一些好的函数。
最近几次比赛发现都吃函数上的亏了，一些非长好用的函数我竟然都不知道，在这里总结一下。gets（）函数：这个函数刚学的时候比较喜欢用，后来慢慢的都不用了，我也不知道为啥，可能是这个函数用处不太大吧，一般只有读入的有空格的字符串的时候才会用它，这不前天比赛的时候我就用这个函数了，结果凉凉，因为c++已经没有这个函数了，当时可把我一顿好整。决定以后我的代码里从今往后不会再出现gets了。ge...
2019-03-19 17:18:13
284
原创 A. Boredom
A. Boredomtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputAlex doesn't like boredom. That's why whenever he gets bored, he comes...
2018-12-11 21:03:18
1021
原创 hdu-2058
晚上放学后没事干准备刷几道题，结果第一道题都不会写了，一道题卡了好久，最后也是没有写出来，唉！好无奈，最后还是看了别人的代码，原来是一道数学类型的题，就是推公式吧，如果你能够推出来，这道题也就写出来了。 Problem Description Given a sequence 1,2,3,......N, your job is to calculate all the pos...
2018-11-12 22:39:45
328
原创 Dijkstra算法
Dijkstra算法，一个名字听起来非常的高大上的算法，他究竟是何方神圣?其实呢这只是一个不是太难而且非常实用的一种算求最短路径的算法，当你真正的掌握之后用起来真的是非常的方便，感觉学习这个算法已经很长一段时间了，但是一直没有去写博客，因为感觉自己并没有完全的掌握它，今天就试一下写一写自己对这个算法的理解吧！！Dijkstra算法解决的是单源最短路径问题：对于给定的有向网络G=(V,E...
2018-11-06 18:46:32
289
原创 hdu-2074
今天晚上写了hdu上的一道水题，题吧，也不难，要不然就不叫水题了，可是却做了好长时间一直错，难受，还是先看题吧 需要的时候，就把一个个大小差一圈的筐叠上去，使得从上往下看时，边筐花色交错。这个工作现在要让计算机来完成，得看你的了。 Input 输入是一个个的三元组，分别是，外筐尺寸n（n为满足0<n<80的奇整数），中心花色字符，外筐花...
2018-10-30 21:03:09
586
原创 hdu-2076
饭后一道水题； Problem Description 时间过的好快，一个学期就这么的过去了，xhd在傻傻的看着表，出于对数据的渴望，突然他想知道这个表的时针和分针的夹角是多少。现在xhd知道的只有时间，请你帮他算出这个夹角。 注：夹角的范围[0，180]，时针和分针的转动是连续而不是离散的。 Input 输入数据的第一行是一个数据T...
2018-10-30 19:09:45
188
原创 hdu-2078
晚上上课回来什么都不干，先刷两道题再说； 为了能过个好年，xhd开始复习了，于是每天晚上背着书往教室跑。xhd复习有个习惯，在复习完一门课后，他总是挑一门更简单的课进行复习，而他复习这门课的效率为两门课的难度差的平方,而复习第一门课的效率为100和这门课的难度差的平方。xhd这学期选了n门课，但是一晚上他最多只能复习m门课，请问他一晚上复习的最高效率值是多少？ ...
2018-10-29 21:53:18
323
原创 牛客——黑魔法师
链接：https://www.nowcoder.com/acm/contest/215/A来源：牛客网 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述“White shores, and beyond. A far green country under a swift s...
2018-10-29 13:02:20
212
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人