wspl09876

hyc

齐河一中蒟蒻一只

• 于  2016~2017  阅读 

day4

alien
飞船降落问题
矩阵前缀和+枚举
求出前缀和，暴力枚举每一个子矩阵的和，是0就可以降落
注意有正方形飞船，长度不等于点

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
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define D "%d"
#define for(i,x,y) for(int i=x;i<=y;i++)
#define prf printf
#define scf scanf
int n,m,r,c,ans;
int a[1999][1999],s[1999][1999];
int main()
{
	freopen("alien.in","r",stdin);
	freopen("alien.out","w",stdout);
	scf(D D D D,&n,&m,&r,&c);
	for(i,1,r)
	{
		int x,y;
		scf(D D,&x,&y);
		a[x][y]=1;
	}
	for(i,1,n)
	 for(j,1,m)	
	 	s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
	for(k,1,c)
	{
		int x,y;
		ans=0;
		scf(D D,&x,&y);
		for(i,1,n)
	     for(j,1,m)
	    if(i+x-1<=n&&j+y-1<=m)
	 	{
	 		int w=s[i+x-1][j+y-1]-s[i-1][j+y-1]-s[i+x-1][j-1]+s[i-1][j-1];
	 		if(w==0)
	 		ans++;
	 	}
		if(x!=y)
	 	{
	 		for(i,1,n)
	         for(j,1,m)
	    	if(i+y-1<=n&&j+x-1<=m)
	 		{
	 		int w=s[i+y-1][j+x-1]-s[i-1][j+x-1]-s[i+y-1][j-1]+s[i-1][j-1];
	 		if(w==0)
	 		ans++;
	 		}	
	 	}
	 	prf(D "\n",ans);
	}
	
}

game
博弈题
有n个点，m条边
两个人给点染色
得到点的权值和边的权值，求最优解的差（保证点偶数个）
直接均摊
他们都是最优解
所以不会看到另一个人得到最多的
所以一定会然一条边的另一边
最后排序减一下就行了

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define D "%d"
#define for(i,x,y,z) for(int i=x;i<=y;i+=z)
#define prf printf
#define scf scanf
int n,m;
double w[19199],ans;
int main()
{
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	scf(D D,&n,&m);
	for(i,1,n,1)
		scf("%lf",&w[i]);
	for(i,1,m,1)
	{
		int x,y;
		double z;
		scf(D D "%lf",&x,&y,&z);
		w[x]+=z/2.0;
		w[y]+=z/2.0;
	}
	sort(w+1,w+n+1);
	for(i,1,n,2)
		ans+=w[i+1]-w[i];
	prf(D,int (ans));
	
}

fortress
大爆搜
这里写图片描述
没有什么技巧
就是一个超级大爆搜花了我两小时才调完
先打个表，将读入的问题搞好
再用邻接表弄，没墙就连上边
dfs搜有多少房间，搜最大的就先那种染色题一样
然后再删边添边，一次一次爆搜，找最大的

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
137
138
139
140
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int a[99][99],c[2600][2699],f[9999],ans,m,n,x,y;
char z;
int nex[99999],head[9999],to[9999],tot,max1;
int up(int x,int y)
{
	to[tot]=0;
	c[y][x]=0;
	head[y]=nex[tot];
	nex[tot]=0;
	tot--;
	to[tot]=0;
	c[x][y]=0;
	head[x]=nex[tot];
	nex[tot]=0;
	tot--;
}
int add(int x,int y)
{
	tot++;
	to[tot]=y;
	c[x][y]=1;
	nex[tot]=head[x];
	head[x]=tot;
	tot++;
	to[tot]=x;
	c[y][x]=1;
	nex[tot]=head[y];
	head[y]=tot;
}
int dfs(int x)
{
	for(int i=head[x];i;i=nex[i])
	{
		int tmp=to[i];
		if(!f[tmp])
		{
			ans++;
			f[tmp]=1;
			dfs(tmp);
		}
	}
}
int cnt;
int b[16][5]={
	4,1,2,4,8,
	3,2,4,8,0,
	3,1,4,8,0,
	2,4,8,0,0,
	3,1,2,8,0,
	2,2,8,0,0,
	2,1,8,0,0,
	1,8,0,0,0,
	3,1,2,4,0,
	2,2,4,0,0,
	2,1,4,0,0,
	1,4,0,0,0,
	2,1,2,0,0,
	1,2,0,0,0,
	1,1,0,0,0,
	0,0,0,0,0,
};
int main()
{
	freopen("fortress.in","r",stdin);
	freopen("fortress.out","w",stdout);
	scanf("%d%d",&m,&n);int t=0;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		++t;
		a[i][j]=t;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		int x;
		scanf("%d",&x);
		for(int k=1;k<=b[x][0];k++)
		{
			if(b[x][k]==2&&i-1>=1)
			add(a[i][j],a[i-1][j]);
			if(b[x][k]==1&&j-1>=1)
			add(a[i][j],a[i][j-1]);
			if(b[x][k]==8&&i+1<=n)
			add(a[i][j],a[i+1][j]);
			if(b[x][k]==4&&j+1<=m)
			add(a[i][j],a[i][j+1]);
		}
	}
	for(int i=1;i<=t;i++)
	if(!f[i])
	f[i]=1,cnt++,ans=1,dfs(i),max1=max(ans,max1);
	printf("%d\n%d\n",cnt,max1);max1=0;
	for(int j=1;j<=m;j++)
	for(int i=n;i>=1;i--)
	
	{
		
		memset(f,0,sizeof(f));
		if(!c[a[i][j]][a[i-1][j]]&&i-1>=1)
		{
			add(a[i][j],a[i-1][j]);
			for(int k=1;k<=n;k++)
			for(int q=1;q<=m;q++)
			{
				ans=0;
				dfs(a[i][j]);
				if(max1<ans)
				{
					max1=ans;
					x=i,y=j,z='N';
				}
			}
			up(a[i][j],a[i-1][j]);
		}
		memset(f,0,sizeof(f));
		if(!c[a[i][j]][a[i][j+1]]&&j+1<=m)
		{
			add(a[i][j],a[i][j+1]);
			for(int k=1;k<=n;k++)
			for(int q=1;q<=m;q++)
			{
				ans=0;
				dfs(a[i][j]);
				if(max1<ans)
				{
					max1=ans;
					x=i,y=j,z='E';
				}
			}
			up(a[i][j],a[i][j+1]);
		}
		
	}
	printf("%d\n%d %d %c",max1,x,y,z);
}
最近的文章

搜索

华容道70设两个变量，记在一个结构体里在进行爆搜，就是一个普通的bfs，只会简单的爆搜，正解是，三个bfs，先处理出白板到起始的最短距离，在处理出移动的代价，在跑一边最短路；123456789101112131415161718192021222324252627282930313233343536 …

• 于  bfsdfs 继续阅读
更早的文章

部落冲突

这题弄k各部落就是把它合并成k个集合所以按最小的边合并的解一定是最优的这就借用了k算法的思想12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include& …

• 于  最小生成树并查集 继续阅读