D-牛牛与整除分块

规律题
临界点是sqrt(n)
令b=n/x （此题分析从此以下的规律即结论都是举例找出来的）
当x<=sqrt(n)时：b大且分布得比较稀疏（每个b相差好几个数），所以x分别对应一个b,所以此时b是第几大的数？第x大的数。
当x>sqrt(n)时：b小且分别得比较稠密，所以可能几个x对应着同一个b（每个b是在整数意义上连续的）,所以此时b是第几大数？第 sqrt(n)+(n/(sqrt(n)+1)-n/x+1) 大的数
以n=25,x=9为例，临界点a=sqrt(25)=5

当x<=5时

#include<bits/stdc++.h>
using namespace std;
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
int t;
ll n,x,z;
int main(){
    fio;
    cin >> t;
    while(t--){
        cin >> n >> x;
        if(x*x<=n) cout << x << "\n";
        else {
            z=sqrt(n);
            z+=n/(z+1)-n/x+1;
            cout << z << "\n";
        }
    }
    return 0;
} 

C-牛牛与字符串border （找规律的题目，要找临界点，然后分别看大于和小于以及等于的情况）

此题找规律，举例子
因为题目要求完全匹配（一模一样）
所以子字符串要有两个，即 2l==n 是临界点
所以分别举 2l<n;2l==n;2l>n; 的例子
例如将n=14,l=6;n=16,l=6;n=5,l=3;时的情况一一列出，
可发现最终的字符串有循环节：
1.当 2l>=n 时，循环节 a=n-l
2.当 2l<n 时，循环节 a=gcd(n,l)
而循环节中用什么字母呢？
因为题目要求修改次数最少
所以使用出现次数最多的字母
注意：此题未给出 t 的取值范围，虽然memset的复杂度为O(n),但TLE了，所以用for手动初始化
补充：memset比用for初始化常数大一些，空间耗费的也多一些；fill的复杂度也是O(n)
参考代码

int const N=1e5+7;
int t,n,l,a;
string str;
int cnt[N][30],maxn[N];  //cnt表示循环节中每个位置26个字母各自出现的次数 //maxn表示循环节中每个位置当前字母出现的最多次数
char ans[N];  //循环节
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    fio;
    cin >> t;
    while(t--){
        //memset(cnt,0,sizeof(cnt));
        //memset(ans,0,sizeof(ans));
        //memset(maxn,0,sizeof(maxn));
        cin >> n >> l;
        cin >> str;
        if(2*l>=n) a=n-l;
        else a=gcd(n,l); 
        //初始化 
        for(int i = 0; i < a; i++){
            for(int j = 0; j < 26; j++)
                cnt[i][j]=0;
            maxn[i]=0;
        }

        int z=0;
        for(int i=0;i<n;++i){
            z=i%a;
            cnt[z][str[i]-'a']++;
            if(cnt[z][str[i]-'a']>maxn[z]){
                maxn[z]=cnt[z][str[i]-'a'];
                ans[z]=str[i];
            }
        }
        for(int i=0;i<n;++i){
            cout << ans[i%a];
        }
        cout << "\n";
    }
    return 0;
}

I-牛牛的“质因数”（埃式筛运用）（用lg求其位数）

规律题
f[x]为题中所给的含义
由于题目中有质数，结合欧拉筛
再举例子观察可得：
f[x]=p* 10^k+f[x/p]; //其中p为最小质因子 //如：f[6]=2 *10^1+f[6/2] ; f[15]=3 *10^2+f[15/3];
上式中的k为f[x/p]的位数,例：f[15/3]的位数为两位，所以此时的k为2

再观察题目：将x的所有质因数从小到大拼接
而欧拉筛是用其最小质因子p，所以p在第一位（也有可能像17这样是两位的），所以此时k求出的是后面的位数，有些耗时，可以再优化一下
所以我们可以考虑p为最大的质因数可得：
f[x]=f[x/p] *10^k+p; //因为质因数从小到大拼接且p为最大的质因数，所以此时的p在最后一位（也有可能像17这样是两位的），所以此时的k为p的位数
如：f[6]=f[6/3] *10^1+2; f[15]=f[15/5] *10^2+3;
那怎样用（找出）最大质因子呢？
比较：欧拉筛每个数筛一次（用最小质因子筛）（ O(n) ）
埃式筛每个数筛多次（最后一次用最大质因子筛掉）（ O(nlglgn) ）
所以用埃式筛找最大质因子，并在筛法中维护f[x]即可解答此题
且初始边界为 if(x==质数) f[x]=x;

怎样求位数k?(以后统一用方法一)：
1.用log10(x)求x的位数，位数=ceil( lg10（x） )
2.令t[x]为x的位数（此方法只针对此题）
t[x]=t[x/p]+t[p]
边界:if(x==质数) t[x]=用函数求其位数

具体请看代码

注（可以不看这段话）：欧拉筛也可以做，但不能边筛边维护
因为欧拉筛用最小质因子筛，如维护f[12]时，f[12/2]此时并无值，并且以后也并不会更新
且初始边界为 if(x==质数) f[x]=x;

int const N=4e6+7;
int const mod=1e9+7;
ll n,ans;
ll f[N];
ll pan(int a){
    ll res=1;
    for(int i=1;i<=a;++i){
        res*=10;
    }
    return res;
} 
int main(){
    cin >> n;
    for(int i=2;i<=n;++i){ //埃式筛复杂度为 O(nlglgn) 
        if(f[i]==0){
            f[i]=i;   //若未被前面的筛掉，说明i是一个质数
            for(int j=i+i;j<=n;j+=i){  //筛掉i的倍数
                f[j]=(f[j/i]*pan ( ceil(log10(i)) )%mod+i)%mod;   
            }
        }    
    }
    for(int i=2;i<=n;++i){
        ans=(ans+f[i])%mod;
    }
    cout << ans;
    return 0;
}

F-牛牛与交换排序（reverse-O(n)）（deque）

k=第一个乱序的数 的位置 - 本该待在这个位置的数 的位置
求完k后，在判断k是否能把数列变得有序

reverse(a+1,a+n+1)的复杂度为O(n)
所以题目中的反转操作，可以用双端队列deque完成，即每次反转过后就在另一边插入；删除的话同理

int const N=1e5+7;
int n,f,sx,ex;
int a[N];
int main(){
    fio;
    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> a[i];
        if(!f&&i!=a[i]){
            sx=i;f=1;
        }
        if(f&&sx==a[i]){
            ex=i;
        }
    }
    f=0;
    int k=ex-sx+1;
    reverse(a+sx,a+ex+1);
    for(int i=sx;i<=n;++i){
        if(i!=a[i]){
            if(i+k>n+1){
                f=1;break;
            }
            reverse(a+i,a+i+k);
            if(i!=a[i]){ 
                f=1;break;
            }
        }
    }
    if(f) cout << "no";
    else cout << "yes" << "\n" << k;
    return 0;
} 

E-牛牛与跷跷板（前向星的bfs）

题目求最小的跳跃次数，果断可以想到bfs
又相邻的木板之间才可搜（才连通）
那么可以把它抽象成图，相邻的木板连边长为1的边 //若两两看是否相邻会超时，所以先排序，再用了双指针优化了
此时既可以用最短路也可以用bfs(下面用的是bfs,为了使代码短点）

结论：bfs的题目一般都可以用图的最短路来求

int const N=1e5+7;
int n;
struct node{
    int a,next,len;
}e[2000007];
int head[N],cnt;
void add(int x,int y,int len){
    e[++cnt].a=y;
    e[cnt].len=len;
    e[cnt].next=head[x];
    head[x]=cnt;
}
struct L{
    int y,l,r,id;
}a[N];
bool cmp(L a,L b){
    if(a.y==b.y) return a.l < b.l;
    return a.y < b.y;
}
int dis[N];
void bfs(int sx,int ex){
    queue<int>q;
    q.push(sx);
    dis[sx]=1;
    while(!q.empty()){
        int u=q.front();
        for(int i=head[u];i;i=e[i].next){
            if(dis[e[i].a]) continue;
            q.push(e[i].a);dis[e[i].a]=dis[u]+1;
            if(dis[n]) break;  //e[i].a==n
        }
        q.pop();
    }
}
int main(){
    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> a[i].y >> a[i].l >> a[i].r;
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    int p=1,q=1;
    for(int i=1;i<=n;++i){
        if(a[i].r==a[i+1].l&&a[i].y==a[i+1].y){
            add(a[i].id,a[i+1].id,1);
            add(a[i+1].id,a[i].id,1);
        }
        while(p<=n&&a[p].y==a[i].y) p++;
        q=max(p,q);
        while(q<=n&&a[q].y==a[p].y) q++;
        for(;p<q;++p){
            if(a[p].l>=a[i].r) break;
            if(a[p].r<=a[i].l) continue;
            add(a[i].id,a[p].id,1);
            add(a[p].id,a[i].id,1);
        }
        if(p>1) p--;
    }
    bfs(1,n);
    cout << dis[n]-1;
    return 0;
}

J-牛牛想要成为hacker

要使其不构成三角形，用fabi数列
当其数据范围为10^5，直接用会超过10^9,甚至会爆long long
所以要找到一个k使其刚好超过 n* n *logn （n最大取10^5）
即前k个用fabi数列，剩下的补一即可

怎样求k?
当n=10^5时
循环次数之和 >= n^2 lgn
即 循环次数之和 >= 16* n^2 //循环次数可用等差数列求得
得 k=33

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
int n;
ll a[N];
int main(){
    cin >> n;
    a[0]=1;a[1]=2;
    cout << a[1] << " " ;
    for(int i=2;i<=n&&i<=40;++i){
        a[i]=a[i-1]+a[i-2];
        cout << a[i] << " ";
    }
    for(int i=41;i<=n;++i){
        cout << 1 << " ";
    }
    return 0;  
}

G-牛牛与比赛颁奖(离散化的差分)（(n+k-1)/k表示n/k向上取整）

和校门外的树类似（连续的修改，区间修改）

int const M=1e5+7;
struct L{
    int pos,num;
}a[M<<1];   //差分数组
int n,m;
int num[M];   //num[i]表示ac了i题的人数 
bool cmp(L a,L b){
    if(a.pos ==b.pos ) return a.num < b.num ;     //确定先后即先减后加，防止出错
    return a.pos < b.pos ;
}
int cnt; 
int main(){
    cin >> n >> m;
    for(int i=1;i<=m;++i){
        int l,r;
        cin >> l >> r ;
        a[++cnt].pos =l;a[cnt].num++ ;
        a[++cnt].pos =r+1;a[cnt].num--;
    }
    sort(a+1,a+cnt+1,cmp);
    int sum=0,maxn=0;
    for(int i=1;i<=cnt;++i){
        sum+=a[i].num ;   //将离散化的差分做前缀和，从而求出原来的值 //即sum表示某队的ac题目的数量
        if(a[i].pos !=a[i+1].pos ){ 
            num[sum]+=a[i+1].pos -a[i].pos ;
            maxn=max(maxn,sum);
        }
    }
    int j=0,y=0,t=0;
    for(int i=maxn;i>=0;--i){
        num[i]+=num[i+1];  //num[i]表示做后缀和，表示ac了i题以上的人数 
        if(j==0&&num[i]>=(n+9)/10) j=i;    // (n+9)/10)表示n/10向上取整
        if(y==0&&num[i]>=(n+3)/4) y=i;
        if(t==0&&num[i]>=(n+1)/2) t=i; 
    }
    j=max(1,j);y=max(1,y);t=max(1,t);
    cout << num[j] << " " << num[y]-num[j] << " " << num[t]-num[y];
    return 0;
}