Znzryb's Blog
0%

Posted on Edited on

思路讲解

先搞一个布尔运算前缀和，再搞一个布尔运算后缀和，加快查询效率

那么关键就来到了布尔运算前缀数组以及布尔运算后缀数组怎样运算更快（线性复杂度）？

https://www.luogu.com.cn/article/9yd2730s

如果vector的大小很大，复杂度就会变得很劣质，但我们发现当vector的大小超过3 时，可以将中间的所有数字或起来合并。

来讲讲为什么可以这样那？其实vector数组只要超过2，既有三个时，就可以合并了，因为只有最后一个bool不能合并，因为他仍然会受到后续与运算的影响，我们来实践一下试试。

但实际上不是只是把suffix和prefix搓出来就好的，特别是针对&，比如来看下面这个例子

1
2
3
5 7
false and true or true
1 1 false

false & suffix[3] == false看似是对的，但实际上是有问题的，后面这段当中有or出现，false ｜true == true，所以出现了问题。

AC代码

心路历程（WA，TLE，MLE……）

没有考虑其实用&运算直接连起来是不可行的，上面解释的非常清楚

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,m;
// 先搞一个布尔运算前缀和，再搞一个布尔运算后缀和，加快查询效率
void cal(const vector<bool> &temp,vector<bool> &xfix,const int idx){
    xfix[idx]=temp[0];
    for(int i=1;i<temp.size();++i){
        xfix[idx]=(xfix[i] | temp[i]);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    vector<bool> A(n+5);
    vector<bool> prefix(n+5,false),suffix(n+5,false);
    for(int i=1;i<=n;++i){
        string a;
        cin>>a;
        if(a[0]=='f' || a[0]=='o')
            A[i]=false;
        else
            A[i]=true;
    }
    vector<bool> temp;
    // 计算前缀和
    for(int i=1;i<=n;i+=2){
        if(A[i-1]==false){
            temp.push_back(A[i]);
            cal(temp, prefix,i);
            if(temp.size()>3){
                temp[0]=(temp[0] | temp[1]);
                temp[1]=temp[2];
                temp.pop_back();
            }
        }else{
            int last=temp.size()-1;
            temp[last]=(temp[last] & A[i]);
            cal(temp, prefix,i);
        }
    }
    // 计算后缀和
    // 显然可以直接将 [l,r] 的一大串直接替换为目标布尔值
    temp.clear();
    for(int i=n;i>=1;i-=2){
        if(A[i+1]==false){
            temp.push_back(A[i]);
            cal(temp, suffix,i);
            if(temp.size()>3){
                temp[0]=(temp[0] | temp[1]);
                temp[1]=temp[2];
                temp.pop_back();
            }
        }else{
            int last=temp.size()-1;
            temp[last]=(temp[last] & A[i]);
            cal(temp,suffix,i);
        }
    }
    // 执行询问
    for(int i=1;i<=m;++i){
        ll l,r; string op;bool w;  // w即want
        cin>>l>>r>>op;
        if(op[0]=='t')
            w=true;
        else
            w=false;
        if(l==1 && r==n){
            cout<<'Y';
            continue;
        }
        // l==1的特殊情况
        if(l==1){
            bool isWant=false;
            if(A[r+1]==false){
                if((w | suffix[r+2])==w)
                    isWant=true;
                if(isWant)
                    cout<<'Y';
                else
                    cout<<'N'; 
            }else{
                if((w & suffix[r+2])==w)
                    isWant=true;
                if(isWant)
                    cout<<'Y';
                else
                    cout<<'N'; 
            }
            continue;
        }
        // r==n的特殊情况
        if(r==n){
            bool isWant=false;
            if(A[l-1]==false){
                if((w | prefix[l-2])==w)
                    isWant=true;
                if(isWant)
                    cout<<'Y';
                else
                    cout<<'N'; 
            }else{
                if((w & prefix[l-2])==w)
                    isWant=true;
                if(isWant)
                    cout<<'Y';
                else
                    cout<<'N'; 
            }
            continue;
        }
        bool isWant=false;
        if(A[r-1]==false && A[l-1]==false){
            if((prefix[l-2] | w | suffix[r+2])==w)
                isWant=true;
            if(isWant)
                cout<<'Y';
            else
                cout<<'N'; 
        }else if(A[r-1]==true && A[l-1]==false){
            if((prefix[l-2] & w | suffix[r+2])==w)
                isWant=true;
            if(isWant)
                cout<<'Y';
            else
                cout<<'N'; 
        }else if(A[r-1]==false && A[l-1]==true){
            if((prefix[l-2] | w & suffix[r+2])==w)
                isWant=true;
            if(isWant)
                cout<<'Y';
            else
                cout<<'N'; 
        }else{
            if((prefix[l-2] & w & suffix[r+2])==w)
                isWant=true;
            if(isWant)
                cout<<'Y';
            else
                cout<<'N'; 
        }
    }
}

Posted on Edited on

思路讲解

这题难点主要就是不要怕，看起来好像很难，但其实就只有16种状态，我还没加快读只跑了171ms。

看了一下大佬的思路，主要就是状态分解，还是分层图的思想。

image

1
2
3
//       y  x  dir dirs
bool vis[N][M][5][5];  
memset(vis, false, sizeof(vis));

所以我们建一个分层状态vis数组，dir指的是方向，dirs指的是在此方向走过的次数

只要vis[][][][]==true我们就continue；

在这个分层图上跑一个bfs

然后注意一下不要撞墙，不要出界，不要dirs>3

AC代码

注意，该写法仅能在C11及以上环境中编译（C98好像没有array）

https://codeforces.com/contest/2041/submission/293790427

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
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <cstring>

using namespace std;
typedef long long ll;
constexpr int dx[]={0,1,0,-1};
constexpr int dy[]={1,0,-1,0};
ll n,m;

// 这题会不会是分层图问题？
// 分不同的层去解决这个问题？
// 先写个bfs
inline bool check(ll x,ll y,vector<vector<char> > &maze){	
// 检查是否出界以及撞墙
	if(y<1 || y>n)
		return false;
	if(x<1 || x>m)
		return false;
	if(maze[y][x]=='#')
		return false;
	return true;
}

int main() {
	cin>>n>>m;
	vector<vector<char> > maze(n+5,vector<char>(m+5)); 
	ll sy=0,sx=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>maze[i][j];
			if(maze[i][j]=='S')
				sy=i,sx=j;
		}
	}
	queue<array<ll, 5>> q;
	//       x,y,step,dir,dirs;
	q.push({sx,sy,0LL,0LL,0LL});
	const ll N=5+static_cast<ll> (n),M=static_cast<ll> (m)+5;
	bool vis[N][M][5][5];  
	memset(vis, false, sizeof(vis));
	ll ans=1e17;
	while (!q.empty()) {
		ll x=q.front()[0];
		ll y=q.front()[1];
		ll step=q.front()[2];
		ll dir=q.front()[3];
		ll dirs=q.front()[4];
		q.pop();
		if(vis[y][x][dir][dirs]){
			continue;
		}
		if(maze[y][x]=='T'){
			ans=min(ans,step);
			continue;
		}
		vis[y][x][dir][dirs]=true;
		for(int i=0;i<4;++i){
			if(i==dir && dirs<3 && check(x+dx[i],y+dy[i],maze))
				q.push({x+dx[i],y+dy[i],step+1,i,dirs+1});
			else if(i!=dir && check(x+dx[i],y+dy[i],maze))
				q.push({x+dx[i],y+dy[i],step+1,i,1LL});
		}
	}
	if(ans!=1e17)
		cout<<ans<<endl;
	else
		cout<<-1<<endl;
}
// AC https://codeforces.com/contest/2041/submission/293790427

心路历程（WA，TLE，MLE……）

前面少include 一个cstring库，唉，都是clang不支持<bits/stdc.h>导致的

Posted on Edited on

思路讲解

一个小的脑筋急转弯

构造数组为 b b 3a-2b

无论3a-2b 的值是多少，b都是中位数

AC代码

https://codeforces.com/contest/2041/submission/293763683

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>

using namespace std;
typedef long long ll;
ll a,b;

int main() {
	cin>>a>>b;
//	its mean is exactly a
//	and its median is exactly b
//  怎么做才能达到这样的效果那？
	cout<<3<<"\n";
	cout<<b<<" "<<b<<" "<<3*a-(2*b)<<endl;
}
// AC https://codeforces.com/contest/2041/submission/293763683

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

我反正贪心过的，n比较小，所以全部是循环。

先尝试性价比比较高的，再尝试性价比比较低的

AC代码

https://codeforces.com/contest/2038/submission/293535960

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
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;


void solve(ll n){
	ll a=n,b=n,c=n;
	ll cnt=0;
	while (a>=1 && b>=2){
		a-=1;
		b-=2;
		++cnt;
	}
	while (a>=3) {
		a-=3;
		++cnt;
	}
	while (a>=1 && c>=1){
		a-=1,c-=1;
		++cnt;
	}
	while (b>=1 && c>=1) {
		b-=1;
		c-=1;
		++cnt;
	}
	while (c>=1) {
		c-=2;
		++cnt;
	}
	while (b>=1) {
		b-=2;
		++cnt;
	}
	while (a>=1) {
		a-=2;
		++cnt;
	}
	cout<<cnt<<endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll n;
	cin>>n;
	solve(n);
	return 0;
}

// AC https://codeforces.com/contest/2038/submission/293535960

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

用了一个map来存一下每个数出现的次数，然后只有出现两次的数才可参与矩形的构建。

然后C++的map是有序的，所以遍历也是有序的

AC代码

https://codeforces.com/contest/2038/submission/293462817

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
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;
typedef long long ll;
ll T;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		ll n;
		cin>>n;
		vector<ll> A(n+10);
		map<ll,ll> occur;
		for(int i=1;i<=n;++i){
			cin>>A[i];
			if(occur.count(A[i]))
				occur[A[i]]+=1;
			else
				occur[A[i]]=1;
		}
		vector<ll> validNum;	// 因为遍历是有序的，所以validNum也是有序的
		for(map<ll,ll>::iterator it=occur.begin();it!=occur.end();it++){
			ll num=it->first,cnt=it->second;
			while (cnt>=2){
				validNum.push_back(num);
				cnt-=2;
			}
		}
		if(validNum.size()<4){
			cout<<"NO"<<endl;
		}else {
			cout<<"YES"<<endl;
			ll a=validNum[0],b=validNum[1],c=validNum[validNum.size()-1],d=validNum[validNum.size()-2];
			cout<<a<<" "<<b<<" "<<a<<" "<<c<<" "<<d<<" "<<b<<" "<<d<<" "<<c<<endl;
		}
	}
}
// AC https://codeforces.com/contest/2038/submission/293462817

心路历程（WA，TLE，MLE……）

输出顺序要好好想想

1
cout<<a<<" "<<b<<" "<<a<<" "<<c<<" "<<d<<" "<<b<<" "<<d<<" "<<c<<endl;