2021-team02-047

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team02 返回]

[[Image(Rank.png,1000px)]]

[[Image(Submissions.png,1000px)]]

= 流水账 =

春节连休后的第一次线上比赛。
被橄榄了。
只过了三道签到。
甚至其中有一道，就在刚刚，还被自己hack了……

= 总结 =

=== pb： ===
~~这里是总结~~

=== Creatix： ===
~~这里是总结~~

=== Eden_CY： ===
~~这里是总结~~

= 题解 =

 * A：

 * B：

 * C：问怎么找到或声明不存在一组 x，y, s.t. a[x] + a[y] < a[x | y] + a[x & y];

转化成 a[x | y] + a[x | z] < a[x] + a[x | y | z]，然后移项，然后搞出一条不等式链，就证明了有解则必有 y、z 的 bitcount 为 1 的解


 * D：

 * E：

 * F：

 * G：

 * H：n个线段，每次选一个线段，其所表示的区域未被填满的区域最少，然后填满这些区域，求出顺序。
 首先注意到A包含B则一定是B先选。把所有区间按照左端点排序，然后如果有一个区间包含另外的区间就把他设置成inactive。
 每次删一个区间是区间操作（只考虑active的区间），可以线段树维护每个区间有多少个数。

 * I：

 * J：

 * K：

 * L：问最多可以放多少个折线形，才能使之后上帝有办法完成这个拼图。核心要点是，每个折线形，都可以看成左右两个方向里面选一个，然后上下两个方向里面选一个。所以说行和列可以分开考虑。然后把奇数行的格子上下翻转，奇数列的格子左右翻转，就变成需要同色连通块。对于每个两端不同的非同色连通线段，跑一个匹配。

[/wiki/2021-team02 返回]

流水账

春节连休后的第一次线上比赛。

被橄榄了。

只过了三道签到。

甚至其中有一道，就在刚刚，还被自己hack了……

总结

pb：

这里是总结

Creatix：

这里是总结

Eden_CY：

这里是总结

题解

• A：
• B：
• C：问怎么找到或声明不存在一组 x，y, s.t. a[x] + a[y] < a[x | y] + a[x & y];

转化成 a[x | y] + a[x | z] < a[x] + a[x | y | z]，然后移项，然后搞出一条不等式链，就证明了有解则必有 y、z 的 bitcount 为 1 的解

• D：
• E：
• F：
• G：
• H：n个线段，每次选一个线段，其所表示的区域未被填满的区域最少，然后填满这些区域，求出顺序。

首先注意到A包含B则一定是B先选。把所有区间按照左端点排序，然后如果有一个区间包含另外的区间就把他设置成inactive。

每次删一个区间是区间操作（只考虑active的区间），可以线段树维护每个区间有多少个数。

• I：
• J：
• K：
• L：问最多可以放多少个折线形，才能使之后上帝有办法完成这个拼图。核心要点是，每个折线形，都可以看成左右两个方向里面选一个，然后上下两个方向里面选一个。所以说行和列可以分开考虑。然后把奇数行的格子上下翻转，奇数列的格子左右翻转，就变成需要同色连通块。对于每个两端不同的非同色连通线段，跑一个匹配。