- 博客(200)
- 问答 (1)
- 收藏
- 关注
RSS订阅
原创 P5638 【CSGRound2】光骓者的荣耀
抽丝剥茧，仔细读题，其实就是考察 一个数列中，连续K个数，找出期中最大的连续K个数的和sum,然后用数列总的和减去sum 就是这道题的答案了~当然别忘了 ：一定要开long long int ，ai的取值范围<=10^12 n<=106,这个数列最大的和是1018long long 的数据范大约是 1018+,所以可以容纳1018下面是AC code~#include <iostream>#include <cstring>using namespac...
2020-08-28 17:55:12
265
原创 P2004 领地选择
思路：二维数组的前缀和，用这个做很快的~#include <iostream>#include <cstring>using namespace std;typedef long long int ll;#define Max 1001ll a[Max][Max];ll matrix[Max][Max];ll sum[Max][Max];ll M=-999999; int main() { ll n,m,L; l..
2020-08-28 16:33:39
242
原创 P1719 最大加权矩形
这道题用暴力就是前缀和，四层for循环，我们这里用另外一种压缩矩阵的方法做.~emmm思路就不写了，有疑问看看dalao的博客#include <iostream>#include <cstring>using namespace std;#define Max 130int a[Max][Max];int b[Max];int dp[Max];int M=-9999; int main() { int n; ci..
2020-08-28 13:20:30
333
原创 P3397 地毯
这道题暴力其实也可以过，但是最好不要暴力了，能过都是运气而已，正经做法用差分。二维差分来做，不知道的差分的去康康其他dalao的博客~#include <iostream>#include <cstring>using namespace std;#define Max 1005int a[Max][Max];int c[Max][Max]; int main() { memset(a,0, sizeof(a)); m...
2020-08-26 10:55:54
155
原创 P1115 最大子段和
这是一道很好的动态规划的入门题，用暴力当然也能解决，但是肯定会超时，如果是填空题用暴力和动归差不多…用暴力的时间复杂度是o(n^2) n的数据达到10 ^ 5是受不了的，但是用动态规划的时间复杂度是o(n ) .主要讲解动态规划如何做：设置一个状态 dp[i] 表示以i为下标结尾的最长子段和(数组下标从1开始).我们用用例来举例子;72 -4 3 -1 2 -4 3dp[1]=2 a[1]dp[2]= -2 a[1]+a[2]dp[3]=3 a[3]dp[4]=.
2020-08-25 11:56:45
193
原创 P1403 [AHOI2005]约数研究
这道题暴力会T掉，直接用数学方法吧. n/i表示 1—n中有多少个因子有i,一个for循环累加即可.#include <iostream>using namespace std; int main() { int n,sum=0; cin>>n; for(int i=1;i<=n;i++) { sum+=n/i; } cout&l..
2020-08-18 22:19:12
79
原创 P2660 zzc 种田
这道题比较容易，递归可以很快就做出来！不过要注意尽可能降低递归层数，否则容易爆栈。下面是 AC code：#include <iostream>using namespace std;typedef long long int ll;ll fun(ll x,ll y); int main() { ll x,y; cin>>x>>y; cout<<fun(x,y)<<end.
2020-08-16 18:59:21
102
原创 P2651 添加括号III
这道题其实很简单，我们只需要变行就可以啦.a1一定是分子，a2一定是分母 a1 /(a2/a3/a4/a5…an)化简可以得到a1a3a4a5an/a2我们只需要用 a1 a3 …an分别与a2求最大公约数gd 看看有没有那一次可以使得 a2/gd = =1如果某个ai(i= 1 3 4 5 6 … n)与a2的最大公约数是 gd 并且 a2/gd==1，那么可以断定,可以得到整数，即输出Yes，否则输出No下面是 AC代码~#include <iostream>using..
2020-08-16 17:07:34
99
原创 P1414 又是毕业季II
这道题很容易想到暴力的dfs ：选择k个数以后，找出所有选出k 个数以后的最大值。但是，对于这道题的数据n<10000肯定会凉凉，我们只能另辟蹊径.我们可以这样思考：如果k个数都含有某个因素 x 那么x一定是他们的公约数，找到这个k个数的公共因素最大的x 就是这k个数的最大公约数.所以我们可以对每个同学的能力进行因素分解，开一个数组b[] ,就比如某个同学的能力值是12那么他的因素就是 1 2 3 4 6 12 对应的就是b[1]++ b[2]++ b[3]++ b[4]..
2020-08-15 16:52:28
174
原创 P4057 [Code+#1]晨跑
考察：最小公倍数…注意 开 long longAcode~#include <iostream>typedef long long int ll;using namespace std;ll lcm(ll a,ll b); int main() { ll a,b,c; cin>>a>>b>>c; ll res=1; res=lcm(a,b); r...
2020-08-11 17:51:23
128
原创 P1572 计算分数
这道题可以当做一个大的模拟题，难度应该是普及-，思路：用vector v1保存分子，vector v2保存分母 vector v3保存符号 （+ -）然后求出 分母的最小公倍数s v1分子乘以 s/v2对应的分母 然后 v1里根据v3的符号进行加加减减 最后得到res 再对res 与 s 求最大公约数 gd 然后分子分母同时除以 gd 就是最后结果了踩坑点：（1）分母为1 不用输出 /1 输出分母即可（2）求最大公约数要用他们的绝对值来求下面是Accode:#include &.
2020-08-11 17:32:04
250
原创 P1069 细胞分裂
这道题很容易想到质因数分解，满足题目条件可以装入试管的情况是m1的质因子是Si的质因子的子集，也就是说m1有的质因子Si一定要有，Si有的质因子m1 却不一定要有…对于样例112 13m1=2 m2=1, s1=3m1的质因子是2 s1的质因子是3 m1的质因子不是s1质因子的子集，所以无论怎么分裂都不会满足.对于样例2224 130 12m1=24 m2=1 s1=30,s2=12m1=2223s1=23*5对于s1， m1的质因子是s1的子集所以可以装瓶。那么最少需要分...
2020-08-11 11:34:31
460
原创 P1072 Hankson 的趣味题
emmm这道题看到题目首先要打一下草稿，首先暴力的算法可能是会T掉了，最开始我就是用的暴力的算法，T掉了5个点，还是得了50分（如果想不到好办法暴力就暴力吧）附上暴力代码~#include <iostream>using namespace std;int gcd(int a,int b);//a>=bint lcm(int a,int b); //a<=b int main() { int a0,a1,b0,b1; in..
2020-08-09 14:07:18
143
原创 P1029 最大公约数和最小公倍数问题
这道题蛮简单的，但是也需要一点预备知识，两个数的最小公倍数和最大公约数的乘积等于这两个数的乘积.证明·：x0 y0的最大公约数是A,最小公倍数是B,x1=x0/A,y1=y0/A那么x1 y1一定是互质的所以x1 * y1 * A=B展开一下就可以得到A*B=x0 * y0至于为什么x1y1A=B,可以去康一下最小公倍数的短除法的求法，一看就明白了.知道这个定理以后题目就很简单了，满足条件的两个数的乘积就是x0y0, 现在就开始枚举，一个数x的因子我们只需要枚举1----sqrt(x)，..
2020-08-08 17:48:12
352
原创 P3383 【模板】线性筛素数
这道题就是是一个线性筛选 我们这里使用欧拉筛选…对于每一个合数，他被筛选出去一定是他的最小质因数乘以他的除了他自身的最大因子。这个就是原理.证明部分请看其他博主（证明好像挺难的，数学没学好的就没看了，记住结论就行） PS:在这种卡时间的题目，不必要的语句就别写了…时间卡的很紧的下面是AC代码：#include <iostream>#include <unordered_map>#include <cstring>using namespace std;#..
2020-08-06 18:54:25
224
原创 P2926 [USACO08DEC]Patting Heads S
这道题很容易会想到O(n ^ 2)的算法，但是这个肯定会超时，比如我。最后以55分草草收场,改进以后就有100分啦.是这样的，他不是让我们分别求每头牛手上的数字可以整除多少头其他牛上手的数字吗？O(n^2)的算法就是用每头牛分别去判断其他牛的数字是否可以整除…换成另外一钟更快的算法是这样的，首先我们记录每头牛手上的数字有多少个，比如我们在输入的时候 如果输入5就 让b[5]++ 输入的是6 就让b[6]++ 输入完毕以后每头牛手上的数字每个数字的个数都会记录了下来… int n,num=0; ..
2020-08-06 12:03:56
191
原创 P1246 编码
这道题用排列组合来做，但是很难想到.比如某一串字母 cgi他对应的数字是多少呢？，首先他绝对是大于3位以下的字母的数字。首先考虑一个字母： a =1 b=2 c=3 ，一位的情况是C(26,1)=26，再考虑两个字母的那就是C（26，2），在考虑三位的情况。三位的情况稍微复杂点，但是其实也不复杂。先固定第一位可以是a–b任意一个字母，如果第一个是a,那么就加上C（25，2），如果第一个是b，那就加上C（24，2），然后固定第一位c,再考虑第二位可以是d–f之间任意一个字母，如果第二个是d那就加上C(22,.
2020-08-03 23:57:24
198
原创 单链表的翻转
给定一个带头结点的单链表和一个整数K，要求你将链表中的每K个结点做一次逆转。例如给定单链表 1→2→3→4→5→6 和 K=3，你需要将链表改造成 3→2→1→6→5→4；如果 K=4，则应该得到 4→3→2→1→5→6。输入样例：61 2 3 4 5 64输出样例：4 3 2 1 5 6#include <stdio.h>#include <stdlib.h>typedef int ElementType;typedef struct Node *PtrTo
2020-07-02 12:16:08
129
原创 P2638 安全系统
这道题考察的是高中数学知识，排列组合，隔板法。还没有学过或者忘记了的小可爱去看一下百度词条哦~ 点击这里查看隔板法题目中有句话容易读错,每个储存区最多能存储存2个种类不同的信号.，是存储两个种类不同的信号，不是两个信号.对于本题而言换句话说就是任何一个存储区都可以存储无线个信号题目中还说了 存储区可以不用存储信号~问题转化为这个：有a个红球，b个白球.将这些白球和红球放到不同的盒子里面，问有多少种不同的分法，首先a个红球分配到n个盒子有多少种分法，假如说是x1，b个白球分配到n个盒子有多少种分法..
2020-05-26 20:27:23
298
原创 P3913 车的攻击
这道题的数据量有点对不上，其实N是没有10^9的.N最大不会超过10^6如果数据是10^9的话 那么unordered_map才是正解#include <iostream>#include <unordered_map>using namespace std;unordered_map<int ,int > r;unordered_map<int ,int > c;typedef long long int ll; int main(.
2020-05-24 10:51:07
165
原创 P2822 组合数问题
这道题本身倒是不难，但是卡时间卡的太严重了。对于t是10^4次方查找，我们递归将C（n,m）求出来，并用一个数组记忆化保存，然后对于每次查询，我们循环遍历就可以了~#include <iostream>#include <cstring>using namespace std;#define Max 2005typedef long long int ll;ll C[Max][Max];ll get_c(int n,int m); int main()...
2020-05-23 14:38:47
597
1
原创 P1866 编号
可能是DFS写多了，看到这种题直接暴搜，结果T掉了7个点…T7点代码：#include <iostream>#include <cstring>using namespace std;#define Max 1005int t[Max];bool flag[Max];int res=0;int n,num=0;void dfs(int i,int t[]); int main() { cin>>n; .
2020-05-22 12:28:46
473
原创 P1017 进制转换
这道题实际上是一道数学题~首先我们要清楚余数：15 / 4=3…315 / -4=-3…3-15 / 4= -3…-3-15/-4=3…-3开始我也不知道负数除以负数的余数是负数…奇怪的知识增加了~然后题目说了十进制数 ，第二个是负进制数的基础.十进制数可正可负 ，但是第二个负进制数一定是负数.所以我们求以前进制数的时候，余数都是正数对不对，但是这里可能会出现负数.例如上面的：一个负数除以一个正数或者负数的余数都等于负数.但是最后结果不能有负数怎么办呢？很简单，我们只需要让余数-除数..
2020-05-22 11:51:55
271
原创 P1100 高低位交换
很简单的模拟题~注意开long long int 下面是ACcode~#include <iostream>#include <vector>#include <algorithm>using namespace std;typedef long long int ll;vector<int > t; int main() { ll n; cin>>n; int res.
2020-05-21 23:10:25
158
原创 P1469 找筷子
看到数据是10^7, 内存是4MB第一反应：复杂度肯定是0(n) ,用数组肯定会MLE这时候要用到异或^0和任何数异或都等于任何数，0^x=xx和x异或等于0 x^x=0我们只需要最开始设置 res=0,然后不停的与输入的x进行异或，最后得到的结果一定是那个单个筷子ACcode:#include <iostream>using namespace std;int main(){ ios::sync_with_stdio(false); int n..
2020-05-21 22:23:43
293
原创 P1143 进制转换
先转化为10进制，再转换为其他进制数：AC code:#include <iostream>#include <vector>using namespace std;vector<char > t;int main(){ int n,m,num,res=0; char c; cin>>n; string str; cin>>str; cin>>m; for(int i.
2020-05-21 10:46:06
252
原创 P1983 车站分级
这道题层次分明，很显然用拓扑排序：首先要注意审题：如果这趟车次停靠了火车站 xx，则始发站、终点站之间所有级别大于等于火车站 xx 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）这句话要理解一下：她说如果停靠在了火车站XX，后面只要是大于等于XX的都必须停靠，但是他没说小于XX的火车站不停靠…就比如上图第一趟火车 ：3 2 3 2（火车站的优先等级），我们最开始在优先级为3的火车站，后来又跑到了优先级为2的火车站，所以并不是小于XX的都不停，也有可能停住.注意上面，我们停..
2020-05-21 09:54:20
237
原创 P1347 排序
这道题一看就是拓扑排序，不过细节特别要注意。题目中说了，如果某一步能判断n个字母的大小关系，那么就输出第几步可以判断这些大小关系，并输出从小到大的序列，例如样例1就是第4步就可以判断大小关系了，后面说的看都不用看如果某一步会导致矛盾，就输出导致矛盾的那一步。例如上面的样例2第2步可以判断发生矛盾如果遍历完所有步数都不能判断大小关系，也不能判断矛盾关系，那么就是不能确定了，输出即可。思路：对于每次输入一个字符串,我们都建议一条有向边。然后进行拓扑排序。1.**我们如何去判断是否产生矛盾呢？**我..
2020-05-20 11:25:47
322
原创 P2853 [USACO06DEC]Cow Picnic S
很好的一道图的遍历题目，我们开一个1000*1000的数组，a[i][j]==true，表示i号顶点可以到达j号顶点，a[i][j]=false.表示i号顶点不能到大j号顶点，最后们对k个奶牛分别进行遍历，如果这K个奶牛都可以到达1—N之间的一个点，就把结果+1.当然还有更简单的做法，那就是直接开一个数组a[]，a[i]表示这k头奶牛中可以到达i这个点的数量，如果a[i]==k,就把结果+1当然我是用第一种做的，下面是AC代码~#include <iostream>#include ..
2020-05-18 13:04:43
157
原创 P1807 最长路
这道题，第一反应就是SPFA。由于最开始的邻接表没有优化，T了三个点。后来我看了算法笔记才知道。使用SPFA的时候，要在搞一个数组，判断某个节点是否在队列中，如果不在队列中，那么才有资格入队，如果在，就不能入队了，出队的时候将这个元素设置为不在队列中，入队的时候将这个·元素设置在队列中。下面是邻接表的AC代码~#include <iostream>#include <vector>#include <queue>#include <cstring>.
2020-05-15 10:19:39
232
原创 P4017 最大食物链计数
这道题…看到结果要对80112002取模，我就知道数量很大，可我不知道能有这么大…首先测试数据生产者和最高级的食物链顶端可能有多个（亲测）然后我想的是，遍历所有生产者，累加这些生产者到最高级消费者的路径数目，每次加起来就取一次模，害怕数据过大，特地开了long long 结果数据量还是超了，最开始我还以为是我算法写错了，害得我重新检查了一遍。后来我试着在每次dfs都取一下模AC了！！！！,这数据量是有多恐怖。。细思极恐。思路：我们设dp[i]为以i为起点到达最高级食物链的路径条数如图所示，dp[.
2020-05-13 22:09:46
633
原创 P1113 杂务
这道题是一道很好的拓扑排序入门题样例中的图画出来长这样~如图所示，我们可以这样考虑.设dp[i],的意义为从i号节点出发路径的最大值设int time[] 这个数组的意义是完成i号杂物所需要的时间很显然 time[1]=5,time[2]=2,time[3]=3,time[4]=6,time[5]=1,time[6]=8,time[7]=4 ,这样依次赋值就行了最后结果很显然就是 dp[1]=max(dp[2],dp[4])+time[1] ,这样所算出来的dp[1]，就是完成所有杂物所..
2020-05-13 16:24:06
496
原创 P3916 图的遍历
这道题很简单…一上来直接DFS#include <iostream>#include <algorithm>#include <queue>#include <cstring>#define Max 100005using namespace std;vector<int > Graph[Max];int flag[Max];void dfs(int v,int Max_v);int res; int main().
2020-05-11 13:46:37
309
原创 P5318 【深基18.例3】查找文献
这道题可把我坑惨了~说两个踩坑点1.样例能过，如果全WA，多半是没有排序2.第三个点WA掉，请注意审题！！！！！使小 K 可以不重复、不遗漏的看完所有他能看到的文章也就是说并不是所有的文章都能被小A看完，我们只需要从1开始看，看完从1开始的强连通部分即可下面是AC代码~#include <iostream>#include <algorithm>#include <queue>#include <cstring>#define M..
2020-05-11 09:57:04
643
原创 P2814 家谱
题目比较简单，一看就想到了并查集，之前做过的并查集都是数字类型的，这次换成了字符串类型，我们就直接使用map,想更快一点就用unordered_map，这样回更快。代码虽然简单，但是还是有一点细节的~建议自己先实现一遍，下面是AC代码#include<iostream>#include <unordered_map>#include <map>using namespace std;unordered_map<string,string> t;..
2020-05-10 22:26:12
192
原创 P3879 [TJOI2010]阅读理解
STL天下第一~，真的不要太方便了。字典树hash统统不存在，我只要STL用map最后一个点会T掉，所以我们使用unordered_map下面是AC代码~#include <iostream>#include <unordered_map>using namespace std;#define Max 10000unordered_map<string,int > t[Max]; int main() { int N,..
2020-05-09 23:53:58
177
原创 P1955 [NOI2015]程序自动分析
这道题思路很简单~依然用到并查集首先，我们执行所有相等的约束条件，也就是说将为1的操作提前。我们合并输入的那两个数字xi xj所在的集合,执行完所有为1的操作以后，我们再执行所有为0的操作，如果发现xi,xj在同一个集合，则可以判断这个程序的约束条件不满足，输出NO,如果执行所有为0的操作以后，都不会出现xi,xj在同一个集合。则输出YES就题目中的样例我们来解释一下~我们截取一部分~41 2 12 3 13 4 11 4 0有4个约束条件，首先执行前面三个，集合合并以后就是这样。...
2020-05-09 22:25:38
243
原创 P1892 [BOI2003]团伙
淳朴的并查集，思路也很简单~思路：如果是两个人是好盆友，很自然就要将他们所在集合合并了，如果不是朋友比如x—y 是敌人1.那么就将x与y的所有除x以外的敌人合并，why?因为敌人的敌人就是朋友了（他们有共同的敌人~）2.除此之外还要将y与x的所有除y以外的敌人合并.why?下面就来解释这个问题~比如上面的样例~假如我们不执行上面的第二点E 1 4 将4与所有1的其他敌人合并，很显...
2020-05-07 22:35:45
238
原创 P1621 集合
这道题比较简单，可能是假的绿题~题目意思说的很清楚了，我们需要找到有多少个集合，集合内部有大于等于p的公共质因子思路：我们首先枚举所有p----b之间的质数，然后将所有<=b的这个质数的倍数的祖先和这个质数的祖先合并，也就是并查集的思想，假设p—b之间的某一个为x,因为x的倍数都有公共质因子x,所以按照题目的描述他们属于同一集合。一直从p—b的范围从小到大进行下去，然后最后求有多少...
2020-05-07 14:57:04
375
空空如也
快疯了，codeblocks中文乱码，昨天下午2.开始一直弄到晚上
2019-03-24
TA创建的收藏夹 TA关注的收藏夹
TA关注的人