2017.10.19 NOIP模拟赛

题解 套题

目录

• 2017.10.19 NOIP模拟赛
  • 升职数
    • 思路
    • 代码
  • 盖楼房
    • 思路
    • 代码
  • 毕业照
    • 思路
    • 代码

升职数

思路

• 综合数据量和题目所给的问题考虑，这题应该是对树DFS一遍直接求解的；
• 怎么求呢？由于题目所求有些像逆序对，我们考虑用树状数组维护每个$p$值出现的人数；
• DFS完$u$的子树时，我们便能统计出比$p_u$大的$p$的个数了；
• 不过需要记录之前的$sum$值，减一下才是。

代码

#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){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    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>
#include <cstring>
using std::sort;
using std::unique;
using std::lower_bound;
const int MAXN=1e5+5;
int n,tot;
int he[MAXN],p[MAXN],id[MAXN],ans[MAXN];
struct line{int to,nex;}ed[MAXN];
class BIT{
    private:
        int c[MAXN];
        int lowbit(int x){return x&-x;}
        int qry(int r){
            int ret=0;
            for(;r;r-=lowbit(r))
                ret+=c[r];
            return ret;
        }
    public:
        void add(int l){
            for(;l<=tot;l+=lowbit(l))
                ++c[l];
        }
        int gsum(int l){return qry(tot)-qry(l);}
}ta;
inline void addE(int u,int v){
    static int cnt;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
inline void decrete(){
    static int tmp[MAXN];
    memcpy(tmp,p,sizeof(tmp));
    sort(tmp+1,tmp+n+1);
    tot=unique(tmp+1,tmp+n+1)-tmp-1;
    for(int i=1;i<=n;++i)
        id[i]=lower_bound(tmp+1,tmp+tot+1,p[i])-tmp;
}
void DFS(int u){
    int pre=ta.gsum(id[u]);
    for(int i=he[u];i;i=ed[i].nex)
        DFS(ed[i].to);
    ans[u]=ta.gsum(id[u])-pre;
    ta.add(id[u]);
}
int main(){
#ifdef DEBUG
    setIO("a");
#endif
    read(n);
    for(int i=1;i<=n;++i)
        read(p[i]);
    decrete();
    for(int i=2,fa;i<=n;++i){
        read(fa);
        addE(fa,i);
    }
    DFS(1);
    for(int i=1;i<=n;++i)
        write(ans[i],'\n');
    return 0;
}

盖楼房

思路

• 这题开始看错题意了，想去二分，后来发现错了，但想来想去就是二分。。。
• 这个二分不是很显然，我们先考虑如果安排了一个方案，如何调整可以使其更优？
• 显然，当我们把第$i$层的人数减$1$放到第$j$层可以减少的时间最多的话，这个操作最优；
• 那么，当且仅当加一个人对第$j$层的影响不比其它任何层数优的话，我们的方案是最优解；
• 也就是$a_i/c_i-a_i/(c_i+1)$都相等了，这是最优解；
• 那么我们不妨二分这个值，设为$\Delta t$，那么可以解出每个$c_i$；
• 如果符合要求（也就是$\sum_{i=1}^n c_i \leq k$），我们可以试图令答案更优（刚才不是说那个式子都相等最优了吗？不一定，因为这样可能并未用上所有人去工作）；
• 观察求$c_i$的式子，$c_i=\lceil\frac{-1+\sqrt{1+4 \times\frac{a_i}{\Delta t}}}{2}\rceil$，发现$c_i$随$\Delta t$的增大而减小，这就明确了二分时的操作（其单调性也验证了二分的可行。。。但是我每次都没有先考虑这个问题）；
• 最后，求$ans$时也要注意，看是否用完所有人，不然要补上那些人的贡献。

代码

#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){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    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>
#include <cmath>
using std::ceil;
using std::min;
using std::sqrt;
const int MAXN=1e5+5;
const double EPS=1e-12;
int n;
long long k;
long long a[MAXN];
inline bool jud(double lim){
    long long rest=k,c;
    for(int i=1;i<=n;++i){
        //lim*c^2+lim*c=a
        //c=ceil(-lim+sqrt(lim*lim+4*lim)/2/lim);
        c=ceil((-1+sqrt(1+4*a[i]/lim))/2);
        rest-=c;
        if(rest<0) return false;
    }
    return true;
}
inline long long bin_chop(){
    double l=1e-12,r=1e12,mid;
    while(r-l>EPS){
        mid=(l+r)/2;
        if(jud(mid)) r=mid;
        else l=mid;
    }
    mid=(l+r)/2;
    double ret=0;
    long long c,sum=0;
    for(int i=1;i<=n;++i){
        c=ceil((-1+sqrt(1+4*a[i]/mid))/2);
        ret+=(double)a[i]/c,sum+=c;
    }
    ret-=mid*(k-sum);
    return (long long)(ret+0.5);
}
int main(){
#ifdef DEBUG
    setIO("b");
#endif
    read(n),read(k);
    for(int i=1;i<=n;++i)
        read(a[i]);
    write(bin_chop());
    return 0;
}

毕业照

思路

• 考虑到这题肯定不是枚举怎么翻转的，我们不妨考虑怎么消除这一影响；
• 如果我们枚举翻转中心的话，那么这个区间DP其实挺好想的，但是不是很好实现，因为题目求的是不下降子序列，有一个值的限制；
• 可是值都很小，那么我们不妨再加一个值的限制，即$dp(l,r,i,j)$是值为$[l,r]$的范围在$i$~$j$的合法最优解，每次加入左右端点时只加入端点值是$l$或$r$的；
• 这样，即使选的子序列被翻转了，也没有影响答案，因为我们选的时候考虑翻转的情况时都是对称选的；
• 那么DP方程就是：
  $$dp(l,r,i,j)=\max \begin{cases} dp(l+1,r,i,j)\\ dp(l,r-1,i,j)\\ dp(l,r,i+1,j)+[a_i=l]\\ dp(l,r,i,j-1)+[a_j=r]\\ dp(l,r,i+1,j-1)+[a_i=r]+[a_j=l] \end{cases}$$
• 前两个就是正常的区间DP，中间两个就是不考虑翻转的情况，最后一个是假设翻转中心是现在枚举的区间中心，两个端点恰好是翻转的子序列的两个对称点；
• 枚举区间长度和值域长度就可以了，和正常的区间DP一样，只是有了两个区间，复杂度$O(n^4)$。

代码

#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){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    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::max;
const int MAXN=55;
int n;
int a[MAXN];
inline int DP(){
    //val in l~r,range is i~j
    static int dp[MAXN][MAXN][MAXN][MAXN];
    for(int i=1;i<=n;++i){
        for(int l=1;l<=a[i];++l){
            for(int r=a[i];r<=50;++r)
                dp[l][r][i][i]=1;
        }
    }
    for(int len=2;len<=n;++len){
        for(int i=1,j;n-i+1>=len;++i){
            j=i+len-1;
            for(int rge=1;rge<=50;++rge){
                for(int l=1,r;50-l+1>=rge;++l){
                    r=l+rge-1;
                    dp[l][r][i][j]=max(dp[l+1][r][i][j],dp[l][r-1][i][j]);
                    dp[l][r][i][j]=max(dp[l][r][i][j],dp[l][r][i+1][j]+(a[i]==l));
                    dp[l][r][i][j]=max(dp[l][r][i][j],dp[l][r][i][j-1]+(a[j]==r));
                    dp[l][r][i][j]=max(dp[l][r][i][j],dp[l][r][i+1][j-1]+(a[i]==r)+(a[j]==l));
                }
            }
        }
    }
    return dp[1][50][1][n];
}
int main(){
#ifdef DEBUG
    setIO("c");
#endif
    read(n);
    for(int i=1;i<=n;++i)
        read(a[i]);
    write(DP());
    return 0;
}