##1001: 显然，对于每一种类型的课程，我们只会选择翘掉 翘课价值最大的前2节课。 于是，最方便的做法，是使用map<string, int>first, second来实现。 即: for(i = 1 ~ n) { scanf("%s%d", s, &v); gmax(second[s], v); if (second[s] > first[s])swap(second[s], first[s]); } 然后把两个map中的权值全部加到sum中即可。 ##1002: 在此非常感谢验题组elfness对出题想法的帮助！ 就是这题，为了保证本次BC难度足够友好，而换掉了另外一个质量还可以，不过大概难一些的题，让更多人2题保本o_o. 首先，因为朋友关系只能是在男羊和女羊之间的，所以这是一个二分图（当然，这个二分图性质并不重要）。 然后，我们发现每个序列都满足一端为男羊，另外一端为女羊，于是我们可以按照"女羊A，男羊B，女羊C，男羊D"的方式计数，在最后使得答案*2就好。 a[x]存是男羊x朋友关系的所有女羊，cnt[y]存女羊y拥有的男羊朋友数。于是: for (int x = 1; x <= n; ++x) //枚举男羊B { LL onepoint = a[x].size() - 1; //除去女羊C，女羊A的可能方案数为a[x].size() - 1 for (auto y : a[x]) //枚举女羊C，这两层for循环其实只枚举了k条边，复杂度为o(n+m+k) { ans += (cnt[y] - 1) * onepoint; //显然除了男羊B，其他与C为朋友的男羊都可以作为男羊D，计数为cnt[y] - 1 } }于是最后ans * 2就是答案啦。 PS: 对于边数很大的完全图在内的某些图时，计数会爆int。对于不算复杂度的暴力做法也会收获hacked或者tle。这是唯一有设计hack点的题目。以前hack多在01，这里把hack放在02怕大家爆零TwT真不容易。 ##1003: 大家要学会分析状态啊喂！多思考多开脑洞，分析出状态之后，就是一个DP或者记忆化搜索，自然就可以写出来啦！ 首先，因为字符不是'2'就是'3'，所以我们可以把字符串当做一个全部都是'3'的串，然后有若干的'2'插入到了某些位置。 显然，我们交换相邻的'2'与'2'或者相邻的'3'与'3'是没有意义的，我们只会进行相邻'2'与'3'之间的交换。因此，所有'2'的相对前后关系其实是不会变化的。 做了这些比较基础的分析之后，基于数据规模很小，我们可以用以下4个要素表示完整的状态： 1.处理到第几个'2' 2.最后一个'2'停留在什么位置，如果当前的'2'与上一个'2'距离相差>=2时则对答案+1 3.呃喵的剩余交换次数是多少 4.当前已经成功得到几个"233" 而这四个要素的大小，最坏情况下分别是n、n、m、n级别的数，我们随便以3个要素作为下标对应状态，使得第4个要素最优做DP. 转移的时候步长也是不超过2m的，所以很容易就可以得出复杂度为O(n * n * m/2 * m)的算法，这个对于本题的时限和数据，没有什么作死写法的话是可以完全无压力顺利AC的。 这题本来是放在02的，可以用Big Zhu God式爆搜通过，但是后来被调整到03，也相应卡掉了大力爆搜。 最后还要提下，claris老师提供了一个复杂度更加优秀的O(n * n * n * 3)的做法，大体如下—— 考虑最后形成的串是'2'与'3'归并排序后的结果。 于是我们显然需要知道—— 1.当前选了多少个2 2.当前选了多少个3 3.当前用了多少次交换 4.影响决策的状态，这里有3种情况—— a.不存在前一个'2'，或者前一个'2'后面已经有了足够的'3'，记做状态0 b.前一个'2'后面只有0个'3'，记做状态1 c.前一个'2'后面只有1个'3'，记做状态2 用g2与g3表示2与3个个数，用p[]记录所有2的位置，于是就可以有—— for(i)for(j)for(k)for(t)if(~f[i][j][k][t]) { if (i < g2)//我们可以考虑接下来放置一个'2' { int sum = k + abs(i + j + 1 - p[i + 1]); if (sum <= m)gmax(f[i + 1][j][sum][1], f[i][j][k][t]); } if (j < g3)//我们可以考虑接下来放置一个'3' { int sta = t; int cnt = f[i][j][k][t]; if (sta) { if (sta < 2)++sta; else sta = 0, ++cnt; } gmax(f[i][j + 1][k][sta], cnt); } }最后在f[g2][g3][0~m][0~2]中更新答案。 PS:由于数据组数过多，直接memset复杂度是1e6*1000级别，会导致TLE哦~ 其实初测已经给了很多组数，目的就是让memset的代码意识到其可能会FST. ##1004: 这道题为什么过了03的这么多人没尝试过QAQ，明明就是贪心+stl模拟，多么良心！是因为大家做了1小时BC就去做日本的比赛了吗怨念>.<！没AC的快把这题补啦！ 分析：如果给出时间点范围只有T，那么我们可以枚举每个时间点，用f[i]表示我们考虑了时间为[1, i]的所有决策下能够玩的最多游戏数，则有f[i] = max(max(f[i - d[j]] + 1), f[i - 1])，要求[i-d[j]+1,i]都是翘课时间，且[i-d[j]+1]为游戏j的兴趣时间（可以用前缀维护），这样我们就得到了一个复杂度为O（Tn）的算法。 然而这道题给出的时间点范围高达1e9，于是需要引入贪心思想， 很显然，对于任意一个时间点，如果是以这个时间点为最早时间开始一局游戏的话，显然，只要一局结束时间依然落在游戏的感兴趣时间范围内的话，我们会选择游戏时间最短的游戏。这是基于"所有游戏局的收益都为1" 的条件，局部最优且不影响全局最优，符合贪心条件。 而同理，如果我们之前开始了一局游戏，还有一个剩余完成时间，然而倘若以此时间点为开端进行某局游戏，两者的剩余游戏时间相比，越小越优。即我们任何时候都会选择剩余完成时间最少的游戏（当然要求合法）。 同时，虽然时间点很多，但是因为游戏感兴趣区间段的划分作用，实际最多只有2m级别的区间段，使得操作变得可能。有一点需要注意，我们需要保证一个游戏的执行是合法的。于是可以按照枚举翘课时间段的方式展开，这首先保证了是在翘课时间段内进行游戏。而如果一个游戏的参数是（l, r, d），我们把该游戏第一个感兴趣的时间点定在l，该游戏第一个不感兴趣的时间点定在r - d + 2，在这2个时间点，分别在另一个multiset中维护d的插入与删除，就可以使得，只要我们是在可以选取该游戏的时间点开始某局游戏，就一定满足游戏可以正常进行的合法性。 接下来就是具体实现了，按照上面原则每段贪一下就好啦。 你们看mjy0724，人家一个女生都做出04来啦，还是最后一个提交，最后一秒AC，多么令人感动！你们还想着"总有出题人想谋害朕"，想着hack，而不是全力搞题，这样怎么进步嘛>.<! 可以看她的代码，或者到 http://blog.csdn.net/snowy_smile 这儿看标程，想法较简单，考验了脑洞和代码实现能力。

##1001 根据排序不等式，显然应该把字母从小往大放。 一种错误的做法是把正权值的字母取出来从前往后放。错误是因为负权的也可能出现在答案中：放在最前面来使后面每个字母的贡献都增加。 正确的做法是把字母从大往小从后往前放，如果加入该字母后答案变劣就停下来。 ##1002 首先考虑应该尝试选择哪些点：区间的左右端点、与区间左右端点距离$0.5$的点，这样就一定可以包括所有情况。 为了方便处理与区间左右端点距离$0.5$的点，只要将所有坐标扩大一倍，然后这些点就变成了“与区间左右端点距离$1$的点”了 考虑选出这些点后如何进行统计。显然先要将可以选的位置进行离散。假如我们选择的温度一开始是负无穷，这时答案是所有的$c$之和，考虑选择的温度不断升高，答案会如何变化。 每当选定的温度达到一个区间$x$的左端点时，答案加上$a_x-c_x$，每当选定温度超过$x$的右端点时，答案会加上$b_x-a_x$。 维护一个数组$v$，初始全为$0$。我们在$x$的左端点处加上$a_x-c_x$，在$x$的右端点处加上$b_x-a_x$，然后某个位置的前缀和就是选择这个位置作为最终温度的答案了。 ##1003 对于一个点，我们维护一个向量$<sx,sy,1>$，其中$sx$、$sy$表示这个点的横、纵坐标。接下来考虑进行了每种操作后这个向量会如何变化。 平移操作M，向量变成$<sx+x,sy+y,1>$ 旋转操作R，假如是顺时针旋转角度$a$，向量变成$<(sx-x)\times \cos{a}+(sy-y)\times \sin{a}+x0,-(sx-x)\times \sin{a}+(sy-y)\times \cos{a}+y,1>$，也就是$<sx\times \cos{a}+\sin{a}\times sy+x-x\times \cos{a}-y\times \sin{a},-\sin{a}\times sx+\cos{a}\times sy+y+x\times \sin{a}-y\times \cos{a},1>$ 缩放操作F，向量变成$<(sx-x)\times d+x,(sy-y)\times d+y,1>$，也就是$<d\times sx+x-d\times x,d\times dy+y-d\times y,1>$ 发现所有变化后的向量都可以由原向量乘上一个矩阵得到 所以把矩阵作为线段树的标记，维护一下每个点要乘上的矩阵的乘积。询问时求出这个乘积，把点的初始向量乘上它就能得到最后的坐标了。 由于矩阵乘法没有交换律，所以后打上去的标记一定要乘在先前标记的后面，顺序不能颠倒。 ##1004 设$f_{m,x}$表示当前图有$m$条边，尚未连通，即所有$m$条边不连通的图都是等概率的，人在$x$点，到最后的期望步数。 如果这个状态加一条边仍然不连通，可以方便地转移。 如果加了一条边连通了，我们需要考虑这个概率。 这个概率就是“所有$m+1$条边连通图的桥边个数和”除以“$(n*(n-1)/2-m)*m$条边不连通图的方案数”。即加入一条边之后恰好连通，一定对应了新图中的一个桥边。 假如能求出$f$之间转移的关系，可以分层高斯消元，有$n^2$层，复杂度$O(n^5)$。 考虑计算$m+1$条边连通图的桥边个数和，强制一条边成为桥边，枚举1号点一侧的点数和边数，用组合数算一下。复杂度$O(n^5)$。 考虑计算$n$个点$m$条边连通图的方案数，可以用总数减去不连通的，枚举1号点所在连通块的点数和边数，组合数算一下。$O(n^6)$。 这样就在$O(n^6)$的时间内解决了这个问题。 另外，本题可以做到$O(n^4)$，只要用斯特林数的一些技巧来做连通图计数，为了降低难度就没有开大范围。

##1001 用两个布尔数组分别维护每个行/列是否被插过旗帜，最后枚举每一行、列统计答案即可。空间复杂度$O(n+m)$，时间复杂度$O(n+m+k)$。 ##1002 设根节点的深度为$0$，将所有深度为奇数的节点的石子数目xor起来，则先手必胜当且仅当这个xor和不为$0$。 证明同阶梯博弈。对于偶深度的点上的石子，若对手移动它们，则可模仿操作；对于奇深度上的石子，移动一次即进入偶深度的点。 时空复杂度$O(n)$。 ##1003 考虑用树状数组维护每一个位置是否为一段颜色的起点（下简称“起点”）。 询问时，只需要查询区间内起点个数，再特判左端点是否为起点，即可求得答案。 针对合并操作，如果暴力合并，复杂度显然是$O(n^2)$的，尝试用启发式合并优化它。 用数组维护每种颜色的位置个数，合并时，将个数少的颜色全部修改成个数多的颜色。 由于具体实现仍与暴力合并类似，因此可以轻易地维护前面提到的树状数组。 需要注意的是，由于合并时可能交换颜色，因此还需要维护每个数代表的真实颜色。 由于采用了启发式合并，因此时间复杂度为$O(nlogn+Qlog^2n)$或$O(nlogn+Qlogn)$。 本题也可以用线段树或其他很多数据结构解决。 ##1004 题目的寻路决策看似复杂，因此考虑转化。 我们发现，如果从起点走到一个目标格子，再从原路返回起点，即可仅改变目标格子被访问次数的奇偶性。 因此，所有的 2^灯数 种情况都是可以“走”出来的，也就是说，我们可以任意地决定每个位置是否“按下”。 题目转化为经典的高斯消元问题。但是暴力求解复杂度为$O((nm)^3)$太高，不能通过全部数据。 找到一个$j$，使得$|x_j|$最大的前提下$|y_j|$最大，不妨假设我们找到的$x_j=dx,y_j=dy$。适当地翻转棋盘后，如果前$|dy|$行$|dx|$列的“按下”情况已经确定，那么其他所有位置的“按下”方案也就确定（由于目标为使棋盘全亮，因此可以递推求出）。于是只需要枚举前$|dy|$行$|dx|$列即可。 然后就是经典的求异或方程组不同解个数的问题了。可以用高斯消元求出自由元个数，并求得答案。 当$n,m$同阶时，时间复杂度约为$O(\frac{(5n)^3}{32})$。 *本题最大的叉点是翻转棋盘。*

第一题的意思可能有点迷，不好意思耽误大家时间了。 ##1001 Fxx and string 枚举$\:i\:$和等比数列公比$\:q\:$，但考虑到$\:q\:$有可能是$\:1/t\:$的形式，所以倒过来枚举一遍就可以了。 ##1002 Fxx and game 设$\:F_i\:$表示将$\:i\:$变为$\:1\:$的最少步骤，如果$\:k|i,F_i=min\{F_j,F_{\frac{i}{k}}\}$，否则$\:F_i=min\{F_j\}$，其中$\:i-t\leq j\leq i-1$。 用单调队列维护一下就好了。 时间复杂度$\:O(n)$。 ##1003 Fxx and tree 考虑从上往下贪心，要将整棵树翻白，有唯一的方案。于是我们只考虑翻了多少个正确的点。 设$\:f_x\:$表示还有$\:n-x\:$个正确的点没有翻需要的期望步数。注意到翻到一个错误的点后，必须要再翻一次这个点才能挽回。于是我们可以列出一个方程。 $$f_0=f_1+1,f_i=\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1,f_n=0$$ 用高斯消元求出解就行了。每组数据复杂度$\:O(n^3)$。 ##1004 Fxx and factory 假设经过一轮操作后本来从左到右第$\:i\:$个桶变为了第$\:p_i\:$个，我们将$\:n\:$个桶抽象为$\:n\:$个点，并在所有的$\:i\:$和$\:p_i\:$中连一条边，那么我们一定会得到若干个环（包括自环）。 由第一类斯特林数可以证明当$\:3\:$操作无限时，环的数量是$\:log(n)\:$级别的。又由于$\:3\:$操作数量对于$\:n\:$的数量是很大的且数据随机，所以我们可以得到在本题中环的数量是$\:log\:$级别的。 对于每条$\:i->p_i\:$的边，这条边上有若干$\:1,2\:$操作，对于每条边我们记录两个量$\:flag,val$，$flag=0\:$表示这条边有没有$\:2\:$操作，否则表示有，$val\:$ 表示这条边最后一个$\:2\:$操作后所有$\:1\:$操作的加数的和。 现在来考虑每一个桶，经过$\:k\:$轮后的值，其实就是在图上的一个点经过$\:k\:$条边，如果这$\:k\:$条边的$\:flag\:$都为0，那么我们直接把这$\:k\:$条边的$\:val\:$相加即可，否则我们把最后一个$\:flag=0\:$的边之后的$\:val\:$相加即可。 那么我们现在就可以对每一个环预处理出经过$\:1-len\:$轮后的最大值，$len\:$为环的长度，这个直接用数组记录就好了，当$\:k>len\:$时，我们可以由$\:k\%len\:$和$\:\frac{k}{len}\:$得出来。 查询的话直接扫每一个环就行了，总复杂度$\:O(n^2+Qlogn)\:$

##1001 Find Q 求出每个位置往左能延伸多少个q即可。 时间复杂度$O(n)$。 ##1002 Abelian Period 枚举$k$，首先$k$必须是$n$的约数，然后就能算出每个数字应该出现多少次，$O(n)$检验即可。 时间复杂度$O(nd(n))$。 ##1003 Tree Cutting 本题有两种可以AC的算法。 算法1： 取一个根，将这棵树转化为有根树，并假设根必须要选，那么对于一个点来说，如果它选了，它的父亲就必须选。 求出dfs序，设$f[i][j]$表示考虑了dfs序的前$i$项，目前连通块的异或和为$j$的方案数。 如果$i$是一个左括号，那么把$f$传给儿子，并强制选择儿子；如果$i$是个右括号，那么这个子树既可以选又可以不选，累加即可。 如果根必然不选，那么可以去掉这个根，变成若干棵树的子问题，这显然是点分治的形式，取重心作为根即可。 时间复杂度$O(nm\log n)$。 算法2： 取$1$为根，设$sum[x]$表示$x$子树的异或和，假如选择的连通块的根是$x$，那么要在$x$子树里选择若干不相交的子树舍弃掉。 设$f[i][j]$表示$i$的子树里舍弃了$j$的方案数，转移是个异或卷积的形式，可以用FWT加速计算。 时间复杂度$O(nm\log m)$。 ##1004 Advanced Traffic System 设原图为$G$，建立新图$G'$，$G$中的点是$G'$中的边，$G$中的边是$G'$中的点，那么$G'$中的边的权值都是$0$。 在$G'$中用Dijkstra求出起点到每个点的最短距离，这个距离包括这个点的点权。 因为Dijkstra每次松弛的距离单调不下降，而边没有权，所以每个点只有第一次被松弛才有用。 在小根堆中每次取出距离最小的点，它对应原图中的一条压缩信息，将所有没有松弛过的点加入堆中，也就是要找到原图上那个矩阵内部所有没有访问过的点，对于每行维护一个并查集即可。 对于每个原图上的点，用线段树按$id$维护链表，表示这个区间内有哪些压缩信息，这些信息同样是用完就可以删掉。 时间复杂度$O(nm\log(nm)+e\log e+en\alpha(m))$。