信息学集训队作业命题

生日蜡烛沈添笑命题报告长沙市雅礼中学主要内容题意简述出题思路考察重点算法分析数据设计预计得分情况总结题意简述有n根蜡烛和n个开关，每根蜡烛至多由两个开关控制。第i根蜡烛由第i个开关控制，此外，还可能由另一个开关j控制，并且满足当i>1时j<i，当i=1时j为任意数。有m个操作，动态修改某根蜡烛的状态和控制它的开关，求每次操作后把所有蜡烛都熄灭最少要按几次开关，无解输出-1。题意简述数据规模和约定：10%的数据满足：n、m≤1020%的数据满足：n、m≤1000另有50%的数据满足：控制蜡烛的开关不会更改100%的数据满足：n、m≤100000

时间限制2s,空间限制256M出题思路本题源自作者对一道经典问题的思考，尝试将其由静态单次求解变为动态多次求解。希望能通过和大家分享、交流我的心得与收获，引发大家对这一类动态维护问题更加深入地思考与挖掘。考察重点异或运算二分图、环套树等图论模型树的动态维护数据结构的灵活运用算法一每个开关按奇数次和按一次效果一样，按偶数次和不按效果一样2n枚举每个开关按或不按时间复杂度：O(mn2n)期望得分：10分算法二先枚举第1个开关按或不按第i(i>1)个开关便可以由之前的开关和第i根蜡烛的状态推导出来最后再检查第1根蜡烛时间复杂度：O(mn)期望得分：20分算法三把开关看做点，蜡烛看做连接两点的边若蜡烛是亮的，则两个开关中应按一个，否则两个开关应同时按或同时不按特别的，增设0号开关，并规定它不能按，这样当蜡烛只由一个开关控制时便不需特殊考虑，可以类似处理算法三由于第i根蜡烛一定由第i个开关控制，我们得到的图是环套树森林！045123

n=51211110000算法三先不考虑第1根蜡烛，将1号点连到0号点，计算答案前再枚举1号开关按或不按

n=51211110000045123算法三环套树森林->树

n=51211110000045123045123算法三开关状态唯一确定(黄色表示不按，蓝色表示按)

n=51211110000045123045123算法三开关状态唯一确定(黄色表示不按，蓝色表示按)

n=51211110000045123045123算法三50%的数据：树的形态不发生改变当蜡烛i状态改变时，以i为根的子树中开关的状态全部改变2号蜡烛改变045123045123算法三子树改变？dfs括号序列！以i为根的子树即两个i之间的连续一段012453052142514330算法三子树改变？dfs括号序列！以i为根的子树即两个i之间的连续一段012435052142514330算法三将开关i的信息存入前一个i(用1、0来表示按或不按)，后一个i看做2修改：将开关i对应的区间中的0变为1,1变为0询问：连接第1根蜡烛的开关的状态

序列中1的个数线段树维护！时间复杂度：O((n+m)logn)期望得分：50分算法四树的形态改变？dfs括号序列变化将一棵子树接在某个节点下，即将一段dfs序列移至另一处0123564740721271433655601032123457764560算法四平衡树维护！取出区间[l,r]：将l的前驱旋转到根，再将r的后继旋转到根的右孩子，[l,r]即为根的右孩子的左子树l-1r+1l~r算法四将[l,r]插入至k后：断开子树l~r与父亲的边，然后将k旋转至根，再将k的后继旋转至根的右孩子，此时根的右孩子的左子树为空，接上子树l~rl-1r+1l~r算法四将[l,r]插入至k后：断开子树l~r与父亲的边，然后将k旋转至根，再将k的后继旋转至根的右孩子，此时根的右孩子的左子树为空，接上子树l~rkk+1l~r算法四用平衡树维护dfs括号序列修改：将开关i对应的区间插入至新位置，并根据

蜡烛i与控制它的开关的状态判断子树是否

需要取反询问：连接第1根蜡烛的开关的状态

序列中1的个数时间复杂度：O((n+m)logn)期望得分：100分算法总览时间复杂度空间复杂度期望得分考察知识点算法一O(mn2n)O(n)10二进制枚举算法二O(mn)O(n)20~35枚举推导贪心算法三O((n+m)logn)O(n)50建立图论模型dfs序列线段树算法四O((n+m)logn)O(n)100建立图论模型dfs序列平衡树数据设计编号规模(n,m)备注编号规模(n,m)备注15,61160000,70000不改29,91280000,80000不改3500,8001390000,100000不改4800,100014100000,100000不改550000,50000环，不改1550000,50000680000,80000环，不改1670000,60000790000,90000环，不改1790000,800008100000,100000环，不改1890000,100000950000,50000不改19100000,1000001060000,60000不改20100000,100000预计得分情况总结从题目设计、知识点考察到数据设计以及区