10.19周四例行测试

...反正就是挂挂挂..也没什么可以说的..

直接题解

T1 升职数

---

emm...基本还是很好想到是要直接dfs换成序列来做的，但是之后求区间有多少大于的就蒙蔽了...
问题可以等价于区间第k大（但是可以很简单）
本来试图苟个主席树，后来没苟住，放弃了。
其实可以换个方向考虑。
考试的时候一直试图排序区间，无果，之后发现是排序权值更好一点。

---

正确的解法就是dfs转化成区间。
之后对于每一个节点都进行权值的排序，在序列相应位置按照权值大小加入，查询即可。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+5;
struct data{
    int id,l,r,p;
}a[N];
struct edge{
    int to,next;
}e[N];
int head[N],gs;
void adde(int fr,int to)
{
    e[++gs].to=to,e[gs].next=head[fr],head[fr]=gs;
}
int tr[N],n,cnt;
int lowbit(int x)   {return x&(-x);}
int getsum(int p)
{
    int an=0;
    while(p)
    {
        an+=tr[p];
        p-=lowbit(p);
    }
    return an;
}
void add(int p,int x)
{
    while(p<=n)
    {
        tr[p]+=x;
        p+=lowbit(p);
    }
}
int ans[N];
void dfs(int u)
{
    a[u].l=++cnt;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        dfs(v);
    }
    a[u].r=cnt;
}
bool cmp(data x,data y) {return x.p>y.p;}
void solve()
{
    dfs(1);
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;++i)
    {
        ans[a[i].id]=getsum(a[i].r)-getsum(a[i].l-1);
        add(a[i].l,1);
    }
    for(int i=1;i<=n;++i)   printf("%d\n",ans[i]);
}
inline int read()
{
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')   x=x*10+c-'0',c=getchar();
    return x;
}
int main()
{
    int y;
    n=read();
    for(int i=1;i<=n;++i)   a[i].p=read(),a[i].id=i;
    for(int i=2;i<=n;++i)   y=read(),adde(y,i);
    solve();
    return 0;
}

T2 盖楼房

---

其实这个题我属于一种：？？？的状态，因为我并不知道考场上这些大佬怎么a掉的...

---

正确解法可以算作一个分数规划（？）

首先我们可以知道，一个解是最优的当且仅当这个解分配的每一个 $C$ 即使加上了 $1$ 个也没什么用处,加到其他任意一层都差不多。
化成式子就是:

$$\frac{a_i}{C_i}-\frac{a_i}{C_i+1}$$
我们的目的就是尽量让这些值一样。
我们可以二分这个值（设为 $t$ )啊。
当然我们对于二分的条件就是，$\sum{c}<=k$
解方程得到 $C_i$
$$C_i=\lceil \frac{-1+\sqrt{1+4*\frac{a_i}{t}}}{2} \rceil$$
二分过后可以发现，这样搞可能不能让总共的 $k$ 个人全部用上，那肯定不是最优的了，所以我们思考把剩下 $k$ 个人的贡献直接加上就好了（因为加到哪层楼都没有区别）

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
#define db double
using namespace std;
const db eps=1e-10;
const int N=1e6+5;
int n;
ll K;
db a[N];
bool check(db x)
{
    ll ret=0;
    for(int i=1;i<=n;++i)
    {
        ll tmp=ceil(((-1.0+sqrt(1.0+4.0*(a[i]/x)))/2.0));
        ret+=tmp;
        if(ret>=K)  return 0;
    }
    return 1;
}
void solve()
{
    db l=0,r=1e10;
    while(fabs(l-r)>eps)
    {
        db mid=(l+r)/2.0;
        if(check(mid))  r=mid;
        else    l=mid;
    }
    ll sum=0;
    db val=0;
    for(int i=1;i<=n;++i)
    {
        ll c=ceil(((-1.0+sqrt(1.0+4.0*(a[i]/l)))/2.0));
        sum+=c;
        val+=a[i]/c;
    }
    val-=((db)K-(db)sum)*l;
    cout<<(ll)(val+0.5)<<endl;
//  printf("%lld",(ll)val+0.4);
}
int main()
{
    freopen("1.txt","r",stdin);
    scanf("%d%lld",&n,&K);
    for(int i=1;i<=n;++i)   scanf("%lf",&a[i]);
    solve();
    return 0;
}

T3 毕业照

---

说实在的我也还没苟住为什么这个是个区间dp...神佬们可能什么都能苟吧...

---

所以说这道题就是区间dp，状态更多一些。
设置状态

$$dp[l][r][i][j]$$
其中 $l,r$ 分别代表了这个区间的最左和最右边的值的大小（保证其中是合法序列）, $i,j$ 为区间左右端点。
那么我们可以设置转移如下：
$$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}$$

于是记忆化搜索之，可以了。
注意：记忆化的时候，如果 $l>r$或者 $i>j$ 要返回 $0$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int dp[51][51][51][51];
int n,a[51];
int solve(int l,int r,int i,int j)
{
    if(l>r) return 0;
    if(i>j) return 0;
    if(dp[l][r][i][j]!=-1)  return dp[l][r][i][j];
    dp[l][r][i][j]=-inf;
    if(l+1<=50&&r-1>=1) dp[l][r][i][j]=max(solve(l,r-1,i,j),solve(l+1,r,i,j));  
    if(i+1<=n)  dp[l][r][i][j]=max(dp[l][r][i][j],solve(l,r,i+1,j)+(a[i]==l));
    if(j-1>=1)  dp[l][r][i][j]=max(dp[l][r][i][j],solve(l,r,i,j-1)+(a[j]==r));
    if(i+1<=n&&j-1>=1)  dp[l][r][i][j]=max(dp[l][r][i][j],solve(l,r,i+1,j-1)+(a[i]==r)+(a[j]==l));
//  if(dp[l][r][i][j]>0)    printf("%d %d %d %d  %d\n",l,r,i,j,dp[l][r][i][j]); 
    return dp[l][r][i][j];
}
int main()
{
    freopen("1.txt","r",stdin);
    freopen("11.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)   scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;++i)
        for(int k=1;k<=a[i];++k)
            for(int f=a[i];f<=50;++f)
                dp[k][f][i][i]=1;
    int ans=solve(1,50,1,n);
/*      for(int i=1;i<=n;++i)
            for(int j=i;j<=n;++j)
                for(int l=1;l<=50;++l)
                    for(int r=1;r<=50;++r)
                    {
                        if(dp[l][r][i][j]<0)    continue;
                        printf("%d %d %d %d %d\n",l,r,i,j,dp[l][r][i][j]);//<<endl;
                    }
*/  printf("%d",ans);
    return 0;
}