TopCoder SRM433 Summary

February 11, 2009 — gnarlycow

MagicWords
枚举+优化
如果直接枚举全排列，然后朴素判断拼接成的字符串是不是magicword会超时。如何优化呢？不难证明如下定理：如果一个长度为L的字符串s为magicword，那么s一定为K个相同子串拼接而成，并且s不能分割成i(i>K)个相同子串。这样，判断s是否为magicword时，我们需要先判断s是否由K个相同子串拼接而成。如果是，就枚举L的大于K的约数i，依次判断s是否由i个相同子串拼接而成，如果都不是，则s为magicword。L的约数个数大约为sqrt(n)个，时间复杂度约为O(n!*L*sqrt(L))。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int g[111];
 
class MagicWords
{
public:
    int count(vector <string> S, int K)
    {
		int ans=0,n=S.size(),L=0,d[11];
		for(int i=0;i<n;++i) d[i]=i,L+=S[i].size();
		if(L%K) return 0;
		int len=0;
		for(int i=L;i>=K;--i)
			if(L%i==0)
				g[len++]=L/i;
		do
		{
			string s="";
			for(int i=0;i<n;++i) s+=S[d[i]];
			int i,j;
			for(i=0;i<len;++i)
			{
				for(j=g[i];j<L;++j)
					if(s[j]!=s[j%g[i]])
						break;
				if(j==L) break;
			}
			if(i==len-1) ++ans;
		} while(next_permutation(d,d+n));
		return ans;
    }
};

SettingTents
枚举+优化
本题解法分为两步：1、枚举出所有菱形的形状，确保不重不漏；2、对于每种形状的菱形，算出有多少个位置可以将其放进网格中。为枚举菱形的形状，我们先确定一个顶点，比如菱形最左边的顶点（如果菱形的左边是一条竖直的边就取下边的那个顶点），以它为原点(0,0)，从这里开始引边。如果我们枚举到两条边对应的顶点分别为(x1,y1)和(x2,y2)，则第四个顶点坐标为(x1+x2,y1+y2)。直接枚举会超时，但是注意到x1*x1+y1*y1==x2*x2+y2*y2，所以我们可以先将边长相同的所有(x,y)预处理到一个表中，这样计算时直接提取边长相同的边可以大大加快速度。最后，如果已确定菱形形状，找出这个菱形的“横平竖直”的外接矩形，设这个外接矩形长W宽H，则放置方案数为(N-W+1)*(M-H+1)。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int min(int a,int b,int c,int d)
{
	return min(min(min(a,b),c),d);
}
 
int max(int a,int b,int c,int d)
{
	return max(max(max(a,b),c),d);
}
 
class SettingTents
{
public:
	int countSites(int r,int c)
	{
		int ans=0;
		map <int,vector<pair<int,int> > > h; 
		for(int i=0;i<=r;++i)
			for(int j=-c;j<=c;++j)
				if(!(i==0&&j<=0))
					h[i*i+j*j].push_back(make_pair(i,j));
		for(int L=1;L<=r*r+c*c;++L)
			for(int i=0;i<h[L].size();++i)
				for(int j=i+1;j<h[L].size();++j)
				{
					int minx=min(0,h[L][i].first,h[L][j].first,h[L][i].first+h[L][j].first);
					int maxx=max(0,h[L][i].first,h[L][j].first,h[L][i].first+h[L][j].first);
					int miny=min(0,h[L][i].second,h[L][j].second,h[L][i].second+h[L][j].second);
					int maxy=max(0,h[L][i].second,h[L][j].second,h[L][i].second+h[L][j].second);
					int x=maxx-minx,y=maxy-miny;
					if(x>r||y>c) continue;
					ans+=(r-x+1)*(c-y+1);
				}
		return ans;
    }
};

BarbarianInvasion
网络流
将入侵部队看成源，首都看成汇，其它方格看成中间结点，相邻方格对应的结点间连边，这样构造出了一个网络。注意到本题的限制条件不在边上而在方格（也就是结点）上，用拆点解决这个问题，即将所有结点拆成两个结点并在其间连一条边，容量限制为破坏这个方格的花费，所有原来的边的容量都设为无穷大。我们希望删除尽可能少的容量小的边使得源到汇不连通，容易联想到最小割。这个网络的最小割能保证所有删除的边容量和最小，但是本题要求删除的边数最小，其次容量和最小，因此我们需要改造网络使得多删除一条边的代价很高：将所有方格的花费都加上一个非常大的整数即可。

Posted in SRM, TopCoder. Tags: , , . No Comments »
«
»