|
A. Min Max Swap
思路：
为了使两个序列最大值的乘积最小，我们可以将同一个位置比较大的元素全部放在系列a中，比较小的全部放在b中，这样两个序列最大值的乘积一定最小。
#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
const int maxn=2e5+100;
int main(){
iostream::sync_with_stdio(false);
int t; cin>>t;
while(t--){
int n,a[105],b[105]; cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
cin>>b[i];
if(b[i]>a[i]) swap(a[i],b[i]);
}
int maxx1=0,maxx2=0;
for(int i=1;i<=n;i++){
maxx1=max(a[i],maxx1);
maxx2=max(b[i],maxx2);
}
cout<<maxx1*maxx2<<endl;
}
return 0;
}
B. Fun with Even Subarrays Swap
思路：
由于我们只能让右边的元素替代左边的元素，显然最后的结果一定是每个元素都等于元素a[n]。 并且为了让替换次数最少，我们每次替换的数目cnt等于序列右边连续的值为a[n]的元素个数。所以我们可以从n-1开始从右往前遍历，当找到值不等于a[n]的元素时，我们将它及它前面cnt-1个元素全部替换为a[n]，并且结果ans+1。一直遍历到0为止。
时间复杂度：O(n)
#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
const int maxn=2e5+100;
int a[maxn];
int main(){
iostream::sync_with_stdio(false);
int t; cin>>t;
while(t--){
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int l=n-1,cnt=1,ans=0;
while(l){
while(a[l]==a[n]) l--,cnt++;
if(l<=0) break;
ans++;
for(int i=max(l-cnt+1,1);i<=l;i++) a[i]=a[n];
}
cout<<ans<<endl;
}
return 0;
}
C. And Matching
思路：
若a&b==0 ,例a=1001,b=0110,那么显然a=b^1111( ^是异或)。所以我们可以定义函数f(a)=b， 则函数返回值便是a^(n-1)。 由于0<=k<=n-1，我们可以分以下三种情况讨论：
1.k==0, 我们只需要输出0~n/2（包括0，不包括n/2）中每一个a和f(a)即可，这样每一对取位运算的交的和一定为0。
2.k==n-1, 首先需要知道,n==4的时候无解，输出-1。而其他情况一定有解，读者可以试着去判断。对于其他情况，我们可以取一对位运算作交为n-2和一对位运算交为1，其他每对和都为0即可。（当然还有其他情况，比如取交为n-3和交为2之类的）。此时一种情况是输出一对n-2和n-1，一对1和3和一对0和n-4，其他的我们只需要输出0~n/2（包括0，不包括n/2和已输出的每一个数）中每一个a和f(a)即可，这样每一对取位运算的交的和一定为0。
3.k>0&&k<n-1, 我们可以取一对位运算作交为k的，其他每对和都为0即可。此时结果是是输出一对k和n-1和一对0和f(k)，其他的我们只需要输出0~n/2（包括0，不包括n/2和已输出的每一个数）中每一个a和f(a)即可，这样每一对取位运算的交的和一定为0。
#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
const int maxn=2e4+100;
ll f(ll x,ll n){
return x^(n-1);
}
int main(){
iostream::sync_with_stdio(false);
int t; cin>>t;
while(t--){
ll n,k; cin>>n>>k;
if(k==0){
for(ll i=0;i<n/2;i++) cout<<i<<" "<<f(i,n)<<endl;
}
else if(k==n-1){
if(n==4) cout<<"-1"<<endl;
else{
cout<<1<<" "<<3<<endl;
cout<<n-2<<" "<<n-1<<endl;
cout<<0<<" "<<n-4<<endl;
for(ll i=2;i<n/2;i++){
if(i==3)continue;
cout<<i<<" "<<f(i,n)<<endl;
}
}
}
else{
cout<<0<<" "<<f(k,n)<<endl;
cout<<k<<" "<<n-1<<endl;
for(ll i=1;i<n/2;i++){
if(i==k||i==f(k,n)) continue;
cout<<i<<" "<<f(i,n)<<endl;
}
}
}
return 0;
}
|