B. Kevin and Geometry
- vector的删除，无论是删除单个元素还是区间，一定是传入迭代器，而且区间一定是左闭右开区间
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a.begin(),a.end());
reverse(a.begin(),a.end());
int maxn=0;
for(int i=1;i<a.size();i++)
{
if(a[i]==a[i-1])
{
maxn=a[i];
a.erase(a.begin()+i-1,a.begin()+i+1);
break;
}
}
bool f=false;
for(int i=0;i+1<a.size();i++)
{
if(a[i]-a[i+1]<2*maxn)
{
f=true;
cout<<maxn<<" "<<maxn<<" "<<a[i+1]<<" "<<a[i]<<"\n";
break;
}
}
if(f==false)
{
cout<<"-1\n";
}
}
return 0;
}
E. Kevin and And
- 直接贪心是不对的。因为消2次的最优解未必包含消1次的最优解
- C++ accumulate:对范围内的元素求和或折叠
- int __builtin_ctz(unsigned int x) consecutive、tail、zero 可以辅助位运算递推
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int f[1030],g[100005][15],id[100005];
struct t
{
int delta;
int i;
};
auto cmp=[](t a,t b)
{
if(a.delta!=b.delta)
{
return a.delta<b.delta;
}
return a.i<b.i;
};
priority_queue<t,vector<t>,decltype(cmp) >q(cmp);
int n,m,k;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
for(int j=1;j<=m;j++)
{
g[i][j]=a[i];
}
id[i]=0;
}
long long sum=accumulate(a+1,a+n+1,0ll);
vector<int>b(m);
for(int i=0;i<m;i++)
{
cin>>b[i];
}
f[0]=INT_MAX;
for(int i=1;i<(1<<m);i++)
{
int x=__builtin_ctz(i);
f[i]=f[i^(1<<x)]&b[x];
for(int j=1;j<=n;j++)
{
int cnt=__builtin_popcount(i);
g[j][cnt]=min(g[j][cnt],a[j]&f[i]);
}
}
for(int i=1;i<=n;i++)
{
q.push((t){a[i]-g[i][1],i});
}
while(k--&&q.size())
{
t n1=q.top();
q.pop();
int i=n1.i;
id[i]++;
sum=sum-n1.delta;
a[i]=a[i]-n1.delta;
if(id[i]<m)
{
q.push((t){a[i]-g[i][id[i]+1],i});
}
}
while(q.size())
{
q.pop();
}
cout<<sum<<"\n";
}
return 0;
}