2017/8/12 考试吐槽

2017 8 12 得分：200

我只能说一句话：这才是$NOIP$难度吧……（神$TM$联赛考$FFT$）

A、灌水

题意：$n$根板子长度是$1~n$全排列，找出一种方法，使得板子组成的容器容量恰好为定值。

眼瞪十分钟$＋$$coding$ $15$分钟 $＋$ $debug$ $5$分钟 $=$ $AC$。

首先我们可以知道，整个容器容量最大的情况就是两根最长的板子夹在两边，中间全是相对较短的板子，这样获得的最大的容量就是[frac{(n - 2)(n- 1)}{2 }]。那么我们就可以知道大于这个的一定不合法。

确定合法之后，我们就可以愉快的贪心了，不断选取当前可抽出的板子中最短的放在左侧并按照递增顺序摆放，避免出现额外容量。合格后直接两个长板放在两边，中间没放过的随意放即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=(int)1e6+5;
int ord[maxn],n;long long x;
bool used[maxn];
int haha()
{
    scanf("%d%lld",&n,&x);
    long long res=1ll*(n-1)*(n-2)/2;
    if(res<x)
    {
        puts("-1");
        return 0;
    }
    int cur=1,cn=1,nn=1;
    while(res>x)
    {
        long long tmp=res-x;
        if(tmp>=n-1-cn)
        {
            ord[cur]=cn;used[cn]=1;
            res-=n-1-cn;
            cn++;cur++;
            nn=cn;
        }
        else
            for(;nn<n-1;nn++)
            {
                if(!used[nn]&&n-1-nn<=tmp)
                {
                    ord[cur]=nn;used[nn]=1;
                    res-=n-1-nn;
                    cur++;break;
                }
            }
    }
    ord[cur]=n;ord[n]=n-1;cur++;
    used[n]=used[n-1]=1;
    int now=1;
    while(cur<n)
        for(;now<=n;now++)
            if(!used[now])
            {
                used[now]=1;ord[cur]=now;
                cur++;break;
            }
    for(int i=1;i<=n;i++)printf("%d ",ord[i]);
}
int sb=haha();
int main(){;}

 B、序列

题意：求出所有长度为$K$子序列的最大元素之和。

撕烤了十五分钟认为不太可能是第二个思博题，但是又想不到风险系数更低的想法，于是敲了上去。事实证明，正解就是这个……

我们可以发现一个子序列的贡献只与最大元素有关。那么我们就可以只观察最大元素的变化。我们先对序列从小到大排序，对于排序后的序列，从第$K$个开始都是可能的。对于第$i$个元素可以发现它成为最大元素的情况有 $inom{i-1}{K-1}$种。

直接计算组合数肯定会超时，那么我们考虑前后项之间关系。我们可以看到，前项与后项关系是 $inom{i-1}{K-1}=inom{i-2}{K-1}*(i-1)/(i-K)$。那么我们递推计算即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100005,mod=(int)1e9+7;
long long C=1,ans=0;
int n,k,a[maxn];
long long qpow(int val,int tim)
{
    long long x=val,tmp=1;
    for(;tim;tim>>=1,x=x*x%mod)
        if(tim&1)tmp=tmp*x%mod;
    return tmp;
}
int haha()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=k;i<=n;i++)
    {
        ans=(ans+C*1ll*a[i]%mod)%mod;
        C=C*i%mod;
        C=C*qpow(i-k+1,mod-2)%mod;
    }
    printf("%lld
",ans);
}
int sb=haha();
int main(){;}

 C、修改二叉树

题意：给出一棵二叉树，问最少修改几次可以转化为$BST$。$BST$特点是，左儿子元素$<$父节点元素$<$右儿子元素。

这道题考试时候坑坏我了……刚开始以为这个题是个树归，但是考虑了很久并没有发现什么树形关系……后来在纸上画了画，发现这个东西其实是个什么呢……就像下面这个图：

当当当当！就是这个！我意识到$BST$中序遍历之后就可以变成一个序列，这个序列之中最长上升子序列的长度就是不需要修改的长度。于是我就这么敲了一发。

但是交卷后我出了一组数据，发现不太对：

就是这张图。如果说单纯求最长上升子序列长度是$3$，但是这个序列是$2、3、5$，显然中间存在问题，因为$2$、$3$之间存在一个数，这两个数不可能作为最优情况连续出现，正确情况是修改$3$次。但是已经交卷了，再加之脑子很乱，并没有想出怎么解决。

直到看见题解，我的脑子真的是炸裂……每一项中序遍历之后都减去这个数所在位置，问题转化为求出新序列的最长不下降子序列……说不太明白，还是直接代码送上吧……

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100005;
int son[maxn][2],ord[maxn],cnt,n,a[maxn];
long long g[maxn];
void Middle(int root)
{
    if(son[root][0])Middle(son[root][0]);
    cnt++;ord[cnt]=a[root]-cnt;
    if(son[root][1])Middle(son[root][1]);
}
int haha()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=2;i<=n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        son[x][y]=i;
    }
    Middle(1);
    for(int i=1;i<=n;i++)g[i]=2147483648ll;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int k=upper_bound(g+1,g+n+1,ord[i])-g;
        ans=max(ans,k);
        g[k]=ord[i];
    }
    printf("%d
",n-ans);
}
int sb=haha();
int main(){;}