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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【被虐总结】【CH Round #30总结】  

2014-04-05 23:54:30|  分类: 某z的日常 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   做完这场CH....深刻体会到乱搞算法的博大精深233....
   今天上午堕落了一上午,下午也只是在复习《冰菓》,看《金田一少年事件簿R》的生肉...然后wsh君叫咱做的题目咱还没有想出来的...
   E题貌似无人A?不过像咱这样的蒟蒻自然是不在乎的啦....只会做三题,然后C题不知道为什么写挂了TAT....然后第二题在神犇的指引下发现自己弱爆了...然后只拿了280分....
   果然蒟蒻呵= =

  A:题目大意:给出一种语法规则,只有形如zwb的句子才符合该种语法(其中z是主语,w是宾语,b是谓语),然后这种语法还支持主语从句(就是zwb中的z是一个符合该种规则的句子),宾语从句。给出一个字符串,求判断它是否符合语法规则,如果是的话输出有多少个句子。
  ...感觉像乱搞题= =咱的做法是这样的...
  1)先读入字符串,然后'bz‘的这样的子串出现的位置必然是两个句子的分割线(这个应该比较容易证明吧),所以这里就可以把整个字符串划分成一段段句子,然后咱们分别判断是否符合语法即可。
  2)咱们设一个状态State,它是一个字符串,每一次读入一个字符,如果当前State='w' 'b' 'zz' 'zb' 'zww’中的一个,则显然不符合,退出。否则转3
 3)判断当前State如果是 ‘zwb'或者'zwz'的话将 State='z',回到2。
 然后这个样子如果2)始终没有退出的话则是符合语法规则的,且句子数就是分割线数+1,否则不符合。
 现在来证明一下为什么是正确的。
 首先 2)的显然是对的,主要是 3)的正确性。当当前状态是 'zwb'的时候,显然这个'zwb'咱们可以看做一个主语从句,即化作主语'z'即可,如果处在分割线上显然无碍。然后’zwz'实际上'zw'就是一个主语+宾语,咱们就知道第二个z以后的就是宾语,咱们现在只需要判断这个宾语是否合法即可,所以咱们就把问题转化成了判断宾语是否合法,即可以类似初始状态直接读入了宾语的第一个字符z。

B:题目大意:m种花n个格子,有的花不能放在一起,可以留空格,给出m*m的矩阵表示哪些花不能放在一起,求满足限制的摆花的方案数。
这个当时以为是神数学题...各种不会,然后 机房的小伙伴 直接虐爆咱= =,其实就是一个很裸的DP嘛...
这里咱们首先设0号花表示空格,它能与所有的花相处,所以g[0][i]=0
咱们设 f[i][j]表示前i个格子,第 i个格子放 种类j的花的方案数,那么咱们有转移 f[i][j]=∑f[i-1][k](k满足g[k][j]=0,1<=k<=n),咱们可以发现这个DP可以用矩阵乘法加速...然后就没了。

C:题目大意:给出N个点,求所有的点对(a,b)(c,d)的曼哈顿距离之和满足 (a-c)*(b-d)>0
这个显然条件可以转化成 a>c且 b>d,咱们离散化之后实际上就是求 (0,0)-(a,b)间的点的x+y之和与个数。
然后这个树状数组就可以做了。
然后不知道为什么莫名其妙地WA了233= =
咱是蒟蒻咱是蒟蒻咱是蒟蒻,写树状数组都WA。
然后发现...是离散化写挫了啊啊啊啊啊啊啊啊....100分就这样没了233。

D:题目大意:N个男人N个女人..每个男人每个女人有一个喜欢的对象,然后男人和不喜欢的对象交往有不满意值,女人和不喜欢的对象交往也有,然后遵循一夫一妻原则,求最小不满意数...
n<=1000
这题大囧,咱是距离比赛结束还有1秒的情况下交上去的,交的还是骗分的KM算法,没想到拿了80分233...数据太水太水太水太水...(其实本来是写Dinic不写KM斯基的...但是不知道负边权Dinic怎么弄)
咱们可以预处理出每两个人交往的不满意程度,然后取负数跑KM算法即可拿到80分(0.0)没想到KM真的可以做负边权的233....

E:神题没看...明天再想...
   

  评论这张
 
阅读(32)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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