20231116模拟赛题解

T1 最大值和最小值的乘积之和

由于要同时搞最大值和最小值，自然想到枚举其中一个。

于是从小到大枚举每一个数作为最小值，然后统计最大值之和，相乘后全部相加即为答案。

怎么求最大值之和呢？可以打个表帮助思考（找规律）。先求枚举到最小的数时的最大值之和，即为${\Sigma }_{i=2}^{i<=n}a[i]\ast 2^{i-2}$，注意此处并没有算自身乘自身的情况。

接下来递推，$sum[i]=(sum[i-1]-a[i])/2$。

T2 倍数序列

打表找规律，但总归还是需要思考的。打个表，把最终答案里分别以1到m为结尾的贡献求出来，然后观察一个数没有重复质因数的情况。可以发现，这个数的贡献即为它的质因子贡献的乘积。

然后再观察全为同一质因子的情况，假设这个数为$k^y$，而$k$得贡献为$x$，那它的贡献则为$(x\ast (x+1)\ast (x+2)\dots \dots (x+y-1))/(1\ast 2\ast \dots \dots \ast y)$。

由此可以推断出，一个数的贡献就是将其中每个质因数按照同一质因子的情况计算，然后再相乘即可。

T3 赢得游戏

$DP$，由于$n、m$均为$5000$，所以可以$O(nm)$解决。

设$f(i,j)$为二进制的前$i$为确定且和为$j$的方案书。

有了这两个量，我们还需要确定当前位上要放多少个1，注意必须要为偶数。

假设枚举出了$k$个1，那么将这$k$个1放在$n$个数中则有$C(n,k)$种情况。

则$f(i,j)={\Sigma }_{k=0}^{k\ast 2^i\le j}f(i-1,j-k\ast 2^i)\ast C(n,k)$。

T4 消息传递

题目即要让所有城市中最晚接收到消息的城市接收到消息的时间最早。

对于这种最大值最小问题，我们可以二分。

显然二分答案的最小值。接下来就是求所有城市中接收到信息最晚的时间。

从数据范围中可以推断，我们要尽量在$O(n)$的时间复杂度内求解最晚时间，这里我们可以贪心求解。

如何贪心？为了方便处理，此处我们要将无根树转化为以1为根的有根树。先预处理出每个点的深度。

每次找到深度最大且没有被覆盖过的节点，然后从它向上找$mid$层，找到它的祖先，在它的祖先处设立站点，随后再从它的祖先处开始暴力地覆盖节点。

实现后发现不需要剪枝。此处有一个细节，就是如果某一个点在暴力覆盖其他点时发现某一个点已经被覆盖了，这时候我们应该继续往它的子孙处覆盖，因为它虽然被覆盖了，但是深度更大的子孙处很可能未被覆盖。

具体实现：

#include
using namespace std;
#define LL long long
const LL MAXN=2e5+5;
LL n,k;
vector<LL>a[MAXN];
LL dep[MAXN],fat[MAXN];
void dfs(LL x,LL fa){
    LL len=a[x].size();
    for(register LL i=0;i<len;i++){
        LL xx=a[x][i];
        if(xx==fa)continue;
        dep[xx]=dep[x]+1;
        fat[xx]=x;
        dfs(xx,x);
    }
}
struct node{
    LL depp,num;
    bool operator <(const node &t)const{
        return depp<t.depp;
    }
};
bool vis[MAXN];
priority_queue<node,vector<node>,less<node> >q;
void col(LL x,LL sum,LL maxn,LL fa){
    if(sum==maxn)return ;
    LL len=a[x].size();
    for(register LL i=0;i<len;i++){
        LL xx=a[x][i];
        if(xx==fa)continue;
        vis[xx]=true;
        col(xx,sum+1,maxn,x);
    }
}
inline bool check(LL x){
    for(register LL i=1;i<=n;i++){
        vis[i]=false;
    }
    while(!q.empty())q.pop();
    for(register LL i=1;i<=n;i++){
        q.push(node{dep[i],i});
    }
    LL cnt=0;
    while(!q.empty()){
        node tt=q.top();
        q.pop();
        if(vis[tt.num])continue;
        ++cnt;
        if(cnt>k)return false;
        LL xx=tt.num,cntt=0;
        while(1){
            LL faa=fat[xx];
            ++cntt;
            if(faa&&cntt<=x){
                xx=faa;
            }else{
                break;
            }
        }
        vis[xx]=true;
        col(xx,0,x,0);
    }
    return true;
}
int main(){
    scanf("%lld%lld",&n,&k);
    for(register LL i=1;i<n;i++){
        LL u,v;
        scanf("%lld%lld",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1,0);
    LL l=0,r=n,ans=0;
    while(l<=r){
        LL mid=(l+r)>>1;
        if(check(mid)){
            r=mid-1;
            ans=mid;
        }else{
            l=mid+1;
        }
    }
    printf("%lld",ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86