正文
noip模拟9[斐波那契·数颜色·分组](洛谷模拟测试)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
这次考试还是挺好的
毕竟第一题被我给A了，也怪这题太简单，规律一眼就看出来了，但是除了第一题，剩下的我只有30pts，还是菜
第二题不知道为啥我就直接干到树套树了，线段树套上一个权值线段树，然后我发现自己跑得特别慢，
然后就手打了一个超级大暴力，然后就很懵逼的发现，我的暴力比我树套树还快十倍
我就很生气，回去算了一遍复杂度，没错是nlog2n，然后我就怀疑自己打假了，直接把自己的暴力程序交上去了
然后成功的30分，然后就人傻了，然后我发现，其实我树套树有35pts，但是正解是二分/主席书/颜色权值线段树都行，
然后我就为了锻炼我的二分能力，就去手打了二分，但是大佬们都是lower_bound/upper_bound害，人家只有20来行
第三题我连写都没写，为啥呢，因为这个K吧数据范围我看都没看，以为他至少也得1e5
然后我就对着题面看到考试结束，然后我就0分了。。。只有 一句话，我脑残
一直以为最后一个题是dp然而我dp方程根本想不出来，好像有点像区间dp的样子
最后发现是贪心，前40分还特别好拿。。。。。
洛谷题面：
斐波那契
数颜色
分组
T1斐波那契
为什么说这个题水？？？
自己去倒一倒，你就发现每天新出生的兔子数量就是一个严格的斐波那契数列，
那这样的话，我们只需在前面在加上一个1，然后对这个序列做一个前缀和，就是每天拥有的兔子量（其实前缀和后的数列还是一个斐波那契数列）
然后题目要求，每个兔子的编号是按照爸爸的编号大小来排列的，所以我们用要去寻找的兔子的编号，找到他在出生的时候的次序，然后，这个次序就是他爸爸的编号
这个过程的实现就是lower_bound一下，再-1然后用编号减去那一项的值，这样一直减下去，得到的就是他的祖先
我们拿着两只兔子，然后，就像求lca一样，让编号大的先跳，一直跳到相等，就找到了
记得做数列题的时候，先吧这个数列输出一下，不然你不会知道，斐波那契数列的第60项已经1e12了
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
const ll maxn=1e12;
int n;
ll fi[105],fro[105];
ll find(ll x){
return lower_bound(fro+1,fro+64,x)-fro;
}
ll lca(ll x,ll y){
if(x<y)swap(x,y);
while(x!=y){
x-=fro[find(x)-1];
if(x<y)swap(x,y);
}
return x;
}
signed main(){
fi[1]=fi[2]=1;
fro[0]=1;fro[1]=2;fro[2]=3;
for(re i=3;i<=65;i++){
fi[i]=fi[i-1]+fi[i-2];
fro[i]=fro[i-1]+fi[i];
}
scanf("%d",&n);
for(re i=1;i<=n;i++){
ll a,b;
scanf("%lld%lld",&a,&b);
printf("%lld\n",lca(a,b));
}
}
T1（考场AC）
T2数颜色
不行为了不辜负我在考场上的一片苦心，我决定把握的暴力O(nm)和树套树O(nlog2n)代码粘到这里。。。
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=3e5+10;
int n,m;
int a[N],ans;
signed main(){
//freopen("color.out","w",stdout);
//int o=clock();
scanf("%d%d",&n,&m);
for(re i=1;i<=n;i++)scanf("%d",&a[i]);
for(re i=1;i<=m;i++){
int typ,l,r,c;
scanf("%d",&typ);
if(typ==1){
scanf("%d%d%d",&l,&r,&c);
ans=0;
for(re i=l;i<=r;i++)if(a[i]==c)ans++;
printf("%d\n",ans);
}
else {
scanf("%d",&l);
swap(a[l],a[l+1]);
}
}
//cout<<"sb"<<endl;
//cout<<endl<<endl<<clock()-o<<endl;
}
超级大暴力
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=3e5+10;
int n,m;
int a[N],col[N*2],l[N*2],r[N*2],typ[N*2];
int lsh[N*3],lh;
int C,ans;
struct node{
int seg;
int sum[N*80],ls[N*80],rs[N*80];
void ins(int &x,int l,int r,int pos){
if(!x)x=++seg;
if(l==r){
sum[x]=1;
return ;
}
int mid=l+r>>1;
if(pos<=mid)ins(ls[x],l,mid,pos);
else ins(rs[x],mid+1,r,pos);
}
int query(int x,int l,int r,int pos){
if(!x)return 0;
if(l==r)return sum[x];
int mid=l+r>>1;
if(pos<=mid)return query(ls[x],l,mid,pos);
else return query(rs[x],mid+1,r,pos);
}
void merge(int x,int y,int &z){
if(!x||!y){
z=x+y;
return ;
}
if(!z)z=++seg;
sum[z]=sum[x]+sum[y];
if(ls[z]==ls[y]||ls[z]==ls[x])ls[z]=0;
merge(ls[x],ls[y],ls[z]);
if(rs[z]==rs[y]||rs[z]==rs[x])rs[z]=0;
merge(rs[x],rs[y],rs[z]);
}
}xds;
int rt[N*4],ir[N];
void build(int x,int l,int r){
if(l==r){
ir[l]=x;
xds.ins(rt[x],1,C,a[l]);
return ;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
//cout<<x<<endl;
xds.merge(rt[x<<1],rt[x<<1|1],rt[x]);
//cout<<x<<endl;
}
void update(int x,int l,int r,int ql,int qr){
if(l==r)return ;
int mid=l+r>>1;
if(ql<=mid)update(x<<1,l,mid,ql,qr);
if(qr>mid)update(x<<1|1,mid+1,r,ql,qr);
//if(qr<=mid||ql>mid)return ;
xds.merge(rt[x<<1],rt[x<<1|1],rt[x]);
}
void find(int x,int l,int r,int ql,int qr,int co){
if(ql<=l&&r<=qr){
ans+=xds.query(rt[x],1,C,co);
return ;
}
int mid=l+r>>1;
if(ql<=mid)find(x<<1,l,mid,ql,qr,co);
if(qr>mid)find(x<<1|1,mid+1,r,ql,qr,co);
}
signed main(){
//freopen("color.out","w",stdout);
scanf("%d%d",&n,&m);
for(re i=1;i<=n;i++){
scanf("%d",&a[i]);
lsh[++lh]=a[i];
}
for(re i=1;i<=m;i++){
scanf("%d",&typ[i]);
if(typ[i]==1){
scanf("%d%d%d",&l[i],&r[i],&col[i]);
lsh[++lh]=col[i];
}
else scanf("%d",&l[i]);
}
sort(lsh+1,lsh+lh+1);
lh=unique(lsh+1,lsh+lh+1)-lsh-1;C=lh;
for(re i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+lh+1,a[i])-lsh;
build(1,1,n);
for(re i=1;i<=m;i++){
if(typ[i]==1){
int tmp=col[i];
col[i]=lower_bound(lsh+1,lsh+lh+1,col[i])-lsh;
if(tmp!=lsh[col[i]]){
printf("0\n");
continue;
}
ans=0;find(1,1,n,l[i],r[i],col[i]);
printf("%d\n",ans);
}
else {
//cout<<l[i]<<" "<<l[i]+1<<endl;
swap(rt[ir[l[i]]],rt[ir[l[i]+1]]);
update(1,1,n,l[i],l[i]+1);
}
}
//cout<<xds.seg<<endl;
}
树套树
不多说了，直接上正解。
正解就是直接将这个颜色序列按照 先颜色，后位置 的双关键字排序
然后我们就可以直接利用二分，在每一个颜色块内寻找这个颜色的数量
所以更改的时候，我们发现，两个颜色的交换不会影响到各个颜色在各自的块内的位置
所以我们找到这两个位置，将他们的位置信息交换就好，仍然满足单调性
但是注意，同颜色的就不要换了，换了就不对了，我因为这WA了好几遍
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=3e5+5;
int n,m;
int a[N],pl[N],pr[N];
struct node{
int col,pos;
bool operator < (node a) const {
if(col!=a.col)return col<a.col;
return pos<a.pos;
}
}rib[N];
signed main(){
scanf("%d%d",&n,&m);
for(re i=1;i<=n;i++){
scanf("%d",&a[i]);
rib[i].col=a[i];
rib[i].pos=i;
}
sort(rib+1,rib+n+1);
pl[rib[1].col]=1;
for(re i=1;i<=n;i++){
if(rib[i].col!=rib[i-1].col){
pr[rib[i-1].col]=i-1;
pl[rib[i].col]=i;
}
}
pr[rib[n].col]=n;
//for(re i=1;i<=3;i++)cout<<pl[i]<<" "<<pr[i]<<endl;
for(re i=1;i<=m;i++){
int typ,x,y,z;
scanf("%d",&typ);
if(typ==1){
scanf("%d%d%d",&x,&y,&z);
int ans=0,l=pl[z]-1,r=pr[z],mid;
while(l<r){
mid=l+r+1>>1;
if(rib[mid].pos<x)l=mid;
else r=mid-1;
}
int L=l;
//if(rib[l].pos<x)L++;
r=pr[z];
while(l<r){
mid=l+r+1>>1;
if(rib[mid].pos<=y)l=mid;
else r=mid-1;
}
printf("%d\n",l-L);
}
else{
scanf("%d",&x);
y=x+1;
if(a[x]==a[y])continue;
int l=pl[a[x]],r=pr[a[x]],mid;
while(l<r){
mid=l+r+1>>1;
if(rib[mid].pos<=x)l=mid;
else r=mid-1;
}
rib[l].pos=y;
l=pl[a[x+1]];r=pr[a[x+1]];
while(l<r){
mid=l+r+1>>1;
if(rib[mid].pos<=y)l=mid;
else r=mid-1;
}
rib[l].pos=x;
swap(a[x],a[x+1]);
}
}
}
T2正解
只有我一个人用手打的二分吗，，哇呜呜。。
T3分组
其实说实话，我挺生气的，为什么不把数据范围放到题面里，那样好歹我也有40分，不至于连代码都没打
K=1或2，气人
分情况讨论呗：：：
当K=1时，我们可以直接贪心嘛，反正块都得是连续的，但是你发现，这字典序很难搞啊，但是我们可以直接从后向前枚举，然后得到的分割点就是最优解啊
当K=2时，我们也还是贪心，也是从后往前枚举，延续上一种情况的做法
但是我们如果分成两组，将不能共存的两个数看作是连边的两个点，然后这个问题就是要我们找到一个最大的二分图
虽然这个知识点我不会，但是我可以用并查集解决这个问题，还记不记得这个题------关押罪犯
我们可以直接利用并查集判断这个点可不可以加进去，
还要注意一个特例，两个数相等的时候，并且这个数的2倍是一个平方数，然后我们只要判断一下，就可以过掉这个题了
还有，如何利用并查集判断，那我们就将敌人放到x+i，这样可以防止查询的紊乱，所以我因为这个WA了好多变；
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=131075;
int n,k;
int a[N];
int ans,sum,dv[N],vis[N*5];
void get_ans1(){
dv[0]=n;
for(re i=n;i>=1;i--){
// cout<<i<<endl;
bool pd=false;
for(re j=sqrt(a[i]);j<=512;j++){
//cout<<j<<endl;
if(j*j<a[i])continue;
if(vis[j*j-a[i]]){
pd=true;break;
}
}
if(pd==true){
ans++;
dv[++sum]=i;
//cout<<sum<<" "<<dv[sum-1]<<" "<<i<<endl;
for(re j=dv[sum-1];j>i;j--)vis[a[j]]=0;//cout<<j<<endl;
}
vis[a[i]]=1;
}
}
int fa[N*3],ops[N*3];
int maxx=131100;
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void get_ans2(){
for(re i=1;i<=512*512;i++)fa[i]=i;
dv[0]=n;
for(re i=n;i>=1;i--){
//cout<<i<<endl;
bool pd=false;
if(vis[a[i]]==1&&(int)sqrt(a[i]*2)*(int)sqrt(a[i]*2)==a[i]*2){
for(re j=sqrt(a[i]);j<=512;j++){
if(j*j<a[i])continue;
if(vis[j*j-a[i]]&&j*j!=a[i]*2){
pd=1;break;
}
}
}
else{
for(re j=sqrt(a[i]);j<=512;j++){
if(j*j<a[i])continue;
int y=j*j-a[i];
if(vis[y]==2&&((int)sqrt(2*y)*(int)sqrt(2*y)==2*y)){
pd=1;break;
}
if(vis[y]){
if(y==a[i])continue;
else{
int fy=find(y),fi=find(a[i]);
int gy=find(y+maxx),gi=find(a[i]+maxx);
if(fy==fi){
pd=1;break;
}
else{
fa[gy]=fi;
fa[gi]=fy;
}
}
}
}
}
if(pd==true){
ans++;
dv[++sum]=i;
for(re j=dv[sum-1];j>i;j--){
vis[a[j]]=0;
fa[a[j]]=a[j];
fa[a[j]+maxx]=a[j]+maxx;
}
}
vis[a[i]]++;
}
}
signed main(){
scanf("%d%d",&n,&k);
for(re i=1;i<=n;i++)scanf("%d",&a[i]);
//cout<<a[913]<<" "<<a[914]<<" "<<a[915]<<endl;
if(k==1)get_ans1();
else get_ans2();
printf("%d\n",ans+1);
for(re i=sum;i;i--)printf("%d ",dv[i]);
printf("\n");
}
T3
