Day 5 高中部寒假集训
浏览 1228 | 评论 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
    评论列表
    暂无评论
    arrow_back 上一篇
    Day 4 高中部寒假集训
    arrow_forward 下一篇
    2019.2.16高中部集训