问题：
观察到，要选找位数最高的数左移k位，才可能使或值最大
尝试通过两次循环而不是排序找出所有最高位元素。
时间复杂度从$O(nlogn)$到$O(n)$
随后，对取出的最高位元素各自尝试左移，找出最大答案。
时间复杂度约$O(nlogn)$
整体时间复杂度约为$O(nlogn)$
成功TLE
代码：
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
| class Solution {
public:
long long maximumOr(vector<int>& nums, int k) {
auto maxIt=max_element(nums.begin(),nums.end());
int maxIndex=maxIt-nums.begin();
int len=nums.size(),big=0,temp=nums[maxIndex];
while(temp){
temp>>=1;
big++;
}
big--;
vector<int> maxIndexs;
for(int i=0;i<len;i++){
if(nums[i]>>big!=0)
maxIndexs.push_back(i);
}
long long ans=0;
for(auto&Index:maxIndexs){
nums[Index]=nums[Index]<<k;
ans=max(ans,cal(nums));
nums[Index]=nums[Index]>>k;
}
return ans;
}
long long cal(vector<int>&nums){
long long res=0;
for(auto&a:nums){
res=res|a;
}
return res;
}
};
|
改进思路：
将逐个左移的操作压缩时间复杂度，先用O(n)时间复杂度处理前缀与后缀或数，以达到降低每次取或的时间复杂度
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
| class Solution {
public:
long long maximumOr(vector<int>& nums, int k) {
auto maxIt=max_element(nums.begin(),nums.end());
int maxIndex=maxIt-nums.begin();
int len=nums.size(),big=0;
long long temp=nums[maxIndex];
while(temp){
temp>>=1;
big++;
}
big--;
vector<int> maxIndexs;
for(int i=0;i<len;i++){
if(nums[i]>>big!=0)
maxIndexs.push_back(i);
}
vector<long long> pre1(len,0),pre2(len,0);
pre1[0]=nums[0];
pre2[len-1]=nums[len-1];
for(int i=1,j=len-2;i<len;i++,j--){
pre1[i]=pre1[i-1]|nums[i];
pre2[j]=pre2[j+1]|nums[j];
}
long long ans=0;
for(auto&Index:maxIndexs){
long long temp=0;
if(len==1)
temp=(long long)nums[Index]<<k;
else if(Index==0)
temp=pre2[1]|(long long)nums[Index]<<k;
else if(Index==len-1)
temp=pre1[len-2]|((long long)nums[len-1]<<k);
else
temp=pre1[Index-1]|((long long)nums[Index]<<k)|pre2[Index+1];
ans=max(ans,temp);
}
return ans;
}
};
|
简单水题
关键在于其搜索分界点是sqrt(n)
但是不能在分界点右边找
在右边查找的时间复杂度为$O(n - n^{\frac{1}{2}})$，而在分界点左边的时间复杂度是$O(n^{\frac{1}{2}})$，在n较大时差别尤其明显
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin>>n;
int l=sqrt(n);
for(int i=2;i<=l;i++){
if(n%i==0)
cout<<n/i;
}
return 0;
}
|
关闭输入同步流黑魔法
1
| std::ios::sync_with_stdio(0)
|
素数筛
P3383 【模板】线性筛素数
欧拉筛：CSDN欧拉筛与埃式筛参考博客
使用了bitset数组代替bool
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
| #include<bits/stdc++.h>
using namespace std;
bitset<100000010> noP;
vector<int> primer;
int main(){
ios::sync_with_stdio(0);
int n,q;
cin>>n>>q;
for(int i=2;i<=n;i++){
if(noP[i]==0)
primer.push_back(i);
for(int len=primer.size(),j=0;j<len;j++){
if(primer[j]*i>n)
break;
noP[primer[j]*i]=1;
}
}
for(int i=0;i<q;i++){
int a;
cin>>a;
cout<<primer[a-1]<<"\n";
}
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
| #include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
const int MAXN = 30;
int n;
string a[MAXN];
bool compare(const string& _a,const string& _b){
return _a>_b;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
a[i] = to_string(temp);
}
sort(a,a+n,compare);
string res = "";
for(int i=0;i<n;i++){
res+=a[i];
}
cout<<res<<endl;
return 0;
}
|
得分：75分
原因：整数按字典序排序，虽然可以正确处理$64$排在$598$这种情况，但是并不能正确处理$32$与$321$的关系。
如果按字典序排序，那么$321$应该在$32$前面。但在本题之中，$321$与$32$之间的顺序关系应该是$32321$，因为$1$小于$3$
因此，不能比较字典序，因为那样会在前缀相同的情况下，把长的放到前面。
实际上，在前缀相同时，应该比较的是超出部分的第一位与另一个字符串的第一位，因此应该稍作修改比较函数
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<iostream>
#include <vector>
#include<algorithm>
using namespace std;
const int MAXN = 30;
int n;
string a[MAXN];
bool compare(const string& _a,const string& _b){
return _a+_b>_b+_a;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
a[i] = to_string(temp);
}
sort(a,a+n,compare);
string res = "";
for(int i=0;i<n;i++){
res+=a[i];
}
cout<<res<<endl;
return 0;
}
|
本题关键：如何理解士兵的转向。
由于士兵相向之后必定转向，且转向无需耗费时间，因此可以认为，当他们开始行动时，就会不断转向转向转向，直到中间的相向对全部消除。
既然如此，最后的状态必然是： 左出口 < < < < < > > > > > > > > > 右出口 ，类似于这种结构，只需要针对士兵位置，特化出最长时间情况（全部同向）和最短时间情况（在中点左右分段）即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e5+10;
int l,n,a[MAXN];
int main(){
cin>>l>>n;
int min_time=0;
int max_time=0;
for(int i=0;i<n;i++){
int t;
cin>>t;
a[t]=1;
min_time = max(min_time,min(t,l+1-t));
max_time = max(max_time,max(t,l+1-t));
}
cout<<min_time<<" "<<max_time;
return 0;
}
|
