历年题目-雅礼训练11-2晚上

solution怎样更有力气讨(che)论(dan)时间大家有没有收到辣鸡出题人送的温暖啊！你看出题人多有良心：部分分辣么多难度辣么小不卡常数据范围提醒选手特判边界Task1m=1由于此部分分低于普及组难度，不再讲述Task2n,m≤104考虑第i天，先处理香港记者染白的区间。令dp[i]表示1~i全染白至少操作几次。则dp[i]=dp[i-1]（i为白点）或dp[i-x]+1（i为黑点）时间复杂度O(nm)Task3x=0二分答案，那么只要看香港记者染白的区间是否将墙完全覆盖即可。将区间按左端点排序，比较区间的左端点与前一个区间的右端点即可。正解其实已经很明了了。在task3中，如果当前区间的左端点小于上一个区间的右端点，就直接退出。现在只要从上一个区间的右端点+1开始凃，一直涂到≥当前区间左端点即可。注意到一次可能直接把整一段覆盖了，那么下一次就要从当前涂到的地方开始。怎样学习哲♂学讨(tu)论(cao)时间这题连出题人都感觉很烂。其实是一道多校的弱化版。此外OI大师抖儿提出这道题很像APIO2016赛艇。向大家致以深深的歉意……Task1n≤10直接暴力枚举即可。时间复杂度O(m!)Task2n≤1000令dp[i][j]表示最后一个选择为i,j的方案总数。转移十分显然。利用前缀和优化之即可。Task3p=0显然答案是C(n,m)由于模数是个较小的质数，可以套用lucas定理。注意线性求逆元。正解令dp[i]表示仅经过i这个空点的方案总数。那么dp[i]=起始点到i的方案数-dp[j]*j到i的方案数。其中j是所有在i左上方的空点。从一点到另一点的方案数，在task3中已经计算过了，不再赘述。但是起始点和终止点都是不确定的，不难发现，其实相当于强制起始点在(0,0)，终止点在(n+1,m+1)还有一种方法，即对所有空点离散化，然后用类似task2中的转移也可以解决怎样打好隔膜讨(che)论(dan)时间

感觉是idea最好的一题了。但是很水啊有木有！部分分许许多多啊某木有！出题人很良心啊有木有！Task1m=1从1出发，路径为1→i→j→n→j→i，耗时n-1+n-j从1出发，路径为1→i→j→i→j→n，耗时n-1+j-i从n出发，路径为n→j→i→1→i→j，耗时n-1+i-1三者取最小值即可Task2m=2从1出发，路径为1→i→j→x→i→x→y→j→y→n，耗时n-1+x-i+y-j从1出发，路径为1→i→j→x→i→x→y→n→y→j，耗时n-1+x-i+n-y从i出发，路径为i→x→j→y→n→y→x→j→i→1，耗时n-1+j-x+n-y从y出发，路径为y→x→j→x→i→1→i→j→y→n，耗时n-1+i-1+j-x从x出发，路径为x→i→1→i→j→x→y→n→y→j，耗时n-1+i-1+n-y从x出发，路径为x→i→1→i→j→x→y→j→y→n，耗时n-1+i-1+y-j取最小值即可p=1时，选择i→x或j→y或x→j的传送门，答案参见Task1不相交的情况同理讨论即可Task3m≤8暴力枚举进入传送门的顺序以及进入传送门的端点，将走过的航线标记，再看看有没有没走完的航线，走完即可。时间复杂度m!*2m*mTask4m≤2000发现问题和找欧拉路十分类似。一个图存在欧拉路当且仅当存在两个奇点（度数为奇数的点）或不存在奇点。问题等价于给定一个图，删除一对奇点的代价为它们的距离，求使图存在欧拉路的最小代价。1和n原先是奇点，其余的点为偶点。一个传送门会使连接的点性质发生变化，即奇点变偶点，偶点变奇点。Task5m≤2000不难发现最终所有的奇点都排成了一行，消去i和j的代价为j-i。显然消去相邻的两个奇点是最优的。那么问题转化为：给定n个a[i]，选出k个a[i]满足两两不相邻且和最小。令dp[i][j]表示前i个数选了j个的最小代价。dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+a[i])正解考虑一个错误的贪心：每次选择最小的a[i]，然后删去a[i-1]和a[i+1]。但是如果要选择两个，可能选择a[i-1]和a[i+1]是更优的，因此每次贪心有可能会“反悔”，我们考虑维护这个“反悔”操作。每次选一个最小的a[i]，然后删去a[i-1]和a[i+1]，a[i]的权值变成a[i-1]+a[i+1]-a