思路：
1.由于最大的数无论放到哪个数组去都还是最大的,因此只能使得另外一个数组的最大的数尽可能的小。
2.因此让另外一个数组进行比较更小的话就交换。
AC Code:
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
vector<int>b(n+1);
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)
if(b[i]>a[i])swap(a[i],b[i]);
sort(a.begin()+1,a.end());
sort(b.begin()+1,b.end());
cout<<a[n]*b[n]<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
时间复杂度 $O(n)$
B. Fun with Even Subarrays
思路：
1.观察题目以后发现最后一个数是不会被操作到的,因此实质上就是让所有的数和最后一个数相等。
2.那么为了保证贪心的正确性,就需要把数组分成两个区间,一个是已经和最后一个数相等的区间,和需要操作的区间。
3.在这个过程中每次都尽量使得相等的区间尽可能的大最后完整覆盖全部[L,R]即可！！！
当然得注意一下使用while时候会产生比较麻烦的边界问题,因此需要清晰的分清两个区间的边界！！！
AC Code：
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
int ans=0;
int l=n-1;//需要操作区间的右边界
while(l>=1)
{
while(a[l]==a[n]&&l>=1)l--;//找到和a[n]不等的位置 l=0
// cout<<l<<endl;
if(l>=1)ans++;
l=2*l-n;//需要操作区间的右边界
}
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
首先此处运用了一个构造的技巧.定义了一种运算$Cal(x)$即对x取反
int cal(int x)
{
return x^(n-1);//取反
}
值得注意的是这里的n-1二进制下每一位都是1,因此和$x$进行$x\oplus n-1$会对x的每一位取反。
由于这里是从0~n-1即每一种可能的0 1排列都存在,因此从0~n-1中的任意一个数都存在cal(x)
利用以上性质可以构造出我们需要的$k$
思路：
1.$1\leq k\leq n-2$
此时构造任意一个数字都可以利用上述性质,首先$k\&{(n-1)}=k$,此时会使得$cal(k)$和$cal(n-1)$无法配对
但是 $cal(n-1)=0$因此可以视作万能数,可以和任何数与或且结果是0
2.$k=n-1$,此时可以使用一个技巧,先构造$n-2$再构造$1$最后由$n-2+1=n-1$
值得一提的是,由于n=4时 这时候由于只有两对数,而上述过程涉及到了三对数,因而 需要在$n=4$时特判一下无法构造出$n-1$.
详细证明参见传送门.
双指针法
AC Code:
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n,k;
int cal(int x)
{
return x^(n-1);//取反
}
void solve()
{
cin>>n>>k;
if(n==4&&k==n-1)
{
cout<<"-1"<<endl;
}else
{
if(k==n-1)
{
cout<<n-2<<' '<<n-1<<endl;
cout<<n-3<<' '<<1<<endl;
cout<<0<<' '<<2<<endl;
for(int i=3;i<=n/2-1;i++)cout<<i<<' '<<cal(i)<<endl;
}else
{
cout<<k<<' '<<n-1<<endl;
if(k!=0)cout<<0<<' '<<cal(k)<<endl;
for(int i=1;i<=n/2-1;i++)
if(i!=cal(k)&&i!=k)cout<<i<<' '<<cal(i)<<endl;
}
}
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
时间复杂度$O(n)$
D. Range and Partition
思路：
1.首先一定需要得到的是$inside$的最小值.
Proof:首先假定一个$Range[X,Y]$,其次构造一个数组$b$用于记录$a$中每一个数组是否在范围之内
即：当$a_i$在[X,Y]之内时,对应的$b_i$取值为1反之取值为-1。这一步十分重要是解出$inside_{min}$至关重要的一步.
其次构造$b$的前缀$sum_b$,此时我们可以观察$sum_b$发现几条重要性质:
1.假定取任意$Range[l,r]$一定需要满足的是与其对应的$b$数组的前缀和数组$sum_n\ge{k}$
解释一下：就是说因为需要分$k$段因此,就需要找$k+1$个点来组成$k$个不同的区间,同时最少每次不同的点
在$sum$数组上增加的值至少是1(保证每段区间都是$inside\>outside$)就需要使得这$k+1$个点的前缀应该是递增的 至少是按1递增的.
$$psum_n \geq k$$
$$\sum\limits_{i=1}^n b_i \geq k$$
$$\sum\limits_{i=1}^n (-1 + 2\cdot [x\le a_i\le y]) \geq k$$
$$\sum\limits_{i=1}^n [x\le a_i\le y] \geq \lceil{\frac{k+n}{2}}\rceil$$
最后根据前缀构造一下,得到$inside$的最小值：$\lceil{\frac{k+n}{2}}\rceil$
AC Code:
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int cal(int x)
{
if(x&1)return (x+1)/2;
return x/2;
}//进行上取整运算
struct node{
int l,r,in,out;
};
void solve()
{
int n,k;
cin>>n>>k;
vector<int>a(n+10,INF);
vector<int>A(n+10,INF);
for(int i=1;i<=n;i++)cin>>a[i],A[i]=a[i];
sort(A.begin()+1,A.end());
int tmp=INF;
int L,R;
for(int l=1,r=1;l<=n&&r<=n;l++)
{
while(r-l+1<cal(k+n)&&r<=n)r++;
int cur=A[r]-A[l];
if(cur<tmp&&r-l+1>=cal(k+n))
{
tmp=cur;
L=A[l],R=A[r];
}//更新范围
}
cout<<L<<' '<<R<<endl;
int in=0,out=0;
int curl=1,curr=1;
vector<node>ans;
for(int i=1;i<=n;i++)
{
if(a[i]>=L&&a[i]<=R)in++;
else out++;
curr=i;
if(in>out)
{
ans.push_back({curl,curr,in,out});
in=0,out=0;
curl=i+1,curr=i+1;//更新至下一位
}//cnt>=k
if(out>=in&&i==n)
{
while(in<=out)
{
auto t=ans.back();
in+=t.in,out+=t.out;
ans.pop_back();
curl=t.l;
}
ans.push_back({curl,n,in,out});
}//特别的处理一下最后一个区间
}
while(ans.size()>k)
{
auto a=ans.back();
ans.pop_back();
auto b=ans.back();
ans.pop_back();
ans.push_back({b.l,a.r,a.in+b.in,a.out+b.out});//合并区间
}
for(auto c:ans)cout<<c.l<<' '<<c.r<<endl;
return ;
}
//1 1 1 5 5 5 5 5 5 5 5 5 5
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
正好不会c就看到了TAT