注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Starry

凄然不作零丁叹,检点平生未尽心

 
 
 

日志

 
 

51Nod泛做  

2017-09-18 21:22:14|  分类: 娱乐 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
随意整理一下。
今年基本在上文化课,几乎没在机房待过。

2017.9.18:

51Nod1589:
题意大概是 Sigma( Max(a[i~j]) * Second_Max(a[i~j]) )    (i<=n,j<=n,(j-i)>=2) 
N,权值范围均小于1kw。

把所有位置的权值丢进一个桶,然后按权值大小从小到大算贡献。每个的贡献只要找出当前它在多少个区间里面当次大值再乘上最大值再乘上区间数量(它当最大值的情况在之前的遍历中已经计算)。
所以开一个链表,每次找左边第一个和第二个比他大的值的位置,右边第一个和第二个比他大的值的位置,然后瞎JB推就可以了。



51Nod1293:
给出一个矩阵,有若干个球从左上角掉下来,如果当前格子是1就往右边走,-1则往下走,0则方向不变。
问最后右下角出去并且方向朝下的球有几个。

大力DP。




51Nod1430=CF549C:
给出N座城市和城市内人数,轮流摧毁到只剩下M座。若剩下人数为奇数则先手胜出。
问是否有办法使先手必胜。

大力找规律。
数据比CF的要弱了不少。




51Nod1859:
大讨论。
感觉不太合口味,本能性抗拒。




51Nod1463:
给出N个点的序列以及包含K个数的集合(K<=10),询问L~R之间满足abs(Bi-Bj)属于集合内,最大的Ai+Aj。

文化课选手复健题。
按L大小大力离线询问,倒叙枚举所有位置,把可以更新的答案插进J+1~N里面,然后询问L~R最值即可。




51Nod1676:
判断两个最多只有200个点4000条边的无向图是否同构。

数据弱到可以被各种姿势跑过。
叙述起来挺繁琐,不如直接看出题人的题解




51Nod1400:
从一个序列里找两个子序列使他们完全相同。

大力搜能过,于是就不考虑别的算法了。




51Nod1199:
子树修改之类的。

大力模板。




51Nod1535=CF103B:
判断一个图是不是基环树。

一个图是基环树当且仅当 图上点数量等于边数量且该图为连通图。




51Nod1515:
给出N个条件,每个条件形似 X和Y能/不能联通,若条件可以成立,则输出YES且让其保持成立。若不能则输出NO。

并查集维护联通,Set维护不连通。
感觉还是挺显然的。




51Nod1832:
给出二叉树的先序和后序遍历,求树形态种类。

因为只有处于叶子节点且没有兄弟的节点无法被确定,所以每碰到一个ANS*2即可。
似乎有多叉树的版本。




51Nod1421=CF484B:
给出一个序列,求最大的Ai%Aj。N<=2e5,权值范围1e6。

设Fi= Max(Aj)  (Aj<=i);
Ans Ai = Max(F [K*(Ai)] % Ai);  (K*(Ai)<=权值范围)




51Nod1249:
全随机数据玩个**。




51Nod1526=CF566A:
给出两种字符串,每种的字符串个数都不超过1e5且总字符数不超过8e5。
定义两个不同种类的字符串对答案的贡献是:两个字符串前缀相同的长度。
求最大总贡献的匹配。

把两种字符串丢进两颗不同的Trie树,记录每个位置被经过了几次。
假设Tr[i][k]表示该树深度为i的位置被经过了几次。Tr1表示第一种字符串,Tr2表示第二种字符串,Tr3在最后统计答案的时候记录该节点的子树一共被经过了几次。
Ans = Sigma( Min(Tr1[i][k],Tr2[i][k]) - Tr3[i][k]) ) *k;
(子树内答案再减去重复计算部分)
记得动态开点即可。




51Nod1158:
题意同题目名字:全是1的最大子矩阵。
行列均500。

单调栈。




51Nod1380:
从N个数组成的环中取N/3个不相邻数字使其最大。
构造方法暂时存疑。




51Nod1456=CF505D:
给出一张点数<=1e5的单向图,要求X单向联通到Y,要求组数<=1e5。询问最少边数。

缩点。如果联通块内是DAG,则Ans+=Size[DAG]-1;若不是,则需要+1.




51Nod1370:
大力DP题,好像没什么科技。
困得要命不写了。
  评论这张
 
阅读(79)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018