题意
给定一个长度为的数组，请你将数组划分为若干连续的段，要求每一段的逻辑与的结果之和最小，问最多划分为多少段
解题思路
根据位与性质：连续位与操作只会让结果不变或变小
由此我们可以得出结论：每一段的逻辑与的结果之和的最小值=将整个数组相与的结果
- 若这个最小值大于，则最多划分成段(因为如果划分成多个段必然会使结果变大)
- 若这个最小值等于，可以采取贪心策略的去划分尽可能多的段：如果一段逻辑与结果为，立即切断，若最后一段不为，则将其并到其前面一段中(因为)，这样可以保证最终的结果为
解题代码
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
| #include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
int sum=a[1],res=0;
for(int i=1;i<=n;i++){
sum&=a[i];
if(sum==0) res++,sum=a[i+1];
}
if(!res) res++;
cout<<res<<"\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
|
题意
给定一个长度为
的序列 ，并给定一个数
每一步可以将序列中的一个数与上
求使序列中出现两个相等的数的最小步数。如果不可能则输出
解题思路
根据位与性质：
因此最多可以分为四种情况：
- 步数为:原序列中本身存在相等的数
- 步数为:原序列存在一个数，与变换后的序列()中的数相等，同时要求
- 步数为:变换后的序列中存在相等的数
- 步数为(即:不存在)：上述情况均不满足
解题代码
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
| #include <bits/stdc++.h>
using namespace std;
void solve()
{
unordered_map<int,int> ma,mb;
int n,x;
cin>>n>>x;
vector<int> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
ma[a[i]]++,mb[a[i]&x]++;
}
for(int i=0;i<n;i++){
if(ma[a[i]]>=2){
cout<<0<<"\n";
return ;
}
}
for(int i=0;i<n;i++){
if(ma[a[i]&x]&&(a[i]&x)!=a[i]){
cout<<1<<"\n";
return ;
}
}
for(auto it:mb){
if(it.second>=2){
cout<<2<<"\n";
return ;
}
}
cout<<-1<<"\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
return 0;
}
|
题意
给你一个长度为的数组和一个整数
可以将这个数组的元素分成几个新的数组
在新数组中，可以改变需要排列元素的顺序，要求新数组中的相邻元素必须满足
求满足条件的新数组的最小个数
解题思路
由此，得出我们的最佳分组策略：
- 将的数或者的数需单独分入一个组中
- 将的数(记其数量为：)和的数(记其数量为：)放入同一组中，放入形式形如:这样交替排列，剩余不能放入交替排列的组的数只能单个成组，最终可以推出由,构成的最小组数
- 不满足上述两种条件的其他元素均需单独成组
我们将数组中的元素中模上放入结果为的桶中
解题代码
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
| #include <bits/stdc++.h>
using namespace std;
void solve()
{
int n,m;
cin>>n>>m;
vector<int> num(m+5,0);
for(int i=0;i<n;i++){
int x;
cin>>x;
num[x%m]++;
}
int res=0;
for(int i=0;i<m;i++){
if((i==0||i*2==m)&&num[i]) res++;
else if(num[i]){
if(num[m-i])
res+=num[m-i]!=num[i]?abs(num[m-i]-num[i]):1,num[m-i]=num[i]=0;
else res+=num[i];
}
}
cout<<res<<"\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
|
题意
给定长度为的串中，可以进行操作: 当前缀中与的个数相等时，可以将前缀进行翻转(，)，问是否通过若干个操作使得
解题思路
我们可以考虑通过将字符串进行按位异或,得到字符串(若,则说明位置，反之则说明)
若前缀能翻转：
- 翻转后不影响前缀中的相对数量，意味着能翻转的前缀永远能翻转，不能翻转的前缀永远不能翻转
- 翻转后不影响字符串前缀之后的字符，翻转大前缀必然影响小前缀
初始前缀中元素被翻转的次数
从后往前遍历(翻转后面的必然影响前面的字符)：
- 若(说明之前的翻转使得)，则需将以结尾的前缀翻转，若不能翻转(判断前缀是否能翻转可以进行预处理出前缀中与的数量是否相等)，则说明不能变换成,反之，则(表示前面的字符翻转次数将增加)
- 反之，则跳过
解题代码
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
| #include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
string s,t;
cin>>s>>t;
vector<int> flag(n,0),a(n);
int cnt=0;
for(int i=0;i<n;i++){
int x=s[i]-'0',y=t[i]-'0';
a[i]=x^y;
cnt+=x;
flag[i]=(2*cnt==i+1);
}
int sum=0;
for(int i=n-1;i>=0;i--){
if(!(a[i]^(sum%2))) continue;
if(!flag[i]){
puts("NO");
return ;
}
sum++;
}
puts("YES");
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
|
题意
给定一个长度为的数组，，试构造一个数组，同时满足：
解题思路
可以构造数组各元素之间呈的倍数关系，即可满足：(或)，选取为离最近的,即满足
解题代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll x)
{
ll res=1;
while(res<x) res<<=1;
if(res==1) return 1;
return res>>1;
}
void solve()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
ll x;
cin>>x;
cout<<f(x)<<" ";
}
cout<<"\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
|