2017-Sp317-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
=== chenjb ===
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：cout<<(long long)(1+(long long)ceil((double)(n-b)/(b-a))*2)<<endl;

 * B：rep(i,n)printf("%d\n",(i-25000)*710);

 * C：连(x,y)->(x+1,y+1),(x,y+1)->(x+1,y)的白边和(x+1,y)->(x+1,y+1),(x,y)->(x,y+1)的黑边，交替走欧拉回路。

 * D：

 * E：换根dp

 * F：

 * G：

 * H：预处理出小于每个数字的最后一个前缀和的下标，这样就可以O(ans)求出答案，对询问进行记忆化之后，答案在1000以内的直接暴力，否则由于n会在1000以内，只会有1000次不同的询问。

 * I：两维分离，转化成2*n个点取最大+最小/2

 * J：做n-1轮，在第i轮的时候你已经知道了现在这张图上每个点j到j+i的方案数，如果跟最终的不一样，就在j到j+i连一条边，然后可以枚举求出j到j+i+1的方案数。

 * K：A可以取到最大值，剩下把周围四个矩形分别做，每次随便取能分割的一刀，不停递归直到只剩一个人即可。

 * L：SA后，等价于lcp+delta/delta，即最大化min(a[i..j])/(b[i]-b[j])，按a数组排序建kruskal重构树，然后启发式合并维护子树中两点差的最小值

 * M：直接统计即可，注意可能要用unordermap。

流水账

chenjb

oipotato

subconscious

题解

• A：cout<<(long long)(1+(long long)ceil((double)(n-b)/(b-a))*2)<
• B：rep(i,n)printf("%d\n",(i-25000)*710);
• C：连(x,y)->(x+1,y+1),(x,y+1)->(x+1,y)的白边和(x+1,y)->(x+1,y+1),(x,y)->(x,y+1)的黑边，交替走欧拉回路。
• D：
• E：换根dp
• F：
• G：
• H：预处理出小于每个数字的最后一个前缀和的下标，这样就可以O(ans)求出答案，对询问进行记忆化之后，答案在1000以内的直接暴力，否则由于n会在1000以内，只会有1000次不同的询问。
• I：两维分离，转化成2*n个点取最大+最小/2
• J：做n-1轮，在第i轮的时候你已经知道了现在这张图上每个点j到j+i的方案数，如果跟最终的不一样，就在j到j+i连一条边，然后可以枚举求出j到j+i+1的方案数。
• K：A可以取到最大值，剩下把周围四个矩形分别做，每次随便取能分割的一刀，不停递归直到只剩一个人即可。
• L：SA后，等价于lcp+delta/delta，即最大化min(a[i..j])/(b[i]-b[j])，按a数组排序建kruskal重构树，然后启发式合并维护子树中两点差的最小值
• M：直接统计即可，注意可能要用unordermap。