记cf一些可能被hack的写法

本文探讨了在Codeforces竞赛中使用unordered_map可能导致的时间复杂度问题。通过具体案例分析了如何利用特定数值构造数据来攻击该容器,以及针对不同GCC版本的攻击方式,并提供了相应的解决方案。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

1. unordered_map

现象

之前经常当O(1)用,作为一些卡常题的必备杀器,

而且,有的hdu/lc题不用umap的话,就只能手写哈希

但是,上次cf里写了个umap被卡了,

这才意识到之前看到的博客不是无稽之谈

其实我赛后也发现了,自己卡了自己几发没卡掉

 

由于ai(1<=ai<=1e9),hack者构造了一组n=2e5的,

分别长为7692的ai%126271=1,...,长为7692的ai%126271=26的数据,就卡t了

原理

https://jiuaidu.com/jianzhan/884887/

参考了这个思路来源,

for gcc 6 or earlier, 126271 does the job, and for gcc 7 or later, 107897 will work.

简言之,

gcc<=6的,用126271作为模数hack,

gcc>=7的,用107897作为模数hack

解决方案

尽量在cf不用umap,只有在以下场合,才可能考虑umap,

1. ai值域非常小,不过此时显然可以用数组

2. 通过题目限制,使ai%mod=j的数组不存在

2. endl

输出endl时会强制清空缓存,可能会慢导致tle

解决方案

#define endl '\n'
=> ERROR [master 4/8] RUN pip install -i https://mirrors.aliyun.com/pypi/simple/ --no-cache-dir -r /app/ 2.9s ------ > [master 4/8] RUN pip install -i https://mirrors.aliyun.com/pypi/simple/ --no-cache-dir -r /app/requirements.txt: 0.944 Looking in indexes: https://mirrors.aliyun.com/pypi/simple/ 1.175 Collecting scrapy_plus (from -r /app/requirements.txt (line 1)) 1.233 Downloading https://mirrors.aliyun.com/pypi/packages/ce/ab/8ff5db0cf85a46e581c3d5086ef0510225712e41e15cd52af1e0171e065e/scrapy_plus-1.0.5-py3-none-any.whl (29 kB) 1.323 Collecting pyhocon (from -r /app/requirements.txt (line 2)) 1.369 Downloading https://mirrors.aliyun.com/pypi/packages/39/2d/cd65dc4fa8c901e6d02b4074771ced04828d71af18b97da24ed1e55507d7/pyhocon-0.3.61-py3-none-any.whl (25 kB) 1.648 Collecting logging (from -r /app/requirements.txt (line 3)) 1.958 Downloading https://mirrors.aliyun.com/pypi/packages/93/4b/979db9e44be09f71e85c9c8cfc42f258adfb7d93ce01deed2788b2948919/logging-0.4.9.6.tar.gz (96 kB) 2.030 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 96.0/96.0 kB 1.3 MB/s eta 0:00:00 2.062 Preparing metadata (setup.py): started 2.451 Preparing metadata (setup.py): finished with status 'error' 2.462 error: subprocess-exited-with-error 2.462 2.462 × python setup.py egg_info did not run successfully. 2.462 │ exit code: 1 2.462 ╰─> [21 lines of output] 2.462 Traceback (most recent call last): 2.462 File "<string>", line 2, in <module> 2.462 File "<pip-setuptools-caller>", line 14, in <module> 2.462 File "/usr/local/lib/python3.10/dist-packages/setuptools/__init__.py", line 8, in <module> 2.462 import _distutils_hack.override # noqa: F401 2.462 File "/usr/local/lib/python3.10/dist-packages/_distutils_hack/override.py", line 1, in <module> 2.462 __import__('_distutils_hack').do_override() 2.462 File "/usr/local/lib/python3.10/dist-packages/_distutils_hack/__init__.py", line 70, in do_override 2.462 ensure_local_distutils() 2.462 File "/usr/local/lib/python3.10/dist-packages/_distutils_hack/__init__.py", line 56, in ensure_local_distutils 2.462 core = importlib.import_module('distutils.core') 2.462 File "/usr/lib/python3.10/importlib/__init__.py", line 126, in import_module 2.462 return _bootstrap._gcd_import(name[level:], package, level) 2.462 File "/usr/local/lib/python3.10/dist-packages/setuptools/_distutils/core.py", line 13, in <module> 2.462 from .cmd import Command 2.462 File "/usr/local/lib/python3.10/dist-packages/setuptools/_distutils/cmd.py", line 7, in <module> 2.462 import logging 2.462 File "/tmp/pip-install-h6uopuco/logging_03f85449da774c7fa6e3ec74f615ec0a/logging/__init__.py", line 618 2.462 raise NotImplementedError, 'emit must be implemented '\ 2.462 ^ 2.462 SyntaxError: invalid syntax 2.462 [end of output] 2.462 2.462 note: This error originates from a subprocess, and is likely not a problem with pip. 2.466 error: metadata-generation-failed 2.466 2.466 × Encountered error while generating package metadata. 2.466 ╰─> See above for output. 2.466 2.466 note: This is an issue with the package mentioned above, not pip. 2.466 hint: See above for details. 2.778 2.778 [notice] A new release of pip is available: 24.0 -> 25.0.1 2.778 [notice] To update, run: python3.10 -m pip install --upgrade pip ------ failed to solve: process "/bin/sh -c pip install -i https://mirrors.aliyun.com/pypi/simple/ --no-cache-dir -r /app/requirements.txt" did not complete successfully: exit code: 1
最新发布
04-03
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

小衣同学

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付:¥1
获取中
扫码支付

您的余额不足,请更换扫码支付或充值

打赏作者

实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值