文章目录：
A Yuki 的连通块
题目描述
Yuki 有一个无向图，这个无向图有 $n$ 个点和 $m$ 条边，Yuki 希望知道这个无向图有多少个不同的连通块？
两个连通块不同，当且仅当两连通块的点集不同。
输入
第一行包含两个正整数 $n$ 和 $m$（$1 \le n, m \le 10^6$），分别表示无向图的点数和边数。
接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示编号为 $u$ 和 $v$ 的点之间有一条无向边。
输出
输出一行，表示该无向图的连通块数量。
输入样例
6 3
1 2
2 3
4 5输出样例
3样例解释
连通块分别是 $\{1,2,3\}$、$\{4,5\}$ 和 $\{6\}$。
Hint
若无向图 $G = (V,E)$ 和 $H = (V',E')$，若 $V' \subseteq V$ 且 $E' \subseteq E$，则称 $H$ 是 $G$ 的子图，记作 $H \subseteq G$。
连通性：若无向图 $G = (V,E)$ 满足在任意两个顶点均连通，则称 $G$ 为连通图。
连通块：若 $F$ 是 $G$ 的一个连通子图，若存在 $H$ 满足 $F \subseteq H \subseteq G$ 且 $F$ 为连通图，则 $H$ 是 $G$ 的一个连通块。
题解
第一种做法是可以使用BFS/DFS遍历一遍图，每一次使用BFS或者DFS函数都可以查找到一个连通图，则答案+1，从1到n遍历一遍即可。
但是这种做法特别容易MLE，即使拿链表存储边也会超内存，需要使用优化的方案，比如数组版的邻接表才可以通过。
第二种是使用并查集。
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int n, m;
int parent[1000009], size[1000009];
int find(int x){
while(x != parent[x]){
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
void he(int a, int b){
a = find(a); b = find(b);
if(a == b) return ;
if(size[a] < size[b]){
int tmp = a;
a = b;
b = tmp;
}
parent[b] = a;
size[a] += size[b];
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n ; i++){
parent[i] = i;
size[i] = 1;
}
for(int i = 1; i <= m ; i++){
int a, b;
scanf("%d%d",&a,&b);
he(a, b);
}
int ans = 0;
for(int i = 1; i <= n; i++){
if(find(i) == i) ans ++;
}
cout << ans;
return 0;
}B Yuki 上课
题目背景
Yuki 是一个勤奋又好学的乖孩子，她选了很多门课程。然而，一些课程的上课时间冲突了！因此 Yuki 只能选择一部分课程进行学习。Yuki 想知道自己最多能上多少门课程。
题目描述
具体来说，Yuki 选了 $n$ 门课程，其中第 $i$ 门课程的上课时间是左闭右开区间 $[A_i, B_i)$。Yuki 不可能同时学习两门时间有重叠的课程。
由于 Yuki 勤奋又好学，她希望知道自己最多能上多少门课程。
输入
第一行包含一个正整数 $n$（$1 \le n \le 10^6$），表示课程数。
第 $i+1$ 行包含两个非负整数 $A_i$ 和 $B_i$（$0 \le A_i < B_i \le 10^7$），分别表示第 $i$ 门课程的开始时间和结束时间。
输出
输出一个非负整数表示 Yuki 最多能上多少门课程。
输入样例
3
2 4
3 5
4 6输出样例
2题解
简单的贪心题目，按照结束时间从小到大排序，然后从第一个开始，每次找与上一次结束时间不冲突的最靠前的课程。
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int n;
int main(){
cin >> n;
vector<pair<int,int>> v(n);
for (int i = 0; i < n; ++i) {
scanf("%d%d",&v[i].first, &v[i].second);
}
sort(v.begin(), v.end(),
[](const pair<int,int>& a, const pair<int,int>& b) {
if (a.second != b.second) return a.second < b.second;
return a.first < b.first;
});
int now = -1;
int ans = 0;
for (int i = 0; i < n; ++i) {
if(v[i].first >= now){
ans ++;
now = v[i].second;
}
}
cout << ans;
return 0;
}C ANTENNA的中型背包
题目背景
Antenna 有个不算很能装的背包，她需要装的「物品」也不是很大。
题目描述
在一次任务中，Antenna 有 $n$ 件物品。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。
她的背包容量是 $V$，只要物品的体积之和 $\sum v_i$ 不超过 $V$，那么这些物品都能放入背包中。
为了给「NAYUTA」带来最大的收益，她需要知道她的背包所能装下的物品，价值之和 $\sum w_i$ 最大是多少。
输入格式
第一行，两个正整数 $n, V$（$1 \le n \le 10^3,\; 1 \le V \le 10^5$），表示物品数量以及背包容量。
接下来 $n$ 行，每行两个整数 $v_i, w_i$（$1 \le v_i \le 10^7,\; 1 \le w_i \le 10^7$），分别表示一件物品的体积与价值。
输出格式
一行，一个整数，表示背包所能装下的物品拥有的最大价值之和。
样例输入
3 5
2 100
3 10
3 1样例输出
110题解
01背包问题，但这道题DP数组太大会MLE，需要优化为一维数组。因为后一次遍历可能改变DP数组值之后影响下面的遍历，可以从后往前遍历/开两个一维数组换着存。
同时注意价值之和可能超过int，需要用long long。
#include <bits/stdc++.h>
using namespace std;
int n, v;
int vw[1001][2];
long long dp[2][100001];
int main(){
cin >> n >> v;
for(int i = 1; i <= n; i++){
scanf("%d%d",&vw[i][0], &vw[i][1]);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= v; j++){
if(i%2==1){
dp[1][j] = dp[0][j];
if(j >= vw[i][0]) dp[1][j] = max(dp[1][j], dp[0][j-vw[i][0]] + vw[i][1]); }
else{
dp[0][j] = dp[1][j];
if(j >= vw[i][0]) dp[0][j] = max(dp[0][j], dp[1][j-vw[i][0]] + vw[i][1]);
}
}
}
if(n%2==0)cout << dp[0][v];
else cout << dp[1][v];
return 0;
}D Toby 的无损压缩
题目描述
哈夫曼编码是一种典型的无损压缩算法，其生成的码字满足前缀条件，即任一符号的编码都不是其他符号编码的前缀，从而避免了解码歧义。在所有满足前缀条件的编码方案中，哈夫曼编码可实现最小的平均码长，因此在前缀码意义下是最优的。
Toby 想知道给定一个长度为 $n$ 的字符串，能不能求出该字符串对应的二进制哈夫曼编码的总长度呢？
输入
一行一个仅包含大小写英文字母的非空字符串，长度不超过 $10^7$。
输出
一行一个正整数，表示该字符串对应的二进制哈夫曼编码的总长度。
输入样例 1
abababac输出样例 1
12输入样例 2
vOEwOVQQtIPatwEZPPOKtApMDDpjEFCQhpJwNqqAfDYvwLFWMOpqXczuw0tBxCiNaVadetEVCaihHHJkIcBoEFSuQRUbGHzucfZ1U输出样例 2
535题解
使用优先队列存每一个节点，每次取出最大的两个结合并放回堆中，直到堆中数目为1。
#include <bits/stdc++.h>
using namespace std;
int a[300];
long long n = 0;
struct node{
struct node *left;
struct node *right;
long long sum;
};
struct compare {
bool operator()(node* a, node* b) const {
return a->sum > b->sum;
}
};
priority_queue<node*, vector<node*>, compare> que;
int main(){
char x; n = 0;
while(scanf("%c", &x)!=EOF){
if (('A' <= x && x <= 'Z') || ('a' <= x && x <= 'z')){a[(int)x]++;n++;}
}
for(int i='A'; i<='Z';i++){
if(a[i]==0) continue;
struct node* aa = (struct node*)malloc(sizeof(struct node));
aa->left = NULL; aa->right = NULL; aa->sum = a[i];
que.push(aa);
}
for(int i='a'; i<='z';i++){
if(a[i]==0) continue;
struct node* aa = (struct node*)malloc(sizeof(struct node));
aa->left = NULL; aa->right = NULL; aa->sum = a[i];
que.push(aa);
}
if (que.size() == 1) {
printf("%lld\n", n);
return 0;
}
long long ans = 0;
while(que.size()>1){
struct node* newnew = (struct node*)malloc(sizeof(struct node));
long long all = 0;
struct node* na = que.top(); que.pop();
all += na->sum;
newnew->left = na;
na = que.top(); que.pop();
all += na->sum;
newnew->right = na;
newnew->sum = all;
ans += all;
que.push(newnew);
}
cout << ans;
return 0;
}E Toby 和 DAG 的拓扑序和最短路
题目描述
Toby 得到了一张有向无环图（DAG）。
请你帮助 Toby 求出这张图的拓扑序，以及从节点 $1$ 出发到所有节点的最短路径。若某个点无法从 $1$ 号点到达，则输出 $-1$。
输入
第一行包含两个整数 $n, m$（$1 \le n \le 10^5$），分别表示点数和边数。
接下来 $m$ 行，每行包含三个整数 $u, v, w$（$1 \le u,v \le n,\; -10^3 \le w \le 10^3$），表示存在一条从 $u$ 到 $v$、长度为 $w$ 的有向边。
保证输入的图是有向无环图。
输出
第一行输出 $n$ 个整数，表示该有向无环图的任意一种拓扑序。
第二行输出 $n$ 个整数，第 $i$ 个数表示从 $1$ 号点到 $i$ 号点的最短距离；若无法到达，则输出 $-1$。
输入样例
5 7
1 5 2
1 3 7
2 3 2
2 4 3
3 4 -3
4 5 1
5 4 7输出样例
1 2 3 5 4
0 6 7 4 6题解
拓扑排序可以使用DFS或者Kahn算法，见拓扑排序 - OI Wiki 。
之后使用基于拓扑序的DAG最短路算法。
#include <bits/stdc++.h>
using namespace std;
int n, m;
int head[100009], nxt[100009], ru[100009];
pair<int, int> bian[100009]; // y, v
int bnum = 0;
void addEdge(int x, int y, int v){
bnum++;
bian[bnum].first = y; bian[bnum].second = v;
nxt[bnum] = head[x];
head[x] = bnum;
ru[y]++; return;
}
void TuoPu(){
}
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u,v,w;
scanf("%d%d%d", &u, &v,&w);
addEdge(u,v,w);
}
queue<int> que;
vector<int> TuoPu;
for(int i = 1; i <= n; i++){
if(ru[i] == 0) que.push(i);
}
while(que.size()!=0){
int a = que.front(); que.pop();
TuoPu.push_back(a);
int w = head[a];
while(w != 0){
if(--ru[bian[w].first] == 0) que.push(bian[w].first);
w = nxt[w];
}
}
for(int i:TuoPu){
printf("%d", i);
if(i!=TuoPu.back()) printf(" ");
}
printf("\n");
vector<long long> dist(n + 1, 1LL<<60);
dist[1] = 0;
for(int u: TuoPu){
if(dist[u] == 1LL<<60) continue;
for(int e = head[u]; e!=0; e = nxt[e]){
int v = bian[e].first;
long long now = dist[u] + bian[e].second;
if(now < dist[v]) dist[v] = now;
}
}
for(int i = 1; i <= n; i++){
if(i > 1) printf(" ");
if(dist[i] == 1LL<<60) printf("-1");
else printf("%lld", dist[i]);
}
return 0;
}F Yuki 分硬币
题目描述
Yuki 拥有 $S$ 枚硬币，最开始所有硬币都被丢在同一个存钱罐中。现在 Yuki 打算将这些硬币放入若干个存钱罐中。
Yuki 每次会选一个至少含有 $Q$ 枚硬币的存钱罐，记这个存钱罐为 $Q \_i$，Yuki 可以从中任意取出 $a$ 枚硬币放入一个新的存钱罐中，其中 $a$ 需要满足 $1 \le a \le Q\_i - 1$，此后 Yuki 获得 $a \cdot (Q\_i - a)$ 的快乐值。
Yuki 现在希望达成至少 $M$ 点快乐值，请问 Yuki 需要最少进行多少次这样的操作。
输入格式
输入一个整数 $S$（$2 \le S \le 1000$），$M$（$1 \le M \le 10^9$）。
输出格式
输出一个非负整数表示答案；如果 Yuki 无论如何都不能获得 $M$ 点快乐值，输出 $-1$。
输入样例 #1
8 20输出样例 #1
2输入样例 #2
765 272182输出样例 #2
14样例解释 #1
第一次步骤，从 $8$ 个硬币的存钱罐中取出 $4$ 个，Yuki 获得 $4 \times (8-4)=16$ 点快乐值；
第二步，从 $4$ 个硬币的存钱罐中取出 $2$ 个，Yuki 获得 $2 \times (4-2)=4$ 点快乐值；
总快乐值达到 $20$，共操作了 $2$ 次。
因此答案为 $2$。
题解
观察样例，以为是每次取最大值一分为二，拿堆维护，但是不对，只拿了0.7。
实际的规律： 当我们最终要把 $S$ 枚硬币分成 $k$ 份、并且要让 $\sum x_i^2$ 最小（从而快乐值最大）时，最优划分是：
- 有 $r = S \bmod k$ 份是 $q+1 = \lfloor S/k \rfloor + 1$
- 有 $k - r$ 份是 $q = \lfloor S/k \rfloor$
#include <bits/stdc++.h>
using namespace std;
int main() {
long long S, M;
cin >> S >> M;
long long ans = -1;
for (long long k = 1; k <= S; ++k) {
long long q = S / k;
long long r = S % k;
long long sumSquares = 0;
for (int i = 0; i < k; ++i) {
long long x = (i < r ? q + 1 : q);
sumSquares += x * x;
}
long long H = (S * S - sumSquares) / 2;
if (H >= M) {
ans = k - 1;
break;
}
}
cout << ans;
return 0;
}
或者直接公式计算：
体积平方和：
总快乐值：
G Yuki 与时间转换器
题目背景
这是「Yuki 上课」的威力加强版。
Yuki 是一个勤奋又好学的乖孩子，她选了很多门课程。然而，一些课程的上课时间冲突了！但是这一次，Yuki 拥有了一个可以回到过去的时间转换器。
题目描述
具体来说，Yuki 选了 $n$ 门课程，其中第 $i$ 门课程的上课时间是区间 $[A_i, B_i)$。如果两门课程的上课时间重叠，则 Yuki 无法在同一时间只靠自己完成所有课程。
为了简化题目，我们规定：Yuki 每发动一次时间转换器的能力，相当于制造了自己的一个分身，在本题中被制造出的分身将会一直存在，不会消失。
此外，Yuki 每制造一个新的分身，对魔法的悟性就会上升一个等级，这会使得 Yuki 学习能力得到提升，学习课程所需的时间就会减少 $1$。不过每门课程都有一个至少学习时间要求。
具体来说，第 $i$ 门课程的最短学习时间要求是 $[A_i, C_i)$（其中 $A_i < C_i \le B_i$），如果 Yuki 一共制造了 $m$ 个分身，那么第 $i$ 门课程的时间变为
$[A_i, \max\{B_i - m, C_i\})$。
由于使用时间转换器消耗能量巨大，Yuki 希望知道她最少需要使用多少次时间转换器才能修完所有课程。
输入
第一行包含一个正整数 $n$（$1 \le n \le 5 \times 10^5$），表示课程数。
第 $i+1$ 行包含三个非负整数，$A_i, B_i, C_i$（$0 \le A_i < C_i \le B_i \le 10^7$），表示第 $i$ 门课程的开始时间、正常结束时间和最短学习结束时间。
输出
输出一个非负整数 $m$ 表示 Yuki 顺利修完全部课程最少需要的分身数量。
输入样例
3
1 4 2
2 4 3
3 4 4输出样例
1样例解释
当 Yuki 使用时间转换器制造了 $1$ 个分身后，三门课的时间分别变为 $[1,3)$、$[2,3)$ 和 $[3,4)$。这样 Yuki 可以亲自上第一门课，让分身上第二门课和第三门课。
题解
这道题的总人数（分身数+1）应该在 $[1,n]$ 的范围，所以可以对于答案进行二分查找。
每一次查找检验人数为 $mid$ 时是否会发生冲突，如果冲突则 mini = mid + 1 ，如果不冲突则往回找，即 maxi = mid ，其中这两个变量意思是左右端点。
检验的方法如下（之前需要先对课程数组进行按开始时间升序的排序）：在mid个分身的情况下，建立一个小根堆记录当前的人上课最晚结束时间，开始为空，使用变量pnum记录当前上课人数量，开始为0，表示开始时没有人在上课。然后对于已经排过序的课程数组遍历，如果与堆头冲突（当前已添加的人最早结束时间大于这个课开始时间），则代表需要添加一个人上课，并且每次循环维护堆。如果某一次循环发现pnum大于mid了，即返回false。如果遍历完成则为true。
#include<bits/stdc++.h>
using namespace std;
int n;
struct lesson{
int ai, bi, ci;
};
vector<struct lesson> l;
bool cmp(struct lesson a, struct lesson b){
if(a.ai == b.ai) return (a.bi<b.bi)||((a.bi==b.bi)&&(a.ci<b.ci));
return a.ai<b.ai;
}
bool check(int m){
priority_queue<int, vector<int>, greater<int>> q;
int pnum = 0;
for(auto k: l){
int start = k.ai;
int end = max(k.bi - m + 1, k.ci);
if(!q.empty() && q.top() <= start){
q.pop();
q.push(end);
}else{
q.push(end);
pnum++;
if(pnum > m) return false;
}
}
return true;
}
int main(){
cin >> n;
struct lesson newL;
for(int i = 1; i <= n; i++){
scanf("%d%d%d", &newL.ai, &newL.bi, &newL.ci);
l.push_back(newL);
}
sort(l.begin(), l.end(), cmp);
int mini = 1, maxi = n;
while(mini < maxi){
int mid = (mini + maxi)/2;
if(check(mid)){
maxi = mid;
}else mini = mid + 1;
}
cout << mini - 1;
return 0;
}H ANTENNA的巨型背包
题目背景
Antenna 有个超级能装的背包，但是同样的，她需要要装的「物品」也很大。
题目描述
在一次任务中，Antenna 有 $n$ 件物品。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。
她的背包容量是 $V$，只要被选中的物品总体积之和 $\sum v_i \le V$，那么这些物品都能放入背包中。
为了给「NAYUTA」带来最大的收益，她需要知道她的背包所能装下的物品，价值之和 $\sum w_i$ 最大是多少。
输入格式
第一行，两个正整数 $n, V$（$1 \le n \le 500,\; 1 \le V \le 10^{12}$），表示物品数量以及背包容量。
接下来 $n$ 行，每行两个整数 $v_i, w_i$（$1 \le v_i \le 10^{12},\; 1 \le w_i \le 500$），分别表示一件物品的体积与价值。
输出格式
一行，一个整数，表示背包所能装下的物品拥有的最大价值之和。
样例输入
3 5
2 100
3 10
3 1样例输出
110题解
这道题体积太大，无法用之前的DP数组，所以可以考虑将DP数组换一种定义，即
代码：
#include <bits/stdc++.h>
using namespace std;
long long n, v;
int wi[503];
long long vi[503];
long long dp[2500007];
int main() {
cin >> n >> v;
int maxW = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld%d", &vi[i], &wi[i]);
maxW += wi[i];
}
const long long INF = (1LL << 60);
dp[0] = 0;
for (int i = 1; i <= maxW; i++) {
dp[i] = INF;
}
for (int i = 1; i <= n; i++) {
for (int j = maxW; j >= wi[i]; j--) {
if (dp[j - wi[i]] == INF) continue;
dp[j] = min(dp[j], dp[j - wi[i]] + vi[i]);
}
}
int ans = 0;
for (int j = maxW; j >= 0; j--) {
if (dp[j] <= v) {
ans = j;
break;
}
}
cout << ans;
return 0;
}