2017.9.14 NOIP模拟赛

题解 套题

目录

• 2017.9.14 NOIP模拟赛
  • Bookstore
    • 思路
    • 代码
  • Table
    • 思路
    • 代码
  • Board
    • 思路
    • 代码

Bookstore

思路

• 显然贪心，将价钱排序降序后，三个三个选就行了；
• 因为这样可以免费拿到的书总价值最大，反证法即易证。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    x=0;
    int pm=1; char c;
    do{c=getchar();}while(!isdigit(c) && c!='-');
    c=='-' ? pm=-1:x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <algorithm>
using std::sort;
const int MAXN=1e5+5;
int n,lim;
int c[MAXN];
long long ans;
inline bool cmp(int a,int b){
    return a>b;
}
int main(){
    setIO("bookstore");
    read(n);
    for(int i=1;i<=n;++i)
        read(c[i]);
    sort(c+1,c+n+1,cmp);
    lim=n/3*3;
    for(int i=1;i<=lim;i+=3)
        ans+=c[i]+c[i+1];
    for(int i=lim+1;i<=n;++i)
        ans+=c[i];
    write(ans);
    return 0;
}

Table

思路

• 由于行与行之间只有和的大小限制，其它互不影响，所以考虑单独处理每行的种类数再用乘法原理乘起来统计；
• 于是进行DP，设$f(i,j)$为第$i$行和为$j$时前$i$行的种类数；
• 那么很容易知道$f(i,j)=g(m,j)\times\sum_{k=0}^{j}f(i-1,k)$，其中$g(i,j)$为$i$个非负整数和为$j$的方案数；
• 观察到每次都要用到上一行结果的前缀和，所以考虑用前缀和优化即可，反正最后$ans=\sum_{i=0}^m f(n,i)$，也是个前缀和；
• 现在考虑怎么处理$g(i,j)$，仍然考虑DP，容易知道$g(i,j)=\sum_{k=0}^j g(i-1,k)$，而且这也是用到了之前的前缀和，优化方式同理；
• 现在，我们已经可以在$O(n^2)$复杂度内解决这个问题了，但其实$g(i,j)$是不必要的；
• 考虑用组合数解决，其实就是插板法：
  
  1. 由于求的是$i$个非负整数和为$j$的方案数，有$0$不好操作，所以考虑将问题转化；
  2. 将$i$个数都加$1$，那么它们的和为$i+j$，最重要的是$i$个数都变成正整数了；
  3. 那么，和为$i+j$看作$i+j$个$1$，我们要把它们分成$i$组；
  4. 也就是我们在$i+j-1$个空隙中“插入$i-1$个隔板”将其分组；
  5. 所以方案数就是$C_{i+j-1}^{i-1}$。

代码

不过考试时递推处理$g(i,j)$感觉比较稳。。。

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    x=0;
    int pm=1; char c;
    do{c=getchar();}while(!isdigit(c) && c!='-');
    c=='-' ? pm=-1:x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <cstring>
const int MAXN=2005,P=1e9;
int n,m;
int tab[MAXN][MAXN],dp[MAXN][MAXN];
inline void pre_tab(){
    for(int i=0;i<MAXN;++i)
        tab[0][i]=1;
    for(int i=1;i<MAXN;++i){
        tab[i][0]=tab[i-1][0];
        for(int j=1;j<MAXN;++j)
            tab[i][j]=(tab[i-1][j]+tab[i][j-1])%P;
    }
    for(int i=1;i<MAXN;++i){
        for(int j=MAXN-1;j;--j)
            tab[i][j]=(tab[i][j]-tab[i][j-1]+P)%P;
    }
}
inline int DP(){
    memset(dp,0,sizeof(dp));
    dp[1][0]=tab[m][0];
    for(int i=1;i<=m;++i)
        dp[1][i]=(tab[m][i]+dp[1][i-1])%P;
    for(int i=2;i<=n;++i){
        dp[i][0]=(long long)dp[i-1][0]*tab[m][0]%P;
        for(int j=1;j<=m;++j)
            dp[i][j]=((long long)dp[i-1][j]*tab[m][j]%P+dp[i][j-1])%P;
    }
    return dp[n][m];
}
int main(){
    setIO("table");
    pre_tab();
    int T;
    read(T);
    while(T--){
        read(n),read(m);
        write(DP(),'\n');
    }
    return 0;
}

Board

思路

• 其实，如果保证节点数在unsigned long long范围内，这题就很好做了；
• 直接按照操作找到相应节点$u,v$（每次操作都是$O(1)$，直接模拟即可），之后把$u,v$上跳到同一层，因为向下跳显然两点间距离是不递减的；
• 之后每次同时上跳到同一层（直至到它们的LCA），用在该层时的最短距离更新答案；
• 之所以跳到同一层后还要继续上跳更新答案，是因为虽然上跳一次距离$+2$，但水平距离可能减了很多；
• 现在考虑节点数过大怎么处理，如果像普通的高精度的话，每次进位借位复杂度就可能高达$O(n)$；
• 可是，我们计算二叉树节点时是二进制操作，只有$0,1$，加减也无非是将一段区间修改为$0$或$1$，用线段树维护就好了，不过细节很多，请仔细看代码；
• 之后，我们考虑从上到下计算，因为虽然理论上应是从下到上更新，但由于节点数巨大，最开始两点间距离也可能巨大到高精都存不下（毕竟$2^n$）；
• 先开始$ans=deep(u)+deep(v)$，并且这是竖直方向上贡献的，所以$disy=ans,disx=0$；
• 之后，到第一次$u,v$向下的路径开始分开后，每次$disy-=2,disx=2 \times disx+1$，如果$u$向右走或$v$向左走则$disx$都减$1$；
• 就这样$ans=\min\{ disx+disy \}$，直到$disx>ans$；
• 这题细节很多，具体的看代码应该就明白了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ls (u<<1)
#define rs (ls|1)
using std::swap;
using std::min;
using std::abs;
const int MAXN=1e5+5;
int ns,nt;
char cmd[MAXN],s[MAXN],t[MAXN];
class segT{
    private:
        int n;
        struct node{int sum,tag;}d[MAXN<<2];
        void upd(int u){
            d[u].sum=d[ls].sum+d[rs].sum;
        }
        void push_d(int u,int l,int r){
            if(l==r || !d[u].tag) return;
            int mid=l+r>>1;
            d[ls].sum=(mid-l+1)*(d[u].tag-1);
            d[ls].tag=d[u].tag;
            d[rs].sum=(r-mid)*(d[u].tag-1);
            d[rs].tag=d[u].tag;
            d[u].tag=0;
        }
        void mdf(int u,int lp,int rp,int l,int r,int k){
            if(l<=lp && rp<=r){
                d[u].sum=(rp-lp+1)*(k-1);
                d[u].tag=k;
                return;
            }
            push_d(u,lp,rp);
            int mid=lp+rp>>1;
            if(l<=mid) mdf(ls,lp,mid,l,r,k);
            if(r>mid) mdf(rs,mid+1,rp,l,r,k);
            upd(u);
        }
        int qry(int u,int lp,int rp,int r,int k){
            if(lp>r) return 0;
            if(lp==rp) return d[u].sum==k ? lp:0;
            if(k==1 && d[u].sum==0) return 0;
            else if(k==0 && d[u].sum==rp-lp+1) return 0;
            push_d(u,lp,rp);
            int mid=lp+rp>>1;
            int ret=qry(rs,mid+1,rp,r,k);
            if(ret==0) ret=qry(ls,lp,mid,r,k);
            return ret;
        }
        void prt(int u,int lp,int rp,int r,char c[]){
            if(lp>r) return;
            if(lp==rp){
                c[lp]=d[u].sum|'0';
                return;
            }
            push_d(u,lp,rp);
            int mid=lp+rp>>1;
            prt(ls,lp,mid,r,c);
            prt(rs,mid+1,rp,r,c);
        }
    public:
        void sgl_mdf(int pos,int k){mdf(1,1,n,pos,pos,k+1);}
        void rge_mdf(int l,int r,int k){
            if(l>r) return;
            mdf(1,1,n,l,r,k+1);
        }
        int qry(int r,int k){return qry(1,1,n,r,k);}
        void init(int sz){
            memset(d,0,sizeof(d));
            n=sz;
            sgl_mdf(1,1);
        }
        void out(int r,char c[]){prt(1,1,n,r,c);}
}T;
inline int find(char c[]){
    int lastbit=1,lim=strlen(cmd+1)+1;
    T.init(lim);
    for(int i=1,lowbit;i<=lim;++i){
        switch(cmd[i]){
            case '1': ++lastbit;
                      T.sgl_mdf(lastbit,0);
                      break;
            case '2': ++lastbit;
                      T.sgl_mdf(lastbit,1);
                      break;
            case 'U': --lastbit;
                      break;
            case 'L': lowbit=T.qry(lastbit,1);
                      T.sgl_mdf(lowbit,0);
                      T.rge_mdf(lowbit+1,lastbit,1);
                      break;
            case 'R': lowbit=T.qry(lastbit,0);
                      T.sgl_mdf(lowbit,1);
                      T.rge_mdf(lowbit+1,lastbit,0);
                      break;
        }
    }
    T.out(lastbit,c);
    return lastbit;
}
inline int cal_dis(){
    int n=min(ns,nt);
    int lim=n-1<<1,disy=abs(nt-ns)+lim,ret=disy;
    bool apart=false;
    for(int i=2,disx=0;i<=n;++i){
        disy-=2;
        if(apart){
            disx=disx<<1|1;
            if(s[i]=='1') --disx;
            if(t[i]=='0') --disx;
        }
        else if(s[i]!=t[i]){
            apart=true;
            ++disx;
            if(s[i]=='1') swap(s,t);
        }
        if(disx>ret) break;
        ret=min(ret,disx+disy);
    }
    return ret;
}
int main(){
    freopen("board.in","r",stdin);
    freopen("board.out","w",stdout);
    scanf("%s",cmd+1);
    ns=find(s);
    scanf("%s",cmd+1);
    nt=find(t);
    printf("%d",cal_dis());
    return 0;
}