纪念一下人生中第一道数据分治题。
Subtask 1&2
这一部分具有的特殊性质是颜色段连续，那我们可以判断当前与前一个的颜色数是否为 1，若是则颜色相同，否则让颜色 +1。
Code
namespace AB
{
void solve()
{
int cur=1;
ans[1]=1;
for(int i=2;i<=n;i++)
{
if(query(i-1,i)>1)
ans[i]=++cur;//颜色不同
else
ans[i]=cur;
}
cout<<"! ";
for(int i=1;i<=n;i++)
cout<<ans[i]<<' ';
cout<<endl;
}
}Subtask 3&4
这一部分由于颜色数不多，我们可以记录当前位置已经出现的颜色数量以及每种颜色最后出现的位置，根据这个直接分类讨论当前位置的颜色。
Code
namespace CD
{
typedef pair<int,int> pii;
int last[10],cnt;
pii mem[10],fir,sec,thi,fou;
void tturn(pii &a,pii &b,pii &ans)
{
mem[1]=a,mem[2]=b,mem[3]=ans;
sort(mem+1,mem+4);
a=mem[1],b=mem[2],ans=mem[3];
return;
}
void fturn(pii &a,pii &b,pii &ans,pii &d)
{
mem[1]=a,mem[2]=b,mem[3]=ans,mem[4]=d;
sort(mem+1,mem+5);
a=mem[1],b=mem[2],ans=mem[3],d=mem[4];
return;
}
void refer(int i,int ncol)
{
ans[i]=ncol;
last[ncol]=i;
return;
}
#define id second
void count(int t)
{
ans[1]=cnt=last[1]=1;
if(t==3)
{
for(int i=2;i<=n;i++)
{
fir={last[1],1};
sec={last[2],2};
thi={last[3],3};
tturn(fir,sec,thi);
if(!sec.first)
{
if(query(thi.first,i)==2)
refer(i,++cnt);
else
refer(i,1);
}
else if(!fir.first)
{
if(query(sec.first,i)==3)
refer(i,++cnt);
else
{
if(query(thi.first,i)==1)
refer(i,thi.id);
else
refer(i,sec.id);
}
}
else
{
if(query(sec.first,i)==3)
refer(i,fir.id);
else
{
if(query(thi.first,i)==1)
refer(i,thi.id);
else
refer(i,sec.id);
}
}
}
}
else
{
for(int i=2;i<=n;i++)
{
fir={last[1],1};
sec={last[2],2};
thi={last[3],3},fou={last[4],4};
fturn(fir,sec,thi,fou);
if(!sec.first)
{
if(!thi.first)
{
if(query(fou.first,i)==2)
refer(i,++cnt);
else
refer(i,1);
}
else
{
if(query(thi.first,i)==3)
refer(i,++cnt);
else
{
if(query(fou.first,i)==1)
refer(i,fou.id);
else
refer(i,thi.id);
}
}
}
else if(!fir.first)
{
if(query(thi.first,i)==3)
{
if(query(sec.first,i)==4)
refer(i,++cnt);
else
refer(i,sec.id);
}
else
{
if(query(fou.first,i)==1)
refer(i,fou.id);
else
refer(i,thi.id);
}
}
else
{
if(query(thi.first,i)==3)
{
if(query(sec.first,i)==4)
refer(i,fir.id);
else
refer(i,sec.id);
}
else
{
if(query(fou.first,i)==1)
refer(i,fou.id);
else
refer(i,thi.id);
}
}
}
}
cout<<"! ";
for(int i=1;i<=n;i++)
cout<<ans[i]<<' ';
cout<<endl;
return;
}
#undef id
}Subtask 5
首先特判掉每个位置颜色都不同的情况。
然后我们考虑双指针，维护两个指针 $i,j$，让它们不断向中间移动的同时保证 $[i,j]$ 的颜色数等于 $j-i$，最后找到的两个指针的位置就是颜色相同的地方。
Code
namespace E
{
void solve()
{
int i=1,j=n,cur=0;
if(query(1,n)==n)
{
cout<<"! ";
for(int k=1;k<=n;k++)
cout<<k<<' ';
cout<<endl;
return;
}
while(query(i,j)==j-i)
i++;
i--;
while(query(i,j)==j-i)
j--;
j++;
for(int k=1;k<=n;k++)
{
if(k==j)
ans[k]=ans[i];
else
ans[k]=++cur;
}
cout<<"! ";
for(int k=1;k<=n;k++)
cout<<ans[k]<<' ';
cout<<endl;
return;
}
}Subtask 6&7
考虑二分，判断 $[mid,i-1]$ 的颜色数是否等于 $[mid,i]$ 的颜色数，如果相同则说明 $[mid,i-1]$ 中有与 $i$ 颜色相同的点，暴力数出来即可。
Code
namespace FG
{
int tot,tim,v[10005];
inline int count(int l,int r)
{
int s=0;
++tim;
for(int i=l;i<=r;++i)
{
if(v[ans[i]]!=tim)
{
v[ans[i]]=tim;
++s;
}
}
return s;
}
int main()
{
int l,r,pos,mid;
ans[1]=1;
tot=1;
for(int i=2;i<=n;++i)
{
l=1;
r=i-1;
pos=i;
while(l<=r)
{
mid=(l+r)>>1;
if(query(mid,i)!=count(mid,i-1))
{
r=mid-1;
pos=mid;
}
else
l=mid+1;
}
if(pos==1)
ans[i]=++tot;
else
ans[i]=ans[pos-1];
}
cout<<"! ";
for(int i=1;i<=n;i++)
cout<<ans[i]<<' ';
cout<<endl;
return 0;
}
}
原文地址：http://www.cnblogs.com/2020gyk080/p/16878561.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
