2017-Sp190-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，yzc读了A感觉可做，上机'''A1y23'''，sub上机写F，'''F1y39'''，cjb读了D，经典的数字打架，丢给yzc，然后cjb写了个checker，'''D1y58'''。之后cjb上机写C，感觉不太行，加了几步调整，'''C4y101'''。cjb和sub讨论了E，sub上机写E，'''E2y126'''。cjb和yzc讨论G，yzc上机'''G1y142'''。cjb和sub讨论K，'''K2y197'''。最后发现B是原题，经典的长链剖分，'''B2y237'''。试图艹I，咕咕。
== 总结 ==
=== chenjb ===

=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：正着二分，倒着二分，随便做。by yzc

 * B：我们设f[I][j]表示点I的子树中有多少和i距离为j的点，g[i][j]表示点i的子树中有多少点对只需要i再往外走j步就能构成符合题意的三元组了。容易得到转移方程(其中y为x的儿子):f[x][i]=sigma(f[y][i-1]),g[x][i]=sigma(g[y][i+1]+f[x][i]*f[y][i-1])。直接转移复杂度为n2，考虑对树进行长链剖分，每一次将重儿子链直接继承给父亲，其他儿子合并进去，复杂度为O(n)。

 * C：按出现次数从大到小隔空填，然后正着调整一次相邻关系，反着调整一次相邻关系，重复这个过程10次(随便设了一个)，如果合法就输出，反之无解。

 * D：数字打架，用线段树维护，需要检查答案是否合法。

 * E：二分答案，一次数星星可以求得哪些点亮着，亮着的点答案进前半部分，没有亮的部分减掉当前能看到的灯的数量，递归求解。

 * F：设答案k，有a/k>b/k,c/k>b/k，一共只有4sqrt(n)个关键点，求出来算一下即可。

 * G：从前往后维护出以每个点为终点最大的起点在哪，倒着也做一次，于是对于每个待定的合法终点，拥有了最紧的区间，在区间外面必须有相同的数字，对于区间左边求里面数字出现的最晚位置的最大值，只要这个最大值在区间的右端即可。

 * H：

 * I：

 * J：

 * K：f[I]=min(max(f[j]+I-j-1,a[I])+I-j-1+2*S)，把max拆开，然后注意到做轻微调整可把a[I]调整为递增，则a[I]-I单调，然后max拆开后是两个基本dp。

 * [https://wiki.icpc.camp/twsf/Warsaw%20U%20Contest,%20Urozero%202015%20Day%204 TheWaySoFar]

流水账

出门各自看题，yzc读了A感觉可做，上机A1y23，sub上机写F，F1y39，cjb读了D，经典的数字打架，丢给yzc，然后cjb写了个checker，D1y58。之后cjb上机写C，感觉不太行，加了几步调整，C4y101。cjb和sub讨论了E，sub上机写E，E2y126。cjb和yzc讨论G，yzc上机G1y142。cjb和sub讨论K，K2y197。最后发现B是原题，经典的长链剖分，B2y237。试图艹I，咕咕。

总结

chenjb

oipotato

subconscious

题解

  • A：正着二分，倒着二分，随便做。by yzc
  • B：我们设f[I][j]表示点I的子树中有多少和i距离为j的点，g[i][j]表示点i的子树中有多少点对只需要i再往外走j步就能构成符合题意的三元组了。容易得到转移方程(其中y为x的儿子):f[x][i]=sigma(f[y][i-1]),g[x][i]=sigma(g[y][i+1]+f[x][i]*f[y][i-1])。直接转移复杂度为n2，考虑对树进行长链剖分，每一次将重儿子链直接继承给父亲，其他儿子合并进去，复杂度为O(n)。
  • C：按出现次数从大到小隔空填，然后正着调整一次相邻关系，反着调整一次相邻关系，重复这个过程10次(随便设了一个)，如果合法就输出，反之无解。
  • D：数字打架，用线段树维护，需要检查答案是否合法。
  • E：二分答案，一次数星星可以求得哪些点亮着，亮着的点答案进前半部分，没有亮的部分减掉当前能看到的灯的数量，递归求解。
  • F：设答案k，有a/k>b/k,c/k>b/k，一共只有4sqrt(n)个关键点，求出来算一下即可。
  • G：从前往后维护出以每个点为终点最大的起点在哪，倒着也做一次，于是对于每个待定的合法终点，拥有了最紧的区间，在区间外面必须有相同的数字，对于区间左边求里面数字出现的最晚位置的最大值，只要这个最大值在区间的右端即可。
  • H：
  • I：
  • J：
  • K：f[I]=min(max(f[j]+I-j-1,a[I])+I-j-1+2*S)，把max拆开，然后注意到做轻微调整可把a[I]调整为递增，则a[I]-I单调，然后max拆开后是两个基本dp。
  • TheWaySoFar
附加文件