信息学集训队作业

1、Ural Volume 4PPLoveTT题目题意简述算法简述1300一个地方的收税方法是：小于 N1 部分收 S1 的税，N1N2 之间的收 S2 的税超过 Nm 的收 Sm+1的税。还有 L%的，即如果你的工资为 R，那么你实际得到的钱是：R-T(R)+R*L%-T(R*L%)计算过程中全部保留两位小数。现在某个人在 P 个地方工作，给出他在每个地方实际得到的钱，求他每个地方分开算税和全部 加起来一起算税，税额相差多 少。首先全部都乘上 100，这样就只需要保留整数就行了。可以通过二分求出他在每个地方的工资。然后再计算一下即可。 (精度非常有问题)时间复杂度：O(P*Log21016)空间

2、复杂度：O(P)1301在一个 N*M 的棋盘上，某些格子之间有墙挡着。求一个 从 (A,B)通过滚动到达(C,D)的最少步数，要求起始和最终朝上的面相同。一个的状态只有 24 种，直接BFS 即可。时间复杂度：O(N*M*24)空间复杂度：O(N*M*24)1302在一个无限大的数字三角形中，求从 A 到 B 的最少步数。算出 A 和 B 的坐标，然后分情况讨论即可。时间复杂度：O(1)空间复杂度：O(1)1303有 N 个区间Li,Ri，要求选择最少的区间个数完整覆盖0,M。贪心。首先将区间按照左端点排序。先设 L=0，然后在所有可行的区间中(li=20000。将th替换成$。时间复杂度：

3、O(Len)空间复杂度：O(Len)1308有一个金字塔，初始位置的底面中心是(0,0)。每次可以把金字塔沿着某条边翻滚一次。如果当前位置是底面，那么下次翻的方向一定要和上次相同。求翻滚不超过 70 次，底面中心能离点(x,y)的最近距离。通过观察可以得知金字塔底面中心的位置只能是某两类形式的，直接BFS 即可。时间复杂度：O(Unknown)空间复杂度：O(Unknown)1309有两个函数 f 和 g，求 fn。将 gx,y 化成 y 主元的形式，就是一个关于 y 的一次函数。因为是%9973，所以可以先求出这 9973个递推关系，将这些先乘以来，然后再 9973 个一起递推。时间复杂度：

4、O(N/M+N%M)空间复杂度：O(M)M=9973。1310求长度为 L 的，每个数字只能是 1.M 的，数字和是 K 的倍数的，第 N 大的序列。首先预处理出 Fi,j。Fi,j 表示长度为 i 的，除以 K 的余数为 j 的序列有多少种。然后可以通过一位一位来确定这个序列。时间复杂度：O(L*K*M*Len)空间复杂度：O(L*K*Len) Len 为高精度复杂度。1311有 H 层砖头，保证每块砖头和比它低的砖头只有一个相碰。求是否稳定。可以将这些砖头看成一棵树，谈后计算出每个的重量和重心的横坐标。然后判断一下就行了。时间复杂度：O(N)空间复杂度：O(N)1312在一个 H*W 的矩

5、形里放三个圆，半径分别为 R1,R2,R3。枚举一个圆放在左下角，然后枚举第二个圆放在右下角，左上角和右上角。如果第二个圆放下后与第一个圆有交，那么就将这个圆向上或向右移动。两个圆放完后，将这两个圆的半径都增加第三个圆的半径，矩形的四边都向内压缩第三个圆的半径。接下来第三个圆放的位置就是矩形的四边和两个圆的交点位置。放完后再判断一下就可以了。时间复杂度：O(1)空间复杂度：O(1)1313一个 N*N 的矩阵，按照对角线输出。1314有一张无向图，有一个罪犯依次经过了一些点。他要去某个目的地，并且走的一定是最短路。求哪些点可能是目的地。枚举目的地，然后从目的地出发 BFS，然后判断它经过的这些

6、点的到目的地的距离是否是依次递减的。时间复杂度：O(N2*K2)空间复杂度：O(N*K)1315有一个 W*H 矿洞，先要从上往下灌水，水只会往不会往上。一个人只能在水中最多呆 D的时间。求这个人能否从(X,Y)走到外面去。类似最短路一样做即可。时间复杂度：O(W*H)空间复杂度：O(W*H)1316在一个拍卖市场里，有三种操 作：出价 x，撤销出价 x，以 x 的价格出售 k 头猪，价格不比 x 低的人能买。每桩交易市场获利 0.01。求最终市场的获利。简单的数据结构题，离散以后树状数组。或者直接用平衡树。时间复杂度：O(N*Log2N)空间复杂度：O(N)1317有一个 N 多边形围墙，里

7、面有个台，发射的无法打穿围墙，并且有距离上限。现在有 M 个位置有东西落下来，求能打到多少。在围墙里面的，掉到地上再打。在围墙外面的，连线刚好在围墙上沿了再打。时间复杂度：O(N*M)空间复杂度：O(N)1318求Log10AiAj。枚举求这个 Log10()用二分，而且要人工打的时间复杂度：O(N2*Log238)空间复杂度：O(N)1319输出一个 N*N 的矩阵1320有一张偶数条边的无向图，求是否将两条边一组分组，使得每一组边都有公共定点。如果每个连通分量都是偶数条边，那么就是可行的。时间复杂度：O(N+M)空间复杂度：O(N)1321一个电梯的指示灯破了，有些灯始终亮着，有些灯只是不

8、会亮。求情况下最少要乘多少层 楼才能发现是哪个坏了。分类。时间复杂度：O(Len)空间复杂度：O(Len)1322有一个循环串，将这 N 个串排序后将每个串的最后一个字符给你，再给你要求的串排序后的位置，还原这个串。先将这 N 个字符排序，得到首字符和尾字符的对应关系。然后如果当前位置对应过去的首字符是 c，且是 c 中的第 k 位，那么在尾串中 c字符排在第 k 位的就是其相同的哪个字符。时间复杂度：O(N)空间复杂度：O(N)1323开始只有一个人知道消息，每一分钟每个知道消息的人可以将消息告诉某个他的朋友。问最少多少时间可以完成。动态规划。Fi,j 表示第 i 分钟状态为 j 是否能达到

9、。j 是三进制的。0 表示还不知道，1 表示这分钟还没传过消息，2 表示已经传过消息。时间复杂度：O(N2*3N)空间复杂度：O(N*3N)1324有一种替换操作，可以将连续 x个空格替换成 1 个。求一个最短的操作序列，使得对于任何长度不大于 L 的空格都能替换成 1 个空格。多解输出能使得最大的 M，任何长度不大于 M 的空格都替换成 1 个的操作序列。每次操作肯定使得剩余的空格最少，递归处理，返回上来一个最大的 M。时间复杂度：O(L*Log2L)空间复杂度：O(Log2L)1325有一个矩形，元素只有 012。0是无法进入的。求从起点到终点最少需要变换几次 12。在变换次数最少的情况下

10、最少需要走几步。两次BFS。第一次先求出终点到其它点最少需要的变换次数。第二次再求出最少需要的步数。时间复杂度：O(N*M)空间复杂度：O(N*M)1326有 N 种东西，要买其中的某几样。还有 M 种 方式，就是某几样一起买需要这么多钱。求状态压缩动态规划。FS 表示哪些东西已经买了的最少花费。转移枚举买什么。最少的花费。时间复杂度：O(2N*M)空间复杂度：O(2N+M)1327求A,B之间的奇数个数。1328一个矩形里有两个点 A,B，从 A发射一束激光，反射 N-1 次以后到达 B。求最小的发射角度。枚举竖着的边反射了几次，然后可以算出B 的新坐标，直接计算角度。时间复杂度：O(N)空

11、间复杂度：O(1)1329有一棵树和一些询问：A 和 B 的关系。关系只有三种：A 是 B 的祖先，B 是 A 的祖先，两者都不是。用 Tarjan 算法求出所有询问的LCA，然后分情况输出。时间复杂度：O(N+M)空间复杂度：O(N+M)1330有一个长度为 N 的序列，以及 M个询问：第 A 个到第 B 个的和是多少。处理出前缀和 Sk，那么就是SB-SA-1。时间复杂度：O(N+M)空间复杂度：O(N)1331有两组点 A 和 B，A 中有 N 个点，B 中有 M 个点。点都是以形式给出的。求对于 A 中的每个点，B 中离它最近的距离。先求出所有点在空间中的坐标，然后枚举就可以了。时间复

12、杂度：O(N*M)空间复杂度：O(M)1332有 N 个圆，半径都是 r。现在可以放入一个半径为 R 的圆，求最多可以完整覆盖多少个圆。将 R 减少 r，那么 N 个圆就变成了 N 个点。放入的圆的圆周上必定有 2 个点，枚举就可以了。时间复杂度：O(N3)空间复杂度：O(N)1333在一个0.1*0.1的正方形内，求 N 个圆的面积并。随机洒点。时间复杂度：O(N*T)空间复杂度：O(N) T=10000001334有一种黑白棋，两人依次放了 32枚棋子。如果第 k 个棋子放下以后，能够发生图中所示的事件，那么就输出 k。否则输出Draw。模拟。时间复杂度：O(32*8*8*4)空间复杂度：

13、O(8*8)1335给三个数 A,B,C，满足： N2=A,B,C2 都无解。 n=1：a=1 b=2 c=3 n=2：a=3 b=4 c=5时间复杂度：O(1)空间复杂度：O(1)1350有 N 种食物，其中有 M 种是有毒的。有 K+1 个人，第一个没有的。求剩下的 K 个人的情况。设第一个人吃了 P 种，当前这个人吃的食物中第一个没吃的有 Q 种。如果 Q=0，那么一定不 。如果 N-P-QM，那么一定 。其它是可能 。时间复杂度：O(K*N)空间复杂度：O(K*N)1351有一个扇形，判断点是否在扇形内。先求出扇形角度的范围，如果点在这个范围内，再判断距离。时间复杂度：O(N)空间复杂

14、度：O(N)1352第 N 个Mersenne Prime。打表时间复杂度：O(T)空间复杂度：O(1)1353求1,1000000000中和为 S 的数的个数。动态规划。Fi,j 表示长度为 i 的，和为 j 的数字有几个。时间复杂度：O(S*81)空间复杂度：O(S)1354给一个串 S1，求一个长度最短的非空串 S2，使的 S1S2 为回文串。枚举时间复杂度：O(Length(S1)2)空间复杂度：O(Length(S1)1355求从 A 变到 B 最少要操作几次，一次操作能将 A 乘以一个质数。如果 B 不是 A 的倍数，那么无解。否则就是 B/A 的质因数个数。时间复杂度：O(T*S

15、qrt(B/A)空间复杂度：O(1)1356求 N 最少是多少个素数的和。根据哥德巴赫猜想，一个大于 2 的偶数必定可以分成两个质数的和，因此 最多为 3时间复杂度：O(T*Sqrt(N)空间复杂度：O(1)1357题意太麻烦了，就不说了就是一个模拟题模拟吧时间复杂度：O(N)空间复杂度：O(1)1358有一棵树，要求将其放置在平面上，是的边不相交且每条边的长度都要大于 1。分层以后一层一层放。时间复杂度：O(N)空间复杂度：O(N)1359要在(0,0)与(N,M)之间搭一段路，使得从(N,M)到(0,0)滚得最快。Fi,j 表示从(i,j)到(0,0)需要的最少时间，转移用 N*M 枚举。

16、时间复杂度：O(N2*M2)空间复杂度：O(N*M)1360有一个函数，求在该函数上的一个点，使得离(x0,y0)的距离不超过 。cos(x)的周期是 2。令 t=acos(y)，然后以 2 为步长一直增加，直到找到一个符合要求的点。时间复杂度：O(Unknown)空间复杂度：O(1)1361有 N 个点的有向图，还有两个人A,B。A 总是走最左边的路，B 总两个人都是先走几个点，然后进入一个环。枚举在哪个点相遇，解模是走最右边的路。求 A 与 B 相遇的最早时间。线性方程。时间复杂度：O(N*Log2N)空间复杂度：O(N)1362有一棵树，一开始只有一个点知道信息。每个时刻，已经直到信息的

17、点可以向一个相邻的点传递信息。求所有点都知道信息最少需要的时间。以一开始知道的哪个点为根建树。然后 Fi 表示以 i 为根的中的所有节点都知道信息所需要的最少 时间。转移的时候将儿子的 F 值从大到小排序，然后按这个顺序传递信息。时间复杂度：O(N*Log2N)空间复杂度：O(N)1363有一个 N*M 的图，构造一个同样大小的图，只有 0 和 255，满足题中所述的条件。随机。对于每个位置，随机出一个值。如果这个值小于图中的 值，那么赋值为 0，否则赋值为 255。时间复杂度：O(N*M)空间复杂度：O(1)1364一张 N*M 的地图，初始位置在 (1,1)，朝北。路线是一直往同一个方向走

18、，走到边界或者一个已经走过的位置，然后转弯，走到输入第二行的那个位置就停下来。求该路线中能通过沿该路线走 K 步走到输入第三行中的那个格子的那些格子。模拟走的过程，然后输出路径中这段区间的所有格子。时间复杂度：O(N*M)空间复杂度：O(N*M)1365自定义表达式求值。模拟。多试试H中提供的东东。时间复杂度：O(Len)空间复杂度：O(Len)1366错排Fn=(n-1)*(Fn-1+Fn-2)时间复杂度：O(N*Len)空间复杂度：O(N*Len) Len 为高精度复杂度。1367一张 W*H 的地图，每个格子可以看成 3*3 的小格子，被填成了那种样子的(#看成是+)。被填的那些格子不能

19、走。求所有#之间的连通情况。卡内存的题一个格子看成 3*3 个格子后，左上、右上、左下、右下角的这些格子肯定是空的。那么把一个 2*2 的这种格子看成是同一个格子，然后用并查集做时间复杂度：O(W*H)空间复杂度：O(W*H)1368用最少的格子数，使得里面有 K个格子。里面的形状是类似斜的正方形一样的。然后就一层一层放格子。到新的一层的时候，从顶端格子的右边开始放起，顺时针放过去。时间复杂度：O(K+Ans)空间复杂度：O(K+Ans)1369平面上有 M 个点，还有 N 个询问，每个询问输出距离这个点最近的那些点。VORONOI 图1370有 N 个数字，初始位置在 1。向后跳 M 个数字

20、，然后输出从这个位置开始的 10 个数字。直接模拟时间复杂度：O(N)空间复杂度：O(N)1371求树上两点间距离的平均值。一条边被计算的次数就是这条边去掉后两边点的个数的乘积。时间复杂度：O(N)空间复杂度：O(N)1373平面上有 N 个等腰直角三角形，每个直角三角形都可以按照斜 边翻转。用最小的矩形覆盖这 N个三角形。所有三角形都是朝向同一方向的时间复杂度：O(N)空间复杂度：O(N)1375求方程 x2+y2=k (mod p)的一组解。枚举时间复杂度：O(p)空间复杂度：O(p)1376同 1308。没有那个限制。搜索时间复杂度：O(Unknown)空间复杂度：O(Unknown)1

21、377一个 N*M 的地图，初始位置在 (1,1)，面朝(1,2)。向前一直走到边界或者已经走过的地方，然后就转弯。求走到两个点的时间差。模拟完了以后直接输出时间复杂度：O(N*M)空间复杂度：O(N*M)1379有一辆卡车要运，起点是 1，终点是 N。每条路有两个值，能承受的重量和通过的时间。卡车重 3 吨，每个重 200 克。求在24 小时内最多能运多少。二分，然后最短路验证。时间复杂度：O(N2*Log2Ans)空间复杂度：O(N2)1381有一幢无限层楼的大楼。每层楼用 Fi,j 表示上面一层的蟑螂数目为都会有蟑螂，且蟑螂数目不超过 N。下一时刻蟑螂的数目与当前蟑螂的数目以及楼上与楼下

22、的蟑螂数目都有关。求是否蟑螂数目始终不变、或者不会减少、或者不会增加、或者有可能减少也有可能增加。i，当前层蟑螂数目为 j 的蟑螂个数能增加或减少的最大值。然后做最短路，判断是否存在一个 F0,0 到 F0,0的正权环或负权环。时间复杂度：O(N4)空间复杂度：O(N2)1382有 N 个人，他们每人都有 1有数字的牌。N 标号为 1.N的一个排列。每个人都说了两句话，第一句是 牌上的数字是 Ai，第二句是 Bi 拿的牌上的数字是 Ci。但是其中有且仅有一句话是对的。求其中 案。2-SAT。时间复杂度：O(N2)空间复杂度：O(N2)1384在一个简单多边形内放一个圆，求圆的最大半径。巨麻烦的

23、几何题这个圆必定是被边或者点卡主的，那么分四种情况分别时间复杂度：O(N3*Log2Ans)空间复杂度：O(N)1385输出长度为 2N 的erse-ting number的个数。erse-ting number是能被前 N位和后 N 位整除的数。N=1 14N=2 155N=3 157500.0 (N-3 个)时间复杂度：O(N)空间复杂度：O(1)1386有一个 N*M 的地图，有四种操作方式，表示在该种操作方式下在这个格子的东西下一次会到某个格子。现在有一个长度为 P的操作序列，求最终可能有东西的是哪些格子。将两个操作并成一个，这样就能Accepted 了时间复杂度：O(N*M*P)空间

24、复杂度：O(N*M)1387求 N 个点的无标号有向生成树数个数。Fi 表示 i 个点的个数。转移的时候 Gi,j 表示之前的的结点个数不超过 i，结点总数为 j 的方案书。转移枚举结点个数为 i 的用了 k个，那么 Gi,j=Gi-1,j-k*i*(Fi*(Fi+1)*.*(Fi+k-1)/k!。注意需要高精度。时间复杂度：O(N4)空间复杂度：O(N)1389一棵有 N 个节点的树，求最大匹配。贪心。选取任意一个点当根，然后从叶子节点开始，选择这个节点和其父亲相连的边，将这两个节点删除。时间复杂度：O(N)空间复杂度：O(N)1391有一张 N*M 的地图，求长度为 2.17 的蛇能否从某个地方进入再从这个地方出去。输出最少步数。先从进入的地方BFS。然后枚举所有可达的格子，从这个格子出发找一个环，如果找到了一个长度为 k的环，那么更新