Znzryb's Blog
0%

Posted on Edited on

思路讲解

哈哈，找规律很难找，找不出来？不妨使用回溯思想，反过来找。

这个操作那其实就是一个倍增操作，我们反过来找我们的这个位置需要倍增几次才能到那？

知道了这个，只需要通过这个（需要倍增几次）%2 进行反转操作就行。

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
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
#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>
#include <cctype>
#include <array>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T,len;
string s;

inline char invert(char a) {
	if(a<='z' && a>='a') {
		a-=32;
		return a;
	}else {
		a+=32;
		return a;
	}
}


// 可以用用这种指针写法
ll calLift(ll x, ll &standLen){
	ll cnt=0;
	while(true){
		if(standLen>x){
			standLen/=2;
			return cnt;
		}else if(standLen==x){
			return cnt;
		}else{
			cnt+=1;
			standLen*=2;
		}
	}
//	return cnt;
}

char dfs(ll x,ll cnt){
	ll needLift=0,standLen=len,res=0;
	needLift=calLift(x,standLen);
	if(needLift==0 /*|| (needLift==1 && x==standLen)*/){
		if(cnt%2==0)
			return s[x-1];
		else
			return invert(s[x-1]);
	}
	res= x==standLen ? standLen/2:x-standLen;
	return dfs(res,cnt+1);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll q;
	s.clear();
	cin>>s;
	len=s.size();
	cin>>q;
	for(int i=1;i<=q;++i){
		ll k;
		cin>>k;
		char ans=dfs(k,0);
		cout<<ans<<" ";
	}
	cout<<endl;
	return 0;
}
// AC https://atcoder.jp/contests/abc380/submissions/60951665
/*
qWeRtYuIoP
8
1 1 2 3 5 8 13 21

aB161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

*/

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

样例给的强，一次提交就过了

https://atcoder.jp/contests/abc380/submissions/60951665

其实调调了半天，尽量函数越少越好（用了一个指针优化掉了一个函数）。

Posted on Edited on

思路讲解

总体我感觉没什么难的，就是写起来比较复杂

细节上的问题主要写在注释上，这里讲一下答题思路。

先把所有在应该放2位置的1换成2。（之前是没有这个步骤的，但好像导致策略不够优秀）

接着把所有在应该放2位置的0先换成1，再换成2

最后放一下1就可以了

AC代码

https://codeforces.com/contest/2034/submission/297475528

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
161
162
163
164
165
166
#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>
#include <cctype>
#include <array>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n;
		vector<ll> A(n+10);
		vector<ll> test(n+10);
		ll cnt2=0,cnt1=0;
		// loc1Up指的是所有>n-cnt2的1.
		vector<ll> loc1,loc2;
		deque<ll> loc1Up,loc2Up;
		vector<pair<ll, ll> > op;
		for(int i=1;i<=n;++i){
			cin>>A[i];
			
			test[i]=A[i];
			
			if(A[i]==2){
				cnt2+=1,loc2.push_back(i);
			}else if(A[i]==1)
				cnt1+=1,loc1.push_back(i);
		}
		while(!loc1.empty()){
			if(loc1.back()<=n-cnt2)
				break;
			loc1Up.push_front(loc1.back());
			loc1.pop_back();
		}
		// loc2里装的是不符合要求的2.
		while (!loc2.empty()) {
			if(loc2.back()<=n-cnt2)
				break;
			// push_front 从前面加入，大的一直被往后面挤
			// 保证loc2Up的递增性（idx的递增型）
			loc2Up.push_front(loc2.back());
			loc2.pop_back();
		}
		
//		ll idx=0;
		// 这是排2的程序
		// 先把所有1都搞过去
		for(int i=n;i>n-cnt2;--i){
			if(test[i]==1){	
				op.emplace_back(i,loc2.back());
				
				swap(test[i], test[loc2.back()]);
				
				loc1.push_back(loc2.back());
				loc2.pop_back();
				// loc1Up遵循递增顺序，遍历是递减
				// 遇到先遇到的1必然最大的
				loc1Up.pop_back();
			}
		}
		for(int i=n;i>n-cnt2;--i){
			if(loc2.empty())
				break;
			// A是不可靠的，需要用test
			if(test[i]==2)
				continue;
			if(test[i]==1){	
				op.emplace_back(i,loc2.back());
				
				swap(test[i], test[loc2.back()]);
				
				loc1.push_back(loc2.back());
				loc2.pop_back();
				// loc1Up遵循递增顺序，遍历是递减
				// 遇到先遇到的1必然最大的
				loc1Up.pop_back();
			}else{
				// loc1不是空的时候
				if(!loc1.empty()){
					op.emplace_back(i,loc1.back());
					swap(test[i], test[loc1.back()]);
					op.emplace_back(i,loc2.back());
					swap(test[i],test[loc2.back()]);
					
					loc1.pop_back();
					loc1.push_back(loc2.back());
					loc2.pop_back();
				}else {
					op.emplace_back(i,loc1Up.back());
					swap(test[i], test[loc1Up.back()]);
					op.emplace_back(i,loc2.back());
					swap(test[i], test[loc2.back()]);
					
					loc1Up.pop_back();
					// 	这个1被交换到了loc2的位置
					loc1.push_back(loc2.back());
					loc2.pop_back();
				}
			}
		}
		
		// 这是排1的程序
		vector<ll> is1(n+10,false);
		sort(loc1.begin(), loc1.end());
		while (!loc1.empty()) {
			// n-cnt1-cnt2+1 需要摆1
			// n-cnt1-cnt2 就不需要摆1了，所以break掉
			if(loc1.back() <= n-cnt2-cnt1){
				break;
			}
			is1[loc1.back()]=true;
			loc1.pop_back();
		}
		// 开始正式排1
		for(int i=n-cnt2;i>=n-cnt1-cnt2+1;--i){
			if(loc1.empty())
				break;
			if(is1[i])
				continue;
			op.emplace_back(i,loc1.back());
			swap(test[i], test[loc1.back()]);
			loc1.pop_back();
		}
		
		cout<<op.size()<<endl;
		for(int i=0;i<op.size();++i){
//			if(abs(test[op[i].first]-test[op[i].second])!=1)
//				cout<<"WA on this: ";
			cout<<op[i].first<<" "<<op[i].second<<endl;
//			swap(test[op[i].first], test[op[i].second]);
		}
		
//		cout<<"Outcome: ";
//		for(int i=1;i<=n;++i){
//			cout<<test[i]<<" ";
//		}
//		cout<<endl;
	}
	return 0;
}

/*
4
41 0 2 0
40 1 2 0
41 1 2 0
42 2 1 0

*/

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

WA1:

https://codeforces.com/contest/2034/submission/297451161

判断哪里应该是2，哪里应该是1的判断有点问题

WA2:

https://codeforces.com/contest/2034/submission/297454477

策略不够优，超过了最大允许操作次数

Posted on Edited on

思路讲解

主要思路就是逆向思维，把所有能出去的点都识别出来，然后剩下的点就是不能出去的。

如果一个问号点周围都是能出去的，那么他也能出去。只要它周围有一个被困住的（不能出去），那么这个问号块也是被困住的。

然后主要是初始化上的一些细节问题

1
2
3
4
memset(isStuck, false, sizeof(isStuck));
for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
		isStuck[i][j]=true;

所有外面的块提前被设为不被困住，里面的块设为可以困住的

然后按照这个做法做就完了。

AC代码

https://codeforces.com/contest/2034/submission/297055462

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
#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>
#include <cctype>
#include <array>
// https://codeforces.com/contest/2034/problem/C
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T,m;
char maze[1010][1010];
bool vis[1010][1010],isStuck[1010][1010];
map<char,array<int, 2> > dir={{'U',{-1,0}},{'D',{1,0}},{'L',{0,-1}},{'R',{0,1}}};
map<char,char> reverseMap={{'U','D'},{'D','U'},{'L','R'},{'R','L'}};
ll mans;
// 我稍微看了一眼题解，大概猜到思路了
// 就是顺着走直接走出去的方块一定没救

inline bool isOut(int x,int y){
	if(x>n) return true;
	if(x<1) return true;
	if(y>m) return true;
	if(y<1) return true;
	return false;
}

void dfs(int x,int y){
	if(isOut(x, y))
		return;
	if(maze[x][y]=='?')
		return;
	if(vis[x][y])
		return;
	isStuck[x][y]=false;
	vis[x][y]=true;
	mans+=1;
//	char dirc=reverseMap[maze[x][y]];
//	int nx=x+dir[dirc][0],ny=y+dir[dirc][1];
	// 如果说要去的那个格子之前可以到你这个格子
	// 那么就是可以去的
	vector<ll> xdir={0,1,0,-1};
	vector<ll> ydir={1,0,-1,0};
	for(int i=0;i<4;++i){
		int nx=x+xdir[i],ny=y+ydir[i];
		if(isOut(nx, ny))
			continue;
		if(nx+dir[maze[nx][ny]][0]==x && ny+dir[maze[nx][ny]][1]==y){
			dfs(nx, ny);
		}
	}
	
	
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n>>m;
//		memset(maze, '0', sizeof(maze));
//		vector<vector<char>> maze(n+10,vector<char>(m+10));
		memset(vis, false, sizeof(vis));
		memset(isStuck, false, sizeof(isStuck));
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				isStuck[i][j]=true;
		mans=0;
		for(int i=1;i<=n;++i){
			for (int j=1; j<=m; ++j) {
				cin>>maze[i][j];
				
//				reverseMaze[i][j]=reverseMap[maze[i][j]];
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(maze[i][j]=='?')
					continue;
				char dirc=maze[i][j];	
				// 反正时间复杂度无所谓，用稍微复杂点的写法
				// 指的是我们能走出去的点，才能进入
				if(isOut(i+dir[dirc][0], j+dir[dirc][1]))
					isStuck[i][j]=false,dfs(i, j);
			}
		}
		
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(maze[i][j]!='?')
					continue;
				vector<ll> xdir={0,1,0,-1};
				vector<ll> ydir={1,0,-1,0};
				bool isBreak=false;
				for(int k=0;k<4;++k){
					if(isStuck[i+xdir[k]][j+ydir[k]]){
						isBreak=true;
						break;
					}
				}
				if(!isBreak)
					mans+=1;
			}
		}
		cout<<n*m-mans<<endl;
	}
	return 0;
}
// AC https://codeforces.com/contest/2034/submission/297055462
/*
3
3 3
UUU
L?R
DDD
2 3
???
???
3 3
?U?
R?L
RDL

0
6
5

1
3 3
?U?
L?R
?D?

0
*/

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

WA：

https://codeforces.com/contest/2034/submission/297053887

没有注意思路中的初始化上的细节问题

Posted on Edited on

思路讲解

这个视频讲解还不错

AC代码

https://www.acwing.com/problem/content/submission/code_detail/38373269/

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
#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>
#include <cctype>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e5)+10,N2=1e6+10;
ll n,m;
char P[N],S[N2];
ll nxt[N];	// next数组

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>P+1>>m>>S+1;
	// nxt 递推
	for(int i=2,j=0;i<=n;++i){
		while (j && P[i]!=P[j+1]) 
			j=nxt[j];
		if(P[i]==P[j+1]) 
			++j;
		nxt[i]=j;
	}
	// kmp 匹配过程
	for(int i=1,j=0;i<=m;++i){
		while (j && S[i]!=P[j+1]) 
			j=nxt[j];
		if(S[i]==P[j+1])
			++j;
		if(j==n){
			cout<<i-j<<" ";
		}
	}
	cout<<"\n";
}
// AC https://www.acwing.com/problem/content/submission/code_detail/38373269/

心路历程（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
#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>
#include <cctype>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e5)+10,N2=1e6+10;
ll n,T,n2;
char P[N],S[N2];
ll nxt[N];	// next数组

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>P[i];
	}
	
	cin>>n2;
	for(int i=1;i<=n2;++i){
		cin>>S[i];
	}
	// nxt数组递推O（n）生成
	for(int i=2;i<=n;++i){
		if(P[i]==P[nxt[i-1]+1])
			nxt[i]=nxt[i-1]+1;
		else
			nxt[i]=0;
	}
	vector<ll> ans;
	for(int i=1,j=1;i<=n2;++i){
		if(S[i]==P[j]){
			if(j==n){
				ans.push_back(i-j);
				j=nxt[j-1]+2;
			}else{
				++j;
			}
		}else{
			if(i==n2)
				break;
			j=nxt[j-1]+2;
		}
	}
	for(int i=0;i<ans.size();++i)
		cout<<ans[i]<<" ";
	cout<<endl;
}
/*
3
aba
5
ababa

5
ABABC
7
ABABABC

2
ab
7
abcababc

3
aaa
10
aaaaaaabaa

*/

Posted on Edited on

思路讲解

树状数组经典题。

然后前面看半天看不太懂，原来是用了频数数组呀，我想为啥要用树状数组那？

原来数组里维护的是频数，需要区间查询+单点修改两个操作，这个树状数组操作我还是会的。

频数数组
很多数据结构都是基于「频数数组」。
给定数组 t 以及它的下标范围 [L,R]，t[x] 就表示元素 x 在数据结构中的出现次数。基于此，上述的两个操作可以变为：
操作 1「查询」：给定一个范围 [left,right]，查询 t[left] 到 t[right] 的和；
操作 2「更新」：给定一个元素 x，将 t[x] 增加 1。
这也是线段树和树状数组的基础，它们需要的空间都与数组 t 的下标范围 [L,R] 正相关。在本题数据规模较大的情况下（例如测试数据中，出现了元素值达到 32 位有符号整数的上下界），线段树和树状数组都会超出空间限制，因此需要借助「离散化」操作，将这些元素映射到一个较小规模的区间内。
https://leetcode.cn/problems/count-of-range-sum/solutions/476205/xian-ren-zhi-lu-ru-he-xue-xi-ke-yi-jie-jue-ben-ti-/

AC代码

https://leetcode.cn/problems/count-of-range-sum/submissions/585372478/

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
class Solution {
public:
    typedef long long ll;
    int countRangeSum(vector<int>& nums, int lower, int upper) {

        int n=nums.size();
        vector<ll> sumA(n+10,0);
        set<ll> li;// 离散化映射关系
        vector<ll> lii(n+10,-1e11+7);// 离散化映射关系数组
        for(int i=1;i<=n;++i){
            sumA[i]=sumA[i-1]+nums[i-1];
            // 0 index -> 1 index
            li.insert(sumA[i]);
        }
        // 我个人认为，就是每次查询查一下以该点为结尾的valid子数组有几个
        // 然后加入答案就行，在线算法
        // 实际上是个频数数组+树状数组
        vector<ll> BIT(n+10,0);
        ll distinctN=li.size();  // 去重以后的n大小
        ll idx=0;
        for(set<ll>::iterator it=li.begin();it!=li.end();it++){
            lii[++idx]=*it;
        }
        int ans=0;
        for(int i=1;i<=n;++i){
            ans+=search(sumA[i]-upper,sumA[i]-lower,
                BIT,lii,distinctN);
            add(sumA[i],BIT,lii,distinctN);
            if(sumA[i]>=lower && sumA[i]<=upper)
                ans+=1;
        }
        return ans;
    }
    inline ll lowbit(ll x){
        return x&(-x);
    }
    inline void pushup(vector<ll> &BIT,ll x,ll v,ll n){
        while(x<=n){
            BIT[x]+=v;
            x+=lowbit(x);
        }
    }
    inline void add(ll x,vector<ll> &BIT,const vector<ll> &lii,const ll n){
        ll idx=lower_bound(lii.begin()+1,
            lii.begin()+n+1,x)-lii.begin();
        if(lii[idx]!=x)
            idx-=1;
        pushup(BIT,idx,1,n);
    }
    inline ll search(ll l,ll r,vector<ll> &BIT,vector<ll> &lii,ll n){
        ll resl=0,resr=0;
        ll idxl=lower_bound(lii.begin()+1,
            lii.begin()+n+1,l)-lii.begin();
        ll idxr=lower_bound(lii.begin()+1,
            lii.begin()+n+1,r)-lii.begin();
        if(lii[idxr]!=r)
            idxr-=1;
        // 因为是两前缀和相减，l往后退一下。
        idxl-=1;
        while(idxl>0) {
            resl+=BIT[idxl];
            idxl-=lowbit(idxl);
        }
        while(idxr>0) {
            resr+=BIT[idxr];
            idxr-=lowbit(idxr);
        }
        // if(resr-resl<0)
        //     return 0LL;
        return resr-resl;
    }
};

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

唉这题搞了半天

记住，离散化之后，传入的数组大小应该是去重以后的大小（即ditinctN），否则搜出lii的递增范围，lower_bound()就不可靠了。

1
search(sumA[i]-upper,sumA[i]-lower,BIT,lii,distinctN);

https://leetcode.cn/problems/count-of-range-sum/submissions/585369029/

记得离散化映射关系数组的初始化值为0容易出事，因为如果是搜0，搜到外面去容易出事

1
vector<ll> lii(n+10,-1e11+7);// 离散化映射关系数组