千题目标CategorySubscribe

http://lx.lanqiao.cn/problem.page?gpid=T451

题意是给定n<=10000个区间，保证总长度大于等于10000，有重叠，让求最大移动的最小值是多少。

首先这个问法就很二分，但是check的方法不好想。

wjjj随便猜了个结论就猜对了（%%%）。二分后按照b排序，优先选b小的。

因为二分出mid后，对于任意一个区间，只能在[a-mid,b+mid]里移动。所以最开始假设没有覆盖，当前点k=0，从左到右选出可以覆盖的区间，尽量往右放进行覆盖，覆盖完以后k移动到本次覆盖区间的最右边。在多个区间都可以覆盖当前点k的时候，b小的肯定在向右移动的时候不是最优解，因为它无论如何都比比它b大的移动得多。最后如果找不到方案可以覆盖完整个区间就说明答案太小，否则答案可能太大。至于小数，可以证明只会有0.5出现，因为最开始的区间都是整数，如果有一个区间移动了1/3那么必然有一个区间需要移动2/3。肯定不是最优解。既然只有0.5那直接把区间长度扩大一倍，规定只能移动整数距离，最后答案half就可以了。

在查找b的时候不能暴力找，否则会炸掉，可以用二分来找，但是注意标记已经用过的区间，我直接用了multiset方便删除用过的区间，复杂度都是logN。总复杂度Nlog²N

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-12;
const int N=20000;
vector<pii> ab;
int vis[10001];
multiset<pii> c2;
int line[10001]; 
int main()
{
    int n,a,b;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        a*=2;b*=2;
        c2.insert({b,a});
    }
    int l=0,r=N;
    while(r>l)
    {
        multiset<pii> c1(c2);
        int mid=(l+r)>>1;
        int now=0;
        while(1)
        {
            int flag=0;
            multiset<pii>::iterator it;
            for(it=c1.begin();it!=c1.end();it++)
            {
                pii tmp=*it;
                int tta=tmp.second,ttb=tmp.first;
                if(tta-mid <= now && ttb+mid >= now)
                {
                    flag=1;
                    int len=ttb-tta;
                    if(now<=tta+mid) 

http://codeforces.com/problemset/problem/1110/C

题意是给一个a让求一个0<b<a使得gcd(a ^ b , a & b) 要最大

• 首先注意到a^b和a&b的每一位都是相反的，所以说很容易想到构造一个b使得b&a=0，这样答案就是a^b。构造方法就是把a的每一位1变成0，0变成1。
• 对于a的每一位全是1的情况需要单独讨论。
• 如果a的每一位都是1，任取一个b，可以得到a^b=a-b , a&b=b 这个结论。那么问题就变成了求gcd(a-b,b)，也就是gcd(a,b)_max。
• 对于求最大的gcd，把a分解质因数，除掉其中一个最小的质因子，就是答案。
• 由于本题时间不紧，而且cf测评机都是香港记者，所以可以直接根号复杂度暴力分解。当然也可以预处理质数表

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int q,a;
int main()
{
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&a);
        //a=q;
        int res=0;
        for(int i=0;(1<<i)+res < a;i++)
        {
            if(!((1<<i)&a) ) 
                res+=(1<<i); 
            //cout<<res<<'-';
        }
        if(res) printf("%d\n",res^a);
        else
        {
            bool flag=true;
            for(int i=2;i*i<=a;i++) 
            {
                if(a%i==0)
                {
                    flag=false;
                    printf("%d\n",a/i);
                    break;
                }
            }
            if(flag) printf("1\n");
        }
    }
}

https://ac.nowcoder.com/acm/contest/327/I

这题有点坑的就是，这题其实和本场比赛上一题一点关系都没有……

直接分解质因子以后暴力n²枚举就可以，下面来分析一下这么做的时间复杂度:

• 对于每个数分解质因子，sqrt(n)的复杂度，打素数表可以更快。2000*20=40000
• 对于每个数枚举其他数，由于分解的时候质因子是有序的，所以对两个数可以归并排序的方法线性合并质因子。
• 小知识点：对于1e9以内的数，一般不同的质因子个数不超过10个
• 所以对于合并的复杂度，不会超过o(20)，2000*2000*20=80000000
• 总复杂度小于1e8，且常数极小，可以接受

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,ans=0;
vector<pii> a[2002];
int main()
{
    scanf("%d",&n);
    for(int j=1;j<=n;j++)
    {
        int k;
        scanf("%d",&k);
        for(int i=2;i*i<=k;i++)
        {
            int res=0;
            if(k%i==0)
            {
                while(k%i==0)
                {
                    k/=i;
                    res++;
                }
                a[j].push_back(make_pair(i,res));
            }  
        }
        if(k>1) a[j].push_back(make_pair(k,1));
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            int l=0,r=0,tmp=1;
            auto &aa=a[i];
            auto &bb=a[j];
            while(l<aa.size() && r<bb.size())
            {
                if(aa[l].first<bb[r].first) tmp*=aa[l++].second+1;
                else if(aa[l].first>bb[r].first) tmp*=bb[r++].second+1;
                else tmp*=aa[l++].second+bb[r++].second+1;
            }
            while(l<aa.size()) tmp*=aa[l++].second+1;
            while(r<bb.size()) tmp*=bb[r++].second+1;
            if(tmp<=10) ans++;
        }
    }
    printf("%d\n",ans);

今天在群里看见一道题目

首先这题模数是一个大质数，所以考虑求分母的逆元

由于只需要算一次，没有变量也没有多次询问，所以直接暴力求20192019!%p的结果，然后用费马小定理求出其逆元即可

对于分母，也可以用欧拉定理来降幂，由于p是个质数，所以p的欧拉函数值就是p-1，可以直接放上分子，然后对分子进行快速幂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll qsm(ll n,ll k,ll md)
{
    ll res=1;
    while(k)
    {
        if(k&1) res=(res*n)%md;
        n=(n*n)%md;
        k>>=1;
    }
    return res%md;
}
int main()
{
    ll fac=1;
    for(int i=1;i<=20192019;i++) fac=(fac*i)%mod;
    ll inv=qsm(fac,mod-2,mod);
    ll son=qsm(2019,qsm(2019,2019,mod-1),mod);
    cout<<inv*son%mod<<endl;
}

补充：
对于阶乘的逆元，可以O(N)预处理出其逆元。
假设用费马小定理求出了q!的逆元(q!)^{-1}。那么就有
(q!) * (q!)^{-1} \equiv 1
(q-1)! * q * (q!)^{-1} \equiv 1
从上式可以看出(q-1)!的逆元就是q * q!^{-1}

fact[0]=1;
for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;
invfact[n]=qsm(n,mod-2);
for(int i=n;i>=1;i--) 

链接：https://ac.nowcoder.com/acm/contest/317/H
来源：牛客网

本题考查对卡特兰数的理解。突破点就是2n天恰好写n天作业。

先把问题抽象成：任意位置，不写为-1，写了为+1，要求在任意位置，前缀和大于-k。

当K=1的时候。结果就是卡特兰数。

如图，卡特兰数的几何理解。假设写了为往x轴+1，没写为y+1，任何时刻写了要大于等于没写，所以任意合法路径不能够超过y=x+1这条线。

对于任意不合法路径，将其从第一个不合法的地方开始，把剩余图像关于y=x+1对称。那么要达到的(n,n)就变成了(n-1,n+1)。所以对于任意不合法路径，可以看作一条到(n-1,n+1)的路径。

合法路径的条数就是到（n,n）的条数减去到（n-1，n+1）的条数。也就是C(2n，n)-C(2n，n-1)  （因为有一次横着走变成了竖着走，所以是n-1）

本题对于卡特兰数的几何意义作了推广，把y=x+1变成了y=x+k,所以答案就是C(2n,n)-C(2n,n-k)

这里还有一个考点就是组合数取模，有很多做法，由于P不一定是质数，不一定有逆元，可以套线性筛模板，把组合的质因子和幂处理出来，再快速幂。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e6+233;
int primes[N], cnt;
ll st[N];
ll sum[N];
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; j < cnt && i * primes[j] <= n; j ++ )
        {
            st[primes[j] * i] = primes[j];
            if (i % primes[j] 

链接：https://ac.nowcoder.com/acm/contest/317/D
来源：牛客网

#include
using namespace std;
typedef long long ll;
const 

链接：https://ac.nowcoder.com/acm/contest/317/C

来源：牛客网

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4;
int n;
int p[maxn];
vector<int> v;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&p[i]);
    }
    if(n==1) {printf("%d",p[0]);return 0;}
    if(p[n-1]>=p[0]) {printf("-1"); return 0;}
    for(int i=1;i<n-1;i++)
    {
        if(p[i]>p[n-1] && p[i]<p[0]) v.push_back(p[i]);
    }
    int ans=p[0]^p[n-1];
    if(v.size())
    {
        for(int i=14,k=0;i>=0;i--)
        {
            for(int j=k;j<v.size();j++)
            {
                if(v[j]>>i & 1) 
                {
                    swap(v[j],v[k]);
                    break;
                }
            }
            if(v[k]>>i & 1)
            {  
                for(int j=k+1;j<v.size();j++)
                {
                    if(v[j]>>i && 1) v[j]^=v[k];
                }
                k++;
            }
        }
        for(int i=14,k=0;i>=0;i--)
        {
            if(v[k]>>i 

链接：https://ac.nowcoder.com/acm/contest/329/G
来源：牛客网

输入描述:

一行包括两个数字l,r，表示你给处女座展示的数字范围为[l,r]。

输出描述:

一行一个整数，表示处女座内心激动的次数。

10 20

1

备注:

$0\le l\le r\le {10}^{18}$

此题做法很多。

1.数学

可以先想求不含6的数有多少个，那么题目实际上是问的去掉6以后，给定一个数，问这个数在不含6的数组成的序列中排第几个。那么可以看成是给定一个9进制数，问在十进制数里排第几个（值是多少）。

比如18，看成九进制，[latex]1*9^1 + 7*9^0 = 16[/latex] 。由于6被去掉了，那么8就排在了第7位。这个思想在很多题目里都可以用到。

那么如果给定的数本来就含6怎么处理呢？第一，x5999和x6xxx内所包含的 不含6 的数其实是一样多的。第二，通过列表可以发现，凡是某一位有6的都不存在了，相当于问1和2之间有多少个1。所以对于含6的数，把最高位的6改为5，低位全部改成9就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r,pl,pr;
ll ni[22]={0},num[22]={0};

string s;
int len;
ll getnum(ll k)
{
    if(k<6) return k;
    return k-1;
}
ll solve(ll k)
{
    int cnt=0;
    memset(num,0,sizeof(num));
    int flag=0;
    while(k)
    {
        if(k%10==6) flag=1;
        num[cnt++]=k%10;
        k/=10;
    }
    if(flag) 
        

http://poj.org/problem?id=1961

Description