夏令营7.22总结

时间安排

$8:00\sim8:50$写T1

$8:50\sim9:30$写T2

$9:30\sim9:50$看T3-T4

$9:50\sim10:30$写T5，（估计）要TLE

$10:30\sim11:00$T3-T4骗分

题目

T1

简单模拟题意即可。

这题的题意其实我不知道为什么看来还久才完全理解，所以一开始理解样例花了好久，但是其实本身的代码时间还是比较简单的。

需要注意的是在往一个方向走的时候， 其实是有可能不在那个极点上，所以要判断是否超过了那个点。

T2

状态定义：$f[x]$多少个以$x$结尾的序列$A$。

初始状态：$f[1]=1$

递推式：$f[x]=\sum_{d|x}f[d]$

$1,…,x,…,xd$

这里$1\le d\le N/x$

$f[x]\times \sum_{d=1}^{N/x}f[d]$

这里要用前向$DP$

算出$f[x]$后，对每个$d=2,…,N/x$

$f[d\times x]$+=$f[x]$

对于每个$x$，要做不超过$N/x$个$f[d\times x]$+=$f[x]$的操作。

时间复杂度：$\sum^N_{x=1}N/x=N(\sum^N_{x=1}1/x)$

结论：$\sum^N_{x=1}1/x\approx ln N$

$ln N:=log_eN$

$e$是欧拉常数，约等于$2.71828$。

T3

考虑叶子。

• 如果叶子已经好了，就不管他，直接删除即可。
• 如果叶子还没好，就做一次操作让他变好。把叶子的值直接加到上限。

从叶子节点往上(贪心)。对于当前节点,记录自己子树的增量 w[i]。
若 tmp<l[i]，那么增加一次操作,将权值设置为 r[i]，上传到根节点。
否则，min(tmp,r[i])，上传至根节点。

伪代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int>t[200001];
int l[200001],r[200001],a[200001],w[200001],n,ans=0;
void dfs(int k){
  int tmp=0;
  for(int i=0;i<(int)t[k].size();i++){
    // 更进一步深搜
    tmp+=w[t[k][i]];//<- 更新tmp
  }
  if(tmp<l[k])w[k]=r[k],ans++;
  //否则   //取min，上传至根节点
}
signed main(){
  cin>>n;
  for(int i=2;i<=n;i++){
    cin>>a[i];
    t[a[i]].push_back(i);
  }
  for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
  //调用dfs函数
  cout<<ans;
  return 0;
}

T4

纯暴力枚举，因为数据范围比较小，所以纯的暴力也是可以接受的。

核心：$\Huge大$暴力。

具体多大，你自己看吧…………。。。

for(int h=N;h>=1;h--){
    for(int w=N;w>=1;w--){
        for(x1=0;x1+h<=N;x1++){
            for(y1_=0;y1_+w<=N;y1_++){
                x2=x1+h;
                y2=y1_+w;
                if(check()){
                    bool ok=true;
                    for(auto r:ans){
                        if(r.x1<=x1&&x1+h<=r.x2&&r.y1_<=y1_&&y1_+w<=r.y2){
                            ok=false;
                            break;
                        }
                    }
                    if(ok){
                        ans.push_back({x1,y1_,x2,y2});
                    }
                }
            }
        }
    }
}

T5

$q\le K\le N\le24$

$1/n.1\le n\le N$

通分

当$N=4$时：

$\frac{1}{1},\frac{1}{2},\frac{1}{2},\frac{1}{4}$

$1,2,3,4$的最小公倍数是$12$

$\frac{12}{12},\frac{6}{12},\frac{4}{12},\frac{3}{12}$

$12,6,4,3$

$1,2,3,……,24$的最小公倍数是多少？

是$54228880$。

代码逻辑：

1. 数学转化：
   问题等价于寻找 K 个分数$\frac{1}{a_1},\frac{1}{a_2},…,\frac{1}{a_k}$（其中$1\le a_i\le N$），并使得它们的和为$1$，即：$1\frac{1}{a_1}+\frac{1}{a_2}+…+\frac{1}{a_k}=1$。

2. 通分处理：
   为了避免浮点数计算，代码先计算了$1$到$N$中除去$13,17,19,23$之外所有数的最小公倍数。这一步通过循环计算$ans=ans\times i\gcd(ans,i)$实现

3. 分数转换：
   将每个可能的分数$\frac{1}{i}$转换为以$ans$为分母的形式：$a[i]=ans/i$
   此时问题转化为寻找$K$个数$a[i_1],a[i_2],…,a[i_k]$，使得它们的和等于$ans$。

4. 动态规划求解：
   使用二维$DP$数组$dp[i][j]$表示：

   • 选择$i$个分数
   • 这些分数转换后之和为$j$的方案数

   状态转移方程：
   $dp[i][l]$+=$dp[i-1][l-a [j]]$
   表示选择第$j$个分数后，总和达到$l$的方案数。

5. 特殊情况处理：

   代码最后添加了$k=13,k=17,k=19,k=23$的判断，这是因为这几个数在计算最小公倍数时被排除了，需要单独处理

6. 最终答案：
   $dp[k][ans]$即为满足条件的分法总数，加上特殊情况的判断结果。

写完了$\sim$，好难写啊$\sim\sim$。