目录
A 巴厘岛的雕塑
\(n\) 个数分为若干组，组数不少于 \(a\) 且不多于 \(b\)。最小化各组和的 \(OR\) 值。
\(n \le 2000\)，\(1=a \le b \le n\) 或 \(n \le 100\)，\(1 \le a \le b\)。
key：贪心，DP
按位处理，从高到低依次尝试每一位是否能够是 \(0\)。\(DP\) 求出在满足高位的条件下的最少分组数和最多分组数即可。
但似乎这个做法是伪的，uoj上没有过。
重新考虑 \(DP\) 状态，考虑到某一位能否分若干组即可。不想写了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
typedef long long ll;
int n,a,b,dp[N][2];ll s[N],res;
int main(){
scanf("%d%d%d",&n,&a,&b);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
s[i]=s[i-1]+x;
}
res=(1ll<<45)-1;
for(int d=44;d>=0;d--){
ll chk=res-(1ll<<d);
dp[0][0]=dp[0][1]=0;
for(int i=1;i<=n;i++){
dp[i][0]=1e9;dp[i][1]=-1e9;
for(int j=0;j<i;j++)
if((s[i]-s[j]|chk)==chk){
dp[i][0]=min(dp[i][0],dp[j][0]+1);
dp[i][1]=max(dp[i][1],dp[j][1]+1);
}
}
if(dp[n][1]>=a&&dp[n][0]<=b)res=chk;
}
printf("%lld\n",res);
return 0;
}
B 雅加达的摩天楼
key：最短路，建图技巧
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int N=3e4+5,M=1e7+5;
int n,m,r,s,t,dis[N],vis[N];
int head[N],nxt[M],ver[M],val[M],tot;
void add(int u,int v,int w){
ver[++tot]=v;val[tot]=w;
nxt[tot]=head[u];head[u]=tot;
}
map<pii,vi> MP;vi d[N];
priority_queue<pii> Q;
int main(){
scanf("%d%d",&n,&m);
for(int i=1,b,p;i<=m;i++){
scanf("%d%d",&b,&p);
if(i==1)s=b;if(i==2)t=b;
d[b].push_back(p);
MP[pii(b%p,p)].push_back(b);
}
for(auto f:MP){
vi x=f.second;
int b=f.first.first,p=f.first.second;
sort(x.begin(),x.end());int len=x.size();
for(int i=0;i<len;i++){
int lst=b,nxt=(n-b)/p*p+b;
if(i!=0)lst=x[i-1];
if(i!=len-1)nxt=x[i+1];
for(int j=lst;j<=nxt;j+=p)
add(x[i],j,abs(x[i]-j)/p);
}
}
memset(dis,0x3f,sizeof(dis));
Q.push(make_pair(0,s));dis[s]=0;
while(!Q.empty()){
int u=Q.top().second,d=-Q.top().first;Q.pop();
if(vis[u])continue;vis[u]=1;
for(int i=head[u],v;i;i=nxt[i])
if(dis[v=ver[i]]>d+val[i]){
dis[v]=d+val[i];
Q.push(make_pair(-dis[v],v));
}
}
if(dis[t]>1e9)printf("-1\n");
else printf("%d\n",dis[t]);
return 0;
}
C 巴邻旁之桥
key：中位数
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,k;ll ans;char c,d;
namespace task1{
int a[N*2],m=0;
void solve(){
for(int i=1,x,y;i<=n;i++){
cin>>c>>x>>d>>y;
if(c==d)ans+=abs(x-y);
else a[++m]=x,a[++m]=y;
}
sort(a+1,a+m+1);
for(int i=1;i<=m;i++)ans+=abs(a[i]-a[m/2]);
printf("%lld\n",ans+m/2);
}
}
namespace task2{
struct P{int l,r;}a[N];
int m=0;ll res=1e18,pre[N],suf[N];
bool cmp(P a,P b){return a.l+a.r<b.l+b.r;}
void solve(){
memset(pre,0x3f,sizeof(pre));
memset(suf,0x3f,sizeof(suf));
for(int i=1,x,y;i<=n;i++){
cin>>c>>x>>d>>y;
if(x>y)swap(x,y);
if(c==d)ans+=y-x;
else a[++m].l=x,a[m].r=y;
}
if(!m){printf("%lld\n",ans);return;}
sort(a+1,a+m+1,cmp);
pre[0]=suf[m+1]=0;
priority_queue<int> Q1,Q2;
while(!Q1.empty())Q1.pop();while(!Q2.empty())Q2.pop();
pre[1]=a[1].r-a[1].l;
Q1.push(a[1].l);Q2.push(-a[1].r);
ll s1=a[1].l,s2=a[1].r;
for(int i=2,x,tmp;i<=m;i++){
tmp=Q1.top();
x=a[i].l;if(x<tmp)Q1.push(x),s1+=x;else Q2.push(-x),s2+=x;
x=a[i].r;if(x<tmp)Q1.push(x),s1+=x;else Q2.push(-x),s2+=x;
if(Q1.size()>i){x=Q1.top();Q1.pop();s1-=x;s2+=x;Q2.push(-x);}
if(Q2.size()>i){x=-Q2.top();Q2.pop();s2-=x;s1+=x;Q1.push(x);}
pre[i]=s2-s1;
}
while(!Q1.empty())Q1.pop();while(!Q2.empty())Q2.pop();
suf[m]=a[m].r-a[m].l;
Q1.push(a[m].l);Q2.push(-a[m].r);
s1=a[m].l;s2=a[m].r;
for(int i=m-1,x,tmp;i>=1;i--){
tmp=Q1.top();
x=a[i].l;if(x<tmp)Q1.push(x),s1+=x;else Q2.push(-x),s2+=x;
x=a[i].r;if(x<tmp)Q1.push(x),s1+=x;else Q2.push(-x),s2+=x;
if(Q1.size()>m-i+1){x=Q1.top();Q1.pop();s1-=x;s2+=x;Q2.push(-x);}
if(Q2.size()>m-i+1){x=-Q2.top();Q2.pop();s2-=x;s1+=x;Q1.push(x);}
suf[i]=s2-s1;
}
for(int i=0;i<=m;i++)res=min(res,pre[i]+suf[i+1]);
printf("%lld\n",ans+m+res);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>k>>n;
if(k==1)task1::solve();
else task2::solve();
return 0;
}