Znzryb's Blog
0%

Posted on Edited on

思路讲解

这句话可以好好琢磨一下

image

具体来说就是这样

我先根据题解的这句话写一写

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75129359

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10,mod=static_cast<ll>(1e9)+7;
ll N,T;
char maze[5][MAXN];
set<char> col[5];
ll factorial[15];
inline ll C(ll k,ll n) {
	// factorial[n]/factorial[n-k] 是排列数，组合数不要排列，所以再除factorial[k]
	ll res=factorial[n]%mod/((factorial[k]%mod)*(factorial[n-k]%mod));
	return res%mod;
}
void solve(){
	cin>>N;
	for(int i=0;i<5;++i) {
		col[i].clear();
	}
	vector<ll> vis(11,-1);
	vector<ll> cnt(4,0);
	set<ll> remele;
	for(int i=1;i<=9;++i) {
		remele.insert(i);
	}
	for(int i=1;i<=3;++i) {
		for(int j=1;j<=N;++j) {
			cin>>maze[i][j];
			col[j%3].insert(maze[i][j]);
		}
	}
	for(int i=1;i<=N;++i) {	// 排除一列中有多个重复元素的情况
		if(maze[1][i]==maze[2][i] && maze[1][i]!='?') {cout<<0<<'\n';return;}
		if(maze[1][i]==maze[3][i] && maze[1][i]!='?') {cout<<0<<'\n';return;}
		if(maze[2][i]==maze[3][i] && maze[2][i]!='?') {cout<<0<<'\n';return;}
	}
	for(int i=0;i<3;++i) {
		if(col[i].size()>=5) {cout<<"0\n";return;}
		if(col[i].size()==4 && col[i].find('?')==col[i].end()) {cout<<"0\n";return;}	// 没找到问号且包含四个元素也是无解的
		for(auto j:col[i]) {
			if(j=='?') continue;
			if(vis[j-'0']!=-1) { // 该元素已经被其他列占有
				cout<<0<<'\n';
				return;
			}
			vis[j-'0']=i;	// 该元素被该列占有
			cnt[i]+=1;	// 该列所拥有元素+1
			remele.erase(j-'0');
		}
	}
	// 列元素分配方案*问号分配方案=答案
	ll qm=1;
	// 计算问号分配方案
	for(int j=1;j<=N;++j) {
		ll qmcnt=0;	// 统计问号数量(question mark)
		for(int i=1;i<=3;++i) {
			if(maze[i][j]=='?') qmcnt+=1;
		}
		if(qmcnt==0) continue;
		if(qmcnt==2||qmcnt==1) qm=(qmcnt*qm)%mod;
		else qm=(6*qm)%mod;
	}
	qm=qm%mod;
	// 计算元素分配方案
	ll ele=1;
	ll rem=remele.size();
	for(int i=0;i<3;++i) {
		if(cnt[i]==3) continue;
		ele*=C(3-cnt[i],rem);
		rem-=3-cnt[i];
	}
	cout<<((ele%mod)*(qm%mod))%mod<<'\n';
	// cout<<"debug\n";
	// cout<<ele<<' '<<qm<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	factorial[0]=1;
	for(int i=1;i<=14;++i) {
		factorial[i]=(factorial[i-1]*i)%mod;
	}
	while (T--) {
		solve();
	}
	return 0;
}
/*

1
3
723
18?
?9?

1
3
13?
1??
2??

*/

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

1
2
3
4
5
6
1
3
13?
1??
2??

以下程序没有处理一列中有多个重复元素的情况

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10,mod=static_cast<ll>(1e9)+7;
ll N,T;
char maze[5][MAXN];
set<char> col[5];
ll factorial[15];
inline ll C(ll k,ll n) {
	// factorial[n]/factorial[n-k] 是排列数，组合数不要排列，所以再除factorial[k]
	ll res=factorial[n]%mod/((factorial[k]%mod)*(factorial[n-k]%mod));
	return res%mod;
}
void solve(){
	cin>>N;
	for(int i=0;i<5;++i) {
		col[i].clear();
	}
	vector<ll> vis(11,-1);
	vector<ll> cnt(4,0);
	set<ll> remele;
	for(int i=1;i<=9;++i) {
		remele.insert(i);
	}
	for(int i=1;i<=3;++i) {
		for(int j=1;j<=N;++j) {
			cin>>maze[i][j];
			col[j%3].insert(maze[i][j]);
		}
	}
	for(int i=0;i<3;++i) {
		if(col[i].size()>=5) {cout<<"0\n";return;}
		if(col[i].size()==4 && col[i].find('?')==col[i].end()) {cout<<"0\n";return;}	// 没找到问号且包含四个元素也是无解的
		for(auto j:col[i]) {
			if(j=='?') continue;
			if(vis[j-'0']!=-1) { // 该元素已经被其他列占有
				cout<<0<<'\n';
				return;
			}
			vis[j-'0']=i;	// 该元素被该列占有
			cnt[i]+=1;	// 该列所拥有元素+1
			remele.erase(j-'0');
		}
	}
	// 列元素分配方案*问号分配方案=答案
	ll qm=1;
	// 计算问号分配方案
	for(int j=1;j<=N;++j) {
		ll qmcnt=0;	// 统计问号数量(question mark)
		for(int i=1;i<=3;++i) {
			if(maze[i][j]=='?') qmcnt+=1;
		}
		if(qmcnt==0) continue;
		if(qmcnt==2||qmcnt==1) qm=(qmcnt*qm)%mod;
		else qm=(6*qm)%mod;
	}
	qm=qm%mod;
	// 计算元素分配方案
	ll ele=1;
	ll rem=remele.size();
	for(int i=0;i<3;++i) {
		if(cnt[i]==3) continue;
		ele*=C(3-cnt[i],rem);
		rem-=3-cnt[i];
	}
	cout<<((ele%mod)*(qm%mod))%mod<<'\n';
	// cout<<"debug\n";
	// cout<<ele<<' '<<qm<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	factorial[0]=1;
	for(int i=1;i<=14;++i) {
		factorial[i]=(factorial[i-1]*i)%mod;
	}
	while (T--) {
		solve();
	}
	return 0;
}
/*

1
3
723
18?
?9?

1
3
13?
1??
2??

*/

Posted on Edited on

思路讲解

P2880 [USACO07JAN] Balanced Lineup G

树状数组做RMQ问题

我的思路是肯定要预处理这个东西，然后重量加减应该没那么复杂，就是加在第一块上就行
然后我们其实就是要求需要加了多少嘛
我们可以把这个问题转化为RMQ，即该区间内最大的A[i]-sumA[i-1];

query的时候这样输出就行

1
cout<<max(query(l+1,r)+sumA[l-1],0LL)<<'\n';

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75111878

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10,MINval=static_cast<ll>(-1e18)-10;
ll N,Q,A[MAXN],sumA[MAXN],tr[MAXN];
inline ll lowbit(ll x) {
	return x&(-x);
}
// 将p位置改为x (我懒得建树，这题当然不需要在线修改)
inline void change(ll p, ll x) {
	while (p<=N) {
		tr[p]=x;  // 这个之所以可以直接赋值是因为我们这道题的change函数调用是从小区间到大区间
		// 可以模拟一下8，8-1=7  8-2=6 8-4=4 相当于把8下面的全部区间都遍历了一遍（lowbit（8）=8）
		for(int i=1;i<lowbit(p);i<<=1) {
			tr[p]=max({tr[p-i],tr[p],x});
		}
		p+=lowbit(p);
	}
}

inline ll query(ll l,ll r) {
	ll res=MINval;
	while (l<=r) {
		if(r-lowbit(r)<l) {
			res=max(A[r]-sumA[r-1],res);
			r-=1;
		}else {
			res=max(tr[r],res);
			r-=lowbit(r);
		}
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i=1;i<=N;++i) {	// 初始化树状数组
		tr[i]=MINval;
	}
	// 我的思路是肯定要预处理这个东西，然后重量加减应该没那么复杂，就是加在第一块上就行
	// 然后我们其实就是要求需要加了多少嘛
	// 我们可以把这个问题转化为RMQ，即该区间内最大的A[i]-sumA[i-1];
	for(int i=1;i<=N;++i) {
		cin>>A[i];
		sumA[i]=sumA[i-1]+A[i];
		change(i,A[i]-sumA[i-1]);
	}

	for(int i=1;i<=Q;++i) {
		ll l,r;
		cin>>l>>r;
		if(l==r) {cout<<0<<'\n';continue;}	// 特判特殊情况
		cout<<max(query(l+1,r)+sumA[l-1],0LL)<<'\n';
	}
	// cout<<"debug:\n";
	// for(int i=1;i<=N;++i) {
	// 	cout<<tr[i]<<' ';
	// }
	// cout<<'\n';
	return 0;
}
/*
6 4
1 1 4 5 1 4
1 2
1 3
2 5
1 6

15 6
5 23 56 71 13 63 24 61 2 76 28 37 46 12 43
1 15
7 8
8 9
4 7
4 11
9 10

28
37
0
0
0
74

*/

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

WA

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75111646

1
2
3
for(int i=1;i<lowbit(p);i<<=1) {
			tr[p]=max({tr[p-i],tr[p],x});
	}

i<lowbit(p)，你想lowbit（p）就是其表示区间的长度

Posted on Edited on

思路讲解

image

这是判断字符串可爱度的代码(也就是这场的D题)，可以发现我们发现要尽量让一个字母倒数第二次出现位置尽可能小，第二次出现位置尽可能大，才有可能使字符串“可爱度”尽可能小（当然，如果该字符没有出现或只出现一次，那自然不会对可爱度有贡献）

我们先来证明一下这个无解条件

1
if(N-26>M) {cout<<"NO\n";return;}

所以说字符串长度>26，可爱度必然不可能=0

参考题解

https://blog.nowcoder.net/n/906fd00ff386438b9d63013a3760e73a

image

通过取模让各个字符之间的距离保持在N-M+1（a……a的长度为N-M+1）

1
2
3
4
5
6
7
8
9
10
11
void solve(){
	cin>>N>>M;
	// 各种排除
	if(N<=M) {cout<<"NO\n";return;}
	if(N-26>M) {cout<<"NO\n";return;}
	cout<<"YES\n";
	for(int i=0;i<N;++i) {
		cout<<char('a'+i%(N-M));
	}
    cout<<'\n';
}

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75110195

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;
ll N,T,M;

void solve(){
	cin>>N>>M;
	// 各种排除
	if(N<=M) {cout<<"NO\n";return;}
	if(N-26>M) {cout<<"NO\n";return;}
	cout<<"YES\n";
	for(int i=0;i<N;++i) {
		cout<<char('a'+i%(N-M));
	}
    cout<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}
/*

1
16 6
abcdefghijabcdef

2
4 3
3 3

*/

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

Posted on Edited on

思路讲解

https://blog.csdn.net/lymww/article/details/122566800

bfs路径还原可以用bfs生成树（也就是树）的性质，即每个节点只有唯一的父节点这一性质进行还原，具体就是在bfs搜索过程中记录节点的父节点

那么这道题就是bfs找到最近的1，然后路径还原就行

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75103248

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<int,4> arr;
const ll MAXN=110;
ll N,T;
bool vis[MAXN][MAXN];	// 总体vis
char maze[MAXN][MAXN];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void solve(){
	vector<arr> out;
	cin>>N;
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=N;++i) {
		for(int j=1;j<=N;++j) {
			cin>>maze[i][j];
		}
	}
	for(int i=1;i<=N/2;++i) {
		for(int j=1;j<=N/2;++j) {
			if(maze[i][j]=='1') {vis[i][j]=true;continue;}
			queue<pii> q;
			q.push({i,j});
			vector<vector<pii> > pa(N+1,vector<pii>(N+1,{0,0}));
			pa[i][j]={i,j};
			// bfs
			while (!q.empty()) {
				int x=q.front().first,y=q.front().second;
				q.pop();
				for(int k=0;k<=3;++k) {
					int u=x+dx[k],v=y+dy[k];
					if(u<1||u>N) continue;
					if(v<1||v>N) continue;
					if(vis[u][v]) continue;	// 不能动已经确定的点
					if(pa[u][v].first!=0) continue;	// 确定了父节点的点，说明是跑过的点，跳过
					pa[u][v]={x,y};
					q.push({u,v});
					if(maze[u][v]=='1') {	// 找到了，回溯路径
						int o=u,p=v;
						// 找根节点
						while (pa[o][p].first!=o || pa[o][p].second!=p) {
							swap(maze[o][p],maze[pa[o][p].first][pa[o][p].second]);
							out.push_back({o,p,pa[o][p].first,pa[o][p].second});
							tie(o,p)=pa[o][p];
							// o=pa[o][p].first;
							// p=pa[o][p].second;
						}
						// cout<<"pa:"<<i<<' '<<j<<'\n';
						// for(int i1=1;i1<=N;++i1) {
						// 	for(int j1=1;j1<=N;++j1) {
						// 		cout<<pa[i1][j1].first<<'_'<<pa[i1][j1].second<<' ';
						// 	}
						// 	cout<<'\n';
						// }
						// swap(maze[i][j],maze[u][v]);
						goto outer;	// 跳出整个bfs
					}
				}
			}
			outer:
			vis[i][j]=true;
		}
	}
	cout<<out.size()<<'\n';
	for(int i=0;i<out.size();++i) {
		cout<<out[i][0]<<' '<<out[i][1]<<' '<<out[i][2]<<' '<<out[i][3]<<'\n';
	}
	// cout<<"debug\n";
	// for(int i=1;i<=N;++i) {
	// 	for(int j=1;j<=N;++j) {
	// 		cout<<maze[i][j];
	// 	}
	// 	cout<<'\n';
	// }
	// for(int i=1;i<=N;++i) {
	// 	for(int j=1;j<=N;++j) {
	// 		cout<<vis[i][j];
	// 	}
	// 	cout<<'\n';
	// }
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}
/*

1
4
1111
0000
0000
0000

1
4
0001
0010
0100
1000

1
4
1010
0100
0100
0000

*/

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

这个蓝注释的地方就是原来有错的地方，这种只有同时更新（用tie，或者其他才行）

否则先更新了o，后面p的结果就不对了

image

还有什么out忘记清空什么的，这就不多说了

Posted on Edited on

思路讲解

说是双指针，但是实际上是用双指针求出一个最长的好区间（同起点中），然后运用一些其他方法求出该最长双生数组中包含几个双生数组（用的是下面的前缀和）

image

这个问题转化还是很厉害的

所谓的好区间就是只有两种数的区间

至于题解讲的什么区间重叠问题好像无所谓？反正以我的统计方法，两区间统计出来的答案不会有重叠。

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74994669

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;
ll N,T,A[MAXN];
inline void rightJ(int &j,map<ll,ll> &Cnt) { // 右移j
	++j;
	if(Cnt.find(A[j])!=Cnt.end()) {
		Cnt[A[j]]+=1;
	}else {
		Cnt[A[j]]=1;
	}
}
inline void  rightI(int &i,map<ll,ll> &Cnt) { // 右移i
	Cnt[A[i]]-=1;
	if(Cnt[A[i]]==0) Cnt.erase(A[i]);	// 这个数被减没了
	++i;
}

void solve(){
	cin>>N;
	for(int i=1;i<=N;++i) {
		cin>>A[i];
	}
	map<ll,ll> Cnt;
	Cnt[A[1]]=1;
	vector<ll> end(N+1);	// 以该点为起点的极大好区间（只含两种数数组的）的最大终点（只有是最长双生数组的起点，其值才有意义）
	fill(end.begin(),end.end(),0);
	// 双指针
	for(int i=1,j=1;j<=N && i<=N && i<=j;) { // 用双指针求最长好区间
		//cout<<i<<' '<<j<<'\n';
		// 看了一眼题解，发现是这样的，这个双指针只是用来统计极长含两种数数组的
		if(Cnt.size()==2) {
			end[i]=max(end[i],j*1LL);
			rightJ(j,Cnt);
		}else if(Cnt.size()==1) {
			rightJ(j,Cnt);
		}else {	// 不满足条件，即是size>2，需要减少区间
			rightI(i,Cnt);
		}
	}
	ll ans=0;
	vector<ll> sumA(N+10);
	// 答案统计阶段
	for(int i=1;i<=N;++i) {
		if(end[i]!=0) {	// 把不同的两种元素看成1，-1，只有前缀和相减等于0的区间才是双生数组
			// 前缀和计数数组
			unordered_map<ll,ll> sumCnt;
			sumA[i-1]=0;
			sumCnt[0]=1;	// sum为0的肯定有一个（就是起始前面一个嘛，你也可以理解为空）
			ll flag=0;	// 用来实现上面的画的辅助变量
			for(int j=i;j<=end[i];++j) {
				if(flag==A[j] || flag==0) {
					sumA[j]=sumA[j-1]+1;
					flag=A[j];
					// 查找在他之前的区间和为sumA[j](和sumA[j]相同的才相减为0，是双生数组)的数量
					ans+=sumCnt.find(sumA[j])==sumCnt.end()? 0:sumCnt[sumA[j]];
					sumCnt[sumA[j]]= sumCnt.find(sumA[j])==sumCnt.end()? 1:sumCnt[sumA[j]]+1;
				}else {
					sumA[j]=sumA[j-1]-1;
					ans+=sumCnt.find(sumA[j])==sumCnt.end()? 0:sumCnt[sumA[j]];
					sumCnt[sumA[j]]= sumCnt.find(sumA[j])==sumCnt.end()? 1:sumCnt[sumA[j]]+1;
				}
			}
		}
	}
	cout<<ans<<endl;
	// for(int i=1;i<=N;++i) {
	// 	cout<<end[i]<<' ';
	// }
	// cout<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}
/*
1
7
1 2 1 1 3 3 4

*/

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