Algorithms Weekly 8

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;
}