洛谷模拟赛 mNOIP DAY1

100+45+12
QAQ基本全是暴力
T1:找规律+模拟（70分树剖+30分乱搞）
题目描述

小 C 养了一些很可爱的兔子。 有一天，小 C 突然发现兔子们都是严格按照伟大的数学家斐波那契提出的模型来进行 繁衍：一对兔子从出生后第二个月起，每个月刚开始的时候都会产下一对小兔子。我们假定， 在整个过程中兔子不会出现任何意外。

小 C 把兔子按出生顺序，把兔子们从 1 开始标号，并且小 C 的兔子都是 1 号兔子和 1 号兔子的后代。如果某两对兔子是同时出生的，那么小 C 会将父母标号更小的一对优先标 号。

输出格式：
输出到标准输出中。 输入一共 m 行，每行一个正整数，依次表示你对问题的答案。

输入输出样例

输入样例#1： 复制
5
1 1
2 3
5 7
7 13
4 12
输出样例#1： 复制
1
1
2
2
4

题目链接https://www.luogu.org/problemnew/show/P3938
我不会加图啊QAQ你们自已去题里看吧
我们很容易发现，这个兔子和它爸爸差的标号数正好是距离他最近的一个斐波那契数列~~然后模拟即可

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#define int long long 
using namespace std;
int m;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int head[3000055];
int to[3000035];
int nex[3000045];
int fei[55];
int dcnt;
struct TREE{
    int fa,siz,s,t,dep,son,top;
}tree[2000015];
int tot;
long long fei2[105];
/*inline void add(int x,int y){ ++tot; nex[tot]=head[x]; head[x]=tot; to[tot]=y; } void dfs1(int u){ tree[u].siz=1; for(int i=head[u];i;i=nex[i]) if(to[i]!=tree[u].fa){ int hxr=to[i]; tree[hxr].dep=tree[u].dep+1; tree[hxr].fa=u; dfs1(hxr); tree[u].siz+=tree[hxr].siz; if(tree[hxr].siz>tree[tree[u].son].siz) tree[u].son=hxr; } } void dfs2(int u,int top){ tree[u].s=++dcnt; tree[u].top=top; if(tree[u].son){ dfs2(tree[u].son,top); for(int i=head[u];i;i=nex[i]) if(to[i]!=tree[u].fa&&to[i]!=tree[u].son) dfs2(to[i],to[i]); } } inline int lca(int x,int y){ int f1=tree[x].top; int f2=tree[y].top; while(f1!=f2){ if(tree[f1].dep<tree[f2].dep){ swap(f1,f2); swap(x,y); } x=tree[f1].fa; f1=tree[x].top; } if(tree[x].dep<tree[y].dep) return x; return y; }*/
main(){
    register int i;
    m=read();
    fei2[1]=1;
    fei2[2]=1;  
    long long  x,y;
    for(i=3;i<=92;i++) fei2[i]=fei2[i-1]+fei2[i-2];
    for(i=1;i<=m;i++){
        x=read();
        y=read();
        while(x!=y){
  //lca
            if(x<y) swap(x,y);
            int wei=lower_bound(fei2+1,fei2+92+1,x)-fei2-1;
            x-=fei2[wei];
        }
            printf("%lld\n",x);
    }
    return 0;
}

请自动忽略树剖。。。。
T2:45分：特判+树上差分
100分：乱搞+STL（呵呵呵）
题目描述

小 C 的兔子不是雪白的，而是五彩缤纷的。每只兔子都有一种颜色，不同的兔子可能有 相同的颜色。小 C 把她标号从 1 到 nn 的 nn 只兔子排成长长的一排，来给他们喂胡萝卜吃。 排列完成后，第 ii 只兔子的颜色是 a_ia
i
​ 。

俗话说得好，“萝卜青菜，各有所爱”。小 C 发现，不同颜色的兔子可能有对胡萝卜的 不同偏好。比如，银色的兔子最喜欢吃金色的胡萝卜，金色的兔子更喜欢吃胡萝卜叶子，而 绿色的兔子却喜欢吃酸一点的胡萝卜……为了满足兔子们的要求，小 C 十分苦恼。所以，为 了使得胡萝卜喂得更加准确，小 C 想知道在区间 [l_j,r_j][l
j
​ ,r
j
​ ] 里有多少只颜色为 c_jc
j
​ 的兔子。

不过，因为小 C 的兔子们都十分地活跃，它们不是很愿意待在一个固定的位置；与此同 时，小 C 也在根据她知道的信息来给兔子们调整位置。所以，有时编号为 x_jx
j
​ 和 x_j+1x
j
​ +1 的两 只兔子会交换位置。 小 C 被这一系列麻烦事给难住了。你能帮帮她吗？

输入输出格式

输入格式：
从标准输入中读入数据。 输入第 1 行两个正整数 nn,mm。

输入第 2 行 nn 个正整数，第 ii 个数表示第 ii 只兔子的颜色 a_ia
i
​ 。

输入接下来 mm 行，每行为以下两种中的一种：

“1\ l_j\ r_j\ c_j1 l
j
​ r
j
​ c
j
​ ” ：询问在区间 [l_j,r_j][l
j
​ ,r
j
​ ] 里有多少只颜色为 c_jc
j
​ 的兔子；

“2\ x_j2 x
j
​ ”： x_jx
j
​ 和 x_j+1x
j
​ +1 两只兔子交换了位置。
输出格式：
输出到标准输出中。

对于每个 1 操作，输出一行一个正整数，表示你对于这个询问的答案。

输入输出样例

输入样例#1： 复制
6 5
1 2 3 2 3 3
1 1 3 2
1 4 6 3
2 3
1 1 3 2
1 4 6 3
输出样例#1： 复制
1
2
2
3
说明

【样例 1 说明】

前两个 1 操作和后两个 1 操作对应相同；在第三次的 2 操作后，3 号兔子和 4 号兔子

交换了位置，序列变为 1 2 2 3 3 3。
用出题人的话来说呢
这道题可以写主席树，树套树，还可以写莫队
如果你用了我上述说的某一种算法呢；
说明你学数据结构学傻了呵呵呵
我们只需要开一个vector数组，把每个颜色出现的位置记下来
然后对于1操作，我们只需二分一下即可
对于2操作，和这个差不多啦~~
我的45分暴力+树上差分+特判（QAQ我特判写错了要不然应该60分）

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n,m;
int a[300005];
int aa[300005][15];
int col[300005];
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int colo,int wei,int ge){
    register int i;
    for(i=wei;i<=n;i+=lowbit(i)) 
     aa[i][colo]+=ge;
}
inline int get(int wei,int colo){
    register int i;
    int res=0;
    for(i=wei;i>0;i-=lowbit(i)) res+=aa[i][colo];
    return res;
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
    register int i,j;
    n=read();
    m=read();
    bool flag=0;
    for(i=1;i<=n;i++) {
        a[i]=read();
        if(a[i]<=10) 
        add(a[i],i,1);
        if(a[i]>10) flag=1;
        col[a[i]]=i;//反向映射 
    }
    if(n<=1000){
  //30分 
    for(i=1;i<=m;i++){
        int ord;
        ord=read();
        if(ord==1){
             int x,y,c;
             x=read();
             y=read();
             c=read();
             int ans=0;
             for(j=x;j<=y;j++) if(a[j]==c) ans++;
             printf("%d\n",ans);
        }
        else{
            int j;
            j=read();
            swap(a[j],a[j+1]);
        }
    }   
    return 0;   
  }
  else if(!flag){   
    for(int i=1;i<=m;i++)
    {
        int ord;
        ord=read();
        if(ord==1){
            int x,y,c;
            x=read();
            y=read();
            c=read();
            printf("%d\n",get(y,c)-get(x-1,c));
        }
        else{
            int j;
            j=read();
            add(a[j],j,-1);
            add(a[j],j+1,1);
            add(a[j+1],j+1,-1);
            add(a[j+1],j,1);
        }   
    }   
  }
  else{
    for(int i=1;i<=m;i++){
        int ord;
        ord=read();
        if(ord==1){
            int x,y,c;
            x=read();
            y=read();
            c=read();
            if(col[c]>=x&&col[c]<=y) printf("1\n");
            else printf("0\n");
        }
        else{
            int j;
            j=read();
            col[a[j]]=j+1;
            col[a[j+1]]=j;
            swap(a[j],a[j+1]);
        }   
    }   
  }
    return 0;
}

正解（又短又快）

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAXN 300005
using namespace std;
int n,t;
vector<int> s[MAXN];
int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x;
}
int a[MAXN];
int main(){
    n=read();t=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        s[a[i]].push_back(i);
    }
    for(int i=1;i<=t;i++){
        int ord=read();
        if(ord==1){
            int l=read(),r=read(),c=read();
            printf("%d\n",upper_bound(s[c].begin(),s[c].end(),r)-lower_bound(s[c].begin(),s[c].end(),l));
        }
        else{
            int l=read(),r=l+1;
            if(a[l]==a[r]) continue;

                int l1=lower_bound(s[a[l]].begin(),s[a[l]].end(),l)-s[a[l]].begin();
                int r1=lower_bound(s[a[r]].begin(),s[a[r]].end(),r)-s[a[r]].begin();
                s[a[l]][l1]=r;
                s[a[r]][r1]=l;
                swap(a[l],a[r]);
            }
    }
    return 0;
}

T3 我不会啊我不会啊呵呵
给你个12分代码自己看吧

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int n,k;
int a[200005];
int ans[200005];
int tt=0;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
    register int i;
    n=read();
    k=read();
    for(i=1;i<=n;i++){
        a[i]=read();
    }
    if(n==2&&k==1){
  //特判大法好 
        int tot=a[1]+a[2];
        int fen=sqrt(tot);
        if(fen*fen!=tot){
            cout<<1<<endl;
            return 0;
        }
        else{
            cout<<2<<endl;
            cout<<1;
            return 0;
        }
    }
    else if(n==2){
        cout<<1<<endl;
        return 0;
    }
    else if(k==1){
        int zhong=n;       
        int last=n;
        while(zhong){
            zhong--;
            if(zhong==0) break;
            for(i=last;i>zhong;i--){
                int tot=a[i]+a[zhong];
                int fen=sqrt(tot);
                bool flag=0;
                if(fen*fen==tot){
                    tt++;
                    ans[tt]=zhong;
                    last=zhong;
                    flag=1;
                }
                if(flag) break;
            }
        }
        printf("%d\n",tt+1);
        for(int i=tt;i>1;i--){
            printf("%d\n",ans[i]);
        }
        printf("%d",ans[1]);
        return 0;
    }   
    return 0;
}
/* 5 1 1 3 15 10 6 */