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

题目

正文

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;
}

C 洛谷 P3231

[HNOI2013] 消毒

题目描述

最近在生物实验室工作的小 T 遇到了大麻烦。 由于实验室最近升级的缘故，他的分格实验皿是一个长方体，其尺寸为 \(a\times b\times c\)。为了实验的方便，它被划分为 \(a\times b\times c\) 个单位立方体区域，每个单位立方体尺寸为 \(1\times 1\times 1\)，并用 \((i,j,k)\) 标识一个单位立方体。这个实验皿已经很久没有人用了。现在，小 T 被导师要求将其中一些单位立方体区域进行消毒操作（每个区域可以被重复消毒）。

而由于严格的实验要求，他被要求使用一种特定的 F 试剂来进行消毒。 这种 F 试剂特别奇怪，每次对尺寸为 \(x\times y\times z\) 的长方体区域（它由 \(x\times y\times z\) 个单位立方体组成）进行消毒时，只需要使用 \(\min(x,y,z)\) 单位的 F 试剂。F 试剂的价格不菲，这可难倒了小 T。

现在请你告诉他，最少要用多少单位的 F 试剂。

输入格式

本题有多组数据。

第一行是一个正整数 \(D\)，表示数据组数。

接下来是 \(D\) 组数据，每组数据第一行是三个正整数 \(a,b,c\) 表示实验皿的尺寸。

接下来会出现 \(a\) 个 \(b\) 行 \(c\) 列的用空格隔开的 01 矩阵，0 表示对应的单位立方体不要求消毒，1 表示对应的单位立方体需要消毒：如，如果第 \(1\) 个 01 矩阵的第 \(2\) 行第 \(3\) 列为 1，则表示单位立方体 \((1,2,3)\) 需要被消毒。

输出格式

\(D\) 行，每行一个整数，表示对应实验皿最少要用多少单位的 F 试剂。

样例 #1

样例输入 #1

1
4  4 4
1  0 1 1
0  0 1 1
0  0 0 0
0  0 0 0
0  0 1 1
1  0 1 1
0  0 0 0
0  0 0 0
0  0 0 0
0  0 0 0
1  0 0 0
0  0 0 0
0  0 0 0
0  0 0 0
0  0 0 0
1  0 0 0

样例输出 #1

3

提示

样例 1 解释

对于区域 \((1,1,3)-(2,2,4)\) 和 \((1,1,1)-(4,4,1)\) 消毒，分别花费 \(2\) 个单位和 \(1\) 个单位的 F 试剂。

数据规模与约定

对于 \(100\%\) 的数据，保证 \(1\le a,b,c\le 5\times 10^3\)，\(abc\le 5\times 10^3\)，且 \(1\le D\le 3\)。

暂时还不会
他的tag是搜索/枚举/二分图
我觉得应该再看看

D 洛谷 P2120

[ZJOI2007] 仓库建设

题目描述

L 公司有 \(n\) 个工厂，由高到低分布在一座山上，工厂 \(1\) 在山顶，工厂 \(n\) 在山脚。

由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L 公司的总裁 L 先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是 L 先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。

由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第 \(i\) 个工厂目前已有成品 \(p_i\) 件，在第 \(i\) 个工厂位置建立仓库的费用是 \(c_i\)。

对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于 L 公司产品的对外销售处设置在山脚的工厂 \(n\)，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，一件产品运送一个单位距离的费用是 \(1\)。

假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据：

• 工厂 \(i\) 距离工厂 \(1\) 的距离 \(x_i\)（其中 \(x_1=0\)）。
• 工厂 \(i\) 目前已有成品数量 \(p_i\)。
• 在工厂 \(i\) 建立仓库的费用 \(c_i\)。

请你帮助 L 公司寻找一个仓库建设的方案，使得总的费用（建造费用 + 运输费用）最小。

输入格式

输入的第一行是一个整数 \(n\)，代表工厂的个数。

第 \(2\) 到 \((n + 1)\) 行，每行有三个用空格隔开的整数，第 \((i + 1)\) 行的整数依次代表 \(x_i,~p_i,~c_i\)。

输出格式

仅输出一行一个整数，代表最优方案的费用。

样例 #1

样例输入 #1

3
0 5 10
5 3 100
9 6 10

样例输出 #1

32

提示

样例输入输出 \(1\) 解释

在工厂 \(1\) 和工厂 \(3\) 建立仓库，建立费用为 \(10+10=20\) ，运输费用为 \((9-5) \times 3 = 12\)，总费用 \(32\)。

数据范围与约定

对于 \(20\%\) 的数据，保证 \(n \leq 500\)。

对于 \(40\%\) 的数据，保证 \(n \leq 10^4\)。

对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^6\)，\(0 \leq x_i,p_i,c_i < 2^{31}\)。

对于任意的 \(1 \leq i < n\)，保证 \(x_i < x_{i + 1}\)。

设答案为 \(ans\)，保证 \(ans + \sum\limits_{i = 1}^{n} p_ix_i < 2^{63}\)。

这题是感觉极其罕见的斜率dp
不会，以后学
先去原题链接看题解吧

E CodeForces 197A

Plate Game

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

You've got a rectangular table with length \(a\) and width \(b\) and the infinite number of plates of radius \(r\). Two players play the following game: they take turns to put the plates on the table so that the plates don't lie on each other (but they can touch each other), and so that any point on any plate is located within the table's border. During the game one cannot move the plates that already lie on the table. The player who cannot make another move loses. Determine which player wins, the one who moves first or the one who moves second, provided that both players play optimally well.

Input

A single line contains three space-separated integers \(a\), \(b\), \(r (1 ≤ a, b, r ≤ 100)\) — the table sides and the plates' radius, correspondingly.

Output

If wins the player who moves first, print "First" (without the quotes). Otherwise print "Second" (without the quotes).

Examples

input

5 5 2

output

#####First

input

6 7 4

output

Second

我的题解

如果不能放，就后手赢
如果能放，就先手赢
因为先手总能找到机会卡后手位置

我的代码

#include <iostream>

#define int long long

int t;

void solve()
{
    int a,b,r,num = 0,num1 = 0;
    std::cin >> a >> b >> r;
    int d = r * 2;
    if(a < d || b < d) std::cout << "Second\n";
    else std::cout << "First\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;
}