计蒜客 NOIP 提高组模拟竞赛第一试 补记

A. 广场车神

题目大意：

一个\(n\times m(n,m\le2000)\)的网格，初始时位于左下角的\((1,1)\)处，终点在右上角的\((n,m)\)。每次移动可以选择移动到自己右上方的某一方格，且横坐标和纵坐标的变化都不能超过\(k(k\le2000)\)。求一共有多少种移动方案？

思路：

\(f[i][j]\)表示走到\((i,j)\)的方案数，一边DP一边维护二维前缀和即可。

时间复杂度\(\mathcal O(nm)\)。

源代码：

#include
    
     #include
     
      #include
      
       inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}const int N=2001,mod=998244353;int f[N][N],g[N][N];inline int sum(int x1,const int &x2,int y1,const int &y2) {    x1=std::max(x1-1,0);    y1=std::max(y1-1,0);    return (((g[x2][y2]+g[x1][y1])%mod-(g[x1][y2]+g[x2][y1])%mod)%mod+mod)%mod;}int main() {    freopen("racing.in","r",stdin);    freopen("racing.out","w",stdout);    const int n=getint(),m=getint(),k=getint();    f[1][1]=g[1][1]=1;    for(register int i=1;i<=n;i++) {        for(register int j=1;j<=m;j++) {            if(i==1&&j==1) continue;            g[i][j]=((g[i-1][j]+g[i][j-1]-g[i-1][j-1])%mod+mod)%mod;            f[i][j]=sum(i-k,i,j-k,j);            (g[i][j]+=f[i][j])%=mod;        }    }    printf("%d\n",f[n][m]);    return 0;}
      
     
    

B. 敌对势力

题目大意：

给定一棵\(n(n\le10^5)\)个结点的树，\(m(m\le10^5)\)次询问，每次询问路径\((a,b)\)和路径\((c,d)\)是否有交。

思路：

树链剖分后，有线段树在\((a,b)\)路径上+1，然后看一下\((c,d)\)路径上是否为\(0\)即可。

时间复杂度\(\mathcal O(m\log^2n)\)。

源代码：

#include
    
     #include
     
      #include
      
       inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}const int N=1e5+1;std::vector
       
         e[N];inline void add_edge(const int &u,const int &v) {    e[u].push_back(v);    e[v].push_back(u);}int dep[N],par[N],size[N],son[N],top[N],dfn[N];void dfs(const int &x,const int &par) {    size[x]=1;    ::par[x]=par;    dep[x]=dep[par]+1;    for(auto &y:e[x]) {        if(y==par) continue;        dfs(y,x);        size[x]+=size[y];        if(size[y]>size[son[x]]) son[x]=y;    }}class SegmentTree {    #define _left <<1    #define _right <<1|1    #define mid ((b+e)>>1)    private:        bool val[N<<2],tag[N<<2];    public:        void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const int &t) {            val[p]+=t;            if(b==l&&e==r) {                tag[p]+=t;                return;            }            if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),t);            if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r,t);        }        bool query(const int &p,const int &b,const int &e,const int &l,const int &r) const {            if(tag[p]) return true;            if(b==l&&e==r) return val[p];            if(l<=mid&&query(p _left,b,mid,l,std::min(mid,r))) return true;            if(r>mid&&query(p _right,mid+1,e,std::max(mid+1,l),r)) return true;            return false;        }    #undef _left    #undef _right    #undef mid};SegmentTree sgt;void dfs(const int &x) {    dfn[x]=++dfn[0];    top[x]=x==son[par[x]]?top[par[x]]:x;    if(son[x]) dfs(son[x]);    for(auto &y:e[x]) {        if(y==par[x]||y==son[x]) continue;        dfs(y);    }}inline void modify(int x,int y,const int &t) {    while(top[x]!=top[y]) {        if(dep[top[x]]
       
      
     
    

C. 提高水平

题目大意：

有\(n(n\le20)\)个东西，第\(i\)个东西放在第\(j\)个东西前可以获得\(a_{i,j}\)的收益。问如何排列这些东西使得收益最大？

思路：

状压DP。

时间复杂度\(\mathcal O(2^nn)\)。

源代码：

#include
    
     #include
     
      #include
      
       inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}const int N=20;int a[N][N],f[1<
       
        <
        
         >23&255)-127;}int main() {    freopen("proficiency.in","r",stdin);    freopen("proficiency.out","w",stdout);    const int n=getint(),all=(1<
         
          >j)&1) { f[i]=std::max(f[i],f[i^(1<