第一题和第二题只是数据不同
第一题可以通过a+b=n 不枚举第二个区间 直接把b算成n-a就能过
第二题只要有枚举那么必超时 所以肯定是推式子
可知答案是取[L2,R2] [n-R1,n-L1]的交集
求交集有固定写法
这个交集就是[max(L2,n-R1),min(R2,n-L1)]
当然可能没有交集 所以最后要和0max一下

[a+b=n] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int n,l1,r1,l2,r2,a;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    int a;
    cin>>a;
    while(a--)
    {
        int tot=0;
        cin>>n;
        cin>>l1>>r1;
        cin>>l2>>r2;
        l1=max(l1,n-r2);
        r1=min(r1,n-l2);
        tot=max(0,r1-l1+1);
        cout<<tot<<endl;
    }
    return 0;
}

j题是个奇怪的思维题 结论就是2n*(abs(a1)+abs(a2)+….+abs(an))
是通过数轴上分类讨论知道的

[j] [c++]
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
#include<bits/stdc++.h>
#define LL long long

using namespace std;

void work()
{
    LL n;
    cin>>n;
    LL ans=0;
    for(int i=1;i<=n;i++)
    {
        int m;
        cin>>m;
        ans+=n*std::abs(m);
        
    }
    cout<<ans*2<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        work();
    }
    return 0;
}

H题 萌新必学题?
集训2最妙的一道题

单独考虑算贡献

不同种类数之间单独考虑如1111223
若2 3已放只考虑1的放法 2和3对答案的贡献是不会变的

那么我们假设只考虑1 1出现了x次 要分成k个子序列
贡献最大的情况便可以分类讨论一下

就是x>k时 前k-1个子序列都放一个1 剩下的都放到最后一个子序列 这样就贡献了k-1
若x<=k 那么每个子序列放一个1就行了 总共为答案贡献了x

知道以上信息 若k是定值 就可以做了
但是题目要求输出k为1到n的所有情况 所以还需要特殊处理

若从k=n开始减 若k一直大于等于最大的每个数出现的个数x(某个)时 贡献就是每个数的x相加 这不会变
变化的情况就是k=x(max)-1
那么我们用一个set集合存这个变化的贡献

[h] [c++]
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
#include<bits/stdc++.h>
using namespace std;
int T,n,a[100010],c[100010];
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            c[a[i]]++;  
        }
        multiset<int>st; //不会去掉重复元素的集合 存每种数的x(出现次数)
        for(int i=1;i<=100000;i++)
        {
            st.insert(c[i]);
        }
        
        long long lesum=0,ge=((int)st.size());
        // ge存有多少种数的出现次数大于k
        for(int i=1;i<=n;i++) 
        {
            while(!st.empty()&&*st.begin()<=i) 
            {
                lesum+=(long long)(*st.begin()); 
                // 若这个数的出现次数小于等于k 那么这个数的贡献就是出现次数
                st.erase(st.begin());
                ge--; //
            }
            cout<<lesum+ge*(i-1)<<endl; //对于这个k 总贡献就是lesum与剩下的数的贡献之和 剩下的这些数的出现次数都大于k 所以每种数的贡献都是k-1
            
        }
    }
    return 0;
}

d题是一个树的dfs
是用到了一个经典但我没见过的结论 两个向量内部允许任意重排 点积最大为升序排列

也就是深度序列由小向大排列 能量值序列由小向大排列 相乘相加

那么剩下就是如何求每个节点的深度了 便用dfs

[h] [c++]
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
#include<bits/stdc++.h>
using namespace std;
int n,fa[200010];
vector<int> g[200010];
long long v[200010],dep[200010];
void dfs(int now,int d) //求每个节点的depth
{
    dep[now]=d;
    for(auto to:g[now])
    {
        dfs(to,d+1);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        cin>>fa[i];
        g[fa[i]].push_back(i);
    }
    for(int i=1;i<=n;i++) cin>>v[i];
    dfs(1,1);
    sort(v+1,v+1+n);
    sort(dep+1,dep+1+n);
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=dep[i]*v[i];
    }
    cout<<ans<<endl;
    return 0;
}