学步园

D2 500p： CirclesCountry

简单题，枚举每两个点是否在同一圆内。

D2 1000p：  Polygons2

首先将数组segments排序。对于segments[i]而言，它能组成的N边形个数=总长度大于segments[i]的前面N-1边形的个数。设状态表示为F[i][k][sum]，k表示边数，则F[i][k][sum] = F[i - 1][k - 1][sum - segments[i]] + F[i - 1][k][sum]。最后对每一个i做统计得和。

class Polygons2<br /> {<br /> long long int f[2][51][50100];<br /> public:<br /> long long number(vector <int> segments, int K)<br /> {<br /> memset ( f, 0, sizeof ( f ) );<br /> sort ( segments.begin (), segments.end () );<br /> int n = segments.size ();<br /> if ( n < K )<br /> return 0;<br /> int i, k, p;<br /> long long sum;<br /> long long max = segments[n - 1] + 1;<br /> long long cnt = 0;<br /> f[0][0][0] = 1;<br /> for ( i = 0, p = 0; i < n - 1; i ++, p = 1 - p )<br /> {<br /> for ( sum = 0; sum <= max; sum ++ )<br /> f[1 - p][0][sum] = f[p][0][sum];<br /> for ( k = 1; k < K; k ++ )<br /> {<br /> for ( sum = 0; sum < segments[i]; sum ++ )<br /> f[1 - p][k][sum] = f[p][k][sum];<br /> for ( sum = segments[i]; sum <= max; sum ++ )<br /> f[1 - p][k][sum] += f[p][k - 1][sum - segments[i]];<br /> for ( sum = max - segments[i] + 1; sum <= max; sum ++ )<br /> f[1 - p][k][max] += f[p][k - 1][sum];<br /> }<br /> for ( sum = segments[i + 1] + 1; sum <= max; sum ++ )<br /> cnt += f[1 - p][K - 1][sum];<br /> memcpy ( f[p], f[1 - p], sizeof ( f[p] ) );<br /> }<br /> //print ( K, max );<br /> return cnt;<br /> }<br /> }

D1 500p : BinaryFlips

很好的一个题目，BFS+压缩路径优化。

假如单纯用BFS，该题的复杂度是O(N*M)，M代表了当前所有能到达的状态。由于在M其中许多状态都是相关联的，考虑对其作优化。

设A[a]代表了走到a状态时最少需要的步数。再建立一个双向链表维护尚未到达的状态。

当在a状态下翻K个硬币，得到的是一串新状态：l, l + 2, l + 4,...h - 2, h，那么此时就可以把l到h的序列从链表里脱链。有新序列时先寻找未到达状态序列的首地址，然后遍历一下就行了。

class BinaryFlips<br /> {<br /> void insert ( int index, int value )<br /> {<br /> a[index] = value;<br /> if ( prev[index] != -1 )<br /> next[prev[index]] = next[index];<br /> if ( next[index] != -1 )<br /> prev[next[index]] = prev[index];<br /> }<br /> int findFirst ( int index )<br /> {<br /> if ( index == -1 || a[index] == -1 )<br /> return index;<br /> return next[index] = findFirst ( next[index] );<br /> }<br /> public:<br /> int minimalMoves(int A, int B, int K)<br /> {<br /> int i, high, low;<br /> int N = A + B;<br /> for ( i = 0; i <= N; i ++ )<br /> a[i] = -1;<br /> for ( i = 0; i <= N; i ++ )<br /> {<br /> next[i] = i + 2;<br /> if ( next[i] > N )<br /> next[i] = -1;<br /> }<br /> for ( i = 0; i <= N; i ++ )<br /> {<br /> prev[i] = i - 2;<br /> if ( prev[i] < 0 )<br /> prev[i] = -1;<br /> }<br /> insert ( A, 0 );<br /> queue < int > q;<br /> q.push ( A );<br /> while ( !q.empty () )<br /> {<br /> int cur = q.front ();<br /> q.pop ();<br /> if ( K > N )<br /> low = -1;<br /> else if ( K < cur )<br /> low = cur - K;<br /> else<br /> low = K - cur;<br /> if ( K > N )<br /> high = -1;<br /> else if ( K + cur < N )<br /> high = K + cur;<br /> else<br /> high = N - ( K + cur - N );<br /> low = findFirst ( low );<br /> int j;<br /> for ( j = low; j <= high && j != -1; j = next[j] )<br /> {<br /> insert ( j, a[cur] + 1 );<br /> q.push ( j );<br /> }<br /> }<br /> return a[0];<br /> }<br /> }