2021-team06-C210912

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

[[Image(QQ截图20210913144341.png,800px)]]
[[Image(QQ图片20210913144519.png,800px)]]

== submission ==

[[Image(QQ截图20210913144742.png,800px)]]


== 概述 ==

solved: 7/13  dirt: 41.67%

rank: 57



==  ==

== 总结 ==

yja:
被大佬带，自己状态不大好。
开场过了两个签到题FG，lxy开了D写了大半没调出来，然后我和whn讨论了一下过I（有点慢了）。接着我M想了个假复杂度的做法，调了半天一直寄。
lxy开H，WA33。whn把K签了，lxy调了一会顺利过H，这里我脑调了M并和whn讨论C。M调出来但是复杂度假了T傻，C在奇怪的地方RE不过还好最后调出来了。
lxy重写M弄错题意，寄。
乱写M题背锅（

== 题解 ==

A: 发现面积为正数的情况只有四种。分类讨论，半平面交求面积即可。

B: yja

C: 题意的两个重点：“变量只能为真或假”、“条件命题的条件一定是一堆变量为真”
读懂题意以后就是一个简单建图bfs，对变量和命题分别设点，预处理时，对于无条件命题直接置相应的变量为真(can[i]=1)或假(cant[i]=1)，对于带条件命题则将每个条件向命题点连边。然后做一个类似拓扑排序的过程，队列维护所有真命题，如果一个带条件命题的所有条件都被访问则其结论的真假便可知。最后一个变量如果同时can或cant就矛盾，否则所有不确定的变量都可以任意输出。

D：打表。

E：题意重点：所有记录会严格的保存到过x个单位时间。也就是说如果x很大，就还会有很多记录在所有操作都结束以后一直留着导致花费巨大。因此符合的X是离散的，并且有意义的X其实就是所有文件的相邻时间差。
于是可以先计算出X=1的所有文件都需要重新载入的花费，然后考虑相邻的有意义的X的花费变化，每个剩余的未能使得后面可以重新载入的时间点要增加(now-pre)的花费，然后使得后面重新载入的时间点会导致对应时间点的同时载入量减少，可以O(1)实现计算。


F：签到，并不需要离散化+树状数组（好像也不行），只需要存一个排序后的数组，每次看当前一段的和是否和排序数组中对应部分和相等，如有则分段即可

G：签到，输出最大的K个数即可。

H：dp,设f[i]为租前i辆车的最小花费。对每一种折扣记一个位置，即dp到当前位置时该折扣卡最远覆盖到哪里。容易dp，时间复杂度O(n*sum_q)。

I：细节题，答案是(2*gcd(h*m,h-1)+1)*gcd(h*m,h-1)。

J: yja

K: 签到，同样只需要考虑分段点，然后根据题意模拟阈值从小到大时一个个元素的判定结果变化的过程即可。

L:

M:把n个串转换成01存储，考虑求相同对数，那么就是两两异或为0，做一次FWT，然后高维前缀和求答案就行了。

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 7/13 dirt: 41.67%

rank: 57

总结

yja:

被大佬带，自己状态不大好。

开场过了两个签到题FG，lxy开了D写了大半没调出来，然后我和whn讨论了一下过I（有点慢了）。接着我M想了个假复杂度的做法，调了半天一直寄。

lxy开H，WA33。whn把K签了，lxy调了一会顺利过H，这里我脑调了M并和whn讨论C。M调出来但是复杂度假了T傻，C在奇怪的地方RE不过还好最后调出来了。

lxy重写M弄错题意，寄。

乱写M题背锅（

题解

A: 发现面积为正数的情况只有四种。分类讨论，半平面交求面积即可。

B: yja

C: 题意的两个重点：“变量只能为真或假”、“条件命题的条件一定是一堆变量为真”

读懂题意以后就是一个简单建图bfs，对变量和命题分别设点，预处理时，对于无条件命题直接置相应的变量为真(can[i]=1)或假(cant[i]=1)，对于带条件命题则将每个条件向命题点连边。然后做一个类似拓扑排序的过程，队列维护所有真命题，如果一个带条件命题的所有条件都被访问则其结论的真假便可知。最后一个变量如果同时can或cant就矛盾，否则所有不确定的变量都可以任意输出。

D：打表。

E：题意重点：所有记录会严格的保存到过x个单位时间。也就是说如果x很大，就还会有很多记录在所有操作都结束以后一直留着导致花费巨大。因此符合的X是离散的，并且有意义的X其实就是所有文件的相邻时间差。

于是可以先计算出X=1的所有文件都需要重新载入的花费，然后考虑相邻的有意义的X的花费变化，每个剩余的未能使得后面可以重新载入的时间点要增加(now-pre)的花费，然后使得后面重新载入的时间点会导致对应时间点的同时载入量减少，可以O(1)实现计算。

F：签到，并不需要离散化+树状数组（好像也不行），只需要存一个排序后的数组，每次看当前一段的和是否和排序数组中对应部分和相等，如有则分段即可

G：签到，输出最大的K个数即可。

H：dp,设f[i]为租前i辆车的最小花费。对每一种折扣记一个位置，即dp到当前位置时该折扣卡最远覆盖到哪里。容易dp，时间复杂度O(n*sum_q)。

I：细节题，答案是(2*gcd(h*m,h-1)+1)*gcd(h*m,h-1)。

J: yja

K: 签到，同样只需要考虑分段点，然后根据题意模拟阈值从小到大时一个个元素的判定结果变化的过程即可。

L:

M:把n个串转换成01存储，考虑求相同对数，那么就是两两异或为0，做一次FWT，然后高维前缀和求答案就行了。

附加文件