Day 5 高中部寒假集训

Day5:

先放课程表:

2019.1.27

上午
  • 讲解订正 Day4 晚上考试的题目。
下午
  • 图论: 线段树 块状数组

考试

  1. 合唱队形(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:
    #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;
    }
  2. 划分(div.cpp/div.in/div.out):

    • 题目描述:将整数 n 分成 k 份,且每份不能为空,请你求出有多少种方案。当n=7,k= 3 时,下面三种情况算一种:

      1 1 5

      1 5 1

      5 1 1

    • 输入格式:两个整数:nk

    • 输出格式:方案数。

    • 输入样例:

      7 3

    • 输出样例:(四种分法为:1,1,5;1,2,4;1,3,3;2,2,3)

      4

    • 数据范围:对于 50% 的数据,有:6<n<=2002 \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]
      1. My classmate's(<-<-这是 dalao) Code:
      #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;
    }
  3. 数的直径(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,我已经自闭了,算了,反正最后一天,晚上就可以玩了(我为什么这么爱玩),我还是菜,多做题吧......


笔记

  1. 块状数组(基本上能用块状数组的东西都能用线段树,所以就偷懒了)

    • 算法:将整个序列分为尽可能均等的若干块,每个块维护一个当前块中元素的和,以及一个加法标记。如果对一个区间加上一个数时,某个块完全落在区间中,则直接改动标记,对于不完全覆盖的块,则暴力修改每个下标上的元素。(乘法亦可)
  2. 线段树

    #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,不开森......

本文链接:https://snowflake.pink/archives/11/
This blog is under a CC BY-NC-ND 4.0 Unported License