缣移双 发表于 2025-6-7 16:13:00

青岛oj集训5

Floyd算法——全源最短路

cerr:标准输出错误流：不会输出到freopen制定的out文件中，而是会输出到错误文件中。
提交上去无论加不加freopen，哪怕是提交到洛谷，也只是比较out文件中的值，而不会管cerr输出的东西
好处：调试的时候用cerr，哪怕忘删调试调试
例题1：传递闭包

floyd可以直接算，但复杂度太高
压缩：用bitset优化
bool：00000001/00000000
bitset：1/0
bool&bool运算时间：O（n）
bitset&bitset：O（n/w）（w是机器字长，一般考试是64，即优化速度快了64倍）

这里看一下这的算法：
假设有一条1-2-3-4的链
f=1100,即能到达12点，到不了34
1:1100    由于这里1能够到达2if(f)成立，才能用2去更新1的所有可达点
2:1110
————
1:1110
3：0111
————
1:1111
这样经过两轮更新，就能到34了
（p.s：其实实际上不是逮着一个点一直更新它，这样可能有更新不到的情况。实际上是先用一个点去更新所有可达点（先枚举k））
例题二：灾后重建

方法一：把所有讯问离线下来，按照t升序进行回答，在排回去
但是这道题保证了Q次讯问的t是不降的，所以就不用离线下来排序了
而且村庄标号越大，解封时间越晚
所以直接枚举点的标号就是解封顺序
用k来代表目前解封到第几个点了
当kv
然后先跑一遍传递闭包，求出所有可达点
如果i可以到达j点，那么说明i可以拿到j的礼物
最后就输出每一个奶牛，如果它能拿到愿望清单上的1号礼物，就输出1号（不一定就是礼物1，只是排名最靠前的那个）
如果能，就输出完了broke掉，否则就下一个，直到找到最靠前的（肯定能找到的，毕竟自己到自己要设为可达）
代码吗……嘿嘿，手速慢没截到，要不那个时候的我（不会吧？我的博文还有除我以外的人看？）再补上？嘻嘻……反正坑是填不完的嘛

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

髡芯 发表于 2025-10-30 16:22:46

过来提前占个楼

米榜饴 发表于 2025-11-10 19:04:02

东西不错很实用谢谢分享

旱由 发表于 2025-12-17 11:30:40

收藏一下   不知道什么时候能用到

拼匍弦 发表于 2025-12-18 23:13:15

谢谢楼主提供！

任俊慧 发表于 2026-1-14 02:59:37

鼓励转贴优秀软件安全工具和文档！

存叭 发表于 2026-1-15 18:38:11

这个好，看起来很实用

夔新梅 发表于 2026-1-18 05:29:04

新版吗？好像是停更了吧。

句惫 发表于 2026-1-19 11:01:00

感谢分享

挚魉 发表于 2026-1-19 22:32:39

东西不错很实用谢谢分享

寇秀娟 发表于 2026-1-25 09:26:21

懂技术并乐意极积无私分享的人越来越少。珍惜

边书仪 发表于 2026-1-27 06:49:54

分享、互助 让互联网精神温暖你我

髭赌 发表于 2026-2-2 13:57:32

这个好，看起来很实用

嗦或 发表于 2026-2-3 08:36:28

热心回复！

余思洁 发表于 2026-2-5 10:48:51

过来提前占个楼

忿惺噱 发表于 2026-2-6 16:33:23

热心回复！

晦险忿 发表于 2026-2-8 03:13:40

过来提前占个楼

滑清怡 发表于 2026-2-9 14:49:55

懂技术并乐意极积无私分享的人越来越少。珍惜

蟠鲤 发表于 2026-2-10 05:04:02

分享、互助 让互联网精神温暖你我

稞冀 发表于 2026-2-11 09:37:56

热心回复！
页: [1] 2
查看完整版本: 青岛oj集训5