2020-team12-036

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(2021-0313standing.png, 1000px)]]
[[Image(2021-0313submissions.png, 1000px)]]




== 问题 ==

whn再次遇到了写不出的几何题（


== 题解 == 

A: 签到。

B: 状压DP，枚举每一种斜率，结算能够拼出多少条这个斜率的线段，将用到的所有点加入子集作为子集初始答案；最后合并即可。

C: 签到。

D: 几何，待whn补。

E: ctc和szb想了两种dp,结果szb的假了，ctc后来才发现自己做法没那么难写然后过了……

F: 较易题，从起点顺向、终点逆向各跑一次dijkstra并结算每个点到起终分别有多少路径（记为cnt(u,0)与cnt(u,1)），后面对于一条边(u,v)，如果cnt(u,0)*cnt(v,1）=cnt(v,1)即可确定为最短路上的边，然后
whn写dijkstra+堆没有写<greater<int>>导致wa15。。。记住greater<int>代表小根堆！！

G: 较易题，观察即可。

H: 一部分贪心，另一部分网络流，待补。

I: 后一部分就是个统计前缀和；前一部分（对一个线段求其与多少其他线段有交）也有个很简单的方法，就是统计有多少线段的右端点在其左边，左端点在其右边，然后用n去减……

J: 看起来像是很复杂的一次函数合并或者是1e9并查集，实际上由于a,b,q都很小且这些关系是排序的，可以考虑计算从每个位置从右向左“跳”到和它字符相同的最左位置，一次O(b)，做a+q次也是复杂度正确的；询问时比较已确定字符的最左位置和询问的最左位置即可。考虑样例2，已知区间[3,1e9]和[1,1e9-2]相同,一次可以往前跳两步，那么对于所有≥3且≤1e9的x，就可以一直向左两格两格跳到3的左边为止，然后如果再到下一个l[i]<x的区间就继续跳。很好实现。

K: 环的统计,szbnb..

[/wiki/2020-team12 返回]

问题

whn再次遇到了写不出的几何题（

题解

A: 签到。

B: 状压DP，枚举每一种斜率，结算能够拼出多少条这个斜率的线段，将用到的所有点加入子集作为子集初始答案；最后合并即可。

C: 签到。

D: 几何，待whn补。

E: ctc和szb想了两种dp,结果szb的假了，ctc后来才发现自己做法没那么难写然后过了……

F: 较易题，从起点顺向、终点逆向各跑一次dijkstra并结算每个点到起终分别有多少路径（记为cnt(u,0)与cnt(u,1)），后面对于一条边(u,v)，如果cnt(u,0)*cnt(v,1）=cnt(v,1)即可确定为最短路上的边，然后

whn写dijkstra+堆没有写>导致wa15。。。记住greater代表小根堆！！

G: 较易题，观察即可。

H: 一部分贪心，另一部分网络流，待补。

I: 后一部分就是个统计前缀和；前一部分（对一个线段求其与多少其他线段有交）也有个很简单的方法，就是统计有多少线段的右端点在其左边，左端点在其右边，然后用n去减……

J: 看起来像是很复杂的一次函数合并或者是1e9并查集，实际上由于a,b,q都很小且这些关系是排序的，可以考虑计算从每个位置从右向左“跳”到和它字符相同的最左位置，一次O(b)，做a+q次也是复杂度正确的；询问时比较已确定字符的最左位置和询问的最左位置即可。考虑样例2，已知区间[3,1e9]和[1,1e9-2]相同,一次可以往前跳两步，那么对于所有≥3且≤1e9的x，就可以一直向左两格两格跳到3的左边为止，然后如果再到下一个l[i]

K: 环的统计,szbnb..

附加文件