Znzryb's Blog
0%

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……）

Posted on Edited on

思路讲解

用的tarjan方法求的LCA（倍增我不太会）

参考讲解（树上差分）

image

AC代码

AC
https://www.luogu.com.cn/record/199856000

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
#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>(5e5)+10;
ll N,K;
vector<ll> g[MAXN];
ll fa[MAXN],par[MAXN];
bool vis[MAXN],done[MAXN],vis2[MAXN];
vector<pll> route[MAXN];
ll diff[MAXN];	// 树上差分数组
ll ans[MAXN];	// 原数组
// https://www.luogu.com.cn/problem/P3128
// LCA+树上差分
ll find(int x) {
	if(fa[x]==x) return fa[x];
	fa[x]=find(fa[x]);
	return fa[x];
}
void dfs(int x,int pa) {  // 求LCA以及进行树上差分
	vis[x]=true;fa[x]=x;	// 一开始并查集要指向自己
	par[x]=pa;	// 另外的一个专门记录父节点的数组
	for(int i=0;i<g[x].size();++i) {
		if(vis[g[x][i]]) continue;	// 走过的我们不走了
		dfs(g[x][i],x);
		fa[g[x][i]]=x;	// 并查集指向自己父亲
	}
	for(int i=0;i<route[x].size();++i) {
		ll t=route[x][i].first,idx=route[x][i].second;
		if(vis[t] && !done[idx]) {	// 树上差分操作
			done[idx]=true;	// 避免重复树上差分
			diff[find(t)]-=1;	// 这里-1是因为最近公共祖先会被记两次
			diff[x]+=1;
			diff[t]+=1;			// 在区间开头+1
			diff[par[find(t)]]-=1; // 在区间结束-1
		}
	}
}
// 还原差分数组为原数组
void restorDiff(int x) {
	vis2[x]=true;
	for(int i=0;i<g[x].size();++i) {
		if(vis2[g[x][i]]) continue;	// 走过的我们不走了
		restorDiff(g[x][i]);
		ans[x]+=ans[g[x][i]];
	}
	ans[x]+=diff[x];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i=1;i<=N-1;++i) {
		ll u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=K;++i) {
		ll s,t;
		cin>>s>>t;
		route[s].push_back({t,i});
		route[t].push_back({s,i});
	}
	// 应当认为1的根节点是0或者是无，而不是自己
	dfs(1,0);
	restorDiff(1);
	ll Ans=0;
	for(int i=1;i<=N;++i) {
		Ans=max(Ans,ans[i]);
	}
	cout<<Ans<<endl;
	// for(int i=1;i<=N;++i) {	// debug
	// 	cout<<ans[i]<<' ';
	// }
	// cout<<endl;
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/199856000
*/

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

这道题数据范围好像是有点问题，需要开到5e5+10才行，反正有点离谱，也不知道是我0数错了还是什么，反正有点离谱

Posted on Edited on

思路讲解

赛时最后30min过了，通过网上搜到的结论，

gcd(a,b)=a xor b=a−b（结论，下面是推理过程）gcd(a,b)=a\ xor\ b=a-b（结论，下面是推理过程）

a−b<=a xor b=gcd(a,b)a-b<=a\ xor\ b=gcd(a,b)

gcd(a,b)∗x=a, gcd(a,b)∗y=b→可得a−b=(x−y)∗gcd(a,b)→可得a−b<=gcd(a,b)→又因为a−b>=gcd(a,b)gcd(a,b)=a−bgcd(a,b)*x=a,\ gcd(a,b)*y=b\xrightarrow{可得}a-b=(x-y)*gcd(a,b)\xrightarrow{可得}\\a-b<=gcd(a,b)\xrightarrow{又因为a-b>=gcd(a,b)}gcd(a,b)=a-b

当然不可能每题都用结论嘛，所以看看枚举可不可以过

搞半天发现和我的赛时代码也差不多，jiangly差不多也是我这个做法

最重要的其实就是更换枚举尺度，枚举a太慢了，可以枚举g，进而枚举a时只用枚举g的倍数就行了

AC代码

AC

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

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 <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,A[MAXN];
ll Cnt[MAXN];
ll gcd(ll a,ll b) {
	if(b==0) return a;
	return gcd(b,a%b);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i=1;i<=N;++i) {
		cin>>A[i];
		Cnt[A[i]]+=1;
	}
	// sort(&A[1],&A[N+1]);
	ll ans=0;ll m=*max_element(&A[1],&A[N+1]);
	for(int g=1;g<=m;++g) {
	// 枚举公因数g
		for(int a=g;a<=m;a+=g) {
		// 枚举a
			ll b=a^g;// 判断a，b，g是否符合条件
			if(a<b && gcd(a,b)==g && b<=m) {
				ans+=Cnt[a]*Cnt[b];
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
15
1 1 4 6 6 9 9 8 8 6 7 6 22 26 28

*/

赛时AC记录

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

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
#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];
ll gcd(ll a,ll b) {
	if(b==0) return a;
	return gcd(b,a%b);
}
inline ll lowbit(ll x) {
	return x&(-x);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i=1;i<=N;++i) {
		cin>>A[i];
	}
	sort(&A[1],&A[N+1]);
	ll ans=0;
	for(int i=1;i<=A[N];++i) {
		for(int j=i;j<=A[N]-i;j+=i) {
			if((j^(j+i))!=i) continue;
			ans+=(upper_bound(&A[1],&A[N+1],j)-&A[0]-(lower_bound(&A[1],&A[N+1],j)-&A[0])) *
				(upper_bound(&A[1],&A[N+1],j+i)-&A[0]-(lower_bound(&A[1],&A[N+1],j+i)-&A[0]));
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
7
1 2 3 4 5 6 7

5
2 6 2 3 4
AC
*/

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