Algorithms Weekly 8

Posted on | Post modified:

A Game of life week

ABC167 F. Bracket Sequencing

题意：

给定$n$个括号串，判断是否存在一种排列顺序使这$n$个串排序后形成的串合法。$(1 \leq n \leq 10^6)$

题解：

对于每个串$s_{i}$,令’(‘为$1$，’)’为$-1$,计算$balance$，如果$balance$大于等于$0$,放到一堆，否则放到另一堆，令$a_{i}$为$-min\{0,pre_{i,j}\}$，$b_{i}$为第$i$个字符串的$balance$,将问题转化: 初试分数为$0$, 得到第$i$个串的前提是拥有$a_{i}$分，得到第$i$个串之后的分数为$ b_{i}$。判断能否拿完所有的串。

那么对于$a_{i}>=0$的情况，按照$a_{i}$从小到大排序，这是很显然的贪心策略。

对于$a_{i} < 0$的情况，需要按照$a_{i}+b_{i}$从大到小排序，其实本质是按照‘（’的个数从大到小排序，至于为什么不用考虑’)’，是因为我们已经先把$a_{i}>=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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
* @author:  codancer
* @createTime:  2020-05-11, 20:15:07
*/
#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
const int N = 2e6+100;
pair<int,int> cnt[N];
int main(){
	int n;
	cin>>n;
	vector<string> s(n+1);
	vector<pair<int,int> > pos,neg;
	rep(i,1,n){
		int minn=0;// I should have -minn opening brackets before take it
		int balance=0;// after take it ,  i can add balance to sum
		cin>>s[i];
		for(char c:s[i]){
			if(c=='(') ++balance;
			else --balance;
			minn=min(minn,balance);
		}
		int need=-minn,get=balance;
		if(balance>=0) pos.push_back({need,get});
		else{
			neg.push_back({need,get});
		}
	}
	sort(pos.begin(),pos.end());
	sort(neg.begin(),neg.end(),[](const pair<int,int> a,const pair<int,int> b){
		return a.first+a.second>b.first+b.second;
	});
	int now=0;
	for(auto v:pos){
		if(now<v.first){
			cout<<"No"<<endl;
			return 0;
		}
		now+=v.second;
	}
	for(auto v:neg){
		if(now<v.first){
			cout<<"No"<<endl;
			return 0;
		}
		now+=v.second;
	}
	if(now){
		cout<<"No"<<endl;
		return 0;
	}
	cout<<"Yes"<<endl;
	return 0;
}

CF641div2 E. Orac and Game of Life

题意：

一款”生命游戏”,规则如下：

游戏在一个$n*m$的平面上，每个格子为黑色或白色。游戏会进行若干轮，初始为第$0$轮，对于每一轮：

  • 对于$(i,j)$，如果它的四周存在同色的格子，该轮$(i,j)$变色。
  • 否则不变色

$Q$次查询，对于每次查询，查询$(x,y)$在第$t$轮的颜色。

$(1 \leq n,m \leq 1000, 1 \leq t \leq 10^5)$

题解：

假设对于$(i,j)$，如果$(i,j)$周围存在同色格子，那么定义其为坏格子，否则为好格子，那么对于所有格子，计算离其最近的坏格子的曼哈顿距离$p$，如果$t<p$，则不会变色，否则每次交替变色。对于距离的计算，一次$BFS$即可。时间复杂度$O(n*m+t)$。

代码:

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
/*
* @author:  codancer
*/
#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define pb push_back
#define SZ(x) ((int)(x).size())
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
typedef vector<int> VI;
typedef pair<int,int> pii;
const int N = 1005;
bool bad[N][N];
int f[N][N];
bool vis[N][N];
char maze[N][N];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int main(){
	int n,m,t;
	cin>>n>>m>>t;
	rep(i,1,n){
		rep(j,1,m){
			cin>>maze[i][j];
		}
	}
	memset(bad,0,sizeof(bad));
	rep(i,1,n){
		rep(j,1,m){
			rep(k,0,3){
				int dx=i+dir[k][0];
				int dy=j+dir[k][1];
				if(dx>=1&&dx<=n&&dy>=1&&dy<=m){
					if(maze[dx][dy]==maze[i][j]){
						bad[i][j]=1;
						break;
					}
				}
			}
		}
	}
	queue<pair<int,int> > q;
	rep(i,1,n) rep(j,1,m) f[i][j]=1e9;
	rep(i,1,n){
		rep(j,1,m){
			if(bad[i][j]){
				q.push({i,j});
				f[i][j]=0;
			}
		}
	}
	while(!q.empty()){
		pair<int,int> rt=q.front();q.pop();
		int x=rt.first;
		int y=rt.second;
		if(vis[x][y]) continue;
		vis[x][y]=1;
		rep(k,0,3){
			int dx=x+dir[k][0];
			int dy=y+dir[k][1];
			if(dx>=1&&dx<=n&&dy>=1&&dy<=m){
				if(f[dx][dy]>f[x][y]+abs(x-dx)+abs(y-dy)){
					f[dx][dy]=f[x][y]+abs(x-dx)+abs(y-dy);
					q.push({dx,dy});
				}
			}
		}
	} 
	while(t--){
		int i,j;
		ll p;
		cin>>i>>j>>p;
		if(f[i][j]==1e9){
			cout<<maze[i][j]<<'\n';
			continue;
		}
		if(p<=f[i][j]){
			cout<<maze[i][j]<<'\n';
		}else{
			p-=f[i][j];
			if(p&1) cout<<(!(maze[i][j]-'0'))<<'\n';
			else{
				cout<<maze[i][j]<<'\n';
			}
		}
	}
	return 0;
}