A. Everyone Loves to Sleep

题目描述

弗拉德和其他人一样，非常喜欢睡觉。

弗拉德每天必须在特定时间做 n 件事。对于这些事情中的每一个，他都设置了一个闹钟，其中第 i 个在每天的 hi 小时 mi 分钟触发（0≤hi<24,0≤mi<60）。 Vlad 使用 24 小时时间格式，因此在 h=12,m=59 之后是 h=13,m=0，在 h=23,m=59 之后是 h=0,m=0。

这次弗拉德在 H 小时 M 分钟（0≤H<24,0≤M<60）上床睡觉，并要求您回答：直到下一个闹钟响，他才能睡多少觉。

如果在他上床睡觉的时间任何闹钟响起，那么他将睡一段长度为 0 的睡眠。

输入
输入数据的第一行包含一个整数 t (1≤t≤100) — 测试中的测试用例数。

案例的第一行包含三个整数 n、H 和 M (1≤n≤10,0≤H<24,0≤M<60)——警报次数和 Vlad 上床睡觉的时间。

以下 n 行包含两个数字，每个 hi 和 mi (0≤hi<24,0≤mi<60) — 第 i 次警报的时间。两个或多个警报同时触发是可以接受的。

描述时间的数字不包含前导零。

输出
输出 t 行，每行包含对应测试用例的答案。作为答案，输出两个数字——分别是弗拉德要睡觉的小时数和分钟数。如果在他上床睡觉的时间任何闹钟响起，答案将是 0 0。

思路：

我们要寻找的是睡觉后第一个响的闹铃，所以把所有的时间转换为秒，记录在数组中， 然后遍历一遍，找到最接近的闹铃，注意如果两数差为负数，代表隔了一天，用24*60 加上即可。

代码：

void solve(){
    int n, h, m;
    cin >> n >> h >> m;
    vi a;
    int num = h * 60 + m;//睡觉时间
    a.push_back(num);
    for (int i = 1; i <= n;i++){
        int x, y;
        cin >> x >> y;
        a.push_back(x * 60 + y);//存入数组
    }
    sort(all(a));//排序
    int xx = 0, yy = 0;
    int flag = 0;//是否刚睡下闹铃就响了
    for (int i = 0; i <= n; i++){
        if(a[i]>num){
            xx = i;//闹铃响的时间下标
            break;
        }
        if (a[i] == num && i + 1 <= n && a[i + 1] == num){
            flag = 1;//如果相邻两个数组元素相同且等于睡觉时间
        }
        if(a[i]==num){
            yy = i;//睡觉时间下标
        }
    }
    if(flag){
        cout << 0 << " " << 0 << nl;
    }else{
        int xxx = a[xx] - a[yy];//时间差
        if (xxx < 0){
            xxx = 24 * 60 + xxx;
        }
        int hh = (xxx) / 60;
        int mm = (xxx) % 60;
        cout << hh << " " << mm << nl;
    }
}
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

t 宝代码：

思路大致相同，而 t 宝是用ans更新最小值

void solve(){
    int n, h, m;
    cin >> n >> h >> m;
    int ans = inf;
    for (int i = 0; i < n; i++){
        int hh, mm;
        cin >> hh >> mm;
        int x = h * 60 + m;
        int y = hh * 60 + mm;
        int diff = y - x;
        if (diff < 0)
            diff += 24 * 60;
        ans = min(ans, diff);
    }
    cout << ans / 60 << " " << ans % 60 << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

B. Remove Prefix

题目大意

Polycarp 提供了一些长度为 $n(1\le a_i\le n)$ 的整数 a 序列。只有由不同的数字（即不同的数字）组成的序列才能使 Polycarp 快乐。

为了使他的序列像这样，Polycarp 将进行一些（可能为零）的移动。

在一个动作中，他可以：

删除序列的第一个（最左边）元素。
例如，在一次移动中，序列 [3,1,4,3] 将产生由不同数字组成的序列 [1,4,3]。

确定他需要进行的最小移动次数，以便在剩余序列中所有元素都不同。换句话说，找到给定序列 a 的最小前缀的长度，将其删除后，序列中的所有值都是唯一的。

输入
输入的第一行包含一个整数 $t(1\le t\le 10^4)$ — 测试用例的数量。

每个测试用例由两行组成。

第一行包含一个整数 $n(1\le n\le 2\cdot 10^5)$ — 给定序列 a 的长度。

第二行包含 n 个整数 $a_1,a_2,\dots ,a_n(1\le a_i\le n)$ — 给定序列 a 的元素。

保证所有测试用例的 n 个值之和不超过 $2\cdot 10^5$。

输出
对于每个测试用例，将您的答案打印在单独的行上——必须从序列开头删除的最小元素数，以便所有剩余元素都不同。

思路解析：

题目大意是给定一个数组，每次从前面删去一个数，删掉多少时，数组剩下元素互不相同。

最初的想法直接用map记录个数，但是后面发现每次更新无法保证剩余都不同

这题很巧妙，因为每次只能从头删，所以我们只需要从后往前遍历，直到出现重复，说明数组中最大可以存在的不重复元素个数为 ans，所以需要删除的元素个数为n - ans

代码解析：

void solve(){
    int n;
    cin >> n;
    int a[maxn] = {0};
    int t[maxn] = {0};
    int cnt = 0;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    int res = 0;
    for (int i = n - 1; i >= 0;i--){
        if(t[a[i]])break;
        t[a[i]]++;
        res++;
    }
    cout << n - res << nl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

C. Minimum Varied Number

题目大意

找到具有给定数字总和 $s$ 的最小数字，使得其中的所有数字都是不同的（即所有数字都是唯一的）。

例如，如果 $s=20$，则答案为 $389$。这是所有数字不同且数字之和为 $20（3+8+9=20）$的最小数字。

对于给定的 $s$ 打印所需的数字。

输入
第一行包含一个整数 $t(1\le t\le 45)$——测试用例的数量。

每个测试用例由包含唯一整数 $s(1\le s\le 45)$ 的行指定。

输出
打印 t 个整数——给定测试用例的答案。

思路解析:

这不是最简单（最暴力）的搜索问题吗？

只有数字1 ~ 9 每个数字选择或不选择

解法1：（暴力枚举）

不是啥聪明(大笨比)做法，大家图一乐就行 hhhhhhhhhhhhh

int res;
void dfs(int x){
    int ans = 0;
    for (int i = 1; i >=0; i--)
    	for (int j = 1; j >= 0; j--)
    		for (int k = 1; k >= 0; k--)
    			for (int ii = 1; ii >= 0; ii--)
    				for (int jj = 1; jj >= 0; jj--)
    					for (int kk = 1; kk >= 0; kk--)
    						for (int iii = 1; iii >= 0; iii--)
    							for (int jjj = 1; jjj >= 0; jjj--)
    								for (int kkk = 1; kkk >= 0; kkk--)
	if (i * 1 + j * 2 + k * 3 + ii * 4 + jj * 5 + kk * 6 + iii * 7 + jjj * 8 + kkk * 9 == s){
		if (i)
		ans = ans * 10 + 1;
		if (j)
		ans = ans * 10 + 2;
		if (k)
		ans = ans * 10 + 3;
		if (ii)
		ans = ans * 10 + 4;
		if (jj)
		ans = ans * 10 + 5;
		if (kk)
		ans = ans * 10 + 6;
		if (iii)
		ans = ans * 10 + 7;
		if (jjj)
		ans = ans * 10 + 8;
		if (kkk)
		ans = ans * 10 + 9;
		res = min(res, ans);
		ans = 0;
	}
}
void solve(){
	int s;
    cin >> s;
    res = inf;
    dfs(s);
    cout << res << nl;
}
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

解法2：（暴力dfs）

int ans;//答案
void dfs(int aim, int i, int now, int cnt){
    //cnt 当前的各个数位和
    //aim 目标值
    //now 当前的这个数
    if(i > 9 || cnt > aim) {
        if(cnt == aim)
            ans = min(ans, now);
        return;
    }
    // yes
    dfs(aim, i + 1, now * 10 + i, cnt + i);
    // no
    dfs(aim, i + 1, now, cnt);
}
 
void solve() {
    int n;
    cin >> n;
    ans = inf;
    dfs(n, 1, 0, 0);
    cout << ans << nl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解法3：（打表法）

这可是非常高效的 $O(1)$ 的时间复杂度呢。。。。

void solve(){
    int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
               19, 29, 39, 49, 59, 69, 79, 89,
               189, 289, 389, 489, 589, 689, 789,
               1789, 2789, 3789, 4789, 5789, 6789,
               16789, 26789, 36789, 46789, 56789,
               156789, 256789, 356789, 456789,
               1456789, 2456789, 3456789,
               13456789, 23456789, 123456789};
    int n;
    cin >> n;
    cout << a[n] << nl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

解法4：（这才是正解）

因为要求数越少越好，所以我们从后往前枚举9 ~ 1

如果这个数可以被使用，就将它加入到字符串中，然后更新当前值，贪心的思路。

void solve(){
    int s;
    cin >> s;
    string res = "";
    for (int i = 9; i >= 1; i--){
        if (s >= i){
            res += (char)('0' + i);//拼接字符串
            s -= i;//更新当前剩余的值
        }
    }
    reverse(all(res));//翻转字符串
    cout << res << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13

D. Color with Occurrences

题目大意：

给定一个字符串，给你n个短串，然后问是否可以用 n 个短串，将给定字符串完全覆盖，可以重复覆盖。

如果可以输出字符串序号和第一个匹配的位置下标。

不可以输出-1

思路解析：

模拟题意，处理每个短串是否匹配，记录匹配下标和右端点位置。

void solve(){
    string t;
    cin >> t;
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i++)
        cin >> s[i];
    int len = (int)t.size();
    vector<int> right_(len + 1, -1);//第 i 个位置匹配串后右端点的位置
    vector<int> index(len + 1, -1);//第 i 个位置匹配子串的序号
    for (int id = 0; id < n; id++){
        string &w = s[id]; //遍历每个短串
        for (int i = 0; i <= (int)t.size() - (int)w.size(); i++){
            if (t.substr(i, w.size()) == w){ //如果子串匹配
                if (i + (int)w.size() > right_[i]){
                    right_[i] = i + (int)w.size();
                    index[i] = id;
                }
            }
        }
    }
    int ans = 0;//匹配个数
    int p = 0;
    vector<pair<int, int>> res;//步骤
    while (p < len){
        int pos = (int)(max_element(right_.begin(), right_.begin() + p + 1) - right_.begin());
        int to = right_[pos];
        if (to <= p){//无法覆盖
            ans = -1;
            break;
        }
        res.push_back({index[pos], pos});
        ans += 1;
        p = to;
    }
    cout << ans << nl;
    if (ans != -1){
        for (auto i : res)
            cout << i.first + 1 << " " << i.second + 1 << nl;
    }
}
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

E. Add Modulo 10

题目大意

给定一个由 n 个整数组成的数组 $a_1,a_2,...,a_n$
您可以应用以下操作任意次数：

选择一个索引 $i(1\le i\le n)$ 并用值 $a_i+(a_i$ $mod$ $10)$ 替换元素 $a_i$ 的值，其中 $a_i$ $mod$ $10$ 是整数除以 $a_i$ 除以 $10$ 的余数。
对于单个索引（值 i），可以多次应用此操作。如果对同一索引重复执行该操作，则每次都考虑 $a_i$ 的当前值。例如，如果 $a_i=47$，那么在第一次操作之后我们得到 $a_i=47+7=54$，在第二次操作之后我们得到 $a_i=54+4=58$。

检查是否可以通过应用多个（可能为零）操作使所有数组元素相等。

例如，您有一个数组 [6,11]。

让我们将此操作应用于数组的第一个元素。让我们将 a1=6 替换为 a1 + ( a1 mod 10 ) = 6 + ( 6 mod 10 ) = 6 + 6 = 12。我们得到数组 [12,11]。
然后将此操作应用于数组的第二个元素。让我们将 a2=11 替换为 a2 + ( a2 mod 10 ) = 11 + ( 11 mod 10 ) = 11 + 1 = 12。我们得到数组 [12,12]。
因此，通过应用 2 个操作，您可以使数组的所有元素相等。

输入
第一行包含一个整数 $t(1\le t\le 10^4)$——测试用例的数量。下面是对每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n(1\le n\le 2\cdot 10^5)$ — 数组的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_i(0\le a_i\le 10^9)$ — 数组元素。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

输出
对于每个测试用例打印：

如果可以使所有数组元素相等，则为 YES；否则，NO。
您可以在任何情况下打印 YES 和 NO（例如，字符串 yEs、yes、Yes 和 YES 将被识别为肯定答案）。

思路解析：

其实如果找规律的话可以看出每个数字每次取余在变化时，有些是有循环的

这里枚举一下个位数是0 ~ 9 的 Add Modulo 10:

0 不能转移
1 2 3 4 5 6 7 8 9 0
2 4 8 6 2
3 6 2 
4 8 2
5 0
6 2 
7 4 8 6 2
8 6 2
9 8 6 2

1
2
3
4
5
6
7
8
9
10
11

我们不难发现，转移到最后取余无非两种结果，要么为0，要么为2

如果数组中有一个 0 那么只需要判断原数组元素的余数是否全部相同，相同为YES 不同为NO

如果都不能到 0 ，说明进入到 2 的循环里面

但是我们通过递推找关系可以看出，他们 mod 20 是一个循环

然后判断每个的余数是否相等即可。

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    bool any = false;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        while (a[i] % 10 != 0 && a[i] % 10 != 2){
        //余数!=0&&!=2时
            a[i] += a[i] % 10;//一直去更新余数
        }
        any |= (a[i] % 10 == 0);
    }
    if (any){
        cout << (a == vector<int>(n, a[0]) ? "Yes" : "No") << '\n';
        return;
    }
    int val = a[0] % 20;
    bool ok = true;
    for (int i = 0; i < n; i++)
        ok &= (a[i] % 20 == val);
    cout << (ok ? "Yes" : "No") << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

F. Build a Tree and That Is It

题目大意：

树是无环的连通无向图。请注意，在这个问题中，我们讨论的是无根树。

给你四个正整数 $n,d_{12},d_{23}$ 和 $d_{31}$ 。构造一棵树，使得：

它包含从 $1$ 到 $n$ 编号的 $n$ 个顶点，
从顶点 $1$ 到顶点 $2$ 的距离（最短路径的长度）为 $d_{12}$，
顶点 $2$ 到顶点 $3$ 的距离为 $d_{23}$，
从顶点 $3$ 到顶点 $1$ 的距离为 $d_{31}$。

输出任何满足上述所有要求的树，或者确定不存在这样的树。

输入
输入的第一行包含一个整数 $t(1\le t\le 10^4)$ — 测试中的测试用例数。

接下来是 t 个测试用例，每个用例写在单独的行上。

每个测试用例由四个正整数 $n,d_{12},d_{23}$ 和 $d_{31}$ $(3\le n\le 2\cdot 10^5;1\le d_{12},d_{23},d_{31}\le n-1)$组成。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$。

输出
对于每个测试用例，如果存在合适的树，则打印 $YES$，否则打印 $NO$。

如果答案是肯定的，则打印另一条 $n-1$ 行，每行包含对树的一条边的描述——一对正整数 $x_i,y_i$，这意味着第 i 条边连接顶点 $x_i$ 和 $y_i$。

边和边的顶点可以按任何顺序打印。如果有几棵合适的树，则输出其中的任何一棵树。

思路解析：

void solve(){
    int n, d12, d23, d31;
    cin >> n >> d12 >> d23 >> d31;
    if (d12 > d23 + d31 || d23 > d31 + d12 || d31 > d12 + d23)
        cout << "NO" << endl;
    else if ((d12 + d23 + d31) % 2 == 1)
        cout << "NO" << endl;
    else if (n <= (d12 + d23 + d31) / 2)
        cout << "NO" << endl;
    else{
        int s1 = (d12 + d31 - d23) / 2;
        int s2 = (d23 + d12 - d31) / 2;
        int s3 = (d31 + d23 - d12) / 2;
        vector<int> p1 = {0}, p2 = {1}, p3 = {2};
        int V = 3;
        for (int j = 0; j < s1 - 1; j++){
            p1.push_back(V);
            V++;
        }
        for (int j = 0; j < s2 - 1; j++){
            p2.push_back(V);
            V++;
        }
        for (int j = 0; j < s3 - 1; j++){
            p3.push_back(V);
            V++;
        }
        if (s1 == 0){
            p2.push_back(0);
            p3.push_back(0);
        }
        else if (s2 == 0){
            p3.push_back(1);
            p1.push_back(1);
        }
        else if (s3 == 0){
            p1.push_back(2);
            p2.push_back(2);
        }
        else{
            p1.push_back(V);
            p2.push_back(V);
            p3.push_back(V);
            V++;
        }
        cout << "YES" << endl;
        for (int j = 0; j < s1; j++)
            cout << p1[j] + 1 << ' ' << p1[j + 1] + 1 << endl;
        for (int j = 0; j < s2; j++)
            cout << p2[j] + 1 << ' ' << p2[j + 1] + 1 << endl;
        for (int j = 0; j < s3; j++)
            cout << p3[j] + 1 << ' ' << p3[j + 1] + 1 << endl;
        if (V < n)
            for (int j = V; j < n; j++)
                cout << j << ' ' << j + 1 << endl;
    }
}
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

G. Path Prefixes

题目大意

给你一棵有根的树。它包含 n 个顶点，从 1 到 n 编号。根是顶点 1。

每条边都有两个正整数值。因此，每个边都给出了两个正整数 $a_j$ 和 $b_j$。

输出 n−1 个数字 $r_2,r_3,\dots ,r_n$，其中 $r_i$ 定义如下。

考虑从根（顶点 1）到 $i（2\le i\le n）$的路径。设沿这条路径的 $a_j$ 的总成本为 $A_i$。那么 $r_i$ 等于该路径的最大前缀的长度，使得沿该前缀的 $b_j$ 之和不超过 $A_i$。

考虑一个例子。在这种情况下：

$r_2=0$，由于到 $2$ 的路径的 $a_j$ 量等于 $5$，因此只有这条长度为 $0$ 的路径的前缀的bj量较小或相等；

$r_3=3$，由于到 $3$ 的路径的 $a_j$ 数量等于 $5+9+5=19$，所以这条路径长度为 $3$ 的前缀 $b_j$ 之和等于 $6+10+1=17$（数量为$17\le 19$)；

$r_4=1$，因为到 $4$ 的路径的 $a_j$ 数量等于 $5+9=14$，所以这条路径长度为 $1$ 的前缀的 $b_j$ 数量等于 $6$（这是最长的合适前缀，因为长度 $2$ 的 $b_j$ 数量已经等于 $6+10=16$，大于 $14$)；

$r_5=2$，因为到 $5$ 的路径的 $a_j$ 量等于 $5+9+2=16$，所以这条路径长度为 $2$ 的前缀 $b_j$ 之和等于 $6+10=16$（这是最长的合适前缀，因为长度为 $3$ 的前缀已经有 $b_j$ 的数量等于 $6+10+1=17$，比 $16$ 还多）；

$r_6=1$，由于到 $6$ 的路径的 $a_j$ 量等于 $2$，所以这条路径长度为 $1$ 的前缀的$b_j$ 量等于1；

$r_7=1$，因为到 $7$ 的路径的 $a_j$ 数量等于 $5+3=8$，所以这条路径长度为 $1$ 的前缀的 $b_j$ 数量等于 $6$（这是最长的合适前缀，因为长度 $2$ 的 $b_j$ 数量已经等于 $6+3=9$，大于 $8$)；

$r_8=2$，由于到 $8$ 的路径的$a_j$ 量等于 $2+4=6$，所以这条路径长度为 $2$ 的前缀的$b_j$ 量等于$1+3=4$；

$r_9=3$，因为到 $9$ 的路径的 $a_j$ 数量等于 $2+4+1=7$，所以这条路径长度为 $3$ 的前缀的 $b_j$ 之和等于 $1+3+3=7$。

输入
第一行包含一个整数 $t(1\le t\le 10^4)$ — 测试中的测试用例数。

测试用例的描述如下。

每个描述都以包含整数 $n(2\le n\le 2\cdot 10^5)$ 的行开头——树中的顶点数。

接下来是 $n-1$ 个字符串，每个字符串包含三个数字 $p_j,a_j,b_j(1\le p_j\le n;1\le a_j,b_j\le 10^9)$ — 顶点 j 的祖先，第一个和第二个值是边从 $p_j$ 到 $j$。 $j$ 的值贯穿从 $2$ 到 $n$ 的所有值。保证每组输入数据都有一个正确的挂树，根在顶点 $1$。

保证所有输入测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

输出
对于每个测试用例，在一行中输出 $n-1$ 个整数：$r_2,r_3,\dots ,r_n$。

思路解析：

void dfs(vector<vi> &c, vi &a, vi &b, vi &res, vll &seq, ll s, int v = 0){
    if (v != 0)
        res[v] = upper_bound(seq.begin(), seq.end(), s) - seq.begin() - 1;
    ll sum = seq.back();
    for (int w : c[v]){
        seq.push_back(sum + b[w]);
        dfs(c, a, b, res, seq, s + a[w], w);
        seq.pop_back();
    }
}
void solve(){
    int n;
    cin >> n;
    vi p(n), a(n), b(n);
    for (int j = 1; j < n; j++){
        cin >> p[j] >> a[j] >> b[j];
        p[j]--;
    }
    vector<vi> c(n);
    for (int j = 1; j < n; j++)
        c[p[j]].push_back(j);
    vi res(n);
    vll seq = {0};
    dfs(c, a, b, res, seq, 0);
    for (int i = 1; i < n; i++){
        cout << res[i] << " \n"[i == n - 1];
    }
}
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