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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[IPSC2014]  

2015-06-18 22:17:32|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
和dx、zyf两位神犇准备组队打ipsc
邀请zyf神犇的时候:
[IPSC2014] - 时光机 - 时光机TimeMachine
 ……
所以今天就来做了
说一下大概情况吧
去年参加的人数大概是200+(和今年差不多?
有三道签到题,难度递增,A掉两个数据的队伍差不多都是200+
剩下的题分为不可做题和非常不可做题两种
其中不可做题可以A掉easy
非常不可做题……
不可做题占大多数吧

我按照做的顺序说一下我过的题……
A
题意:
给你一个密码和一个当前输入,
有三种操作:1.输入一个字母 2.从末尾删除一个字母 3.提交(密码错误的话相当于清空
求最少的步数提交正确的代码。
题解:
分类

I
题意:
给你一棵有根树,要你给每个节点二进制编码,使得Σ所有点编码长度最短
要求对于两个节点ab,如果a编码是b编码的前缀当且仅当a是b的祖先
题解:
给每个节点一个编码2,使得任意一个点的所有祖先的编码2拼起来是这个点真正的编码(编码1)
然后发现答案只和每个点的编码2和它的size有关
所以对每个点的直接儿子进行哈夫曼编码
C
题意:
你有一个数列,还有一个操作:

The copier chooses some ijk such that 0 ≤ ≤ ≤ m. Then the copier inserts a copy of ai, …, aj-1 immediately after ak-1.

给你一个最终序列,求能得到这个序列的最短原序列
保证最短原序列是一个{1..?}的排列(似乎并不是?
题解:
按照每个数在最终数列的第一次出现位置排序输出。
----------------------------------------分界线----------------------------------------
D
题意:
有一个巨大的文件,由一大坨0和其中一个超短的有效信息组成。
给你用bzip2压缩后的文件,求其中的有效信息
Easy: 文件原大小1TB,压缩了2次
Hard:文件原大小1EB,压缩了4次
题解:
这题我直接看官方题解……
Easy:直接用管道去掉0后(似乎不去掉也行?)解压到屏幕,跑100min后能得到答案“PieceOfLie”
Hard:???
H
题意:
卡掉c++和java的HashSet(只有插入操作)
要求你提交的插入序列≤4e5,每个元素范围要在unsigned long long以内
Easy 将两者之一卡成2s
Hard 同时将两者卡成10s
题解:
这题最大的困难之处就是你要自己研究c++和java两个hash的原理……

看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码看源码

c++
unordered_set:
一开始看错题了,以为就是卡“HashSet”,发现头文件里有一坨模数,原理似乎是先模小质数,如果冲突过多就换大质数重建
然后卡不掉……
发现是unordered_set而不是HashSet
翻源码翻源码……
没有模数表……
什么鬼……
然后搜函数,发现微软的官网上写着有这么一个函数
.bucket_count() 输出桶大小
卧槽这直接能输出还翻个p代码啊
打个表:
……
7517,
15173,
30727,
62233,
……
先输出小质数的倍数,发现重建了之后再输出大质数的倍数
本机能卡到20s左右

然后开始搞java
艹这个根本没法玩啊……没地方找代码……也不会java
……
终于找到hash函数:(翻译成c++inline int Hash(ll x){
int h = 0;
h ^= HashCode(x);
h ^= (h >> 20) ^ (h >> 12);
return h ^ (h >> 7) ^ (h >> 4);
}
最后 &(length-1)
length是2^k
ljs、zky、和我一块搞
ljs手推构造,zky乱搞,我暴力
然后大家都搞出来了……然后发现算的hash值都是一样的,但是只有我的暴力能卡住程序????
c++和java只能卡掉两者之一,拼起来一个都卡不掉
然后蛋疼……蛋疼……蛋疼……蛋疼……
发现java是强行把longlong转成了int……我的是都在int内所以没事……
结果还是不对???
又发现x = Long.HashCode
HashCode = (x>>32) ^ x……
大家都弃疗了我继续搞……
要同时卡掉两个程序,所以枚举数i
要满足i%{...|30727|62233}=k1 并且hash(i)=k2
所以强行枚举{...|30727|62233}的倍数然后找hash(i)=k2的
只找30727和62233的倍数比较有效率(因为不考虑30727的倍数卡不掉
我每次大概搜出1e5个数就退出,开了O2要跑100s
本机能同时卡掉两个了!!!
交上去:
Wrong answer: C++ finished too quickly.
为啥啊!!
蛋疼好久,决定下它的solve的数据跑跑看看
结果发现我的数据c++跑20s,他的要跑1min+
果然是评测姬太快了……
最后发现是因为30727的倍数要找30727个,换模数后浪费了一半多的资源……
所以用一开始不找30727的倍数而找30727*62233的倍数,换模数之后就不浪费了!
虽然找2e4个就爆longlong,但是后面的只要找62233的倍数就行了
H-Hard这个点我搞了6h……感觉今天一天啥也没干
所以正式比赛的时候策略大概就是切掉签到题之后找Easy做
题意:
 给你数列上的2048 
 Easy:模拟 
 Hard:求方案获得最大分数
题解:
不想想了……
  评论这张
 
阅读(93)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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