Znzryb's Blog
0%

Posted on Edited on

思路讲解

和这题代码基本一样，还是比较适合我复训的。

我们来解释一下为什么可以这样pushup

1
2
3
4
5
6
inline void invert(ll s,ll e){
	pushup(s, 1);
	if(e<n){
		pushup(e+1, -1);
	}
}

众所周知，我们知道差分数组是给diff[s]+1，给diff[e+1]-1，那为什么可以直接pushup那？那是因为树状数组中遍历你上面的数组是必然遍历不到你的，这点你不用担心，所以不用担心差分连续加导致出错。

AC代码

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

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
#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>(5e5)+10;
ll n,m,tr[N];
inline ll mod2(ll x){	// 对2取模
	return (x+2)%2;
}
inline ll lowbit(ll x){		
	// 负数补码原理，负数就是把你之前的书全部取反再加1
	// 正数和0的补码就是该数字本身再补上最高比特0
	// 负数的补码则是将其绝对值按位取反再加1。
	return x&(-x);
}
inline void pushup(ll x,ll v){
	while(x<n+1){
		tr[x]+=v;
		x+=lowbit(x);
	}
}
// 
inline void invert(ll s,ll e){
	pushup(s, 1);
	if(e<n){
		pushup(e+1, -1);
	}
}

inline ll search(ll x){
	if(x==0) return 0;
	return search(x-lowbit(x))+tr[x];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	while(m--){
		ll op;
		cin>>op;
		if(op==1){
			ll s,e;
			cin>>s>>e;
			invert(s, e);
		}else{
			ll x;
			cin>>x;
			cout<<mod2(search(x))<<endl;
		}
	}
	return 0;
}
// AC https://www.luogu.com.cn/record/192393560

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

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