最近我们开始了暑假集训
现在我来补一下第一场集训的题解

题目

正文

A 黑暗爆炸 4771

题面

Description

给定一棵 \(n\) 个点的有根树，编号依次为 \(1\) 到 \(n\) ，其中 \(1\) 号点是根节点。每个节点都被染上了某一种颜色，其中第 \(i\) 个节点的颜色为 \(c[i]\) 。如果 \(c[i]=c[j]\) ，那么我们认为点 \(i\) 和点 \(j\) 拥有相同的颜色。定义 \(depth[i]\) 为 \(i\) 节点与根节点的距离，为了方便起见，你可以认为树上相邻的两个点之间的距离为 \(1\) 。站在这棵色彩斑斓的树前面，你将面临 \(m\) 个问题。每个问题包含两个整数 \(x\) 和 \(d\) ，表示询问 \(x\) 子树里且 \(depth\) 不超过 \(depth[x]+d\) 的所有点中出现了多少种本质不同的颜色。请写一个程序，快速回答这些询问。

Input

第一行包含一个正整数 \(T(1<=T<=500)\) ，表示测试数据的组数。
每组数据中，第一行包含两个正整数 \(n(1<=n<=100000)\) 和 \(m(1<=m<=100000)\) ，表示节点数和询问数。
第二行包含 \(n\)个正整数，其中第 \(i\) 个数为 \(c[i](1<=c[i]<=n)\) ，分别表示每个节点的颜色。
第三行包含 \(n-1\) 个正整数，其中第 \(i\) 个数为 \(f[i+1](1<=f[i]<i)\) ，表示节点 \(i+1\) 的父亲节点的编号。
接下来 \(m\) 行，每行两个整数 \(x(1<=x<=n)\) 和 \(d(0<=d<n)\) ，依次表示每个询问。
输入数据经过了加密，对于每个询问，如果你读入了 \(x\) 和 \(d\) ，那么真实的 \(x\) 和 \(d\) 分别是 \(x\) \(xor\) \(last\) 和 \(d\) \(xor\) \(last\) ，
其中 \(last\) 表示这组数据中上一次询问的答案，如果这是当前数据的第一组询问，那么 \(last=0\) 。
输入数据保证 \(n\) 和 \(m\) 的总和不超过 \(500000\) 。

Output

对于每个询问输出一行一个整数，即答案。

Sample Input

1
5 8
1 3 3 2 2
1 1 3 3
1 0
0 0
3 0
1 3
2 1
2 0
6 2
4 1

Sample Output

1
2
3
1
1
2
1
1

这题的解法是主席树 但是我不会

先放个其他大佬的链接后面再补吧

B 黑暗爆炸 3399

题面

Description

约翰用沙子建了一座城堡．正如所有城堡的城墙，这城墙也有许多枪眼，两个相邻枪眼中间那部分叫作城齿．
城墙上一共有 \(N(1≤N≤25000)\) 个城齿，每一个都有一个高度 \(M~i~(1≤M~i~≤100000)\) ．
现在约翰想把城齿的高度调成某种顺序下的 \(B~i~\) ， \(B~2~\) ，…， \(B~N~(I≤B~i~≤100000)\) .

• 一个城齿每提高一个单位的高度，约翰需要 \(X(I≤X≤100)\) 元；
• 每降低一个单位的高度，约翰需要 \(Y(1≤y≤100)\) 元．

问约翰最少可用多少钱达到目的．数据保证答案不超过 2³²．

Input

第1行输入3个整数 \(N\) ， \(X\) ， \(Y\) .
第2到N+1行每行输入两个整数 \(M~i~\) 和 \(B~i~\) ．

Output

最少花费.

Sample Input

3 6 5
3 1
1 2
1 2

Sample Output

11

Hint

第 \(1\) 个城齿降低 \(1\) ，第 \(2\) 个城齿提高 \(1\)

我的题解

先说结论：签到题
两个数组排序
然后求差值
再分类讨论求和
就行了

一开始我看到城墙的时候
我认为城墙是不可移动的
但是Hint又说：第 \(1\) 个城齿降低 \(1\) ，第 \(2\) 个城齿提高 \(1\)
我以为是那就要这个城齿能和隔壁的城齿交换
想来想去都不对
后面看过的人多了才这么写的
真让人头大

我的代码

#include <iostream>
#include <algorithm>

#define int long long

int t;
const int N = 1e7;
int a[N];
int b[N];

int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}

void solve()
{
    int n,x,y,ans = 0;
    std::cin >> n >>x >> y;
    for(int i = 0 ; i < n ; i ++)
        std::cin >> a[i] >> b[i];

    std::sort(a,a+n);
    std::sort(b,b+n);

    for(int i = 0 ; i < n ; i ++)
    {
        if(a[i] > b[i]) ans += y * (a[i] - b[i]);
        else ans += x * (b[i] - a[i]);
    }

    std::cout << ans << "\n";
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

	t = 1;
	//std::cin >> t;
	
	while(t--)
	{
		solve();
	}
    return 0;
}
~~~cpp