[An interesting picture]Suicides

May 16, 2009 — gnarlycow
Suicides-An interesting picture

Suicides-An interesting picture

Posted in 生活瞬间. Tags: . 3 Comments »

POI 1998 Frogman, SPOJ 181 Scuba diver Summary

March 31, 2009 — gnarlycow

动态规划

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

?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

#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: , , . No Comments »

This Is My Life, Rated

March 27, 2009 — gnarlycow
This Is My Life, Rated
Life: 8
Mind: 7.9
Body: 8.2
Spirit: 8.2
Friends/Family: 6.3
Love: 3.6
Finance: 7.1
Take the Rate My Life Quiz
Posted in 生活瞬间. Tags: , . 2 Comments »

Shawn Xu 许烁…

March 19, 2009 — gnarlycow
你可知道我在facebook你的墙上写下了如下这段话
It all came as a stunning shock to me. You just passed away, leaving so many people and things behind. I’ve never expressed my appreciation of you, but now I want you to know, and I’m sure you will know, that I’ve always been thinking highly of you. There are many, as you surely know it, people who love you so much and you, in turn, love each and everyone of them. I don’t reckon I’m able to be counted as your close friend, but I can’t really express my grief in words. There are so many people who know and care more about you. Love has power beyond death. With so many love, yours as well as others, in your heart, you may smile at the other end of the world. From my point of view at the very least, you are Master of Death…

细细想来，虽然从初中我与你相识，但我们真正相处的时间实在是太短了。我清楚记得你穿着制服手拿照相机的身影，我清楚记得初三时我参加信息学奥赛吉林省队选拔赛时你在机房门外关切的问我成绩时的面庞，我清楚记得我存你手机号时你特意强调你名字中的“烁”不是硕大的“硕”…

可你分明是一个硕大的人，不仅是你的外表，你总是那样乐观积极，好像世界上没有什么事能够压倒你硕大的身躯…但是…我真的不知道该把你的悲剧归因于或者归咎于什么…

生命是如此脆弱，如此易逝。我们这些仍然可以享受生命的幸运的人真的应该放慢生活匆忙的脚步，时常停下来去闻路边玫瑰的花香，时常停下来去感受大家对自己的爱，时常停下来去把爱的种子播撒…

Posted in Uncategorized. Tags: , , . No Comments »

TopCoder SRM 429 Summary

March 13, 2009 — gnarlycow

SubrectanglesOfTable
简单统计题

?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

#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
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
50
51
52
53
54

#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
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
50
51

#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: , , . 1 Comment »

TopCoder SRM 431 Summary

March 9, 2009 — gnarlycow

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

?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

#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
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

#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: , , . 1 Comment »

TopCoder SRM 432 Summary

March 9, 2009 — gnarlycow

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

?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

#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: , . 1 Comment »

OI Summary Bird’s-eye View

March 8, 2009 — gnarlycow

TopCoder

SRM435 (完成度2/3，第三题待实现)

SRM433 (完成度2/3，第三题待实现)

SRM432 (完成度1/3，第二题待思考，第三题待实现)

SRM431 (完成度2/3，第三题待思考)

SRM429 (完成度3/3，DONE!)

USACO Contest

FEB09 Gold (完成度3/3，DONE!)

JAN09 Gold (完成度3/3，DONE!)

Posted in General. Tags: , . No Comments »

CQTSC2009 Summary

March 4, 2009 — gnarlycow

中位数(median)
简单统计题

?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

#include <cstdio>
 
const int BASE=100000;
int d[100001],f[100001],h[200002];
 
int main()
{
	freopen("median.in","r",stdin);
	freopen("median.out","w",stdout);
	int n,b,s;
	scanf("%d%d",&n,&b);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",d+i);
		if(d[i]==b) s=i;
	}
	h[BASE]=1;
	for(int i=s-1;i;--i)
	{
		if(d[i]>d[s]) f[i]=f[i+1]+1;
		else f[i]=f[i+1]-1;
		++h[BASE+f[i]];
	}
	int ans=h[BASE];
	for(int i=s+1;i<=n;++i)
	{
		if(d[i]>d[s]) f[i]=f[i-1]+1;
		else f[i]=f[i-1]-1;
		ans+=h[BASE-f[i]];
	}
	printf("%d\n",ans);
	return 0;
}

跳舞(dance)
二分答案+网络流
经典的拆点构图模型，这里不加说明地直接给出构图方法：将每个人都拆成两个点，分别表示喜欢和不喜欢。从源向每个男喜欢连一条边，容量为二分枚举的曲子数。每个男孩从喜欢向不喜欢连一条容量为k的边，每个女孩从不喜欢向喜欢连一条容量为k的边。从每个女喜欢向汇连一条为容量为二分枚举的曲子数的边。对于每对相互喜欢的男女，从男喜欢向女喜欢连一条为容量为1的边；对于相互不喜欢的男女，从男不喜欢向女不喜欢连一条为容量为1的边。如果最大流恰为此时枚举的曲子数的n倍则可行。

?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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

#include <iostream>
 
using namespace std;
 
const int MAXNODE=444,MAXEDGE=30000;
struct network
{
	int S,T,len;
	int v[MAXEDGE],capacity[MAXEDGE],flow[MAXEDGE],head[MAXNODE],next[MAXEDGE];
	void initialize();
	void insertEdge(int,int,int);
	bool makeLevelGraph();
	bool changeFlow(int,int);
	void makeMaxFlow();
	int getMaxFlow();
} g;
int q[MAXNODE],h[MAXNODE],cur[MAXNODE],mark[MAXNODE];
bool used[MAXNODE],flag[MAXNODE];
char fancy[55][55];
 
void network::initialize()
{
	len=0;
	memset(head,0,sizeof(head));
	memset(flow,0,sizeof(flow));
	next[0]=0;
}
 
void network::insertEdge(int a,int b,int c)
{
	len++;
	v[len]=b;
	capacity[len]=c;
	next[len]=head[a];
	head[a]=len;
	len++;
	v[len]=a;
	capacity[len]=0;
	next[len]=head[b];
	head[b]=len;
}
 
bool network::makeLevelGraph()
{
	memset(h,0,sizeof(h));
	memset(used,false,sizeof(used));
	used[S]=true;
	q[0]=S;
	for(int headQ=0,tailQ=1;headQ<tailQ;++headQ)
		for(int i=head[q[headQ]];i;i=next[i])
			if(capacity[i]>flow[i]&&!used[v[i]])
			{
				h[v[i]]=h[q[headQ]]+1;
				if(v[i]==T) return true;
				used[v[i]]=true;
				q[tailQ++]=v[i];
			}
	return false;
}
 
inline bool network::changeFlow(int k,int w)
{
	if(k&1) flow[k+1]-=w;
	else flow[k-1]-=w;
	return (flow[k]+=w)==capacity[k];
}
 
void network::makeMaxFlow()
{
	while(makeLevelGraph())
	{
		memcpy(cur,head,sizeof(head));
		memset(used,false,sizeof(used));
		q[0]=cur[S]+1;
		for(int num=0;!used[S];)
			if(v[q[num]]==T)
			{
				int delta=INT_MAX;
				for(int i=1;i<=num;i++) delta<?=capacity[q[i]]-flow[q[i]];
				for(int i=num;i;--i)
					if(changeFlow(q[i],delta))
						num=i-1;
			}
			else
			{
				int &i=cur[v[q[num]]];
				for(;i;i=next[i])
					if(!used[v[i]]&&h[v[i]]==h[v[q[num]]]+1&&capacity[i]>flow[i])
					{
						q[++num]=i;
						break;
					}
				if(!i) used[v[q[num--]]]=true;
			}
	}
}
 
int network::getMaxFlow()
{
	makeMaxFlow();
	int res=0;
	for(int i=head[S];i;i=next[i]) res+=flow[i];
	return res;
}
 
int main()
{
	freopen("dance.in","r",stdin);
	freopen("dance.out","w",stdout);
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i) scanf("\n%s",&fancy[i][1]);
	int L=0,R=n+1;
	while(L+1<R)
	{
		int M=(L+R)>>1;
		g.initialize();
		g.S=0;
		g.T=4*n+1;
		for(int i=1;i<=n;++i)
		{
			g.insertEdge(g.S,i,M);
			g.insertEdge(3*n+i,g.T,M);
			g.insertEdge(i,n+i,k);
			g.insertEdge(2*n+i,3*n+i,k);
		}
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				if(fancy[i][j]=='Y') g.insertEdge(i,3*n+j,1);
				else g.insertEdge(n+i,2*n+j,1);
		if(g.getMaxFlow()==M*n) L=M;
		else R=M;
	}
	printf("%d\n",L);
	return 0;
}
Posted in 省选. Tags: , , . No Comments »

USACO DEC08 Gold Summary

February 24, 2009 — gnarlycow

treat
不错的图论基础题。
本题中涉及到的图是一种特殊的有向图：每个结点都有且仅有一条出边。这样的有向图有一个很实用的性质：在每个连通分量中有且仅有一个环，而这个连通分量中的其它结点以树形连接到环上。对于环上的结点来说，题目要我们求的答案就是这个环的长度；而对于非环上的结点来说，答案就是它到环的距离再加上环的长度。这样，很容易想到一个线性算法解决问题。

?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

/*
ID: lipeiqi1
LANG: C++
PROB: treat
*/
#include <cstdio>
#include <cstring>
 
int next[100001],p[100001],ans[100001],mark[100001];
 
int main()
{
	freopen("treat.in","r",stdin);
	freopen("treat.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",next+i);
	for(int i=1;i<=n;++i)
		if(ans[i]==0)
		{
			int j=i,k=0;
			for(;ans[j]==0;j=next[j])
			{
				mark[j]=k;
				p[k++]=j;
				ans[j]=-1;
			}
			if(ans[j]==-1)
			{
				for(int v=k-1;v>=mark[j];--v) ans[p[v]]=k-mark[j];
				for(int v=mark[j]-1;v>=0;--v) ans[p[v]]=k-v;
			}
			else
				for(int v=k-1;v>=0;--v) ans[p[v]]=ans[j]+k-v;
		}
	for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
	return 0;
}

sec
字符串处理
输入数据给我们两组字符串A和B，我们只要先对A组中的字符串进行适当的预处理，就能快速找出B组中每一个字符串与A中多少个字符串相匹配。对于B组中每一个字符串s来说，我们需要知道A组中有多少个字符串是s的前缀和A组中有多少个字符串以s为前缀，一般情况下这两者之和即为所求结果。有一种特殊情况是A中有与s完全相同的字符串，这时注意不要重复计数。容易想到利用Trie树这种数据结构来解决问题，字典树可以很方便提供我们所需要的功能。

?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
50
51
52
53

/*
ID: lipeiqi1
LANG: C++
PROB: sec
*/
#include <cstdio>
 
struct node
{
	int end,part;
	node *c[2];
	node():end(0),part(0)
	{
		c[0]=c[1]=NULL;
	}
} *root=new node();
 
int main()
{
	freopen("sec.in","r",stdin);
	freopen("sec.out","w",stdout);
	int m,n,k,v;
	scanf("%d %d",&m,&n);
	for(int i=0;i<m;++i)
	{
		node *t=root;
		for(scanf("%d",&k);k;--k)
		{
			scanf("%d",&v);
			if(!t->c[v]) t->c[v]=new node();
			t=t->c[v];
			++t->part;
		}
		++t->end;
	}
	for(int i=0;i<n;++i)
	{
		node *t=root;
		int ans=0;
		for(scanf("%d",&k);k;--k)
		{
			scanf("%d",&v);
			if(t)
			{
				ans+=t->end;
				t=t->c[v];
			}
		}
		if(t) ans+=t->part;
		printf("%d\n",ans);
	}
	return 0;
}
Posted in Gold Division, USACO. Tags: , , . No Comments »
« Older posts
Newer posts »