Day 5 高中部寒假集训
浏览 75 | 评论 0 | 字数 9013
Snowflake_Pink
2019年01月27日
  • 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

      • 输入格式:两个整数:$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:
        #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

    1. namespace std;
    2. long n,m;
    3. dp1010;
    4. 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;
      }

    5. main(){
      freopen("div.in","r",stdin);
      freopen("div.out","w",stdout);
      cin>>n>>m;
      if (n<m){

      cout <<0<<endl;
      return 0;

      }
      dp0='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<<dpm<<endl;
      return 0;
      }

    1. 数的直径(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,不开森......

    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/11/
    最后修改时间:2020-04-13 11:10:25
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论