本文共 9909 字，大约阅读时间需要 33 分钟。

Powered by:AB_IN 局外人

只会这些题了。。

模拟就$ok$。

#include <bits/stdc++.h>using namespace std;int main() {   	int v1, v2, t, s, l;	cin >> v1 >> v2 >> t >> s >> l;		int s1 = 0, s2 = 0;		int time1 = 0, time2 = 0;		while (s1 < l && s2 < l) {   			if (s1 - s2 >= t) {   				s1 = v1 * time1;				time2 += s;				s2 = v2 * time2;			}			else {   				time1++, time2++;				s1 = v1 * time1;				s2 = v2 * time2;			}		}		if (s1 < s2)			cout << "Hong " << l / v2 << endl;		else if (s1 > s2)			cout << "Ming " << time2 << endl;		else			cout << "Tie " << time2 << endl;}

bfs板子题。
手贱一个地方写错了，改了将近两小时，按着标程提交了三四十次，终于找出来了。。

#include <bits/stdc++.h>using namespace std;int x2[] = {    0,0,1,-1 ,1,1,-1,-1 };int y2[] = {    1,-1,0,0 ,1,-1,1,-1 };struct sa{       int x;    int y;    int step;};queue<sa>q;char a[55][55];bool judge[55][55];int n,m,xg,yg;bool check(int x,int y){       if (x<0||y<0||x>n||y>m) return false;    for(int i=0;i<8;i++){           int x5=x+x2[i];        int y5=y+y2[i];        if(a[x5][y5]=='*') return false;    }    return !judge[x][y];//最后再判断是否经过}int bfs(int x,int y){       q.push({   x,y,0});    judge[x][y]=true;    while(!q.empty()){           sa tmp=q.front();        q.pop();        int x3=tmp.x;        int y3=tmp.y;        if(a[x3][y3] == 'E')             return tmp.step;        for(int i=0;i<4;i++){               int x4=x3+x2[i];            int y4=y3+y2[i];            if(check(x4,y4))            {                   q.push({   x4,y4,tmp.step+1});                judge[x4][y4]=true;//就是这！！！！！if里都是x4,y4!!!!            }        }    }    return -1;}int main(){       ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);    while(cin>>n>>m){       memset(judge,0,sizeof(judge));    for(int i=1;i<=n;i++){           for(int j=1;j<=m;j++){               cin>>a[i][j];            if(a[i][j]=='S') {   xg=i;yg=j;}        }    }    int ans=bfs(xg,yg);    if(ans==-1) cout<<"Impossible"<<endl;    else cout<<ans<<endl;    }    return 0;}

异或的最大值，那么就得出1。怎么出1呢？两个数不同就出1。
比如给出10，它的二进制为1010。
那么10以内必有一个0101。这样两个数异或就是1111，就是最大了。
需要特判一下1。

n=len(bin(int(input()))[2:]);ans=0if n==1:    print('0')else:    for i in range(n):        ans+=2**i    print(ans)

#include <bits/stdc++.h>using namespace std;typedef unsigned long long ll;ll n,x=1;int main(){       cin>>n;    if(n==1)        cout<<'0'<<endl;    else{           while(x<=n)  x*=2;        cout<<x-1<<endl;    }    return 0;}

板子

#include <bits/stdc++.h> const int N=1e7+5;int  cnt,sum,ans,prime[N],pre[N];bool flag[N]; using namespace std;void init(){       memset(flag,1,sizeof(flag));    flag[1]=cnt=0;    for(int i=2;i<=N;i++)    {           if(flag[i])        {               prime[++cnt]=i;            pre[i]=cnt;        }        for(int j=1;j<=cnt&&prime[j]*i<=N;j++)        {               flag[prime[j]*i]=0;            if(i%prime[j]==0)break;        }    }}

二分做法
记一下cnt是记录当前素数个数。
这个使用的是prime数组，然后二分即可，之前提到过区间问题，全是闭的话，就左区间--,右区间不变,然后都用upper_bound即可。

#include <bits/stdc++.h>#pragma GCC optimize(2)#pragma GCC optimize(3)typedef  long long ll;const ll N=1e7+5;ll  cnt,sum,ans,prime[N],pre[N];bool flag[N];using namespace std;namespace IO{       char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);    inline char gc(){           if(ip!=ip_)return *ip++;        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);        return ip==ip_?EOF:*ip++;    }    inline void pc(char c){           if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;        *op++=c;    }    inline ll read(){           register ll x=0,ch=gc(),w=1;        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;        return w*x;    }    template<class I>    inline void write(I x){           if(x<0)pc('-'),x=-x;        if(x>9)write(x/10);pc(x%10+'0');    }    class flusher_{       public:        ~flusher_(){   if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}    }IO_flusher;}using namespace IO;void init(){       memset(flag,1,sizeof(flag));    flag[1]=cnt=0;    for(ll i=2;i<=N;i++)    {           if(flag[i])        {               prime[++cnt]=i;            pre[i]=cnt;        }        for(ll j=1;j<=cnt&&prime[j]*i<=N;j++)        {               flag[prime[j]*i]=0;            if(i%prime[j]==0)break;        }    }}ll t,a,b;int main(){       init();    t=read();    while(t--){           a=read();b=read();        a--;        write(upper_bound(prime+1,prime+cnt+1,b)-upper_bound(prime+1,prime+cnt+1,a));        pc('\n');    }}

前缀和做法
定义了一个数组v[N]为前缀和数组，那加什么呢？加的是判断数组flag[N]。
如果是True那么加1，不是则不变。
看一看这个数组长啥样：

每一个数都有值。
再对照着看看flag:

#include <bits/stdc++.h>#pragma GCC optimize(2)#pragma GCC optimize(3)typedef  long long ll;const ll N=1e7+5;ll  cnt,sum,ans,prime[N],pre[N],v[N];bool flag[N];using namespace std;namespace IO{       char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);    inline char gc(){           if(ip!=ip_)return *ip++;        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);        return ip==ip_?EOF:*ip++;    }    inline void pc(char c){           if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;        *op++=c;    }    inline ll read(){           register ll x=0,ch=gc(),w=1;        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;        return w*x;    }    template<class I>    inline void write(I x){           if(x<0)pc('-'),x=-x;        if(x>9)write(x/10);pc(x%10+'0');    }    class flusher_{       public:        ~flusher_(){   if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}    }IO_flusher;}using namespace IO;void init(){       memset(flag,1,sizeof(flag));    flag[1]=cnt=0;    for(ll i=2;i<=N;i++)    {           if(flag[i])        {               prime[++cnt]=i;            pre[i]=cnt;        }        for(ll j=1;j<=cnt&&prime[j]*i<=N;j++)        {               flag[prime[j]*i]=0;            if(i%prime[j]==0)break;        }    }}ll t,a,b;int main(){       init();    t=read();    for(ll i=2;i<=N;i++)//这里变成了N        v[i]=v[i-1]+flag[i];    while(t--){           a=read();b=read();        write(v[b]-v[a-1]);        pc('\n');    }}

a=int(input())b=int(input())if a>b:    print(">")elif a<b:    print("<")else:    print("=")

逆元+组合数。

1. 什么时候用逆元？
   当处理除数很大时。

2. 逆元是什么？
   每个数a均有唯一的与之对应的乘法逆元x，使得 $ax\equiv 1(modn)$

3. 什么是费马小定理？
   费马小定理是数论中的一个重要定理。如果n是一个质数，而整数a不是n的倍数，则有 $a^{n-1}\equiv 1（modn）$。

4. 怎么用费马小定理推导逆元公式？
   一般ACM要求的模数都是质数，所以是存在逆元的
   $$a^{n-1}\equiv 1(modn)$$
   $$a\ast a^{n-2}\equiv 1(modn)$$
   $$\frac{a}{b}\equiv \frac{a}{b}\ast (b\ast b^{n-2})(modn)$$($(b\ast b^{n-2})(modn)$其实相当于1）
   $$\frac{a}{b}\equiv a\ast b^{n-2}(modn)$$
   证毕。

   注：a必须可以整除以b！！！

• 代码注意事项

1. 因为 要求$C_{n+m-2}^{n-1}$故数组要开2*(1e6+10)。
2. 预处理将所有的阶乘都取模算好。
3. 本身求最短路径可以用$dp$做，但是这个$n,m$较大，不支持用二维数组和复杂度，并且还是多组输入，所以直接用组合数算。
4. 从$(1,1)$到$(n,m)$ 向下向右一共走$n+m-2$步，其中向下走$n-1$步，向右走$m-1$步，所以$C_{n+m-2}^{n-1}$ 或者$C_{n+m-2}^{m-1}$

#include <bits/stdc++.h>#pragma GCC optimize(2)#pragma GCC optimize(3)typedef unsigned long long ull;typedef long long ll;const ll maxn=2*(1e6+10);const int mod = 1e9 + 7;ll fac[maxn],t,n,m;using namespace std;namespace IO{       char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);    inline char gc(){           if(ip!=ip_)return *ip++;        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);        return ip==ip_?EOF:*ip++;    }    inline void pc(char c){           if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;        *op++=c;    }    inline ll read(){           register ll x=0,ch=gc(),w=1;        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;        return w*x;    }    template<class I>    inline void write(I x){           if(x<0)pc('-'),x=-x;        if(x>9)write(x/10);pc(x%10+'0');    }    class flusher_{       public:        ~flusher_(){   if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}    }IO_flusher;}using namespace IO;ll quickmod (ll a, ll b ,ll c){       ll ret=1%c;    while(b){           if(b&1)            ret=ret*a%c;        a=a*a%c;        b=b>>1;    }    return ret;}ll inv(ll x) {       return quickmod(x, mod-2, mod);}ll C(ll n,ll m){       return fac[n]*(inv(fac[n-m])*inv(fac[m])%mod)%mod;}int main(){       fac[0]=1;    for(int i=1;i<=maxn;i++){           fac[i]=fac[i-1]*i%mod;    }    t=read();    while(t--){           n=read();m=read();        write(C(n+m-2,n-1));        pc('\n');    }}

排个序，滑动窗口过一遍就行了。

#include <bits/stdc++.h>#pragma GCC optimize(2)#pragma GCC optimize(3)typedef  long long ll;const int  maxn=2e5+10;using namespace std;namespace IO{       char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);    inline char gc(){           if(ip!=ip_)return *ip++;        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);        return ip==ip_?EOF:*ip++;    }    inline void pc(char c){           if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;        *op++=c;    }    inline ll read(){           register ll x=0,ch=gc(),w=1;        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;        return w*x;    }    template<class I>    inline void write(I x){           if(x<0)pc('-'),x=-x;        if(x>9)write(x/10);pc(x%10+'0');    }    class flusher_{       public:        ~flusher_(){   if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}    }IO_flusher;}using namespace IO;int a[maxn],n;int main(){       n=read();    for(int i=1;i<=n;i++)        a[i]=read();    sort(a+1,a+1+n);    int i=1,j=1;    int ans=0;    while(i<=j&&j<=n){           if(a[j]-a[i]>5){               i++;        }       else{               ans=max(ans,j-i+1);//基本都在指针变化前            j++;       }    }    write(ans);    pc('\n');    return 0;}