本文主要是介绍GYM101481 2011-2012 ACM-ICPC, Central Europe Regional Contest (CERC 11),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
GYM101481 2011-2012 ACM-ICPC, Central Europe Regional Contest (CERC 11)
A.Vigenere Cipher Analysis
先想到一种做法:枚举key的长度,然后每个串分别枚举匹配位置,计算出相应的秘钥,然后hash,两个串得到的结果分别匹配,注意预处理在 O ( 1 ) O(1) O(1)的复杂度得到每个位置的hash值,得到的hash值需要有序,总复杂度 O ( K C log C ) O(KC\log C) O(KClogC)。时间限制比较宽松,可以通过。
貌似有更好的 O ( K C ) O(KC) O(KC)的方法。
B.Boring Card Game
很快可以找到每张卡片置换的环, T ≡ x m o d    D T \equiv x \mod D T≡xmodD 环长度D,这张卡在第T局会来到环上第x人的位置,那么单独看每一个人,有五个相应的条件,应用中国剩余定理,时间复杂度 O ( N ∗ 5 ! ∗ 5 log N ) O(N*5! * 5 \log N) O(N∗5!∗5logN)
C.Stack Machine Executor
暴力… 数据有点小
貌似如果DUP MUL MOD这样子循环数据满了做不了。emmm
E.Stack Machine Programmer
利用mod构造
G.Racing Car Trail
网格上游走,显然是一个二分图。轮流二分图上游走,不可经过重复点的博弈,这是一个经典问题。考虑博弈与匹配的关系,在所有最大匹配中都被匹配的点即为先手必胜点,否则必败。网络流残余网络上跑tarjan来判断一个点是否必然被匹配。
H.Unchanged Picture
所有边预处理,直接暴力,比较难写。
这篇关于GYM101481 2011-2012 ACM-ICPC, Central Europe Regional Contest (CERC 11)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!