YZBPXX - 个人主页动态

2019-08-16 16:57

0 点赞评论收藏

2019-08-16 14:46

沈阳技师学院算法工程师

CF 655c Enduring Exodus

http://codeforces.com/contest/655/problem/C   题目描述：小牛带着他的k头牛住旅馆（每头牛和人一间），但是旅馆有些房间已经住了人了，小牛怕有人偷牛，所以选择尽可能靠的近，现在让你输出最优情况的最远距离   (总共n间房子，0表示空，1表示已经有人住了)   (1 ≤ k < n ≤ 100 000)    分析：暴力各个点的情况然后二分找优解的最长距离时间复杂度O(n*log(n))，理解下这里的”单调“   ac代码：   #include<bits/stdc++.h...

0 点赞评论收藏

2019-08-15 20:44

沈阳技师学院算法工程师

CF 733D Kostya the Sculptor

题目描述：给你n个矩形的长宽高，你最多可以选择两个面相同的矩形合并，现在让求出这几个矩形的最大内切圆（可以选一个也可以选两个）   1 ≤ n ≤ 105   分析：对于一个矩形没啥好说的直接找最短边输出就好，考虑两个矩形合并的情况，两个矩形当且只有合并的面没有这两个矩形的最短边时这两个矩形 内切圆才有变化否则还是这两个之中的一个内切圆大小               且当变化时有两种情况要么还是这里最小边，要么不是，不是的话就是相同面的次小边；当时没想出来 太弱了~~   ac代码：   #i...

0 点赞评论收藏

2019-08-15 19:01

沈阳技师学院算法工程师

CF 741# div2 D

题目描述：给你n个小姐姐的重量和颜值，而且给你几组关系x,y表示x认识y ，现在要邀请她们吃饭，总共邀请的小姐姐的重量不能大于w （可能怕桌子会跨~~） 且互相认识的小姐姐要么最多邀请一个要么全部邀请                       现在想问你邀请来的小姐姐颜值最高是多少   分析：显然是个分组背包，顶多在加个并差集分组的过程（先分堆，在标记她们的堆，然后分别加入vector里）   ac代码：   #include<bits/stdc++.h> using namespace std; int pa[10003]; int n,m,w; int dp[1003]; i...

0 点赞评论收藏

2019-08-15 11:58

沈阳技师学院算法工程师

分组背包

对于分组背包问题与01背包不同的是物品被分好组了  且一个组最多拿一个（也可能出现其他情况，但大致是这样的）   其实也很容易想到多加个for遍历这个组拿哪个合适，这里注意多加的for放在第二个，这样保证每个最多选一个   for(int i=1;i<=n;i++){             for(int k=m;k>=0;k--){                 for(int j=1;k-j>=0;j++){                     dp[k]=max(dp[k],dp[k-j]+group[i][j]);                 }     ...

0 点赞评论收藏

2019-08-14 18:19

已编辑

沈阳技师学院算法工程师

CF Anton and Making Potions

题目描述：你要制作n瓶药水，每瓶花费x分钟  现在你有两个优化的方案（给你s个能量）   1 有m个魔法每个魔法花费b[i] 个能量使得制作时间缩短为a[i]   2 有k个魔法 每个魔法花费d[i]个能量，使得c[i]个药水瞬间制作完成（d[i],c[i] 都是从小到大）   这每个方案最多只能选一次   n, m, k (1 ≤ n ≤ 2·10^9, 1 ≤ m, k ≤ 2·10^5)  2 ≤ x ≤ 2·10^9, 1 ≤ s ≤ 2·10^9    分析：因为题目给出了 第二个方案花费和效果都是递增的且只能选一种，那么不妨选取满足条件的最大花费（此时...

0 点赞评论收藏

2019-08-15 20:52

已编辑

沈阳技师学院算法工程师

CF Knight Tournament

http://codeforces.com/group/xrTA2IaQje/contest/249959/problem/F   题目描述：给你n个人  并且给你m个区间 l 到 r，和x，表示这个区间剩下的人里获胜者是x，其他人出场剩x继续战斗  ，现在让你输出每人是被谁打败的（最后一个获胜者是0）    n, m (2 ≤ n ≤ 3·10^5; 1 ≤ m ≤ 3·10^5)， li, ri, xi (1 ≤ li < ri ≤ n; li ≤ xi ≤ ri)  保证数据有效   分析: 开始想到了用并差集做，但没考虑好区间关系 导致无从下手，首先分析一个区间只有一个获胜者,那...

0 点赞评论收藏

2019-08-13 16:33

沈阳技师学院算法工程师

CF Little C Loves 3 II

题目描述： 给你一个图n*m 如果曼哈顿距离等于3 就可以匹配  问你最多匹配多少个点   分析：反正当时我是没推出来，n=2,m=5,写成了8没想到是10~~~~~   ac代码：   #include<bits/stdc++.h> using namespace std; int x[6]={0,0,0,0,2,4}; int main(){     long long  n,m;     cin>>n&gt...

0 点赞评论收藏

2019-08-12 20:46

沈阳技师学院算法工程师

hdu2222

#include<bits/stdc++.h> using namespace std; const int MAX=1e6; int trie[MAX][30]; int sum[MAX]; int tot; void build_trie(string s){     int root=0;     for(int i=0,len=s.length();i<len;i++){         int id=s[i]-'a';         if(trie[root][id]==0) trie[root][id]=++tot;         root=trie[root...

0 点赞评论收藏

2019-08-12 20:13

已编辑

沈阳技师学院算法工程师

ac自动机入门

ac自动机应该和trie放一块好些  因为ac自动机就是KMP+trie的结合版   原理 trie是每个单词都会匹配吧，按照KMP的思想前面我已经匹配过了的是不是可以不用再匹配了 直接跳到下一段去？  答案是肯定的，并且就产生了ac自动机（此ac非彼ac，以前还以为是自动ac的咯~~~~）   具体内容不详细介绍可以看博客：https://blog.csdn.net/bestsort/article/details/82947639#commentsedit   模板代码：   #include <queue> #include <cstdlib> #include ...

0 点赞评论收藏

2019-08-12 19:31

沈阳技师学院算法工程师

判断内存是否超限

1bit=1e-7 mb 题目要求一般是32mb 也就是对于int型接近开1e8

0 点赞评论收藏

2019-08-12 19:21

已编辑

沈阳技师学院算法工程师

字典树入门（模板）

首先说下字典树给来干嘛的；   字典树建立是把单词按前缀建立的，这样遍历或者比较都可以根据前缀来判断 少了不必要的操作，其实以前用set容器对单词去重的时候就考虑过这个办法，但能力有限实现不了   今天才知道原来这个就叫字典树   上一个模板题：http://acm.hdu.edu.cn/showproblem.php?pid=1251   题目描述给你一些单词，然后在给你一个单词询问前缀能与此单词匹配的单词有多少；   分析：模板，KMP是处理单一的模式匹配 而字典树可以处理多个模式串匹配   注意：1是怎么处理不同树上相同的节点（++tot），可以看成是hash；             ...

0 点赞评论收藏

2019-08-11 12:38

沈阳技师学院算法工程师

2019.08.11 在牛客打卡1天！

0 点赞评论收藏

2019-08-11 12:37

沈阳技师学院算法工程师

CF Cow Program

0 点赞评论收藏

2019-08-10 20:01

已编辑

沈阳技师学院算法工程师

牛客多校

题目描述： 给你一个数组，每个区间段的值等于该区间内不相等元素的个数，现在让你输出这个大区间所包含区间段的总值   1<=a[i],n<=1e5;(看数据也可以看出来要处理a[i]的值)   分析：比赛时自闭了4.30个小时，，，，，             这个题的思路是把它按每个元素的贡献来写的，首先从输的方向从左到右，该元素又可以看成是前一个的往后延伸了一位，那么多出来的贡献是那段没有该值的区间；   所以记录每个值最后出现的位置   这点的贡献等于前面一点的贡献+这点的位置-上次出现过...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：