集训队作业sgu部分解题报告

1、SGUSGU需用到(上底 + 下底)* 高 / 2 才能使得 精确。根据zhouyuan code，在处理步长为delta 的体积P SGUSGU需用到(上底 + 下底)* 高 / 2 才能使得 精确。根据zhouyuan code，在处理步长为delta 的体积P 为(top+ low + mid * 4)/ 3 * 二+匈牙利算法weiran的解题 所讲，可以用寻找 0环的方法解决。0alive alive 结点。 alive性显然是相同的。但是怎么判断这个强连通分块是否是 alive 的fire alive 的。alive alive 的。rook的状态，DP先枚举旋转的状况（3种在枚举

2、平移的情况（n2种v初度不大于1，所以此时置xu = v，yv = u；如果点u 平移后对Qxu0yv0。现在 是判断一个 Q u 是属于第一个集合还是第二个u=S1有xuS2vs2有 yv = s1。xu0yu0u v, xv -w, Dfs一次，这其中如果 见中对于环串问题的研究2006SrbGa讲课的难题选讲(P48)uu=Su所有的相邻节uu=TCover 其实，感觉上本题可以不用网络流求解，显然后面构造方案的时1）u 可不可以用其他的方法的？感觉是可以的，因为本题太特殊了。（T（T+1O(mn3)。QueenQueenQ 方向上的点 Q，必有 Q=S(T+2)。前者是显然的，而后者实

3、际上相当于是相一个方向走一步，在 回另一个方向。由于性质发现时间可以只从奇偶性由于性质 2、3，考虑了Queen 行走路径不相交(Q=S(T+1)2、3 进行广搜。DP采取二分 。对于 anss到DP3DP采取二分 。对于 anss到DP3DP2n-1 11n考虑在 0 1，那么 n+1)便不能够放置了，于是根据贪心的 ， 在 (2*(n+1)1。如果这样能够把所有的位置都确定，那么 为 n。N=5定，此-1)个不相关的部分LL21。所(n+1,2n-1) * (L/ 2)+ 1(C(2p, p) + 2p2) / 将所预处理出来即可Gray显然上下两个矩形的右边界必然有树阻挡，那么枚举这两个

4、树的O(1)的得到当前最优解。分，见ysy2005 年解fkkey为kunblockedMKfkM。F 的性质：2k+1 2(k+1)；1) k+1 unblocked 2(k+1)unblocked 就是说，k+1fk1fk2) 2k+1为unblockedfk+1就是说，k+1fk1fk2) 2k+1为unblockedfk+1fk10；也就是说，fk + 1 fk2k+1 有关，给出精确的描述：fk+ 1 fk= ord(2k+1is么必然（K）2 1；如果对于给定的MfkKfkfk11，也就是说二进制(k -11)3 1，即(k-1)3 1。 Kfk+1fk1fkfk 1 = 1，即

5、(k)2 1 且(k -1)2 1。可以看到，符合这个条件的 K 的型式必然是(1000010)，即 2p+2+2的型式，那么 gp = fkgp能否很快的计算fk1fkord(2k+1isunblocked)gp0k-1gp= C(2, p+1) +M 有唯一非负整数解，这样就转化为了判断一元二次方程的解的O(1)解决了。)fM,p1,p2,p3,p4表示最后4个为p1,p2,p3, p4时完成M的最少O(n)* 8种情况（1表示大，0表示小。对所有的情况分类 ：100debti1i是最优的，如果debti = 1，那么就算这个钱币给i 也最多是1value000 型；110i、j中的一个必

6、然是最优的；否则 考虑将此钱币调整000 1案：选定顺序 i、j、k，先处理（i、j）的情况，此时优先 ki，j，k 即可debt 没区别，哪个 symbol：3）pixel 改变当前状态，可以发现，有影响的本pixelO(2k3）pixel 改变当前状态，可以发现，有影响的本pixelO(2k)个，枚举并进行状态转移（O(k)）即可。 K 6。M_preferu, vmanU v woman，F_orderu, v表示 manV womanU 第几喜欢的。manpartner假设前 k-1 个男士已经找到了 partner，此时为第k个男士寻找partner。womanTM_preferk1

7、，如果T还没+partner，那么w如果womanT 更喜欢W 的话T=M_preferk, 每；假设存在一组 unstable pair_(manU, womanV)，那么一定有 M_orderu,v M_orderu, partneruF_orderv, u F_orderv, 那么在为 U 寻找 partner 时，过V，但是 没 盾，所以不存在这样的unstable pair。O(n+首先，给出一些计算几何的计算法则（zhouyuan程序里看出来：在中设向量OP垂直于OQ 且|OP| = |OQ|，要求P 在平面OPQ 上向相 Q 方向旋转 alpha 度，则得到向量 V = cos(

8、alpha)P + P Q* Px + Qy * Py + Qz * Pz|Q| * QPT PPQW = 且置|W|P|1）1000 100000 n*m 原点的位置，以及向量x,y,z与O的相对位置O缩放操作，需要将所有的坐标都缩放，也就是缩放O 点的坐O缩放操作，需要将所有的坐标都缩放，也就是缩放O 点的坐O向量以O点按照旋转向量旋转。P，最终的位置为：x*xpy*ypz* zpO相2005 解首先，可以看到，(1,4,2,3)与(1,2,3,4)的方案数是一样的，也就board的位置时不会影响结果的，所以， 可以将 bFp,qp行放置qfp,qfp1,q + fp1, q1* (bpq

9、q)如果存在一条从1至u的路径且路径上至少存在3个不同的结点。则u 可以成为考虑路径外的边（p,p、q中至少有一个顶点属于该路径。由路径上不同的q 的结点上，此时便可以执行操作（p，q u简便起见称该类路径为类路径1 的节点u如果1 与u 不连通，则u 显然不可能成，不予考虑，如1 与u 1至uu 一条A类路径。（u，v，（1，v1，ua) 11 如果存在顶点u1至u1121A类路径(1,u,v1)。如u，v 1，则成立，对于这种情况， 只需u如果存在顶点u1至u1121A类路径(1,u,v1)。如u，v 1，则成立，对于这种情况， 只需u，v 即可。在ysy2005 年解kA u 的路径采取

10、深搜的策略。其满足一个重要的性质： uv 的路径，那么今后v。Fk,l,rk扩展成输入中l.rFk, l, r = true if exist ptfc1,l,pand fc2,p1, rand kc1, 2在1）的前提下，尽量为1，如果其为0；希望次尽量为取一个polyon 内点，向polygon的所有顶点连边，就了一个三角剖分。将这个三角剖分按照极角排序就形成了一个有序结构当加入一个新顶点时首先在有序表内查找到极角的位置在执行操作即可。 详细解答见05应用polya 定理，在BABA，AB 的作用向量为 AB，有：ma(Va + p * BA) + mb(Vb + q * AB) = ma

11、*Va + mb*Vb；ma*Vap*BA)2mb*Vbq*AB)22E，解方13th question sigman 种概率/n。 fu,vSclubu分，viewersv分，问题的回答情S（状态压缩）出现的概率。递推即可解决。Answeru,v=sigmafu,v,首先回路给每条边定向，然后求最大匹配即可13th question sigman 种概率/n。 fu,vSclubu分，viewersv分，问题的回答情S（状态压缩）出现的概率。递推即可解决。Answeru,v=sigmafu,v,首先回路给每条边定向，然后求最大匹配即可fii那么有：fi= fi 1+ fi c1 +1（解f

12、Q T的时间已确认，所为T+Cn1 变成偶数以保证每轮n-1个对手。考虑采用每次对战的选手的序号和mod(n1)的同余等价类划tour。 选手 unvnuv，(uv)mod (n -1)是唯一的。但是唯一的特殊情况是(u + u) mod (n 1)也唯一n 比赛即可。le:n= 1 234Rest = 2143Rest = 3412Rest = 4321现用预处理把所有的状态都算出来，询问就很好解决了。简单的AC 了对于第一种情况，empty的个数是(namodn)*(nbmod对于第一种情况，empty的个数是(namodn)*(nbmodn)；对于第二种情况，empty 的个数是(a m

13、od n) * (b mod n)。放置1*n矩形的个数为（a*bempty）/n。是否对于任意输入都有解呢（RP）？这道题目非常巧妙，就像CTSC2003 用到的三角梯一样，本题就 如果把所有的元素尽量连成块，序列加入两个元 后，由于但是，这毕竟是两种特例，如果 它们的优点结合起来，就能够创造一种更好的结构， 给出这种结构的描述：在中间元素两旁各布置(a b) / 2101相间的放置在右端，10 相间的放置在左端，如下就是一个符合0可以看到中间元素是 0，两端各有 4 个 1，然后在布置相间的 01 01010。实际上，经过尝试之后 发现， 可以用最多两次操作去维burnside 定理得应用，直接套公式即可。需2 的幂需要用倍增，否则速度很可观。简单的递推，但是要考虑高精度（超过64贪心，显然选取的最 1nk + 次 有一样的原则，但必须低于最 。显然为summodnai为顶点，(xi,yi)ci0s,t 和边集(s,显然为summodnai为顶点，(xi,yi)ci0s,t 和边集(s, i)0与(I, t)0diss0用拓扑排序可求得满足条件的每个点的最小距dist20000an a1尽 a1 a110000得 。O(n*500)然后