6
18
2015
0

IPSC2015

后天就IPSC了,为了不给队友拖后腿做点题……

【IPSC2014 H HashSets】

题意:你要往c++11和java的hash表里插5e4个元素,卡掉它= =

较小的测试点要求卡到c++或java 2s,较大的要求同时卡掉c++和java到10s

真是一道***的题,涨了不少姿势

先研究了半天c++的实现

原来我一直研究的是ext/hash_set的,它的实现在backward/hash_table.h里,在这里可以看到

注意到从第220行开始有一个不大的素数表,里面记了hash_set所使用的模数

  template<typename _PrimeType> const _PrimeType
  _Hashtable_prime_list<_PrimeType>::__stl_prime_list[_S_num_primes] =
    {
      5ul,          53ul,         97ul,         193ul,       389ul,
      769ul,        1543ul,       3079ul,       6151ul,      12289ul,
      24593ul,      49157ul,      98317ul,      196613ul,    393241ul,
      786433ul,     1572869ul,    3145739ul,    6291469ul,   12582917ul,
      25165843ul,   50331653ul,   100663319ul,  201326611ul, 402653189ul,
      805306457ul,  1610612741ul, 3221225473ul, 4294967291ul
    };

于是不断插每个模数的倍数,发现卡不掉= =

仔细研究了一下发现了hashset的是这样的:

解决冲突用开方寻址法

当元素个数>=当前桶的/2时重建整个hash表,使用更大一点的模数

于是每次插 当前模数/2 个当前模数的倍数就卡掉啦!

 

然后才发现它是让卡掉c++11的unordered_set……

这两个实现不一样= =

它的实现在这里

翻了半天找不到一个质数表??!?!?

然而发现了一个函数bucket_count(),它能够返回当前桶的大小,

不断插入打个表出来

11,23,47,97,199,409,823,1741,3739,7517,15173,30727,62233,126271
 
啊哈!c++11你不还是用的质数吗
 
X掉!
 
 
然后去找java的  
 
发现hashset就是无映射的hashmap
public V More ...put(K key, V value) {
      if (table == EMPTY_TABLE) {
          inflateTable(threshold);
      }
      if (key == null)
          return putForNullKey(value);
      int hash = hash(key);
      int i = indexFor(hash, table.length);
      for (Entry<K,V> e = table[i]; e != null; e = e.next) {
          Object k;
          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
              V oldValue = e.value;
              e.value = value;
              e.recordAccess(this);
              return oldValue;
          }
      }

      modCount++;
      addEntry(hash, key, value, i);
      return null;
  }
 
而hash和indexFor函数的实现是这样的
final int More ...hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}
注意到length一定是2的整数次幂
java使用的是拉链
当元素个数>=0.75*大小的时候重构
hashSeed默认是0
也就是说要想卡掉就得构造出一坨x使得hash(x)的后十来位bit相同
卧槽这TM怎么卡
对hash函数打个表
咦……很有规律啊
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,16,19,18,21,20,23,22,25,24
而且似乎不会有冲突
然后发现了一个重要的现象!
如果不断令x=H(x),那么过不了几次x就会变回到原来的初值!
哈哈
于是构造出一个数列使得他们都是(1<<20)的倍数
然后通过循环暴力找到一个y使得H(y)=我想要的数
然后java就卡掉啦!——才怪
写完之后莫名卡不掉
蛋疼了半天
后来liangjs发现了一个重要的问题
k.hashCode()对于整数的实现是
k^(k>>32)
也就是说对于int32来说没有变化,对于int64就……
而我的数列超了int32……
只好把他们都改成(1<<15)的倍数……
交上去卡掉了java
 
然后最关键的的是如何同时卡掉他们两个
 
可以用一组数据前面卡java后面卡c++对吧
 
于是……
 
 
大家要是想看能过的请找TimeMachine
 
 
【IPSC2015 Practice Session】
 
【S Solitaire】给你4n张牌,1..n每个牌有4个花色,4个花色各有一个槽,一开始槽里没有牌.然后这么玩:
1.依次从牌顶取出一张牌
2.如果是1那么放到对应的槽里
3.如果它对应花色的槽顶的数值是它的值-1,那么放到槽的顶部
4.否则放入弃牌区的顶部
5.如果每个槽顶都是n那么你就赢了,否则把弃牌区翻过来继续做1
输出弃牌区翻转次数+1
sol:
首先考虑只有一种花色,那么若某一个值x出现了但x-1还没有出现则答案加一,考虑到多种花色相互独立,答案取个max就好了
【T Town】
你有0-9每个数码d_i个,拼1..n,问n最大到多少,比如474需要消耗2个'4'和1个'7'.
sol:二分之后就是bzoj1833 = =,我不会告诉你我从bzoj上粘的代码
【U Unusual Game Show】
有d个门,其中d-1个后面是羊,一个是奖品,你选择一个门不打开,主持人打开一个羊门,问你换不换其他的,现在主持人有p的概率只打开他能打开的标号最小的门,给定d,p,问你使用最优策略得到奖品的概率
sol:不会做,队友过的,队友:ans=(1-p)*(d-1)/d/(d-2)+p*2/d,最优策略是第一个随便取,然后换成编号最小的可能是奖品的.
 

 

 

【IPSC2015】

和队友拼手速切完水题

然后就什么都不会做了

【完】

 

Category: OI | Tags: | Read Count: 806

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com