Day 5 高中部寒假集训 - 粉粉何所似？

Day5：

先放课程表：

2019.1.27

上午

讲解订正 $Day4$ 晚上考试的题目。

下午

图论： 线段树、块状数组。

考试

合唱队形（queue.cpp/queue.in/queue.out）:
- 题目描述：要排合唱队形，从n个学生中，选出k个同学，是他们的身高先上升再下降（一直上升或一直下降亦可）。请你求出不选的人数的最小值。
- 输入格式：第一行是一个整数 $N(2 \leq N \leq 100)$ ，表示同学的总数。第二行有 $n$ 个整数，用空格分隔，第 $i$ 个整数 $T_i(130 \leq T_i \leq 230)$ 是第 $i$ 位同学的身高。
- 输出格式：至少要几位同学出列。
- 输入样例：
  8 186 186 150 200 160 130 197 220
- 输出样例：
  4
- 分析：这道题就是求最长上升+最长下降子序列。求出每个人所在的最长上升子序列和最长下降子序列，然后从头到尾扫一遍，看看哪个人作为峰顶最合适。最后！！！！一定要输出选出的人数，而不是被选的人数！！！
- My Code：
CPP
#include <cstdio> #include <iostream> using namespace std; int up[105],down[105],data[105],n,Max; int main(){ freopen("queue.in","r",stdin); freopen("queue.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&data[i]); for (int i=1;i<=n;i++){ up[i]=1; for (int k=1;k<i;k++) if (data[i]>data[k]) up[i]=max(up[i],up[k]+1); } for (int i=n;i>=1;i--){ down[i]=1; for (int k=n;k>i;k--) if (data[i]>data[k]) down[i]=max(down[i],down[k]+1); } for (int i=1;i<=n;i++) Max=max(Max,up[i]+down[i]-1); printf("%d\n",n-Max);//我这次考试就挂在这里，90分没了。 fclose(stdin); fclose(stdout); return 0; }

划分（div.cpp/div.in/div.out）：

题目描述：将整数 $n$ 分成 $k$ 份，且每份不能为空，请你求出有多少种方案。当 $n$ =7， $k$ =3时，下面三种情况算一种：
1 1 5
1 5 1
5 1 1
输入格式：两个整数： $n$ 和 $k$ 。
输出格式：方案数。
输入样例：
7 3
输出样例：（四种分法为：1，1，5；1，2，4；1，3，3；2，2，3）
4
数据范围：对于50%的数据，有： $6<n<=200$ ， $2 \leq k \leq 6$ ；对于100%的数据，有： $n \leq 1000，k \leq 1000$ )，你意识到了什么吗？？
分析：这道题原题是用本题前50%的数据的。所以正解应该用 $dp$ 做。可是我 $dp$ 方程就是想不出来QAQ~~（最讨厌 $dp$ 了）~~，先放个60分（没错，搜索可以拿60分）的搜索：
My Code：

#include <cstdio>
#include <iostream>
using namespace std;
int n,k;
long long ans;
inline void dfs(int last,int sum,int deep){
    //cout <<last<<endl;
    if (deep==k){
        ans++;
        return;
    }
    int start;
    if (deep==0) start=1;
    else start=last;
    if (deep+1==k){
        dfs(sum,0,deep+1);
        return;
    }
    for (int i=start;i<=sum/(k-deep);i++){
        dfs(i,sum-i,deep+1);
    }
    return;
}
int main(){
    freopen("div.in","r",stdin);
    freopen("div.out","w",stdout);
    scanf("%d%d",&n,&k);
    dfs(0,n,0);
    printf("%d\n",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

现在是70分的 $dp$ ：
1. 设置状态：将 $i$ 分为 $j$ 份的方案数为 $f[i][j]$
2. 设置转移方程：方案的转移分为两类：
  - 最小值为1，即选一个1，这些方案可以从 $f[i-1][j-1]$ 转移 $（f[数字-1][方案-1]）$
  - 最小值大于1，那么这 $j$ 个方案都要加1（为了不重复，后面的选的数一定要大于等于前一个数），每个方案就对应一个将 $i – j$ 分为 $j$ 份的方案，这些方案可以从 $f[i-j][j]$ 转移。
  - $dp$ 方程： $f[i][j]=f[i-1][j-1]+f[i-j][j]$
3. My classmate's（ $<-<-$ 这是dalao） Code：
CPP
#include<bits/stdc++.h> using namespace std; long long n,m,dp[1010][1010]; int main(){ freopen("div.in","r",stdin); freopen("div.out","w",stdout); cin>>n>>m; dp[0][0]=1; for(int i=1;i<=m;i++){ for(int j=i;j<=n;j++){ dp[i][j]=dp[i][j-i]+dp[i-1][j-1]; } } cout<<dp[m][n]<<endl; return 0; }
100分正解：没发现会这个数据会爆 $long$ $long$ 吗？？以下是带了高精的正解 $dp$ ：
STD

#include<bits/stdc++.h>
using namespace std;
long long n,m;
string dp[1010][1010];

string add(string str1,string str2)//高精度加法
{
    string str;
    int len1=str1.length();
    int len2=str2.length();
    if(len1<len2)
    {
        for(int i=1;i<=len2-len1;i++)
           str1="0"+str1;
    }
    else
    {
        for(int i=1;i<=len1-len2;i++)
           str2="0"+str2;
    }
    len1=str1.length();
    int cf=0;
    int temp;
    for(int i=len1-1;i>=0;i--)
    {
        temp=str1[i]-'0'+str2[i]-'0'+cf;
        cf=temp/10;
        temp%=10;
        str=char(temp+'0')+str;
    }
    if(cf!=0)  str=char(cf+'0')+str;
    return str;
}

int main(){
    freopen("div.in","r",stdin);
    freopen("div.out","w",stdout);
    cin>>n>>m;
    if (n<m){
        cout <<0<<endl;
        return 0;
    }
    dp[0][0]='1';
    for(int i=1;i<=m;i++){
        for(int j=i;j<=n;j++){
            dp[i][j]=add(dp[i][j-i],dp[i-1][j-1]);
        }
    }
    cout<<dp[m][n]<<endl;
    return 0;
}

数的直径（diam.cpp/diam.in/diam.out）：

题目描述：一棵树中有 $n$ 个点，编号为 $1$ ~ $n$ ，求这棵树的直径。树的直径定义为：树中距离最远的两个点的距离。两个点的距离即它们之间最短路径上的边数。
输入格式：第一行一个数 $n$ ，第二行 $n$ 个数，第 $i$ 个数代表点 $i$ 的父结点编号（为0则代表该点为根节点）。
输出格式：一个整数，代表树的直径。
输入样例：
5
4 4 1 0 1
输出样例：
3
数据范围：对于30%的数据，有： $n \leq 50$ ；对于100%的数据，有： $n \leq 5000$ 。
分析：这就直接 $dfs$ 就可以了，不需要用LCA算法。
STD

#include <bits/stdc++.h>
using namespace std;

#define fre(pn) freopen(pn ".in", "r", stdin), freopen(pn ".out", "w", stdout)
const int MAXN = 5e3 + 10;

int n, ans = 0;
vector<int> G[MAXN];

void addEdge(int u, int v) {
    G[u].push_back(v);
}

void dfs(int x, int fa, int dep) {
    ans = max(ans, dep);
    for (int i = 0; i < G[x].size(); i++)
        if (G[x][i] != fa)
            dfs(G[x][i], x, dep + 1);
}

int main() {
    fre("diam");
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int fa;
        cin >> fa;
        if (fa != 0) {
            addEdge(fa, i);
            addEdge(i, fa);
        }
    }
    for (int i = 1; i <= n; i++)
        dfs(i, 0, 0);
    cout << ans << endl;
    return 0;
}

总结

这次考试最可惜的是T1输出 $Max$ ，而不是 $n-Max$ QAQ，我已经自闭了，算了，反正最后一天，晚上就可以玩了~~（我为什么这么爱玩）~~，我还是菜，多做题吧......

笔记

块状数组~~（基本上能用块状数组的东西都能用线段树，所以就偷懒了）~~
- 算法：将整个序列分为尽可能均等的若干块，每个块维护一个当前块中元素的和，以及一个加法标记。如果对一个区间加上一个数时，某个块完全落在区间中，则直接改动标记，对于不完全覆盖的块，则暴力修改每个下标上的元素。（乘法亦可）

线段树

emm，本人太菜了，突然看到一个有1.2k赞的洛谷题解讲线段树（dalao的链接），~~本人可以溜了~~。
例题：【洛谷】【模板】线段树1
STD

#include<iostream>
#include<cstdio>
#define MAXN 1000001
#define ll long long
using namespace std;
unsigned ll n,m,a[MAXN],ans[MAXN<<2],tag[MAXN<<2];
inline ll ls(ll x)
{
    return x<<1;
}
inline ll rs(ll x)
{
    return x<<1|1;
}
void scan()
{
    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    scanf("%lld",&a[i]);
}
inline void push_up(ll p)
{
    ans[p]=ans[ls(p)]+ans[rs(p)];
}
void build(ll p,ll l,ll r)
{
    tag[p]=0;
    if(l==r){ans[p]=a[l];return ;}
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
} 
inline void f(ll p,ll l,ll r,ll k)
{
    tag[p]=tag[p]+k;
    ans[p]=ans[p]+k*(r-l+1);
}
inline void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
    if(nl<=l&&r<=nr)
    {
        ans[p]+=k*(r-l+1);
        tag[p]+=k;
        return ;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
    if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p)
{
    ll res=0;
    if(q_x<=l&&r<=q_y)return ans[p];
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(q_x<=mid)res+=query(q_x,q_y,l,mid,ls(p));
    if(q_y>mid) res+=query(q_x,q_y,mid+1,r,rs(p));
    return res;
}
int main()
{
    ll a1,b,c,d,e,f;
    scan();
    build(1,1,n);
    while(m--)
    {
        scanf("%lld",&a1);
        switch(a1)
        {
            case 1:{
                scanf("%lld%lld%lld",&b,&c,&d);
                update(b,c,1,n,1,d);
                break;
            }
            case 2:{
                scanf("%lld%lld",&e,&f);
                printf("%lld\n",query(e,f,1,n,1));
                break;
            }
        }
    }
    return 0;
}

总结

这次笔记好短啊，哈哈哈哈哈，不要在意这些细节，因为我要回家过年了。这5天学的东西还挺多的，感觉自己突然从普及 $-$ 到了普及/提高 $-$ 。我还是一如既往的菜，只是想一边帮助自己一边帮助别人~~（说得好像有很多人上这破站一样）~~。好像过完年还要上7天课QAQ，不开森......