Znzryb's Blog
0%

Posted on Edited on

思路讲解

这题的贪心策略是选择有最早结束时间的活动

AC代码

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

Posted on Edited on

思路讲解

模拟题，没什么好说的

我的写法是学的题解的写法，我觉得挺好的

化曲为直，是个好做法。

AC代码

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>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e3)+10;
ll n,T,m;
char maze[N][N];
// 呃，题目还是很清楚的
// 就是模拟嘛，谁怕谁
// 唉，我怕了，这模拟不给我数据我咋调
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		ll ans=0;
		cin>>n>>m;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				cin>>maze[i][j];
			}
		}
		ll ceng=min(n,m)/2;
		for(int i=1;i<=ceng;++i){
			ll cnt=0;string s;
			// 最右边            最下边
			ll upm=m-(i-1),upn=n-(i-1);
			for(int j=i;j<=upm;++j) s+=maze[i][j];
			for(int j=i+1;j<=upn;++j) s+=maze[j][upm];
			for(int j=upm-1;j>=i;--j) s+=maze[upn][j];
			for(int j=upn-1;j>=i+1;--j) s+=maze[j][i];
			ll len=s.size();
			for(int j=0;j<len;++j)
				if(s[j]=='1' && s[(j+1)%len]=='5' && s[(j+2)%len]=='4' && s[(j+3)%len]=='3')
					++ans;
		}
		cout<<ans<<endl;
	}
	return 0;
}
// WA on 2 https://codeforces.com/contest/2036/submission/293979229
// AC https://codeforces.com/contest/2036/submission/293986402

心路历程（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
#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>(1e3)+10;
ll n,T,m;
char maze[N][N];
const char ob[6]={'1','5','4','3'};
// 呃，题目还是很清楚的
// 就是模拟嘛，谁怕谁
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		ll ans=0;
		cin>>n>>m;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				cin>>maze[i][j];
			}
		}
		ll ceng=min(n,m)/2;
		for(int i=1;i<=ceng;++i){
			ll cnt=0;
			// 最右边            最下边
			ll upm=m-(i-1),upn=n-(i-1);
			for(int j=i;j<=upm;++j){
				if(maze[i][j]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
			for(int j=i+1;j<=upn;++j){
				if(maze[j][upm]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
			for(int j=upm-1;j>=i;--j){
				if(maze[upn][j]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
			for(int j=upn-1;j>=i;--j){
				if(maze[j][i]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
			ll step=1;
			// 这下面是为了避免样例7那种情况搞的
			if(cnt<2)
				continue;
			for(int j=i+1;j<=upm;++j){
				if(step>=3)
					break;
				++step;
				if(maze[i][j]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
			for(int j=i+1;j<=upn;++j){
				if(step>=3)
					break;
				++step;
				if(maze[j][upm]==ob[cnt]){
					++cnt;
				}else {
					cnt=0;
				}
				if(cnt==4)
					++ans,cnt=0;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
// WA on 2 https://codeforces.com/contest/2036/submission/293979229

Posted on Edited on

思路讲解

主要思路就是使用二叉堆的一个贪心（pq）

把这个障碍物前面的全部奖励都放到pq里，然后用一个弹出一个，避免后面重复用，还有一个就是降低算法复杂度

其实还有一个对于算法复杂度的一个判断

其实push pq不用担心时间复杂度的问题，因为用过的我们都会push掉，所以每个奖励我们只会遍历一次，所以差不多是O(nlogn+mlogm)

AC代码

https://codeforces.com/contest/2037/submission/293963686

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 <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,T,m,L;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n>>m>>L;
		vector<pair<ll,ll> > ban(n+5),enc(m+5);
		vector<ll> senc(m+5,0);	
		priority_queue<ll> q;
		for(int i=1;i<=n;++i){
			cin>>ban[i].first>>ban[i].second;
		}
		for(int i=1;i<=m;++i){
			cin>>enc[i].first>>enc[i].second;
		}
		for(int i=1;i<=m;++i)
			senc[i]=senc[i-1]+enc[i].second;
		// 跑一个greedy就行
		ll sadd=1; // 起始push
		ll curk=1; // 当前跳跃能力
		ll ans=0;
		bool isBreak=false;
		for(int i=1;i<=n;++i){
			ll len=ban[i].second-ban[i].first+1;
			if(curk>len){	// 说明跳得过去
				continue;
			}
			ll idx=lower_bound(enc.begin() + 1, enc.begin() + m + 1,make_pair(ban[i].first,0LL))-enc.begin()-1;
			if(senc[idx]+1<=len){
				cout<<-1<<endl;
				isBreak=true;
				break;
			}
			// 其实push pq不用担心时间复杂度的问题，因为用过的我们都会push掉，分摊一下就是O（n）
			for(int i=sadd;i<=idx;++i){
				q.push(enc[i].second);
			}
			while(!q.empty()){
				curk+=q.top();
				q.pop();
				++ans;
				if(curk>len)
					break;
			}
			sadd=idx+1;
		}
		if(!isBreak)
			cout<<ans<<endl;
	}
	return 0;
}
// AC https://codeforces.com/contest/2037/submission/293963686

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

二分搜索vector记得这么写

1
ll idx=lower_bound(enc.begin() + 1, enc.begin() + m + 1,make_pair(ban[i].first,0LL))-enc.begin()-1;

Posted on Edited on

思路讲解

状压dp的整体思想就是将状态用一个数表示出来，进而方便状态转移。

1
2
double dp[25][33000];  // 状压dp数组
//      当前点  状态

那么问题就来了，怎么进行状态转移（在这题里）？

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=1;i<=(1<<n)-1;++i){     // 枚举所有状态
        for(int j=1;j<=n;++j){       // 枚举当前点
            if((i & (1<<j-1))==0)    // 说明当前点没走过,这是不合法的
                // 该操作相当于只保留了i的第j位二进制数（0，1）
                continue;
            for(int k=1;k<=n;++k){  // 枚举要去的点
                if((i & (1<<k-1))==0){
                    int status=(1<<k-1)+i;
                    dp[k][status]=min(dp[j][i]+Dis[j][k],dp[k][status]);
                }
            }
        }
    }

AC代码

https://www.luogu.com.cn/record/191940029

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
#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,T;
double Loc[25][3],Dis[25][25];
double dp[25][33000];  // 状压dp数组
//      当前点  状态
// 2**15==32768,也就是用二进制下的15位数可以搞定
// 当然第十五位二进制下表示2**14 
// 一共约33000种状态

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>Loc[i][0]>>Loc[i][1];
    }
    for(int i=0;i<=n;++i){
        for(int j=0;j<=n;++j){  // 原点到不同点之间的距离也需要统计
            if(i==j)
                continue;
            double x1=Loc[i][0],y1=Loc[i][1];
            double x2=Loc[j][0],y2=Loc[j][1];
            Dis[i][j]=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
        }
    }
    memset(dp, 127, sizeof(dp));   // 初始化dp为极大值
    for(int i=1;i<=n;++i)   // 初始化原点到各个点的值
        dp[i][1<<(i-1)]=Dis[0][i];
    for(int i=1;i<=(1<<n)-1;++i){     // 枚举所有状态
        for(int j=1;j<=n;++j){       // 枚举当前点
            if((i & (1<<j-1))==0)    // 说明当前点没走过,这是不合法的
                // 该操作相当于只保留了i的第j位二进制数（0，1）
                continue;
            for(int k=1;k<=n;++k){  // 枚举要去的点
                if((i & (1<<k-1))==0){
                    int status=(1<<k-1)+i;
                    dp[k][status]=min(dp[j][i]+Dis[j][k],
                        dp[k][status]);
                }
            }
        }
    }
    double ans=1e17;
    for(int i=1;i<=n;++i){
        int status=(1<<n)-1;
        ans=min(dp[i][status],ans);
    }
    cout<<setprecision(2)<<fixed<<ans<<endl;
}
// AC https://www.luogu.com.cn/record/191940029

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

前面status和点的idx位置放反了，导致了RE

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