Znzryb's Blog
0%

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);// 离散化映射关系数组

Posted on Edited on

image

思路讲解

思路很简单，一个块要么走上边，要么走下边（先忽略下去的那个块）

然后我们看走上面性价比高还是走下边性价比高，选择性价比高的。

再通过sort得到要从哪个块下去。

总的来说我觉得挺简单的，但是算法实现上有一些细节。

AC代码

https://codeforces.com/contest/2047/submission/295161620

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
#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>(5e3)+10;
ll n,T;
//inline bool cmp(pair<ll, ll> a,pair<ll, ll> b){
//	return a.second>b.second;
//}
// 我的想法是每个应该走上面的归为一类
// 应该走下面的也归为一类
// 然后最后看应该从哪里下去
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		vector<pair<ll, ll> > A(n+10);
		ll ans=0;
		for(int i=1;i<=n;++i){
			cin>>A[i].first;
		}
		for(int i=1;i<=n;++i){
			cin>>A[i].second;
		}
		vector<ll> upBlock,dowBlock;
		for(int i=1;i<=n;++i){
			if(A[i].first>A[i].second){
				ans+=A[i].first;
				upBlock.push_back(A[i].second);
			}else if(A[i].first<A[i].second){
				ans+=A[i].second;
				dowBlock.push_back(A[i].first);
			}else{
				ans+=A[i].second;	// 这是相等的情况，加哪个都无所谓
				upBlock.push_back(A[i].second);
				dowBlock.push_back(A[i].first);
			}
		}
		ll lans=-1e18-7;
		if(!upBlock.empty()){
			sort(upBlock.begin(),upBlock.end(),greater<ll>());
			lans=upBlock[0];
		}
		if(!dowBlock.empty()){
			sort(dowBlock.begin(),dowBlock.end(),greater<ll>());
			lans=max(dowBlock[0],lans);
		}
		ans+=lans;
		cout<<ans<<endl;
	}
}
// AC https://codeforces.com/contest/2047/submission/295161620
/*
https://codeforces.com/contest/2047/submission/295154910
应该是A[i].first==A[i].second的情况出了问题
好像和这个没关系，修了这个问题还是WA了。
https://codeforces.com/contest/2047/submission/295157816
*/

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

https://codeforces.com/contest/2047/submission/295154910

1
2
3
4
5
6
7
if(A[i].first>=A[i].second){
	ans+=A[i].first;
	upBlock.push_back(A[i].second);
}else{
	ans+=A[i].second;
	dowBlock.push_back(A[i].first);
}

应该是A[i].first==A[i].second的情况出了问题

好像和这个没关系，修了这个问题还是WA了。
https://codeforces.com/contest/2047/submission/295157816

最后发现是因为lans的初始化

没事这种lans（算max）的初始化还是直接-1e18+7走起，不管后面怎么样都不会出问题

1
2
3
4
5
6
7
8
9
10
11
ll lans=-1e18-7;
if(!upBlock.empty()){
	sort(upBlock.begin(),upBlock.end(),greater<ll>());
	lans=upBlock[0];
}
if(!dowBlock.empty()){
	sort(dowBlock.begin(),dowBlock.end(),greater<ll>());
	lans=max(dowBlock[0],lans);
}
ans+=lans;
cout<<ans<<endl;

Posted on Edited on

思路讲解

image

由于p给你的一般是素数，一般不用担心b，p互素的问题，除非b%p=0

AC代码

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

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
#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>
// https://www.luogu.com.cn/problem/P2613

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
const int m=19260817;

void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b) x=1,y=0;
	else exgcd(b,a%b,y,x),y-=a/b*x;
}

inline ll getll(){
	char c=getchar();
	ll res=0;
	while (!isdigit(c) && c!=EOF) {
		c=getchar();
	}
	while (isdigit(c)) {
		res=((res<<3)+(res<<1)+c-'0')%m;
		c=getchar();
	}
	return res;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//#ifndef ONLINE_JUDGE
//	freopen("P2631_1.in", "r", stdin);
//#endif
	ll a=getll();
	ll b=getll();
	if(b==0){
		cout<<"Angry!"<<endl;
		return 0;
	}
	ll x,y;
	exgcd(b, m, x, y);
	cout<<(x*a%m+m)%m<<endl;
//#ifndef ONLINE_JUDGE
//	fclose(stdin);
//#endif
	return 0;
}
// AC https://www.luogu.com.cn/record/192866597

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