学步园

相比起443来略为简单。D1三道题分别是简单题、简单题和简单题。

D1 250p  Underprimes

没什么好说的，分解质因数，拼手速的题目。

D1 500p  BedroomFloor

模拟题，有些麻烦。

首先算出中间完整的正方形个数。然后用边上完整的正方形去和原长方形做交集运算，分出各种小矩形。

最后用4和1相拼，3和2相拼，3和1相拼，2和1相拼，1和1相拼。

class BedroomFloor<br /> {<br /> long long a[6];<br /> void add ( int x, int y, int x1, int y1, int x2, int y2 )<br /> {<br /> //printf("add: (%d,%d) in (%d,%d)×(%d,%d)/n", x, y, x1, y1, x2, y2);<br /> x1 = Max ( x, x1 ), y1 = Max ( y, y1 ), x2 = Min ( x + 5, x2 ), y2 = Min ( y + 5, y2 );<br /> if ( x1 >= x2 || y1 >= y2 )<br /> return;<br /> if ( ( ( x / 5 ) + ( y / 5 ) ) & 1 )<br /> {<br /> //printf(" -> %d of length %d/n", x2 - x1, y2 - y1 );<br /> a[y2 - y1] += x2 - x1;<br /> }<br /> else<br /> {<br /> a[x2 - x1] += y2 - y1;<br /> //printf(" -> %d of length %d/n", y2 - y1, x2 - x1 );<br /> }<br /> }<br /> public:<br /> long long numberOfSticks(int x1, int y1, int x2, int y2)<br /> {<br /> memset ( a, 0, sizeof ( a ) );<br /> // translation<br /> int t = x1 / 10 * 10;<br /> x1 -= t, x2 -= t;<br /> t = y1 / 10 * 10;<br /> y1 -= t, y2 -= t;<br /> int x, y, xx = x2 / 10 * 10, yy = y2 / 10 * 10;<br /> if ( x2 > 10 && y2 > 10 )<br /> a[5] += ( long long ) ( xx - 10 ) * ( long long ) ( yy - 10 ) / 5;<br /> //printf ( "%lld/n", a[5] );<br /> for ( x = 0; x < x2 + 10; x += 10 )<br /> {<br /> //printf ( "1/n" );<br /> add ( x, 0, x1, y1, x2, y2 );<br /> add ( x, 5, x1, y1, x2, y2 );<br /> add ( x + 5, 0, x1, y1, x2, y2 );<br /> add ( x + 5, 5, x1, y1, x2, y2 );<br /> }<br /> for ( y = 10; y < y2 + 10; y += 10 )<br /> {<br /> //printf ( "2/n" );<br /> add ( 0, y, x1, y1, x2, y2 );<br /> add ( 5, y, x1, y1, x2, y2 );<br /> add ( 0, y + 5, x1, y1, x2, y2 );<br /> add ( 5, y + 5, x1, y1, x2, y2 );<br /> }<br /> if ( yy >= 10 )<br /> {<br /> //printf ( "3/n" );<br /> for ( x = 10; x < x2 + 10; x += 10 )<br /> {<br /> add ( x, yy, x1, y1, x2, y2 );<br /> add ( x, yy + 5, x1, y1, x2, y2 );<br /> add ( x + 5, yy + 5, x1, y1, x2, y2 );<br /> add ( x + 5, yy, x1, y1, x2, y2 );<br /> }<br /> }<br /> if ( xx >= 10 )<br /> {<br /> //printf ( "4/n" );<br /> for ( y = 10; y < yy; y += 10 )<br /> {<br /> add ( xx, y, x1, y1, x2, y2 );<br /> add ( xx, y + 5, x1, y1, x2, y2 );<br /> add ( xx + 5, y + 5, x1, y1, x2, y2 );<br /> add ( xx + 5, y, x1, y1, x2, y2 );<br /> }<br /> }<br /> //printf ( "%lld %lld %lld %lld %lld/n", a[1], a[2], a[3], a[4], a[5] );<br /> long long ret = a[5];<br /> while ( a[4] > 0 )<br /> a[4] --, a[1] --, ret ++;<br /> while ( a[3] > 0 )<br /> {<br /> ret ++, a[3] --;<br /> if ( a[2] > 0 )<br /> a[2] --;<br /> else if ( a[1] >= 2 )<br /> a[1] -= 2;<br /> else<br /> a[1] = 0;<br /> }<br /> while ( a[2] > 0 )<br /> {<br /> ret ++, a[2] --;<br /> if ( a[2] > 0 )<br /> {<br /> a[2] --;<br /> if ( a[1] > 0 )<br /> a[1] --;<br /> }<br /> else if ( a[1] >= 3 )<br /> a[1] -= 3;<br /> else<br /> a[1] = 0;<br /> }<br /> while ( a[1] > 0 )<br /> ret ++, a[1] -= 5;</p> <p> return ret;<br /> }<br /> }

D1 1000p  NowhereLand

网络流。这个题的建图还不甚清楚，好像是把所有已有的点和源点相连无穷大，可以建立公司的点和汇点相连无穷大，边与边相连1。

 已有点设为黑点，不能建立公司的点设为白点，剩下的点黑白染色，求黑白集合间的最小割。

class NowhereLand<br /> {<br /> int guard[60][60];<br /> int agency[60][60];<br /> int a[60][60];<br /> int prev[60];<br /> int dist[60];<br /> int src, dst;<br /> int fflow ( int s, int d, int v )<br /> {<br /> queue < int > Q;<br /> memset ( dist, 0, sizeof ( dist ) );<br /> Q.push ( s ); dist[s] = 1000000;</p> <p> while ( !Q.empty () && dist[d] == 0 )<br /> {<br /> int cur = Q.front (); Q.pop ();<br /> printf ( "%d/n", cur );<br /> for ( int i = 0; i < v; i ++ )<br /> {<br /> if ( a[cur][i] == 0 )<br /> continue;<br /> if ( dist[i] != 0 )<br /> continue;<br /> dist[i] = MIN ( dist[cur], a[cur][i] );<br /> prev[i] = cur;<br /> Q.push ( i );<br /> }<br /> }<br /> printf ( "/n%d/n", dist[d] );<br /> return dist[d];<br /> }<br /> public:<br /> int placeGuards(vector <string> cities, int k, vector <string> guards, vector <string> agencies)<br /> {<br /> int i, j, n = cities.size ();<br /> memset ( guard, 0, sizeof ( guard ) );<br /> memset ( agency, 0, sizeof ( agency ) );</p> <p> for ( i = 0; i < guards.size (); i ++ )<br /> {<br /> istringstream in ( guards[i] );<br /> int x;<br /> while ( in >> x )<br /> guard[i][x] = 1;<br /> }<br /> for ( i = 0; i < agencies.size (); i ++ )<br /> {<br /> istringstream in ( agencies[i] );<br /> int x;<br /> while ( in >> x )<br /> agency[i][x] = 1;<br /> }</p> <p> src = n, dst = n + 1;<br /> int flow = 0;<br /> int iter;<br /> for ( iter = 0; iter < n; iter ++ )<br /> {<br /> memset ( a, 0, sizeof ( a ) );<br /> for ( i = 0; i < n; i ++ )<br /> for ( j = 0; j < n; j ++ )<br /> if ( cities[i][j] == '1' )<br /> a[i][j] = 1;<br /> for ( i = 0; i < n; i ++ )<br /> if ( !agency[i][iter] )<br /> a[i][dst] = 10000;<br /> for ( i = 0; i < n; i ++ )<br /> if ( guard[i][iter] )<br /> a[src][i] = 10000;</p> <p> memset ( prev, 0xff, sizeof ( prev ) );<br /> for ( int f; f = fflow ( src, dst, n + 2 ) > 0; )<br /> {<br /> flow += f;<br /> for ( int b = dst; b != src; b = prev[b] )<br /> {<br /> a[prev[b]][b] -= f;<br /> a[b][prev[b]] += f;<br /> }<br /> }<br /> }<br /> return flow;<br /> }<br /> }

 改进版最大流模板，适用于稀疏矩阵：

namespace MF<br /> {<br /> const int MAXN = 10001;<br /> const int MAXM = 30001;<br /> const int INF = 1 << 20;<br /> vector < PII > e[MAXN];<br /> int flow[MAXM], dist[MAXN], prev[MAXN], edge[MAXN];<br /> int N;<br /> int len = 0;<br /> int src, dst;<br /> queue < int > Q;</p> <p> void clear ( int _N )<br /> {<br /> N = _N, len = 0;<br /> for ( int i = 0; i < N; i ++ )<br /> e[i].clear ();<br /> }<br /> void addEdge ( int i, int j, int c1, int c2 )<br /> {<br /> //printf ( "%d %d %d %d/n", i, j, c1, c2 );<br /> e[i].push_back ( MP ( j, len ) );<br /> flow[len ++] = c1;<br /> e[j].push_back ( MP ( i, len ) );<br /> flow[len ++] = c2;<br /> }<br /> int bfs ()<br /> {<br /> for ( int i = 0; i < N; i ++ )<br /> dist[i] = 0;<br /> dist[src] = INF; Q.push ( src );<br /> while ( !Q.empty () )<br /> {<br /> int cur = Q.front ();<br /> Q.pop ();<br /> for ( int i = 0; i < e[cur].size (); i ++ )<br /> {<br /> int v = e[cur][i].first, j = e[cur][i].second;<br /> if ( dist[v] || flow[j] == 0 )<br /> continue;<br /> dist[v] = min ( dist[cur], flow[j] );<br /> prev[v] = cur, edge[v] = j;<br /> Q.push ( v );<br /> }<br /> }<br /> return dist[dst];<br /> }<br /> int maxFlow ()<br /> {<br /> int ret = 0;<br /> for ( int f; ( f = bfs () ) > 0; )<br /> {<br /> ret += f;<br /> for ( int v = dst; v != src; v = prev[v] )<br /> {<br /> flow[edge[v]] -= f;<br /> int j = ( edge[v] & 1 ) ? edge[v] - 1 : edge[v] + 1;<br /> flow[j] += f;</p> <p> }<br /> }<br /> return ret;<br /> }<br /> }