csp-s模拟测试103「game,time」
rtrt
3月 14, 2025
归档于 2019-11-07 07:39
time
题解
贪心考虑,考试时想错了,我想的是移动最大值,枚举最大值位置,然后把左面和右面逆序对拼起来,
当然,处理不了有多个最大值情况,于是我就想着打个部分分吧
然而对拍还是挂,
枚举最大值位置是不对的
考虑一种情况a,b,c,d,e,f,g
其中d最大可能出现a移动到d右面更优,b,c留在左面,我只移动最大值的话默认a,b,c都在左面
附赠一组点4 5 2 3 1 6 7 最优决策是6步,方案是2 4 5 6 7 3 1 .
出现了我说的这种情况
考试时打这个题花费时间还是过于多了
正解是贪心移动最小值,这样是保证正确的,只移动最大值相当与限制了一些情况出现
然后最小值考虑了所有情况且一定正确
正难则反__by yangguangjie
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 111111
ll p[A],a[A],b[A],c1[A],c2[A];
ll n,ans=0;
vector <ll> v[A];
//正
void add1(ll x,ll d){for(ll i=x;i!=0&&i<=100000;i+=i&-i) c1[i]+=d;}
ll ask1(ll x,ll ans=0){for(ll i=x;i>=1;i-=i&-i) ans+=c1[i];return ans;}
//逆
void add2(ll x,ll d){for(ll i=x;i>=1;i-=i&-i) c2[i]+=d;}
ll ask2(ll x,ll ans=0){for(ll i=x;i!=0&&i<=100000;i+=i&-i) ans+=c2[i];return ans;}
void sol(){
for(ll i=1;i<=n;i++){
add1(i,1);add2(i,1);
v[a[i]].push_back(i);
}
for(ll i=1;i<=100000;i++){
if(v[i].size()){
for(ll fr=0,ba=v[i].size()-1;fr<=ba;){
ll x=v[i][fr],y=v[i][ba];
ll l=ask1(x-1),r=ask2(y+1);
// printf("l=%lld r=%lld\n",l,r);
if(l<r){
ans+=l;
add1(x,-1);
add2(x,-1);
fr++;
}
else {
ans+=r;
add1(y,-1);
add2(y,-1);
ba--;
}
}
}
}
}
int main(){
freopen("time.in","r",stdin);
freopen("time.out","w",stdout);
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]),p[i]=i;
sol();
printf("%lld\n",ans);
}
View Code
game
题解
做过一个类似的题(老司机的狂欢),也是求字典序最小,也是第一问特别简单,然后根据第一问推第二问
但实在没想到可以每一位上二分求字典序最小
推单调性
如果upper_bound有值具有单调性,当前选的值越大,以后高的可能性就越小
如果upper_bound没值具有单调性,当前选的值越大,以后得分高的可能越小
但是函数是分段的
可以分两次二分
这样每次set暴力check复杂度$n^2*{log}^2$
现在思考如何check
可以用权值线段树维护
维护A的没用上的牌
维护B的没用上的牌
向上合并时右子树每一张A都可以于左子树中B匹配
代码大致是这样
void up(ll x){
ll de=min(tr[x<<1|1].L,tr[x<<1].R);
tr[x].s=tr[x<<1].s+tr[x<<1|1].s+de;
tr[x].L=tr[x<<1].L+tr[x<<1|1].L-de;
tr[x].R=tr[x<<1].R+tr[x<<1|1].R-de;
}
代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define A 1010100
#define maxx 100000
ll read(){ll x;scanf("%d",&x);return x;}
ll tot,n;
ll b[A],a[A];
multiset<ll> st;
multiset<ll> ::iterator it;
struct node{
ll l,r,L,R,s;
//L:A的牌
//R:B的牌
//s得分
}tr[A];
void built(ll x,ll l,ll r){
tr[x].l=l,tr[x].r=r;
if(l==r){
return ;
}
ll mid=(l+r)>>1;
built(x<<1,l,mid);
built(x<<1|1,mid+1,r);
}
void up(ll x){
ll de=min(tr[x<<1|1].L,tr[x<<1].R);
tr[x].s=tr[x<<1].s+tr[x<<1|1].s+de;
tr[x].L=tr[x<<1].L+tr[x<<1|1].L-de;
tr[x].R=tr[x<<1].R+tr[x<<1|1].R-de;
}
void insert(ll x,ll pla,ll vala,ll valb){
if(tr[x].l==tr[x].r){
tr[x].L+=vala;
tr[x].R+=valb;
return ;
}
ll mid=(tr[x].l+tr[x].r)>>1;
if(mid>=pla) insert(x<<1,pla,vala,valb);
else insert(x<<1|1,pla,vala,valb);
up(x);
}
void getans(ll now){
insert(1,b[now],0,-1);
ll l=b[now]+1,r=*st.rbegin(),ans=0;
while(l<=r){
ll mid=(l+r)>>1;
insert(1,mid,-1,0);
if(tr[1].s+1==tot){
l=mid+1;
ans=mid;
}
else r=mid-1;
insert(1,mid,1,0);
}
insert(1,ans,-1,0);
if(tr[1].s+1==tot){
tot--;
printf("%d ",ans);
it=st.find(ans);
st.erase(it);
return ;
}
insert(1,ans,1,0);
l=1,r=b[now],ans=0;
while(l<=r){
ll mid=(l+r)>>1;
insert(1,mid,-1,0);
if(tr[1].s==tot){
l=mid+1;
ans=mid;
}
else r=mid-1;
insert(1,mid,1,0);
}
insert(1,ans,-1,0);
printf("%d ",ans);
it=st.find(ans);
st.erase(it);
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
n=read();
built(1,1,maxx);
for(ll i=1;i<=n;i++){
b[i]=read();
insert(1,b[i],0,1);
}
for(ll i=1;i<=n;i++){
a[i]=read();
insert(1,a[i],1,0);
st.insert(a[i]);
}
tot=tr[1].s;
for(ll i=1;i<=n;i++){
getans(i);
}
}
View Code