 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
先贴个今天题解吧1001: 枚举正方形对角线上的两个点(x1, y1), (x3, y3)，然后通过计算可得:
正方形上的另外两个点是(x1, y3), (x3, y1), 当然，对角线上的两个点需要满足正方形的特点，这里需要特判一下。
1002: 以单词为点，能前后相连的单词之间连边，得到一个有向图，求长度为奇数且小于等于N的不同的S->T的路径数。设邻接矩阵为A，则可通过求A
+ A ^ 3 + ... + A ^ N求解。构造一个矩阵后可通过logN次矩阵乘求解。
1003:
Define S[i] as the sum of the first i elements of the given number sequence A.
Define R[i] as the reminder of Si module P: R[i] = S[i] % P.
Then the target of this problem is to find a maximum partial summation
of A which satisfy the reminder of it module P isn't bigger than K.
That is:
max{s[i] - s[j]} st. j < i && (s[i] - s[j]) % p <= K
The number given are all non-negative, so max{s[i] – s[j]} is equal to
min{j}. With the help of the sorted R sequence, we can obtain a linear
solution to this problem.
1004:
The problem is equivalent to the following problem:
How many ways to divide an positive integer N to integers larger than
1? ( We consider integers with the same value to be the same.)
Such problem can be solved easily by simple dynamic programming in O(N^2) time.
1005:
注意到K<N，可以推导所求的第K项分子不会大于3，枚举一下分子然后二分分母再求出之前的项数，这样时间复杂度是O(logN)，或者直接找规律，时间复杂度O(1)
1006:
暴力算法：枚举每条边，然后对每个点求一次单源最短路，由于题目中的边的权值都是1，因此可以用bfs来求得每个点的单源最短路。复杂度是O(M*N*M)。由于M*N*M=3000*100*3000=9*10^8,
因此只能通过数据规模较小的测试数据。
标程算法：仍然使用上面的思路，但要作一些预处理。对每个顶点u求一次单源最短路，把求得的结果称作u的最短路径树。若被破坏的公路不在该最短路径树上，则从u出发的所有最短路径的总和就是u到该树上的所有顶点的路径的总和，这里可以作O(M)的预处理，然后花费O(1)时间就能返回结果；否则，删除被破坏的公路后，从新计算从u出发的所有最短路径的总和，这步的复杂度是O(M)。由于最短路径树上只有N-1条边，因此需要从新计算的次数只有N-1次。因此，程序的复杂度变为O(N*N*M)=3*10^7。
1007: 模拟题。按照规则模拟，注意" The top card of the remaining stock is exposed to
start the game, treated as if player 1 dropped that card" 和 "If the
last card is an action card, the special effect still occurs." 即可。
1008: 网络流。设原来的源和汇分别为s和t，先用一次最大流算法求出残余网络，设对应的最小割集为（S,T）。那么分别求以s为源点，|S|中的其它点为汇点的最大流的最大值，以及以|T|中的其它点为源点，t为汇点的最大流的最大值。两个最大值的较小值即为答案。
1009:
比较简单的做法是"移动"球心直到其在x,y,z轴上都接触到长方体为止（例如对于X轴，也就是计算满足MinX<=BallX'<=MaxX的最小的|BallX'-BallX|,
MinX和MaxX是长方体X轴的最小最大坐标，BallX和BallX'是移动前后球心X坐标），判断移动的距离是否少于半径即可。
1010:
Notice that the graph given is acyclic, so we can use dynamic
programming to calculate the optimal solution in topological order.
O(MK)
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
