第一阶段作业-试题泛做

试题谷JULY15.EASYEXEasy 有一个写着1到K的K面，还有两个整数L和F（0<L≤K），掷N次，记掷出数i的次数为ai，求1aF×aF×···×aF的期望值（设分子为P，分母为Q，答案为×Q−1mod2003，Q的逆元不存在时输出0，简化分母为0时的情况。多组数据。 1≤T≤90<N,K<90<L×F≤F≤法先F=1的情况把ai拆成ai,j表示第j回合是否掷出i则要求(a1,1+a1,2+···+a1,N(a2,1+a2,2+···+a2,N)×···×(aL,1+aL,2···+aL,N 的期望。展开后每一项

× ×···×

全! 1，对答案的贡献就 。总贡献可以用组合公式!

N×L2,A再除以分母KL

(N再更一般的F。此时要求(a1,1+a1,2+···+a1,N)F×(a2,1+a2,2···a2,N)F×···×(aL,1aL,2···aL,NF的期望。展开后每一项类似

×···×

×

i，XiYi01，可以看做一个。但是不Xi=j̸=j)，即某回合掷出两个不同的 情况每一项里不同变量个数由原来的L个变成了现在的L至L×个。对于所有有P个不同变量的贡献项，总贡献

(N)×P!×

再除以分 KP。nP表示每种（P个不同变量已确定）如何计算nP？考虑对于某个i,a1,A×a1,B1,C ×···这F个变量中 1FtSF,t。由于1≤i≤L，构造这样一个多项式(SF,0x0+SF,1x1+···+SF,FxF()，展开后,xP的系数就是要求的nP。可以一并求出所有nP。斯特林数可()PO(F2)的递推求。多项式相乘不需要FFT，注意N×P×np，≥P时模2003一定为0，所以计算多项式最多只要保留2003项，可 计算O(F2+MOD2)，单组数据O(MOD2logLL×F 空间：O(F+MOD JULY15.HAMILGAgameona家Asar和Bo，在无向图G行：sar起始点，并把硬币放在这个点上。接下来，两个玩家轮流操作。b先进行操作。轮到每个玩家操作时，他需要把硬币沿着一条边移至另一点。硬币不能重个。vAskarv为起始点来获胜。假设两个玩家都按最优策略进行操作。给出图G，求出有多少胜利点。多组数据。T≤N≤6M6法为了确定哪些点可以是最大匹配中的未匹配点，可以先任意构造一个最大匹配，从每个未匹配点开始尝试增广，走到的偶点都是可行点（因为此时走过的路径比增广路少一条末端的未匹配边，将这样的“不完整的增广路”反相，匹。原图是一般图，需要使用带花树开花算法求最大匹时间：O(NM)空间：O(NM)JUNE15.CHEFBOOKN个人，M个单向关系。每个关<i,j>Lij和限制范围jj，可以调整P,Q两个数组来修正关系数值，修正后的关系数值为∑Wij=Pi+Lij−Qj，要在满足所有Sij≤Wij≤Tij的情况下最大 WijN100 O(min-cost-max-flow(N,MJUNE15.CONPOINConnect输入一个无向图，判断它是不是最大（不能再加边）平面法3N6的平面图。本题可以使用一般的平面图嵌小于等于2度的点，且最小度数不超过5。考虑以下删点操作：3删除任意一个4度点，在四元环上连接一条对角删除任意一个5度点，在五元环上连接两条从一个点引出的“对角线442454时间：O(NM空间：O(NM)MAY15.CBALChefandBalanced定义平衡字符串为每种字符都出现偶数次的字符串。给定一个只包含小写字母的字符串和若干询问，每个询问给定一个区间和一个数0,1,，需要回答在这个区间中所有平衡子串的长度的T次方之和。要求回答询问。N≤。 首先计算所有字母出现次数的前缀奇偶性，可以表示为一个26以内的整数，离散化后可以再缩小到N串变成了两个相等的整数，子串长度变成了坐标之差。很容易得出一种线性回答一个询问的方法，即扫描相应区间，用数组记录每个整数的出现次数、出现 N2N右端点在块的边界上时询问的答案。对于一个至少跨过一个整块的一般的询问[LR][SE]ANS[LRANS[L,E]+ANS[S,R]−ANS[S,E]+G[L..S,E..R]，G[L..S,E..R]表示第一]√..]一块以内，线性求解复杂度不超过都已预处理空间：O(N1.5)

N)，ANS[L,E],ANS[S,R],ANS[S, TCountingonadirected给定一个N个点（从1N标号）M条边的有向请你统计无序对(X,Y)(X,Y)1X1到点Y的路径，且两条路径除了点1以外没有公共点。N≤100000,M≤500000法XY，称Y为X的必经点，所有必经点中离起点最远的称为最近必经点。每个点的DominatorTreeDominatorTree以后，根据题意，答案为根节点的所有子树大小两两相乘之和。利用Lengauer-Tarjan算法可以快速求出一般有向图的DominatorTree。时间：O((N+MlogN空间：O(NM)APRIL15.BWGAMEBlack-whit给定一个N×N的矩阵，每行有连续一段染成黑色。两个人玩，每回 P(iPi)都是黑色的。谁先取不了谁输。问哪个人会胜利。N≤100000法通过行列式的正负，可以比较01矩阵中对应格全为1的奇排列和偶排列哪个多。但本题矩阵过大，无法直接高斯消元计算行列式。考虑用数据结构加速消元。由于每一行都只有连续一段为1，把行按照出现1次取左端点最靠左的那一类中，右端点最靠左的一行,R0]（一样，不用继续计算，行列式为0，用它来对同类其它行L,x]消元，变为[R0+,Rx，堆。时间：O(NlogN空间：O(N)APRIL15.LPARTYLittle有N个人，M场派对，这些派对都不太愉快。告诉你每场派对中每个人的心情好或不好。一旦出现就会导致不愉快的心情组合称为为基子集，求一组可以总结所有派对的总大小最小的基子集。例如三个派对AC,Abc,BC，BC,AbC,c,aBC5。M≤1000,N≤法M≤05=2先枚举所有心情组合，找出所有合法的基子集和他们对应的派对集合。原问题变为最小代价集合覆盖问题，即给定若干集合和对应代价，要求选择一组代价之和最小的集合，使得其并集等于全集。这个问题没有多项式算法，只能通过+时间：O(3NM2MM32空间：O(3N)T2Countingona每次修改一条边的权值，要输出Q+1个答案。N≤100000Q100最大边权M≤106法FiiF数组，可以通过“莫比乌斯反演”求得最终答案。重点F数组。ii整除的边，用并查集连边计算答案。iMN—1条边，复杂度太大。设边权中不同的质因子个数最多为cc≤72c次，可以预处理本题有修改，但次数少，最多100次，受影响的边也最多100条。把不时间：O(M2c(NQ2logN空间：O(M2c(NQ2))FEB15.DEVLOCKDevuandNPM0，答案对998244353取模。要求对所有的0≤M≤MM计算答案。N≤109P≤50MM≤500P≤16MM≤15000法为了方便，把答案写成多项式形式，Fi的j次项系数表示每位之和（下称“代价”）jiF0的前MM+1项的所有系数。i位（0开始）110imodP，由Pk的数位个数cnt[k]。对于第k类数位，构造多项式(x0+x+x2+x3+x4+x5+x6+x7x+x)cnt []。展开后，x的系数代表代价为t，具tkmodP的方案数。根据i=t×kmodP的值将这个多项式拆成P个多项式Gi，和答FiP2998244353，多项式模x+x)cnt 时间：O(PMMlogMMPMM 空间：O(P·MM)JAN15.RANKA99的棋盘上下围棋，两个人都由你控制。允许跳过。要求局面（当前轮到谁+当前棋盘状态）不能重复。构造一局有N步的棋局。数据1：N数据2：N法考虑这样一种下法：黑方不断下棋保持所有黑子在通块内，白方不棋环80次数600N=080N=1000本题可以打DEC14.DIVIDENDir法N≡0(mod3)603633N空间：O(N)NOV14.FNCSChefandNN个函数，每个函数是数组的一个子区间和。要NQ≤105法改时可以更新每个块的答案，同时树状数组数组前缀和。询问时对于完整设块大小为2BO(NBB单次修改ONlogNBO(BlogN2B空间：O(N)BOCT14.TRIPSChildrenN12Q(SFP)S走到法先考P比较大的询问，可以分步倍增向上走LCA计算答案。P比较，就不能了。时间：O(N1.5logN空间：O(NlogN)SEPT14.QRECTRectangle法先考虑一维情况，询问有几个区间与给定区间相交，只要计算“总区间数2时间：O(NlogN22空间：O(NlogN)（树状数组套动态开点线段树2AUG14.SIGFIBTeamSigmaand∑

6xyzfxfyfz)modM，fiFibonacci数列第i项。多组询∑N≤1018,M≤法

M≤12212O(logN)O(logP)，P为周期，123的大常数12×12JULY14.GNUMGameofS1,S2，初始时集合均为空。每次操作，他将会选择两个数(i,j),(p,q)，满(i,jS1中,(p,q)S2中，Bj>AiBp<Aq,(Ai,Bj)̸=1,(Aq,Bp)̸=1，且(Aq,Bp)与(Ai,Bj)不互质。(i,j),(p,qS1,S2中。问最多能进行几N400AiBi109法首先预处理出所有可行数对和对应的，题目变为二分图匹配问题，可ON4) O(maxflow(NlogN,NlogN))，但优化后大部分数据中点数和边数远达 PTwo点数N≤105M700法 时间：O(N+MlogN+maxflow(M,M 空间：O(MN)MAY14.ANUDTQDynamicTreesand个子树所有点权加x，询问某个子树点权和。要求。法由于只有子树操作，可以使用Splay来DFS序或欧拉遍历序时间：O((N+QlogN空间：O(N)MARCH14.GERALD07ChefandGraphN,M,Q200000法使用莫队算法+按秩合并的并查集来回答所有询问。由于并查集只能撤销最后几次操作，所以本题和通常的莫队算法细节上有一些区别，需要将左端点所在的块分出来，右端点向右移动时将对应边合并进并查集，左端点所在块里面的边在回答询问时合并，回答完撤销，左端点移出块后要重构。在一个接。N,M,QN时间：O(N1.5logN空间：O(N)FEB14.DAGCHGraph1DFS序标号。对于x,yx<yxyx,y以外所有点（可能是0个）（DFS时间戳）都比y大，则称x是y的supremevertex。其中最小的supremevertex称为superiorvertex。询问对于每个点，有几个点以它为superiorvertex。法本题中的superiorvertex实际上就是计算dominatortreeLengauer-Tarjan算法中提到的semidominator（半必经点。套用该算法就可以解决本时间：O((N+MlogN空间：O(NM)TDSETSCountingD-计算有多少点集，满足其直径恰好等于D9+。维度N1000D≤109法将原题=D的限

D，则答案为

AnsD−1。限×每个点的坐标在[0,D]内，且每一维都至少有一个点坐标为0，这样就满足了题目对点集等价的要求。至少有k 维坐标不满足要求（没0）的点集数量为(N) 2Dk(D+1)N−k，最终答案可以用容斥法来计算。×k2O(N)O(Nlog22空间：O(N)2DEC13.QTREE6Queryonatreen(黑/白)，初始都为黑。v(uv)1uu(黑变白，白变黑)法先考虑链上的情况，可以用Splay来，每个节点里保存区间两端的颜色和同色节点数量。树上的情况可以用Link/cuttree来，每个节点额外与它相连的虚边信息，Access操作时更新。时间：O(nlogNOV13.MONOPLOYGangstersof有N个城市连成树结构，每个城市开始时由不同的帮会控制。如果两个相邻城市被同一个帮会控制，距离为01的帮会控制了从某个点到根的所有城市；询问某个子树里所有城市到根的距离法Link/cuttreeAccess01Link/cuttree来模拟操作，用树链剖分统2时间：O(nlog2OCT13.FNFibonacciFibonacci数列中第一FnC(modP的Pmod10P≤2109，P是质2×109法x

≡5(modP)可以在本题中使用FibonacciϕnBaby-step-giant-step算法求n的值。此题中涉及模意义下的平方根的求解，可以使√√

P空间：O(P)给一些模板串和文本串，求每个模板串在所有文本串中的匹配次数法本题是一个简单的字符串多模匹配问题，直接使用AC自就可以解决。注意在匹配时不要顺着Fail边更新答案，而是先在点上打标记，最后再根据拓JUNE13.TKCONVEXTwok-ConvexPoly-给N根不同长度的棍子，要求回答是否能用这些棍子组成两个凸k边形，要输出方案。n≤1000,k≤10，棍子长度不超过109。法k根棍子能组成多边形的条件是最长边长度小于其它边之和，能组成多边形长，而本题棍子长度有限，所NN>70则一定找到案，使得选中的2k根棍子要么是两段连续k根（一段一个凸k边形要么是连续2k根。可以很方便地枚举求解。k时间：O(M +NlogN),M=min{N,k空间：O(N)MAY13.QTREEQueriesontree有一NN条边的无向简单连通图，且保证图中唯一的环长度为奇数。要求支持以下两种操作：对两个点之间的最短边权取相反数，询问一条最短法如果是链上问题，可以很方便地用线段树做，每个节点权值和，子区间++2时间：O(NlogN2空间：O(N)MARCH13.LECOINSLittleElephantandCol-oredCoins有N种类型的硬币，从1到，第i种硬币价值Vi，颜色是Ci，每种硬币都有无限个。QS最多可以用几N≤30ViQ≤200000S≤1018法M的硬币，FSmodM=S则有解且不用面M的硬币，FSmodMS则无解。数组F可以用SPFA算法计算。再考虑有颜色的情况。把一个方案所用的硬F，Fji表示使j种颜色时，能凑成的最小Mi的价格。然后就可以回答所有询问了Codechef题解里讲述了另一种做法，将状态转移中遇到的环有依据地拆开，避免了SPFA，在情况下复杂度比本文算法更优。时间：DP

O(×O(N∑空间 FEB13.ROCRoomN×M的ASCII一个小朋友（每行最多两个，将房间墙壁看成一个环，相邻的小朋友可以相互1法2|−2PCDmax|(A−P|,|B−P|)，较简单的做法是将N个位置在后面一遍。O(NM)O(NlogN空间：O(NM)JAN13.ANDOORANew在一个W×H的门上挖N个圆洞装玻璃，问玻璃在门内的周长之和，N≤5000法需要拆成两个）2时间：O(NlogN2空间：O(N)DEC12.DIFTRIPDifferentN法把度数看成字符，则互不相似的祖先-Trie上本质不同的子NOV12.COUNTARIArithmeticN个数，问有多少(ijk)i<j<kAiAjAk为等差数N≤100000Ai30000法++卷积来统计，卷积可用FFT实现。BB时间：O(NB+NAlogAB空间：O(NA)SEPT12.KNGHTMOVKnight有一张无限大的方格棋盘。有一个“骑士(0,0格开始，按照如下规则，移(X,Y)格：每一步，它只能(u,v)格移动(u+Ax,v+Ay)或者(u+Bx,v+By)（不能往回走。此外，棋盘上有K个格，骑士不能进入这i使得两种方案据，K≤15。法(本题有两种情况。当两个向量线性无关时，可以以这两个向量为基底建立新设终点的新坐为为p+q于容(p斥计算松的范围（比如5002）把无限棋盘变成有限棋盘（需要使用无穷远点的情况答无解，用拓扑排序找环和DP计算答案。设最大坐标为M O(M)O(Klogϕ)O(M2空间：O(M)2AUG12.MAGICTwo两个人在一个简单无向图上玩，每个人每回合这样行动：首先走到同一一条不存在的边；连完边后可以选择消耗1点魔法值传送到任意位置（N≤。法小，连接后不改变连通性的边（下称“无用边”）性，魔法值。状态O(N2P2)，太多考虑传送操作，对于其它条件相同的状态，魔法值显然是越多越好（太多了（且至少有一个，两个有人连通块大小为奇数，必须将自己和对方所在连通块N2打表观察可以发现，当偶数连通块足够多（大于10即可）时，答案不变，数连通块足够多（8即可）4为周期。只有常数个状态，可以预处理和回答一个询问都为MAY12.LEBOXESLittleElephantand有N个盒子，打开第i个盒子有Pi概率获得Vi ，否则获得1个钻石。有M个物品，每个物品都要花费一定钱和钻石才能 品。N,M≤30,Vi≤107法考虑用meetinthemiddle策略。把N分为A+B，对后B个盒子，预i个钻石时每种可能的钱数和概率，按钱数排序，概率求前缀和。DP出有i个钻石要买j个物品最少要。然后对前A个盒子枚举结果，在后B个盒子的结果中二分统计答案。时间：O(NM2AB空间：O(NM+2B)APRIL12.TSUBSTRSubstringsonaTrieTrieQ个询问，每次询问第K小的子串。法题目中的两个询问，都是后缀自的经典用法空间：O(N)JULY11.BB有N个位置可以放牌，每连续M个位置至少要有K个。放置能满足300N≤109M500法先考MN的情况。依次把连M个位置分成一组。可以证明每组中只 案数可以用公 M 来计算。但是矩阵可能很大。观察上述公式，K+T现分子和分母里有很多项可以约分，最后的有效项数规模不超过O(MK)。牌，最终可以将其转换为M整除N的能解情况。MAY15.RNGRandomNumberKKN项。K≤法K太大，不能使用矩阵乘法。本题需要使用特征多项式来优化线性递时间：O(KlogKlogN空间：O(K)AUG14.PUSHFLOWPushthe修改一条边的权值，或询问两个点S,T的最大流。法S到T-Linkute时间：O(NlogN空间：O(N)JAN14.TAPAIRCountingTheImportant有一个无向图，询问去掉两条边后图不连通的方案法考虑图的一个生成树，如果有一个非树边(u,v)，则称树上u到v的路非树边才会使图不连通。给每条非树边赋一个随机权值，每个树边的权值 0，说明它是桥，去掉它和任意其它边后图不连通。为防止，随机数的范围要大一些，最好是64位整数。时间：O(NlogN空间：O(N)MAY12.TICKETSSelling有N道菜，M人吃。询问最多能让几个人入场，使得无论是哪几个人，每人都能吃到一道喜N≤,M≤法求最大可行人数比较麻烦，可以改求最小不可行人数。相当于在一个无向图中选出一个最小的边数大于点数的子图，这样的图一定至少包含两个环，具体可能有三种形式：两个点间有三条不同路径，两个共用一个节点的简单环，两个由一条路径相连的简单环。第一种情况可以枚举起点三次SS2时间：O(NM2空间：O(NM)FEB15.CUSTPRIMPayton定义三元(a,bc)，c2411}乘法(a1b1c1·(a2b2c2)：s=(a1a2+b1b2+c1c2)+(a1b2+b1a2)+(c1+c2)st=⌊2⌋+16(c1+c2)−A=(t−2(a1b2+b1a2)−(a1c2+c1a2)+33(a1+a2)+(b1b2−B=(t−5(a1b2+b1a2)−(c1b2+b1c2)+33(b1+b2)+(2b1b2+如果s

540,B

54024)，否则为

533,B

53311)A是对于任B×B=B的三元组，定义zeroA是对任何B都满足AB=A的三元组，定义一个三元组是素数当且仅当这个法ω为方程ω2=ω—3的解，每个三元组(a,b,c)都有到域Z[ω]=

∈Z}的ϕ(a,b,c)=

–2a

c)+(b

域Z下的数a+bω(abω)′=(a+bbω)Nx=xx′，有以下结论：如x不是整数，xNxx是整数，x是素数当且仅当整x|x|=2|x|=11−11xMiller-RabinJAN15.XRQRSXork大；查询区间小于等于某数的数的数量；查法Trie的经典应用。此处是在某个区间里查点，TrieL的节点，限Triek大相关问题可以通过在Trie上子树中数的个数来实现。时间：O(NlogN空间：O(NlogN)DEC14.RINCourseN门课，M个学期，每门课都必修，可以在任意一个学期学习。有些课会有前置课程，有KjiFij（0-100范围内。最大化期望平均分。NM,K≤ Mi门课，(j−1)个点（j=1时为源点）j100−FijM个点a从课程a的第i个点（i=0为源）连一条∞的边到课程b的第i+1个点。时间：O(maxflow(NM,(NK)M空间：O((NK)M)NOV14.SEAORDSerejaandNiAi秒，在第二Bi秒。一台电脑同时只能运行一个任务。一个任务的两个子任务法 答案的下界是max

B,Ai+Bi)，且最优解一定取到下界。如果最∑值取到∑

iBi，由

≤AiBi

Bi，同

B−Bi≤−A所以安排好耗时最长的任务后，其他任务都可以填到两台机器的−A时间（期望）：O(NC)C空间：O(N)JULY14.SEAEQSerejaand两个长度相同的数组相似当且仅当对于iCA(Ai)=CB(Bi)，其中CX(x)表示数X中满足Xi<x的个数。F(A,B)等于A[l..r]与B[l..r]A[l..r]E(lr)的数量。求对于所有排列，∑F(P1P2)。T≤10000N≤500E≤106 Fi,ji个数不超过j个逆N的排列的个数有递Fi,jN!Fi−1,j−Fi−1,j−i，则有结论：最终答案

((N−i+1)∗Fi,E∗(i!)3O(N)O(N33空间：O(N)3MAY14.SEINCSerejaandSubsegmentIn-组B至少要操作几次。法两个数组太麻烦考虑变成一个

←(Bi−Ai)mod4∑ max(0,

—Ai−1)，但是可以选一些数加上4的若干倍来减少代价具体方法是：设差分后的数组为C，从左到右扫描，如果遇到

∈{−1,0,1∈i2,下来。遇到

∈{−,

}3,j<∑（−3Cj4，Ci4（相当于原数组区间[ji∑

max(0,Ci)空间：O(N)OCT12.MAXCIRMaxABCNiA(xiyi)。最多使用这N个操作里的K个，求最大周长。法|BC不变，只要最大|AC

最大化uxavya的同时最大化|AC||AB|。因为所有达到最优解的点在一BCAu,v，uv后,KA的坐标了uxivyiuxjv的情况，可以解出两u,v，通过这v操作时期相等的向量，按极角排序后取相邻向量夹角之间的任意向量作为(u,v)K个正权操作就行了。另uxi+vyi=0的情况也要考虑。这题还有一个问2时间：O(NlogN22空间：O(N)2SEPT13.TMP01ToQueueornotto护字符串中本质不同的子串个数。N≤1000000，3秒。法LCP，但是如果减到了某两个后缀的LCP就会出问题。为了决这个问题，规定，线段树中不得出现某个后缀指删过字符的后缀）LC时间：O(NlogN空间：O(NlogN)（O(NlogN)/O(1)RMQSEPT13.TWOROADSTwoN个点，要求作两条直线，使每个点到直线的最短距离平方和最法，3时间：O(NlogN3空间：O(N)JUNE13.SPMATRIXCountSpecialMatri-N×NAj,i=Ai,j∈[1,N−Ai,j≤max(Ai,k,Ak,j)(i,j,k∈[1,N对于所有k[1N2]，至少存在Ai,jN109+7。N≤107，100000法

1答案等于n!(n−1)! 3×2n−1(2−2 需要线性筛求逆元。注意乘法和取模的常数空间：O(N)JAN13.CUCUMBERCucumberBoyandCu-cumberGirlBN×N矩阵(ab)表示一个新的BBi,j

Aa,i,kAb,j,k。一个排P是好排列当且仅当存iBi,Pi为奇数。数(ab)BN≤B≤法B变成Bi,j(Bi,j1)mod2。此时好数对对应的矩B式为奇数。此时

=N

×

1)mod2，可以在每个矩阵后加b1B=AaAT（2意义下Binet-Cauchyb

删去第j列|B|=N|A||A|

消元后做一处理就能求出所有j 时间：O(NBB 2空间：O(NB)2AUG15.DISTNUMSimpleAi5令S为某区间内不同的元素构成的有序集合。你需要∑ (mod109+删除一修改一询问某区间内不同的数的法以用容斥法考虑，假设区间内的数各不3−3+2它们的一次方，二次方方之和分别S,S,S，则答案为

S1

S3。再考虑操作1和操作5 维区间查询[l,r]变为二维矩形查询[l,r][0,l−1]，可以用二维数据结构。时间：O(Nlog2N空间：O(Nlog2N)SEPT14.FIBTREEFibonacciNumberson作后。所有数值模109+9。强制。法xx2≡5(mod109+，从 x≡5(mod109+ibnacciFibnacci到的，可以分别考虑两个等比数列。需要实现一个“区间加等比数列（公比始终不变”的操作。由于公比不变，每个区间只要首项就行了，这样的标记是可以合并的。线段树上每个节点两个公比的正着、倒着共计4剖3时间：O(NlogN32空间：O(NlogN)2JUNE14.SEAARCSerejaandN个点(i,0),1≤i≤N，每个点一个颜色，相同颜色点之间连接法相交的异色圆弧对数不好做以改为求圆弧

相离的异色圆弧—相互包含的异色圆弧对数。前三者可以O(1)或O(N)的颜色称为“大”的颜色（显然这种颜色数量不超过N。把相互包含的异色圆B弧对分成三类：外侧为“大”颜色，内侧为“大”颜色且不属于第一类，不属2B时间：O(NBNlogNB空间：O(N)APR14.GERALD08ChefandTree两个人在一棵树上玩，树上有两种颜色的边，每个人操作时可以删除一条自己颜色的边，把与根节点不连通的部分删除。两人轮流操作，谁先不能操法本题中的是经典的多人博弈Hackenbush，对于此类学术界目F>0第一人必胜，F<0第二人必胜，F=0后手必胜。则有结论：与根节点用第一类边相连的权值为x的点，对根的贡献为x+p（p为最小的满足x−p<−1的正整数。注意此处的权值不能用浮点数（2p−1度不够22时间：O(NlogN2空间：O(NlogN)MARCH14.STREETTATheN税费，初始每个商店都没有商品，税费为0，要求实现以下三种操作：给某区间内的所有商店里加一个商品价格为等差数列，给某区间内的所有商店的税费都增加一定值等差数列，花MN≤9,M≤3000法商店可以离散化。本题要两个数列，一个需要区间加等差数列，另一个需要区间与等差序列取ax。区间加等差序列与本次作业中另外一题（题号EYax合并，由于两个等差数列（一次函数）取ax如果有相交，把一个标记放在当前节点上，另一个标记向产生交点的那一侧下时间：O(Mlog2M空间：O(M)FEB14.COT5Countona有一个大根rep，支持三种操作：一个给定优先级和权值的点，删法只要能求深度和LCALCA区间中优先级最大的点。考虑互为祖先-子孙的两个节点，对应的区间上不存在优先级更大的节点。所以一个节点的深度就是它向左和向右的上升序列的长度和。由于两侧的情况相似，仅考虑一侧，可以段树的每个节点上最大优先级和上升序列的长度，查询和更新时需要用到“查询节点对应的区间中首k2时间：O(NlogN2空间：O(N)DEC13.REALSETPetyaand给定一个N个数的序列A，求是否存在非全0的序列B，满足对于任意AiB(i+j)modN=∑，N30000|Ai|1000，多组询问，N150000法0对于f(xNN

FFTBluestein’sFFTAlgorithm实现（此算法的思想是构造两个向量，使得它们的卷积再乘一组系数就是DFT的结果，将任意点数FFT（对因数无要求）转化为卷积问题，使用2K点数的FFT或分治乘法解决。注意到N个复数相乘会爆精度，可以改为在模意义下计算，要取2个50000以上的kN1形式的质数作为卷积的模23109以上×c2K1形式NTT的模，实现较为繁琐。它部分复杂度O(NlogN)；空间：O(N)NOV13.QPOINTQueriesWith法考虑扫描线。以每个顶点的x坐标来划分区间（有些线段会被切开线段的出现时间是连续的一些区间，且对于某个线段集合，只要这些线段都存个区间保留一个状态。查询时，只要找到对应区间的平衡树，查出这个点下方的线段条数就可以知道内外，如果在多边形内，再查出下方最近的线段所属区域编y时间：O((N+QlogN空间：O(N)AUG13.PRIMEDSTPrimeDistanceOn求一棵树上任取两点，路径长度是质数的概率。N≤法可以求出树上每种不同长度的路径条数。可以使用点分治+时间：O(Nlog2N空间：O(NlogN)APR13.STRQUERYString的出现次数。涉及的字符串总长度不超过1500000。法头结，用别就把它们平分复杂度均摊后一样，查询时中间的那些可以MP这串equ间 串equ个 时间：O(|S|logFEB13.QUERYObservingthe个等差数列，求某个路径点权和，回退到第i次操作之后。法ABCD的两个等差数列相加可得到一个首项(A+B)，公差(C+D)的等差数列。所以“区间加等差数列”可以段树的(首项,公差)来实现，标记可以轻松地合并。这里的标记是2时间：O(NlogN22空间：O(NlogN)2NOV12.MARTARTSMartialNNi人和客队第j人比赛，两队分别得分Ai,j,Bi,j，设两队得分为H和G，则你要安排比赛最大化make_pair(H−G,H)，但是你安排好后，对方会在最大化make_pair(G−H,G)的前提下故意取消一场比赛。求最优答案。 最大二分图匹配。动态匹配可以通过将KM算法经过少量修改实现。4时间：O(N42空间：O(N)2SEPT12.PARADEAnnual有N（N≤250）座城市M条道路，可以安排若干条路线（每条路线必用累计）+起点不等于终点的路线数C+没有路线经过的城市数。给定若干个关于C的询问，回答最小费用。法,j)i到j）K，费用为S的匹配，说明有 —K)条路径未闭合或是单点，总费用SN—K×C。对于多个询问，预处理时每次增1流量，记下每次的费用增量，回答询问时二分最优位置（后面的费用全改。时间：O(N3NSPFA(NN2QlogN2空间：O(N)2AUG12.GTHRONESAGameof纸上N（N

500）之间必须只相差一个质因子。不能操作者输。问是否先手必胜，选哪些数作为 分时间：O(maxflow(N,N2)+N×back(N,N2))，back(N,M)为退掉一条3空间：O(N)3JULY12.DDynamic有一棵N个节点的树，两种操作：树上一条路径每个点点权加上某个值，求树上一条路径里所有点的。法有这样的性质：(A,B,C,···)= (A,B−A,C−B,···)，可以对所有点差分，区间修改变成单点修改，区间变成“区间，前缀和”的，线段树可实现。树上问题直接套用树链剖分。2时间：O(NlogNlog2空间：O(N)JUNE12.COOLNUMCool一个各位数之和K的数，如果取其13位（SKS)S是原数的倍数，则它是CoolNumber。最多100000组询问，每次一个不超过1000位的数，询问小于等于它的最大CoolNumberLC(N)和大于它的最小CoolNumberRC(N)。法O(L)LC(N)RC(N)Cool(9L

27)27>10L−1，L80，可以枚举

S再枚举(K−CoolNumber40000个，时间：O(P+TlogNlogCnt)，P为爆搜预处理的时间,CntCoolNumber的个JUNE12.MATCHExpectedumMatch-有一个左边N个点(N≤5)右边M个点(M≤100)的二分图，每条边有法HallU⊆U，相邻的右边点数不少于|S|。称这样的集合S为Hall点集，这样的点集的集合U={S1,S2,···称为Hall点集集合。考DP，FU,i表示仅考虑右边前i个点，点集集合U是Hall点集集合的期望。点集集合最多有 多都不可能满足条件，合法的只有4000个左右，可以BFS得到时间：O(CM)，C空间：O(CM)APRIL12.CONNECTFindaspecialconnectedNM(N,M≤15)的矩阵，每个格子填一个−[1N×M的整数，要求选通块，不包含-1格子且包含至少K种正数(≤7)，每个格子有法K+最短路来实现。权值比较大的情况，可以随机将权值到[1,K]的范围内，这样的结时间：O(SPFA(2kNM,3kNM空间：O(2kNM)MARCH12.EVILBOOKEvilN(N10)个敌人，i个敌人代Ci，可Mi点魔力，只有第一次才有魔力。可以消耗X点魔力寻求帮助（必须手里有至少X点）CiMi3666点法kii（必须有X点魔力可以限制按照ki递增的顺序敌人。由于要花最小666kiki4种有效取值。于是可以搜索+剪枝。时间：O(4N空间：O(N)MARCH12.CIELQUAKCielandRCP(11)(R连通概率。R≤8C≤1018法C比较小的情况，可以使用插头DP计算概率。打表观察可以发现，C 增大，C

的比值趋向一个常数。可以取一个M，计算AnsR,M (AnsR,M+1)(C−M) 左右精度就达到要求了。有效的连通性对应的 BFS3000时间 t)，Cnt为有效连通性状态数空间 FEB12.FINDSEQFinda15BAA5个数的子序列，要求相对顺序和B一样。N≤600法枚举第二个数和第四个数，然后可以贪心地选第一个数和第五个数（比第三个数大，取所有合法数中最大的，否则取最小的大小在某个区间内，可以判断有没有这个数，然后找到一组可行解。需要预处理前缀（后缀）比某个数大（小）的数以及一定范围内值在一定范围内的数的个数，可以ON2)2时间：O(N22空间：O(N)2FEB12.FLYDISTFlightN+1或-1。问使得对于所有边(i,j)，i到j的最短路不小于边(i,j)的长度的最小代价。N≤10。法题目的条件等价于对于所有的简单环，环上每一条边长度都大于等于其它边的和。只要考虑所有无弦环，其它所有环会自动满足要求。本题变为一个线性时间：单纯形算法理论时间复杂度是指数级的，但在本题上效果很好空间：O(NMC)，CJAN12.CARDSHUFCardNMABA上方，最后将C张牌直接放回牌堆上方。法直接用平衡树模拟所有操时间：O(MlogN空间：O(N)JAN12.MISINT2MisinterpretationL,RLR之间的小法每个重排相当于一个置换，如果循环数是f(n)f)n为奇数时，最后一个字符不变，所以f(2n+1)=f(2n)+1。现在只需要考虑数情况。T组询问。T5L,R1010RLord(x2x的阶，有结f(n)=

ϕ(p)。需要n∈[L−1R]f(n)[L−1R1]分ord(p)ab互)100000的数预处理出来L1R1]里每个数只要额外算一个质数的ord(p)。3log时间：O(R4R1.5T(RL)(Clog√

√)，CDEC11.SHORT2Shortpab>p(a−p)(b−p)|ab，TT≤p≤法abpa,bab|(ap)(bp)，等价于ab|p(abp)，设kab=p(abp)，分三种情况有且仅有5种解:(11)(12)(21)(23)(32) papb时ab，只有ab1满足要求。a̸b，不妨abk=pttab=abp，b=apabp≥ab p+1≥(a−1)(b−1)，a有上界1(a,b)满足：p∤d|(a+a|(d+

db=a+p>d此时bd至少有一个不

√ p1p1，可

p的时间内枚举addab(a当p|a和p|b有一者满足时，答案为前一种情况的两倍。因为前一种情况中一组可行解(a,b)对应这种情况的两组可行解(a,p(a+p))(p(b+p),b) √时间：O(TNOV11.LUCKYDAY有一个数S1A,S2BSiXSi−1YSi−2Z)modP(i个询问，求k(Lik≤Ri)满足SkCP是质数，PQ≤Li,Ri≤法X,Y有一个为0时循环节长度是O(P)，可以。X,Y均不为0时循环节长度可能达到O(P2)，可以使用矩阵乘法（实际使用时不一定要写矩阵，只要知道有结合性就行了）+大步小步来解决。时间：O(P1.5QlogP空间：O(P1.5)OCT11.BAKETheBakingQI产品[.大小]省[.城市[.地区]]出售数。第二种Q产 ] [.地 表示一个询问，方括号部分缺失或者产品、省为

1表示不限定这10310205个地区。S≤法开一个七维数组直接统计即可常数较SEPT11.SHORT−输出满足条件的数对n≤k≤法

n=0时答案(k−n

1)2n>0的情况 p(an)(bnabnab，bn+n(a−1)，a有上2n+ （n(a−1)的因数）ba很大时（a≥n+3000）枚举d比较，改为枚举p时间：O(nC)，Ca空间：O(nlogn)THEXCounting[1n]中。要求用这些木棍拼六边形，满足：最LXK根。计算有N≤N−L≤法dp，f[i][j][k][li位，进（1bit，6棍长度−1。 —L)logBaseN)，Base为 ，MaxCarr空间：O(MaxCarry·logBaseN6有大常数26AUG11.SHORTCIRShortestCircuitEvalu-给一个含and,or,not,变量和括号的短路逻辑表达式和每个变量为true的概率，式中所有涉及优先级的地方都加了括号|S|≤变量数目N≤数据组数T≤法FitrueGiFi(or)或Fi(and)从小 大排序，结果最优时间：O(T|S|logJUNE11.CLONESAttackofthe殊函数，它们的集合分别用Z,P,D,A表示：Z0-f(000···0)=P1-f(111···1)=D是自对偶函数集合，满足¬f(A1A2···An)=f(¬A1¬A2···[1,某个位置i上的数。Q个询问，每个询问给定一个上述集合的组合（一个含有并、交、差、补和括号的表达式1000003。n,Q,|S|≤100法函数是否属4个集合16种情况，可以先打表找规律推公式算出“属时间：O(logϕDEC11.HYPER3-3个点。3-超树是去掉任意一条边都不连通的连通3-超图。给定N，询问有N个点的带标号的本质不同的3-超树有几个。N≤17法考虑一个点数大于3的点双连通超树，每条边连接的3个点中，有且仅有个点是叶子（如果为0个叶子，则它不是超树，去掉这条边后仍然连通；如2个叶子，则它一定不是双连通的，3个叶子仅出现于3个点的情况N≤7本题可以打NOV11.DOMNOCUTColoredDominoTilingsandCuts你N和TT≤N,M≤法N×MN,M3种颜色的方案，因为5×66×8的情况，并(5+2k)×(6+2t)(62k(82t)的情况1M22K2(2K1)3M,4442K,4×(2K+1),6×6这几种情况时间：O(TNM空间：O(NM)OCT11.PARSINSinePartition∑f(n,m,X)m,n,Xf(n,m,m≤n≤

sin(k1X)sin(k2X)···法可以得到递推式f(ijX)=f(i−1j−1Xsin(X)+2f(ij−1X时间：O(M3logN空间：O(M3)AUG11.DIVISORSSomethingAboutDivi-少存在一个数D(N<D≤B)能整除N×X。T组数据。T≤X≤B≤法Di=NX，显然iX，可以考虑枚i，计算对应的满足i|NXN的数量。但是可能存在i<j<N,j|NX，导致重复计数。D因为i|NX， |N。设Ai ,N=Aip，因为N≤Bi，p 上界P=Bi考虑j|AiXp， |p，设Bj ，可以枚举j的集合容∑ansi

。直接计算会超时， lcm(Bj还有一个问题是X5859}Bj1|BjBj2。另一个是可以对所有询问排序，X2时间：O(XC)，Clcm2空间：O(XC)JULY11.YALOPTrialof有一个N×M的房间，每个格子是红色或蓝色，起点在(1,1)，终点在(N,M)5格颜色取反。移动为八连通。规定到达终点时所有格子必须蓝色，问是否能到达终点。T组数据。T≤N,M≤min(N,M)<K≤法不妨M<=NM>1时实际上每次操作可以任意选一格将周围格反色，因为可以2

2的区域实现“不改变颜色走一格”和“原地改变色”两种操作。此时本题相当于普通的“点灯”，可以用xor方程组高斯消元求解。本N很大，可以考虑通过递推把所有红色格子转移到第一行。递推有两种实现，一是矩阵乘法，但本题状态大小2M，矩阵乘法复杂度太高无法再考M1的情况，可以发现：总步数的奇偶性是一定的；如果N个格况，用O(K)的算法计算后面所有格子的状态，判断奇偶性是否有。实现较2时间：M1的情况为O((KM)PM)（P为循环节长度）M22空间：O(M)2JUNE11.MINESREVMinesweeper数据组数T≤R,C≤法把空连通块看成点，能一起打开的空连通块之间连边，则最小点击次数数时间：单组询问O(R3C3)，但本题可以通过ChallengeJUN