» Summary Gnarly Cow

March 2010
M	T	W	T	F	S	S
« Jan
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

USACO OPEN09 Gold Summary

May 27, 2009 — gnarlycow

Ski Lessons

动态规划

f[i][j]表示时刻i时滑雪能力为j的前提下，前i个时间单位里最多能滑多少次雪。我们采用向后递推法转移，有三种选择：(1)喝汽水；(2)参加时刻i开始的课程，能力值改变；(3)在能滑的雪坡中选择一个滑。

现在障碍在于雪坡数太多，每次都尝试所有能滑的雪坡转移代价太高。实际上我们并不需要尝试所有能滑的雪坡，因为滑雪用的时间越短越好，而滑任何雪坡效果都是一样的，能滑的雪坡之间没有优劣之分，所以要选择能滑的雪坡中用时最短的那个。通过预处理，可以在常数时间内获取这个信息。

^?View Code CPP

/*
ID: lipeiqi1
LANG: C++
PROB: ski
*/
#include <iostream>
 
using namespace std;
 
struct tlesson
{
    int start,length,ability;
} lesson[10001];
int prev[101][101],mintime[101],f[10001][101];
 
bool operator<(const tlesson &a,const tlesson &b)
{
    return a.start<b.start;
}
 
void update(int &u,int v)
{
    if(u<v) u=v;
}
 
int main()
{
    freopen("ski.in","r",stdin);
    freopen("ski.out","w",stdout);
    int t,s,n,require,length;
    scanf("%d%d%d",&t,&s,&n);
    for(int i=0;i<s;++i) scanf("%d%d%d",&lesson[i].start,&lesson[i].length,&lesson[i].ability);
    sort(lesson,lesson+s);
    for(int i=1;i<101;++i) mintime[i]=INT_MAX;
    for(int i=0;i<n;++i)
    {
        scanf("%d%d",&require,&length);
        for(int j=require;j<101;++j) mintime[j]=min(mintime[j],length);
    }
    memset(f,-1,sizeof(f));
    f[0][1]=0;
    int cur=0,ans=-1;
    for(int i=0;i<=t;++i)
    {
        while(cur<s&&lesson[cur].start<i) ++cur;
        for(int j=1;j<101;++j)
            if(f[i][j]>-1)
            {
                update(ans,f[i][j]);
                if(i<t) update(f[i+1][j],f[i][j]);
                if(cur<s&&lesson[cur].start==i&&i+lesson[cur].length<=t) update(f[i+lesson[cur].length][lesson[cur].ability],f[i][j]);
                if(mintime[j]<INT_MAX&&i+mintime[j]<=t) update(f[i+mintime[j]][j],f[i][j]+1);
            }
    }
    printf("%d\n",ans);
    return 0;
}

Posted in Gold Division, USACO. Tags: DP, Summary, USACO. No Comments »

POI 2000 Skiers

May 19, 2009 — gnarlycow

贪心策略、深度优先搜索

网络流模型理论上可以解决此题，把除1和n以外的每个结点都拆成两个结点，中间用一条容量为1的边连接，结点1为源，结点n为汇求最大流。无奈本题数据规模较大，最多有5000个结点，而且边数未知。

注意到题目给出的图具有特殊的性质：边是按从东到西的顺序给出的，而且所有边不相交。这样我们可以采取如下贪心策略：用深度优先搜索从结点1出发找一条尽可能靠东（或尽可能靠西）的路径，让一个运动员沿此路径滑雪，把此路径上的除起点和终点外的所有结点从图中删去，然后重复此过程。这个策略显然正确，由于所有边都不相交，每次找最靠东（或最靠西）的路径可以给后面要找的路径腾出最大的空间。

^?View Code CPP

#include <iostream>
 
using namespace std;
 
struct edge
{
	int v;
	edge *next;
	edge(int v,edge *next):v(v),next(next) {}
} *e[5005];
int n;
bool u[5005];
 
bool dfs(int v)
{
	if(v==n) return true;
	u[v]=true;
	for(edge *t=e[v];t;t=t->next)
		if(!u[t->v]&&dfs(t->v))
			return true;
	return false;
}
 
int main()
{
	freopen("nar.in","r",stdin);
	freopen("nar.out","w",stdout);
	scanf("%d",&n);
	int t,v,ans=0;
	for(int i=1;i<n;++i)
		for(scanf("%d",&t);t;--t)
		{
			scanf("%d",&v);
			e[i]=new edge(v,e[i]);
		}
	for(edge *p=e[1];p;p=p->next)
		if(!u[p->v]&&dfs(p->v))
			++ans;
	printf("%d\n",ans);
	return 0;
}

Posted in POI. Tags: POI, Summary. No Comments »

注意到边界上的格子一定不能存水，否则会流到外面去。现在考虑与边界相邻的格子。注满水后，对于某个与边界相邻的格子来水，它的积水状态只与它自己的恶高度和相邻边界格子的最低高度有关。这样，我们可以取边界格子中高度最低的格子，然后来得到与之相邻的内部格子的水位。假设边界格子中高度最低的为格子(x,y)，那么对于(x,y)的任意一个相邻非边界格子(x’,y’)来说，只要 $h(x,y)>h(x’,y’)” />，格子(x’,y’)就会有高度为<img src=$ 的积水，这时我们可以把 $h(x,y)-h(x',y')$ 累加到答案中去，然后把 $h(x',y')$ 赋为 $h(x,y)$ 并把(x’,y’)看作边界格子。如果 $h(x,y)<=h(x',y')$ ，我们可以直接把(x’,y’)看作边界格子。当处理完所有(x,y)的相邻非边界格子后，把(x,y)从边界格子中删去。重复这个过程，直至边界格子集合为空为止。显然，用一个小根堆来维护边界格子集合是在适合不过了。

^?View Code CPP

#include <iostream>
 
using namespace std;
 
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
bool u[111][111];
int ans,heapsize,h[111][111];
struct node
{
	int x,y,v;
} heap[11111];
 
void insert(int x,int y,int v)
{
	node key={x,y,v};
	int p=++heapsize;
	while(p>1&&heap[p>>1].v>v)
	{
		heap[p]=heap[p>>1];
		p>>=1;
	}
	heap[p]=key;
}
 
void deleteMin()
{
	int p=1;
	while((p<<1)<heapsize)
	{
		int i=p<<1;
		if(i+1<heapsize&&heap[i+1].v<heap[i].v) ++i;
		if(heap[i].v<heap[heapsize].v)
		{
			heap[p]=heap[i];
			p=i;
		}
		else break;
	}
	heap[p]=heap[heapsize--];
}
 
int main()
{
	freopen("wod.in","r",stdin);
	freopen("wod.out","w",stdout);
	int r,c;
	scanf("%d%d",&r,&c);
	for(int i=0;i<r;++i)
		for(int j=0;j<c;++j)
			scanf("%d",&h[i][j]);
	for(int i=0;i<c;++i)
	{
		u[0][i]=u[r-1][i]=true;
		insert(0,i,h[0][i]);
		insert(r-1,i,h[r-1][i]);
	}
	for(int i=1;i+1<r;++i)
	{
		u[i][0]=u[i][c-1]=true;
		insert(i,0,h[i][0]);
		insert(i,c-1,h[i][c-1]);
	}
	while(heapsize)
	{
		int x=heap[1].x,y=heap[1].y;
		deleteMin();
		for(int i=0;i<4;++i)
		{
			int tx=x+dx[i],ty=y+dy[i];
			if(tx>-1&&tx<r&&ty>-1&&ty<c&&!u[tx][ty])
			{
				u[tx][ty]=true;
				if(h[tx][ty]<h[x][y])
				{
					ans+=h[x][y]-h[tx][ty];
					h[tx][ty]=h[x][y];
				}
				insert(tx,ty,h[tx][ty]);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

Posted in POI. Tags: POI, Summary. No Comments »

POI 2003 Monkeys

May 18, 2009 — gnarlycow

并查集

这是一道很棒的并查集类问题，具有较高的思维难度。注意到题目中所描述的猴子的连接方式，有可能猴子a抓住猴子b的尾巴，也有可能b抓住a的尾巴，也有可能a和b互相抓住对方的尾巴。其实我们只关心两个猴子是否相连，以上三种情况都是猴子a和b相连。现在题目要求的就是每只猴子第一次直接或间接脱离猴子1的时间。看起来好像和并查集的操作是相反的，那我们就反过来求解。首先求出时刻m所有放手行为都执行后猴子们的连接情况，然后从时刻m往前反过来执行“抓尾巴”行为，这样问题转化为求每个猴子第一次直接或间接与猴子1相连的时刻。这正是并查集所支持的操作，只是每次将猴子1所在集合与其它集合合并时，需要把那个集合的所有猴子的答案都设置为这个时刻。我们可以另外对每个集合维护一个链表，包含这个集合的所有猴子，合并时将链表合并。这样总的时间复杂度不变，问题成功解决。

^?View Code CPP

#include <iostream>
 
using namespace std;
 
struct node
{
	int v;
	node *next;
	node(int v,node *next):v(v),next(next) {}
} *first[200002],*last[200002];
int d[400004][2],holdOrig[200002][2],holdCur[200002][2],ans[200002],f[200002];
 
int getRoot(int v)
{
	if(f[v]==v) return v;
	else return f[v]=getRoot(f[v]);
}
 
void unite(int a,int b)
{
	int x=getRoot(a),y=getRoot(b);
	if(x!=y)
	{
		f[x]=y;
		last[y]->next=first[x];
		last[y]=last[x];
	}
}
 
void uniteAndUpdateAns(int a,int b,int moment)
{
	int x=getRoot(a),y=getRoot(b);
	if(x!=y)
	{
		if(x==getRoot(1))
			for(node *t=first[y];t;t=t->next)
				ans[t->v]=moment;
		else if(y==getRoot(1))
			for(node *t=first[x];t;t=t->next)
				ans[t->v]=moment;
		f[x]=y;
		last[y]->next=first[x];
		last[y]=last[x];
	}
}
 
int main()
{
	int n,m;
	memset(ans,-1,sizeof(ans));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&holdOrig[i][0],&holdOrig[i][1]);
		holdCur[i][0]=holdOrig[i][0];
		holdCur[i][1]=holdOrig[i][1];
	}
	for(int i=0;i<m;++i)
	{
		scanf("%d%d",&d[i][0],&d[i][1]);
		--d[i][1];
		holdCur[d[i][0]][d[i][1]]=-1;
	}
	for(int i=1;i<=n;++i)
	{
		f[i]=i;
		first[i]=last[i]=new node(i,NULL);
	}
	for(int i=1;i<=n;++i)
	{
		if(holdCur[i][0]>-1) unite(i,holdCur[i][0]);
		if(holdCur[i][1]>-1) unite(i,holdCur[i][1]);
	}
	for(int i=m-1;i>-1;--i)
		if(holdOrig[d[i][0]][d[i][1]]>-1)
			uniteAndUpdateAns(d[i][0],holdOrig[d[i][0]][d[i][1]],i);
	for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
	return 0;
}

Posted in POI. Tags: POI, Summary. No Comments »

POI 1998 Word Equations

May 17, 2009 — gnarlycow

并查集

本题中不同的变量可以表示不同长度的01串，这给解题带来了麻烦。我们可以把所有长度为p的变量拆成p个长度为1的变量，以简化问题。这样，所有拆分后得到的变量都只能表示一个0或1。假设等号两边的长度都为L，如果把0和1本身也看成特殊的变量的话，等式告诉我们的就是L个相等关系，即某两个变量相等。用并查集维护这些相等关系：初始时每个变量自成一个集合，每遇到一个相等关系，把相等的变量所在集合合并。如果某一时刻0和1所在的集合被合并，则说明出现矛盾，输出0；否则，没有矛盾出现，假设最终除0和1所在集合外共有r个集合，则答案为 $2^{r}$ 。

注意测试数据中存在展开后等式两边长度不等的情况。

^?View Code CPP

#include <iostream>
 
using namespace std;
 
char s1[10011],s2[10011];
int total,len[33],s[10011],f[10011],size[10011],ans[11111111];
 
int getRoot(int v)
{
	if(f[v]==v) return v;
	else return f[v]=getRoot(f[v]);
}
 
void unite(int a,int b)
{
	int x=getRoot(a),y=getRoot(b);
	if(x!=y)
	{
		if(size[x]<size[y])
		{
			size[x]+=size[y];
			f[y]=x;
		}
		else
		{
			size[y]+=size[x];
			f[x]=y;
		}
		--total;
	}
}
 
int main()
{
	freopen("row.in","r",stdin);
	freopen("row.out","w",stdout);
	int T;
	for(scanf("%d",&T);T;--T)
	{
		int num,l1,l2;
		scanf("%d",&num);
		for(int i=0;i<num;++i) scanf("%d",len+i);
		scanf("%d\n%s\n%d\n%s",&l1,s1,&l2,s2);
		for(int i=1;i<num;++i) len[i]+=len[i-1];
		for(int i=num;i>0;--i) len[i]=len[i-1]+2;
		len[0]=2;
		int top=0;
		for(int i=0;i<l1;++i)
			if(s1[i]>='a'&&s1[i]<='z')
				for(int j=len[s1[i]-'a'];j<len[s1[i]-'a'+1];++j)
					s[top++]=j;
			else s[top++]=s1[i]-'0';
		for(int i=0;i<10005;++i) f[i]=i,size[i]=1;
		int firstTop=top;
		top=0;
		total=len[num]-2;
		for(int i=0;i<l2;++i)
		{
			if(s2[i]>='a'&&s2[i]<='z')
				for(int j=len[s2[i]-'a'];j<len[s2[i]-'a'+1];++j)
					unite(s[top++],j);
			else unite(s[top++],s2[i]-'0');
		}
		if(getRoot(0)==getRoot(1)||top!=firstTop) puts("0");
		else
		{
			memset(ans,0,sizeof(ans));
			int m=1;
			ans[0]=1;
			for(;total;--total)
			{
				int x=0;
				for(int i=0;i<m;++i)
				{
					ans[i]=(ans[i]<<1)+x;
					if(ans[i]>9) x=1,ans[i]-=10;
					else x=0;
				}
				if(x) ans[m++]=1;
			}
			for(int i=m-1;i>=0;--i) putchar('0'+ans[i]);
			putchar('\n');
		}
	}
	return 0;
}

Posted in POI. Tags: POI, Summary. No Comments »

POI 1999 Three-coloring of Binary Trees

May 17, 2009 — gnarlycow

树型动态规划

首先根据给出的先序遍历序列建树，然后用两遍树型动态规划求出最大和最小值。假设绿色用0表示，1、2表示另外两种颜色。 $fmax(v,c)$ 表示以v为根的子树中根结点v的颜色为c时的绿色结点数最大值。当v为叶结点时， $fmax(v,0)=1$ 而 $fmax(v,1)=fmax(v,2)=0$ ；当v为非叶结点时，我们要给v的孩子结点分配不同于c的颜色，并在所有方案中去最大值，还有不要忘记当c为0时把根结点v自己加进去。求最小值与之类似，只要把所有的max都变为min即可。

^?View Code CPP

#include <iostream>
 
using namespace std;
 
int m,p,num[10011],cleft[10011],cright[10011],f[10011][3];
char s[10011];
 
int max(int a,int b,int c)
{
	return max(max(a,b),c);
}
 
int min(int a,int b,int c)
{
	return min(min(a,b),c);
}
 
void buildTree()
{
	num[m]=s[p++]-'0';
	if(num[m]==1)
	{
		cleft[m]=m+1;
		cright[m]=-1;
		++m;
		buildTree();
		return;
	}
	if(num[m]==2)
	{
		int t=m;
		cleft[t]=m+1;
		++m;
		buildTree();
		cright[t]=m;
		buildTree();
		return;
	}
	if(num[m]==0) cleft[m]=cright[m++]=-1;
}
 
int getMax(int v,int c)
{
	if(f[v][c]>-1) return f[v][c];
	int r=(c==0);
	if(num[v]==1) r+=max(getMax(cleft[v],(c+1)%3),getMax(cleft[v],(c+2)%3));
	else if(num[v]==2) r+=max(getMax(cleft[v],(c+1)%3)+getMax(cright[v],(c+2)%3),getMax(cleft[v],(c+2)%3)+getMax(cright[v],(c+1)%3));
	return f[v][c]=r;
}
 
int getMin(int v,int c)
{
	if(f[v][c]>-1) return f[v][c];
	int r=(c==0);
	if(num[v]==1) r+=min(getMin(cleft[v],(c+1)%3),getMin(cleft[v],(c+2)%3));
	else if(num[v]==2) r+=min(getMin(cleft[v],(c+1)%3)+getMin(cright[v],(c+2)%3),getMin(cleft[v],(c+2)%3)+getMin(cright[v],(c+1)%3));
	return f[v][c]=r;
}
 
int main()
{
	freopen("trot.in","r",stdin);
	freopen("trot.out","w",stdout);
	gets(s);
	buildTree();
	memset(f,-1,sizeof(f));
	printf("%d ",max(getMax(0,0),getMax(0,1),getMax(0,2)));
	memset(f,-1,sizeof(f));
	printf("%d\n",min(getMin(0,0),getMin(0,1),getMin(0,2)));
	return 0;
}

Posted in POI. Tags: DP, POI, Summary. No Comments »

POI 1998 Frogman, SPOJ 181 Scuba diver Summary

March 31, 2009 — gnarlycow

动态规划

本题中的物品涉及两个价值，属于背包问题的简单变形，氧气和氮气各占一维即可。和普通的一维背包问题一样，这里可以通过调整状态转移的顺序来实现空间降维。

^?View Code CPP

#include <cstdio>
#include <cstring>
 
int f[80][80];
 
int main()
{
    int m,n,a,b,w,num,T;
    for(scanf("%d",&T);T;--T)
    {
        memset(f,-1,sizeof(f));
        f[0][0]=0;
        scanf("%d%d%d",&m,&n,&num);
        for(int k=0;k<num;++k)
        {
            scanf("%d%d%d",&a,&b,&w);
            for(int i=79;i>=a;--i)
                for(int j=79;j>=b;--j)
                    if(f[i-a][j-b]>-1&&(f[i][j]==-1||f[i][j]>f[i-a][j-b]+w))
                        f[i][j]=f[i-a][j-b]+w;
        }
        int ans=-1;
        for(int i=m;i<80;++i)
            for(int j=n;j<80;++j)
                if(f[i][j]>-1&&(ans==-1||ans>f[i][j]))
                    ans=f[i][j];
        printf("%d\n",ans);
    }
    return 0;
}

Posted in SPOJ. Tags: POI, SPOJ, Summary. No Comments »

TopCoder SRM 429 Summary

March 13, 2009 — gnarlycow

SubrectanglesOfTable
简单统计题

^?View Code CPP

#include <cmath>
#include <ctime>
#include <iostream>
#include <sstream>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
class SubrectanglesOfTable
{
public:
	vector<long long> getQuantity(vector <string> table)
	{
		vector <long long> r(26);
		int m=table.size();
		for(int i=0;i<m;++i)
		{
			table[i]+=table[i];
			table.push_back(table[i]);
		}
		m<<=1;
		int n=table[0].size();
		for(long long i=0;i<m;++i)
			for(long long j=0;j<n;++j)
				r[table[i][j]-'A']+=(i+1)*(j+1)*(m-i)*(n-j);
		return r;
	}
};

IngredientProportions
构造
随便给某个原料（比如原料0）设定一个质量值，由于题目保证有唯一解，通过给出的比例关系一定可以求出其它所有原料的质量，最后将所有原料的质量统一放大或缩小到最简整数比即可得到正确解。为避免分数运算，我们可以给原料0分配一个恰当的整数质量使得以后的运算中不出现分数。先运用类似Floyd的方法求出原料0与其它所有原料的直接比例，求完后假设原料0与任意原料k的质量比为A[k]:B[k]，那么为使求得的原料k的质量为整数，原料0的质量必须为A[k]的倍数，因此我们应该给原料0分配A[1..N-1]所有数的最小公倍数这么大的质量。这样，我们得到了所有原料的整数质量，最后求出它们的最大公约数而后化为最简比。

^?View Code CPP

#include <cmath>
#include <ctime>
#include <iostream>
#include <sstream>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
int p[11][11][2];
long long f[11];
 
long long gcd(long long a,long long b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}
 
class IngredientProportions
{
public:
	vector <int> getMasses(vector <string> d)
	{
		memset(p,0,sizeof(p));
		int n=d.size()+1;
		for(int i=0;i<d.size();++i)
		{
			int a=d[i][1]-'0',b=d[i][8]-'0',r=d[i][13]-'0',s=d[i][15]-'0';
			p[a][b][0]=r;
			p[a][b][1]=s;
			p[b][a][0]=s;
			p[b][a][1]=r;
		}
		for(int k=0;k<n;++k)
			for(int i=0;i<n;++i)
				if(p[i][k][0])
					for(int j=0;j<n;++j)
						if(p[k][j][0]&&!(p[i][j][0]))
						{
							p[i][j][0]=p[i][k][0]*p[k][j][0];
							p[i][j][1]=p[i][k][1]*p[k][j][1];
						}
		f[0]=1;
		for(int i=1;i<n;++i) f[0]=f[0]/gcd(f[0],p[0][i][0])*p[0][i][0];
		for(int i=1;i<n;++i) f[i]=f[0]/p[0][i][0]*p[0][i][1];
		long long g=f[0];
		for(int i=1;i<n;++i) g=gcd(g,f[i]);
		vector <int> r;
		for(int i=0;i<n;++i) r.push_back(f[i]/g);
		return r;
	}
};

SpecificPolyominoCovering
构造
本题的难点在于如何快速判断一个棋盘能否用给定的两种棋子填满。
注意到所有的AB嵌套棋子
ABBA
AAAA
都可以用4个B型棋子
BBBB
BBBB
替换，所以在判定时我们可以禁止AB嵌套棋子，而不失正确性。这样我们可以从上到下，从左到右扫描棋盘，每次遇到空缺先尝试B棋子再尝试A棋子，如果都不成功则判定失败，否则继续判定。（详细的正确性证明请参考官方题解）
注意到我们的判定过程实际上构造了一组解，但题目要求我们返回字典序最小的解。我们可以多次利用上述判定过程，仍然从上到下，从左到右扫描棋盘，每次遇到空缺先尝试A棋子，如果可以成功放进去A棋子并且调用上述过程判定剩下的棋盘可以填满棋子，那么就把A棋子真正放到棋盘上，否则就放B棋子，这样可以正确得出字典序最小的解。

^?View Code CPP

#include <cmath>
#include <ctime>
#include <iostream>
#include <sstream>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
int r,c;
bool u[55][55];
 
bool able(const vector <string> &g)
{
	memset(u,false,sizeof(u));
	for(int i=0;i<r;++i)
		for(int j=0;j<c;++j)
			if(g[i][j]=='X'&&!u[i][j])
			{
				if(j+1<c&&g[i][j+1]=='X') u[i][j+1]=true;
				else if(i+1<r&&j+3<c&&g[i][j+3]=='X'&&g[i+1][j]=='X'&&g[i+1][j+1]=='X'&&g[i+1][j+2]=='X'&&g[i+1][j+3]=='X') u[i][j+3]=u[i+1][j]=u[i+1][j+1]=u[i+1][j+2]=u[i+1][j+3]=true;
				else return false;
			}
	return true;
}
 
class SpecificPolyominoCovering
{
public:
	vector <string> findCovering(vector <string> g)
	{
		r=g.size();
		c=g[0].size();
		if(!able(g)) return vector <string>();
		for(int i=0;i<r;++i)
			for(int j=0;j<c;++j)
				if(g[i][j]=='X')
				{
					if(i+1<r&&j+3<c&&g[i][j+3]=='X'&&g[i+1][j]=='X'&&g[i+1][j+1]=='X'&&g[i+1][j+2]=='X'&&g[i+1][j+3]=='X')
					{
						g[i][j]=g[i][j+3]=g[i+1][j]=g[i+1][j+1]=g[i+1][j+2]=g[i+1][j+3]='A';
						if(able(g)) continue;
						else g[i][j]=g[i][j+3]=g[i+1][j]=g[i+1][j+1]=g[i+1][j+2]=g[i+1][j+3]='X';
					}
					g[i][j]=g[i][j+1]='B';
				}
		return g;
	}
};

Posted in SRM, TopCoder. Tags: SRM, Summary, TopCoder. 1 Comment »

TopCoder SRM 431 Summary

March 9, 2009 — gnarlycow

LaserShooting
简单概率题
显然本题中target并不阻挡射线，所以各个targe之间互不影响，那么射中个数的数学期望值就是射中各个targe的概率和。值得注意的是C++中求反正切arctan时最好用atan2(y,x)函数，因为它不仅能处理斜率不存在的情况还能正确处理角度符号。

^?View Code CPP

#include <cmath>
#include <ctime>
#include <iostream>
#include <sstream>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
const double PI=3.1415926535;
 
class LaserShooting
{
public:
	double numberOfHits(vector <int> x, vector <int> y1, vector <int> y2)
	{
		int n=x.size();
		for(int i=0;i<n;++i)
			if(y1[i]>y2[i])
				swap(y1[i],y2[i]);
		double ans=0;
		for(int i=0;i<n;++i) ans+=(atan2(y2[i],x[i])-atan2(y1[i],x[i]))/PI;
		return ans;
	}
};

MegaCoolNumbers
动态规划首先挖掘一下cool number of power A这个定义的本质：一个N位数如果是cool number of power A（A9时直接返回0，下面我们考虑A<=9的情况。采用动态规划，f[n][i][last][diff]表示所有n位数中最小power值为i且最后一个数字为last且最后一段的公差为diff的mega cool numbers个数（其中0<=diff<=8，用diff=9表示最后一组仅包含last这一个数字的情况，表示此时公差不确定），按照题意容易想出状态转移方法，这里不赘述。

^?View Code CPP

#include <cmath>
#include <ctime>
#include <iostream>
#include <sstream>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
const int MOD=1000000007;
int f[1001][10][10][10];
 
class MegaCoolNumbers
{
public:
	int count(int n,int A)
	{
		if(A>9) return 0;
		memset(f,0,sizeof(f));
		for(int i=1;i<10;++i) f[1][1][i][9]=1;
		for(int i=2;i<=n;++i)
			for(int j=1;j<10;++j)
				for(int last=1;last<10;++last)
				{
					for(int diff=0;diff<last;++diff) f[i][j][last][diff]=(f[i-1][j][last-diff][diff]+f[i-1][j][last-diff][9])%MOD;
					for(int prev=1;prev<=last;++prev)
						for(int diff=0;diff<9;++diff)
							if(diff!=last-prev)
								f[i][j][last][9]=(f[i][j][last][9]+f[i-1][j-1][prev][diff])%MOD;
				}
		int ans=0;
		for(int i=1;i<10;++i)
			for(int j=0;j<10;++j)
				ans=(ans+f[n][A][i][j])%MOD;
		return ans;
	}
};

Posted in SRM, TopCoder. Tags: SRM, Summary, TopCoder. 1 Comment »

TopCoder SRM 432 Summary

March 9, 2009 — gnarlycow

LampsGrid
枚举(思维难度大)
每次操作改变一整列的状态，所以如果初始时某两行状态相同，那么经过任意次操作后这两行的状态仍然相同；如果初始时某两行状态不相同，那么经过任意次操作后这两行的状态仍然不相同。枚举每一行，考虑能否把它通过K次操作变为全亮，如果能的话再数一数有多少行和这一行初始状态相同，它们也能通过同样的K次操作变为全亮。找出能变为全亮的且与之状态相同的行数最多的行即可。

^?View Code CPP

#include <cmath>
#include <ctime>
#include <iostream>
#include <sstream>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
class LampsGrid
{
public:
	int mostLit(vector <string> initial, int K)
	{
		int ans=0;
		for(int i=0;i<initial.size();++i)
		{
			int num=0;
			for(int j=0;j<initial[i].size();++j) num+=initial[i][j]=='0';
			if(num>K||(K-num)%2) continue;
			num=0;
			for(int j=0;j<initial.size();++j) num+=initial[i]==initial[j];
			ans=max(ans,num);
		}
		return ans;
	}
};

Posted in SRM, TopCoder, Uncategorized. Tags: Summary, TopCoder. 1 Comment »

« Older posts

Gnarly Cow We are continually faced with a series of great opportunities brilliantly disguised as insoluble problems.

Meta

Recent Posts

Spam Blocked

USACO OPEN09 Gold Summary

POI 2000 Skiers

POI 1999 Water

POI 2003 Monkeys

POI 1998 Word Equations

POI 1999 Three-coloring of Binary Trees

POI 1998 Frogman, SPOJ 181 Scuba diver Summary

TopCoder SRM 429 Summary

TopCoder SRM 431 Summary

TopCoder SRM 432 Summary

Tag Explosion

Best Friends

Recent Comments

Categories

Archives