NOIP提高组模拟赛3

A. 斐波那契

周围大佬都说初中打过n遍,我一个菜鸡瑟瑟发抖。

把斐波那契数列写出来找了半天性质,用了半个多小时推出来

x兔子的父亲,就是x减去是在斐波那契数列中最大的小于x的数

举个栗子

13号兔子,应减去8,得到他的祖先5

10号兔子,应减去8,得到他的祖先2

预处理出斐波那契数列,然后让ab中较大的到他的祖先,a==b时输出答案,过程可以二分,但是因为菜还懒,发现减去的数一定越来越小,单调指针往前扫就行

那么为什么减去是正确的?他的含义是什么?

首先对斐波那契数列求前缀和,得到第i天有几只兔子,然后发现前缀和不用另算,实际就是斐波那契数列第i+2项,这么显然的东西我还是打表发现的,实际还是在斐波那契数列上,找到第一项大于等于x的,就是x在当天出生,减去前一项,得到k,就是x是当天第k只出生的兔子,而标号是按照父亲标号从小到大编号的,当天第i只出生的兔子的父亲就是k,所以减去最大的小于x的就是x的父亲。

#include<cstdio>
#include<cstring>

using namespace std;

long long fib[1005];
int main()
{
    freopen("fibonacci2.in","r",stdin);
    freopen("fibonacci.out","w",stdout);
    int m;scanf("%d",&m);
    fib[0]=1;fib[1]=1;fib[2]=1;
    for(int i=3;i<=60;++i)fib[i]=fib[i-1]+fib[i-2];
    for(int i=1;i<=m;++i){
        long long a,b;scanf("%lld%lld",&a,&b);
        int pa=60,pb=60;
        while(a!=b){
            if(a>b){
                while(pa>=1&&fib[pa-1]>=a)pa--;
                a-=fib[pa-1];
            }else{
                while(pb>=1&&fib[pb-1]>=b)pb--;
                b-=fib[pb-1];
            }
        }
        printf("%lld\n",a);
    }
    return 0;
}

B. 数颜色

没错,学数据数据结构学傻的就是我

记得做分块莫队时候看到过这题,于是就往分块想,于是喜提TLE

其实开个数组存一下第i种颜色位置的下标,每次二分查找指定区间内颜色个数就好,数组好像开不下?用vector

特判一下不存在的情况

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=300005;
int c[maxn];
vector <int> a[maxn];
void ask(){
    int l,r,col;scanf("%d%d%d",&l,&r,&col);
    int p1=lower_bound(a[col].begin(),a[col].end(),l)-a[col].begin();
    int p2=upper_bound(a[col].begin(),a[col].end(),r)-a[col].begin()-1;
    if(p1>p2)printf("0\n");
    else printf("%d\n",p2-p1+1);
}
void update(){
    int x;scanf("%d",&x);
    if(c[x+1]==c[x])return;
    int p1=lower_bound(a[c[x]].begin(),a[c[x]].end(),x)-a[c[x]].begin();
    a[c[x]][p1]++;
    p1=lower_bound(a[c[x+1]].begin(),a[c[x+1]].end(),x+1)-a[c[x+1]].begin();
    a[c[x+1]][p1]--;
    swap(c[x],c[x+1]);
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&c[i]);
    for(int i=1;i<=n;++i)a[c[i]].push_back(i);
    for(int i=1;i<=m;++i){
        int op;scanf("%d",&op);
        if(op&1)ask();
        else update();
    }
    return 0;
}

C. 分组

分类讨论,由于某些奇奇怪怪的原因还是菜想对了k=1的情况然而只得到了部分部分分。。。

k只有1、2两种取值,分类讨论即可

k=1时,用vis数组记录当前团体内有谁,每次加入新兔子时枚举所有平方数减去该兔子颜色,判断是否存在与之矛盾的兔子,如果有就重新分组,为了保证字典序最小,从后往前倒叙枚举,为了保证时间效率,令开数组rem记录那些位置有兔子,清零时清空rem对应位置即可

k=2时,仿照团伙那题,维护两个并查集,表示两个团体,令开数组记录与矛盾i的兔子在哪个集合,每次有一对新的矛盾关系i-j,判断这两个兔子是否在一个并查集中,在的话重新分组,不在就将i与j敌人所在团体合并,j与i所在团体合并,倒叙枚举。

实际上这玩意叫扩展域并查集,记录i敌人的数组相当于把i拆成两点中的虚拟点。领会精神吧。。

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=301075;
int a[maxn],n,k,rem[maxn],cl[maxn];
bool flag[maxn];
void work1(){
    int cnt=0,temp=0;
    for(int i=n;i>=1;--i){
        bool fl=0;
        for(int j=512;j;--j){
            if(j*j-a[i]<=0)break;
            if(flag[j*j-a[i]]){fl=1;rem[++cnt]=i;break;}
        }
        if(fl){
            while(temp)flag[cl[temp--]]=0;
        }
        cl[++temp]=a[i];
        flag[a[i]]=1;
    }
    printf("%d\n",cnt+1);
    for(int i=cnt;i>=1;--i)printf("%d ",rem[i]);
    printf("\n");
}
vector<int>v[maxn];
int f[maxn],d[maxn];
int fx(int x){
    if(f[x])return f[x]=fx(f[x]);
    return x;
}
void hb(int x,int y){
    x=fx(x);
    y=fx(y);
    if(x!=y)f[x]=y;
}
int up(int l,int r){
    for(int i=l;i<=r;++i)
      vector<int>().swap(v[a[i]]);
    return l-1;
}
void work2(){
    int cnt=0,fl=0,las=n;
    for(int i=n;i>=1;--i){
        //printf("%d ",i);
        for(int j=512;j;--j){
            if(j*j-a[i]<=0)break;
            int ss=v[j*j-a[i]].size();
            if(ss){
                for(int k=0;k<ss;++k){
                    if(fx(i)==fx(v[j*j-a[i]][k])){
                        las=up(i+1,las);
                        rem[++cnt]=i;
                        break;
                    }
                    else{
                        if(!d[v[j*j-a[i]][k]])d[v[j*j-a[i]][k]]=i;
                        if(!d[i])d[i]=v[j*j-a[i]][k]; 
                        hb(d[v[j*j-a[i]][k]],i);
                        hb(d[i],v[j*j-a[i]][k]);
                    }
                }
            }
        }
        v[a[i]].push_back(i);
    }

    printf("%d\n",cnt+1);
    for(int i=cnt;i>=1;--i)printf("%d ",rem[i]);
    printf("\n");

}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    if(k&1)work1();
    else work2();
    return 0;
}

这次考试最大收获(大雾)发现自己还是最菜的,学到了不少vector使用方法

上一篇:linux CPU100% xmrig病毒处理


下一篇:CentOS 7 以太网卡配置文件代码含义(ifcfg)