UOJ Logo Cyanic的博客

博客

#338. 【清华集训2017】小 Y 和地铁 std 挂了 以及一些情况说明

2019-12-03 22:43:33 By Cyanic

Hack

其实,这道题在数据范围和时间限制的设置上不太合理。

常见做法的复杂度是 $O(T \cdot 2^{n/2} \cdot n)$, $O(T \cdot 2^{n/2} \cdot \log n)$ 或者 $O(T \cdot 2^{n/2} )$(可能要预处理一些东西,这是一个 例子)。

这差不多是 $4 \cdot 10^{8}$ 左右,时限只给了$2$ 秒... 但是对于官方数据加上 now >= ans 优化遍历到的状态就很不满了(不加这个优化大概率会 TLE)。

捂脸熊

但是加上各种优化之后,单组数据的 dfs 的调用次数仍然可以卡到 3500000 次以上,常数最小的代码也要跑至少 $3.5$ 秒。

UOJ 上的std 为了防止被卡常,实现的是模拟退火。这个正确性不大靠谱,本来打算卡 TLE 的 Hack 变成了 WA...

所以有什么比较好的解决方案吗?

思考熊

评论

zhouzhendong
经过与Cyanic同学的若干天的激烈hack战斗,我向发表一下观点: 1. 麻烦勤劳的管理员顺手给std加个srand(time(0)),并顺手把std的退火次数改大一点可能会靠谱一些。 2. 对于现在的std,我进行了随机数据(T=100,n=44)对拍,平均 10 ~ 30 组数据就会有一组WA(偶尔能连着跑100多组),个人认为它不靠谱。 3. **假设没有更优秀的做法**,希望时限*=2,让至少为确定性算法的搜索可能可以通过。 造数据代码如下 ```cpp puts("100"); For(_,1,100){ int n=44; int a[50]; For(i,1,n/2) a[i]=a[i+n/2]=i; random_shuffle(a+1,a+n+1); cout<<n<<endl; For(i,1,n) printf("%d ",a[i]); puts(""); } ```
ouuan
“常数最小的代码也要跑至少 $3.5$ 秒”的话,时限直接 7~10s 吧。
peehs_moorhsum
我把时限改成了7s 给std加了srand(time(0)), 且增大了随机次数// 如果有必然能通过的确定性算法..可以私聊和我说一哈?我来把他设成std qwq

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。