c ++零基础可视化——vector

c ++零基础可视化——vector

初始化
vector<int> v0(5);         // 0 0 0 0 0
vector<int> v1(5, 1);      // 1 1 1 1 1
vector<int> v2{1, 2, 3}    // 1 2 3
vector<int> v3(v1);        // 1 1 1 1 1
vector<vector<int>> v4(2, vector<int>(8, 3));   
//   3 3 3 3 3 3 3 3
//   3 3 3 3 3 3 3 3
auto v5 = vector(2, vector<int>(8, 3));
//   3 3 3 3 3 3 3 3
//   3 3 3 3 3 3 3 3

启发:使用auto可以更好对二位vector进行初始化。

赋值运算,比较运算
vector<int> v0{1, 2, 3};
vector<int> v1;
v1 = v0;
vector<int> v2{1, 2, 4};
v0 < v2;

比较大小:按字典序比较。

vector常用成员函数

v.front()获取vector的第一个元素

v.back()获取vector的最后一个元素

v.size()获取vector的元素个数

v.empty()判断vector是否为空

v.clear()清空vector的数据

v.push_back()将数据塞入vector的末尾

v.pop_back()将数据从vector的末尾移除

v.resize(3)重新定义vector的大小。若比原先小,则删除末尾元素;若比原先大,则用0填充新增的元素;v.resize(5, 1)若有第二个参数,则用第二个参数来填充

v.begin()

v.end()

以下示例仅代表用法,并不是对同一数组进行连续操作,而代表的是每次都对最上面的数组进行操作,即不考虑之前对数组操作的语句对数组的改变。以此来演示语法规则。

vector<int> v{1, 2, 3, 4, 5};
v.erase(v.begin()); //删除1,得到2 3 4 5
v.erase(v.begin() + 1, v.end() + 3) //删除2 3,得到1 4 5    
vector<int> v{1, 2, 3};
v.insert(v.begin(), 4);  //插入4,得到4 1 2 3
v.insert(v.begin + 1, {4, 5, 6});  //插入4 5 6,得到 1 4 5 6 2 3
vector<int> v1(1, 2, 3);
vector<int> v2(4, 5, 6);
v1.insert(v1.end(), v2.begin(), v2.end()); //插入 4 5 6,得到 1 2 3 4 5 6
题目一【旋转排列】:https://www.luogu.com.cn/problem/B3688

[语言月赛202212] 旋转排列

题目背景

我们称一个数列 p p p 是一个长度为 n n n 的排列,当且仅当 p p p 满足如下条件:

  1. p p p 的长度为 n n n
  2. 1 , 2 , 3 , … n 1, 2, 3, \dots n 1,2,3,n n n n 个数在 p p p 中均恰好出现一次。

题目描述

对于一个排列 p p p,定义一次“shift”操作是指:将 p p p 里的每一个数字都依次向后移动一位,并把 p p p 的最后一个数字移动到开头去。

例如,若排列 p p p 初始时为 [ 1 , 4 , 2 , 3 ] [1,4,2,3] [1,4,2,3],则“shift”一次以后将变为 [ 3 , 1 , 4 , 2 ] [3,1,4,2] [3,1,4,2]

现在,给定一个长度为 n n n 的排列 p p p,请你按照如下规定循环操作:

  1. 对当前的排列 p p p 做一次“shift”操作;
  2. 输出本次“shift”以后的排列 p p p
  3. 判断排列 p p p 的最后一个数字是否是 n n n,如果是,则结束循环操作;否则回到 1 1 1 继续操作。

提示:请严格按照题目给出的顺序进行循环操作。

输入格式

第一行是一个整数,表示排列 p p p 的长度 n n n
第二行有 n n n 个整数表示排列 p p p,第 i i i 个整数表示 p i p_i pi

输出格式

对于每次操作的第二条“输出”操作,请你输出一行 n n n 个整数,按顺序表示当前排列的每个数,一行中相邻两个数之间用一个空格隔开。

样例 #1

样例输入 #1

4
1 4 2 3

样例输出 #1

3 1 4 2
2 3 1 4

样例 #2

样例输入 #2

3
1 2 3

样例输出 #2

3 1 2
2 3 1
1 2 3

样例 #3

样例输入 #3

10
1 7 6 5 8 4 3 9 10 2

样例输出 #3

2 1 7 6 5 8 4 3 9 10

提示

样例 2 解释

p = [ 1 , 2 , 3 ] p = [1, 2, 3] p=[1,2,3],按如下顺序进行循环操作:

  1. 进行一次“shift”操作, p p p 变为 [ 3 , 1 , 2 ] [3,1,2] [3,1,2]
  2. 输出当前的排列 p p p,故输出第一行为 3 1 2
  3. 判断 p 3 = 2 ≠ 3 p_3 = 2 \neq 3 p3=2=3,故继续循环操作;
  4. 进行一次“shift”操作, p p p 变为 [ 2 , 3 , 1 ] [2,3,1] [2,3,1]
  5. 输出当前的排列 p p p,故输出第二行为 2 3 1
  6. 输出判断 p 3 = 1 ≠ 3 p_3 = 1 \neq 3 p3=1=3,故继续循环操作;
  7. 进行一次“shift”操作, p p p 变为 [ 1 , 2 , 3 ] [1,2,3] [1,2,3]
  8. 输出当前的排列 p p p,故输出第二行为 1 2 3
  9. 输出判断 p 3 = 3 = 3 p_3 = 3 =3 p3=3=3,故停止循环;

数据规模与约定

各测试点的信息如下表:

测试点编号$n = $特殊约定
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
4 ∼ 6 4 \sim 6 46 2000 2000 2000 p n − 1 = n p_{n - 1} = n pn1=n
7 ∼ 10 7 \sim 10 710 2000 2000 2000

对全部的测试点,保证 1 ≤ p i ≤ n ≤ 2000 1 \leq p_i \leq n \leq 2000 1pin2000 p p p 是长度为 n n n 的排列。

#include <bits/stdc++.h>using namespace std;using LL = long long;#define endl "\n"int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> nums(n);for(auto& x : nums) cin >> x;do {int back = nums.back();nums.pop_back();nums.insert(nums.begin(), back);for(auto& x : nums) cout << x << " ";cout << endl;}while(nums.back() != n);return 0;
}

启发:使用do while语句可以完美契合题意;注意精简代码。

问题二【进制转换】:https://www.luogu.com.cn/problem/B3849

[GESP样题 三级] 进制转换

题目描述

小美刚刚学习了十六进制,她觉得很有趣,想到是不是还有更大的进制呢?在十六进制中,用 A 表示 10 10 10F 表示 15 15 15。如果扩展到用 Z 表示 35 35 35,岂不是可以表示 36 36 36 进制数了嘛!

所以,你需要帮助她写一个程序,完成十进制转 R R R 进制( 2 ≤ R ≤ 36 2\le R\le 36 2R36)的工作。

输入格式

输入两行,第一行包含一个正整数 N N N,第二行包含一个正整数 R R R,保证 1 ≤ N ≤ 1 0 6 1\le N\le 10^6 1N106

输出格式

输出一行,为 N N N R R R 进制表示。

样例 #1

样例输入 #1

123
25

样例输出 #1

4N
#include <bits/stdc++.h>using namespace std;using LL = long long;#define endl "\n"int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, R;cin >> n >> R;vector<int> digit;while(n) {digit.push_back(n % R);n /= R;}reverse(digit.begin(), digit.end());for(auto& x : digit) {if(x < 10) {cout << x;} else {cout << char(x - 10 + 'A');}}return 0;
}

启发:隐式转换;如何取出数字的每一位。

问题三【排排队,做游戏】:https://www.luogu.com.cn/problem/B3766

[语言月赛202305] 排排队,做游戏

题目描述

n n n 名小朋友站成了一排,他们会按照体育老师的指令进行排队做游戏。

体育老师会向他们依次下发 T T T 条指令,每条指令包含一个小于等于 n n n 的正整数 k k k

对某一条指令,小朋友们会按照如下步骤进行排队:

  1. 该指令下发前,排在从左到右数第 1 , k + 1 , 2 k + 1 , ⋯ 1, k + 1, 2k + 1, \cdots 1,k+1,2k+1, 位的小朋友,在指令下发后应该依次站在从左到右第 1 , 2 , ⋯ 1, 2, \cdots 1,2, 个位置。
  2. (如果 k ≥ 2 k \geq 2 k2)该指令下发前,排在从左到右数第 2 , k + 2 , 2 k + 2 , ⋯ 2, k + 2, 2k + 2, \cdots 2,k+2,2k+2, 位的小朋友,在指令下发后应该依次站在第一步中的小朋友(原来从左到右数第 1 , k + 1 , 2 k + 1 , ⋯ 1, k + 1, 2k + 1, \cdots 1,k+1,2k+1, 位的小朋友)右边的第 1 , 2 , ⋯ 1, 2, \cdots 1,2, 个位置。
  3. (如果 k ≥ 3 k \geq 3 k3 3 , k + 3 , 2 k + 3 , ⋯ 3, k + 3, 2k + 3, \cdots 3,k+3,2k+3, 的小朋友站在第二步的小朋友右边,(如果 k ≥ 4 k \geq 4 k4 4 , k + 4 , 2 k + 4 , ⋯ 4, k + 4, 2k + 4, \cdots 4,k+4,2k+4, 的小朋友站在 3 , k + 3 , 2 k + 3 , ⋯ 3, k + 3, 2k + 3, \cdots 3,k+3,2k+3, 的小朋友右边,以此类推,直至所有小朋友都被安排过(无论位置是否有变化)。

我们依次给出初始时从左到右每个小朋友的学号 a 1 , a 2 , ⋯ , a n a _ 1, a _ 2, \cdots, a _ n a1,a2,,an。现在我们想要知道,在 T T T 次指令下发后,从左到右每个小朋友的学号依次是什么。

输入格式

输入共三行。

第一行为两个整数 n , T n, T n,T,代表小朋友的数量和指令数。
第二行为 n n n 个整数 a 1 , a 2 , ⋯ , a n a _ 1, a _ 2, \cdots, a _ n a1,a2,,an,代表初始时从左到右每个小朋友的学号。
第三行为 T T T 个整数,代表体育老师下发的 T T T 条指令。

输出格式

输出共一行 n n n 个整数,代表在 T T T 次指令下发后,从左到右每个小朋友的学号。

样例 #1

样例输入 #1

8 4
72818 21895123 25718513 289523 52783 18520 295123 285952
1 2 3 5

样例输出 #1

72818 285952 295123 52783 18520 289523 25718513 21895123

样例 #2

样例输入 #2

4 1
28910 65363 274993 653516
2

样例输出 #2

28910 274993 65363 653516

提示

样例 1 解释

为了方便表述,我们先按照初始时的排队顺序将小朋友依次编号为 1 , 2 , ⋯ , 8 1, 2, \cdots, 8 1,2,,8。下表为初始时及每次指令后队列中每个位置上的小朋友的编号。

队列中的位置12345678
初始时 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8
第一个指令后 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8
第二个指令后 1 1 1 3 3 3 5 5 5 7 7 7 2 2 2 4 4 4 6 6 6 8 8 8
第三个指令后 1 1 1 7 7 7 6 6 6 3 3 3 2 2 2 8 8 8 5 5 5 4 4 4
第四个指令后 1 1 1 8 8 8 7 7 7 5 5 5 6 6 6 4 4 4 3 3 3 2 2 2

样例 2 解释

前三个小朋友的学号分别是三个出题人的洛谷 UID。
有人说学号是随机生成的,学号可不是随机生成的啊。

数据规模与约定

对于 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 1 0 4 1 \leq n \leq 10 ^ 4 1n104 1 ≤ T ≤ 1 0 4 1 \leq T \leq 10 ^ 4 1T104 1 ≤ k ≤ n 1 \leq k \leq n 1kn 1 ≤ a i ≤ 1 0 9 1 \leq a _ i \leq 10 ^ 9 1ai109

测试点编号 n n n T T T特殊限制
1 1 1 = 1 = 1 =1 ≤ 5 × 1 0 3 \leq 5 \times 10 ^ 3 5×103
2 ∼ 4 2 \sim 4 24 ≤ 10 \leq 10 10 ≤ 10 \leq 10 10
5 5 5 ≤ 5 × 1 0 3 \leq 5 \times 10 ^ 3 5×103 ≤ 5 × 1 0 3 \leq 5 \times 10 ^ 3 5×103 k = 1 k = 1 k=1
6 ∼ 8 6 \sim 8 68 ≤ 5 × 1 0 3 \leq 5 \times 10 ^ 3 5×103 ≤ 5 × 1 0 3 \leq 5 \times 10 ^ 3 5×103
9 ∼ 10 9 \sim 10 910 ≤ 1 0 4 \leq 10 ^ 4 104 ≤ 1 0 4 \leq 10 ^ 4 104
#include <bits/stdc++.h>using namespace std;using LL = long long;#define endl "\n"int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, T;cin >> n >> T;vector<int> nums(n);vector<int> newNums;for(auto& x : nums) {cin >> x;}while(T --) {int k;cin >> k;for(int i = 0; i < k; i ++) {for(int j = i; j < n; j += k) {newNums.push_back(nums[j]);}}nums = newNums;newNums.clear();}for(auto& x : nums) {cout << x << " ";}return 0;
}

启发:每次选人相当于分成k组。比如:当k = 2时,就会先选出索引为0 2 4 6 8…的人,再选出1 3 5 7 9…的人,先选出来的排在前面,后选出的排在后面。对题面的理解:每次选出的人都应该在第一个人的索引上加上k的倍数。

每次排出新的队伍,就保存在newNums中,再将新队伍newNums赋值给nums,最后将newNums清空。

要加深对数学型题面的理解。本题面加深了我的理解力。

问题四【你的牌太多了】:https://www.luogu.com.cn/problem/B3745

[语言月赛202304] 你的牌太多了

题目描述

笨蛋扶苏和坏蛋小 F 在打一种很新的牌。

初始时,扶苏和小 F 手中各有 n n n 张牌。每张牌有一个花色 f f f 和一个点数 p p p。在本题中,花色是不超过 m m m 的正整数,点数是不超过 r r r 的正整数。

打牌共会进行 n n n 轮,每轮扶苏会从手中选择一张牌打出。小 F 会从当前手牌中,选择与扶苏本轮打出的牌花色相同且点数大于扶苏打出的牌中点数最小的一张打出。如果这样的牌不存在,那么小 F 不会接牌(也就是不会出牌)。

注意,无论小 F 打出什么牌,本轮都立即结束,扶苏不会继续接牌,而是会开启下一轮出牌。

给出扶苏的出牌顺序,请你求出小 F 最终手里剩了几张牌。

输入格式

第一行是三个整数,表示一个人的手牌数 n n n,花色的上界 m m m 和点数的上界 r r r
第二行有 n n n 个整数,第 i i i 个整数表示扶苏第 i i i 张牌的花色 f 1 i f1_i f1i
第三行有 n n n 个整数,第 i i i 个整数表示扶苏第 i i i 张牌的点数 p 1 i p1_i p1i
第四行有 n n n 个整数,第 i i i 个整数表示小 F 第 i i i 张牌的花色 f 2 i f2_i f2i
第五行有 n n n 个整数,第 i i i 个整数表示小 F 第 i i i 张牌的点数 p 2 i p2_i p2i
第六行是一个长度为 n n n 的排列,描述扶苏的出牌情况。第 i i i 个整数 p i p_i pi 表示扶苏第 i i i 轮出了第 p i p_i pi 张牌。

输出格式

输出一行一个整数,表示坏蛋小 F 结束时手里剩余的牌数。

样例 #1

样例输入 #1

3 1 2
1 1 1
1 2 1
1 1 1
2 2 1
2 3 1

样例输出 #1

1

样例 #2

样例输入 #2

3 2 2
1 2 1
1 1 1
1 2 1
2 2 2
1 2 3

样例输出 #2

0

提示

样例 1 解释

小 F 花色为 1 1 1 且点数也为 1 1 1 的牌管不住任何牌。其余牌都被打出去了。

数据规模与约定

  • 对于 10 % 10\% 10% 的数据, r = 1 r = 1 r=1
  • 对于 20 % 20\% 20% 的数据, n = 1 n = 1 n=1
  • 对于 50 % 50\% 50% 的数据, m = 1 m = 1 m=1
  • 对于 100 % 100\% 100% 的数据, 1 ≤ n , m , r ≤ 100 1 \leq n,m,r \leq 100 1n,m,r100 1 ≤ f 1 i , f 2 i ≤ m 1 \leq f1_i, f2_i \leq m 1f1i,f2im 1 ≤ p 1 i , p 2 i ≤ r 1 \leq p1_i, p2_i \leq r 1p1i,p2ir 1 ≤ p i ≤ n 1 \leq p_i \leq n 1pin p p p 是长度为 n n n 的排列。
#include <bits/stdc++.h>using namespace std;using LL = long long;#define endl "\n"int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, r;cin >> n >> m >> r;vector<int> f1(n), p1(n), f2(n), p2(n);for(auto& x : f1) cin >> x;for(auto& x : p1) cin >> x;for(auto& x : f2) cin >> x;for(auto& x : p2) cin >> x;while(n --) {int order;cin >> order;order --;int idx = -1;for(int i = 0; i < f2.size(); i ++) {if(f2[i] == f1[order] && p2[i] > p1[order]) {if(idx == -1 || p2[i] < p2[idx]) {idx = i;}}}if(idx != -1) {f2.erase(f2.begin() + idx);p2.erase(p2.begin() + idx);}}cout << f2.size() << endl;return 0;
}
#include <bits/stdc++.h>using namespace std;using LL = long long;#define endl "\n"int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, r;cin >> n >> m >> r;vector<int> p1(n), f1(n), p2(n), f2(n);vector<int> output(n);for(int i = 0; i < n; i ++) {cin >> f1[i];}for(int i = 0; i < n; i ++) {cin >> p1[i];}for(int i = 0; i < n; i ++) {cin >> f2[i];}for(int i = 0; i < n; i ++) {cin >> p2[i];}for(int i = 0; i < n; i ++) {cin >> output[i];}int cnt = 0;for(int i = 0; i < n; i ++) {int outF = f1[output[i] - 1], outP = p1[output[i] - 1];vector<pair<int, int>> temp;for(int j = 0; j < n; j ++) {if(f2[j] == outF && f2[j] != -1 && p2[j] > outP) {temp.push_back({f2[j], p2[j]}); // F P}}int maxMin = 101;for(auto& x : temp) {if(x.second > outP && x.second < maxMin) {maxMin = x.second;}}if(maxMin != 101) {for(auto& x : temp) {if(x.second == maxMin) {for(int k = 0; k < n; k ++) {if(f2[k] == x.first && p2[k] == x.second) {f2[k] = p2[k] = -1;break;}}break;}}cnt ++;}temp.clear();}cout << n - cnt << endl;return 0;
}

启发:模拟题,题目不难,显然上面的代码精简。但我的方法很冗长复杂,究其原因还是没有熟练掌握vector的精髓之处。我与其对比,纵观我的代码,我总是想要存储数据,但这完全不必要。而且应用的函数也很少,总是用push_back()。这导致我的方法不够好。

题目五【Coin Selection G】:https://www.luogu.com.cn/problem/B3723

[语言月赛202303] Coin Selection G

题目描述

Farmer John 和 Bessie 正在一起玩硬币选择游戏。

初始时桌面上有 n n n 枚硬币,每枚硬币有一个面额,我们使用 a 1 , a 2 , ⋯ , a n a _ 1, a _ 2, \cdots, a _ n a1,a2,,an 分别代表第 1 , 2 , ⋯ , n 1, 2, \cdots, n 1,2,,n 枚硬币的面额。

他们还各有一个属于自己的钱包,初始时,钱包都是空的。

Farmer John 开始,双方轮流操作。每次操作中,当前的操作者会从桌面上剩余的硬币中选择面值不超过当前自己钱包中硬币的总面额的硬币中面额最大的一枚硬币,把它从桌子上拿走,放到自己的钱包里。如果桌面上剩余的所有硬币面值都超过了自己钱包里已有硬币的总面额,那么选择剩余的所有硬币中面额最小的一个。

当桌面上没有硬币时,游戏结束。

请你分别求出, 游戏结束后,Farmer John 和 Bessie 钱包里硬币的总面额。

输入格式

第一行为一个整数,代表初始时桌面上的硬币的数量 n n n
第二行为 n n n 个整数 a 1 , a 2 , ⋯ , a n a _ 1, a _ 2, \cdots, a _ n a1,a2,,an,分别代表第 1 , 2 , ⋯ , n 1, 2, \cdots, n 1,2,,n 枚硬币的面额。

输出格式

输出共一行两个整数,第一个整数表示 Farmer John 最终钱包里的总面额,第二个整数表示 Bessie 最终钱包里硬币的总面额,两个整数之间使用一个空格隔开。

样例 #1

样例输入 #1

2
3 2

样例输出 #1

2 3

样例 #2

样例输入 #2

5
1 2 3 4 5

样例输出 #2

9 6

提示

样例 1 解释

Farmer John 开始时「自己钱包中硬币的总面额」为 0 0 0,小于桌面上的任何一枚硬币,因此他只能选择剩下的所有硬币中面值最小的一个,为 2 2 2

接下来 Bessie「自己钱包中硬币的总面额」为 0 0 0,小于桌面上的任何一枚硬币,因此只能选择剩下的所有硬币中面值最小的一个,为 3 3 3

数据规模与约定

  • 20 % 20\% 20% 的数据,保证 n ≤ 2 n \leq 2 n2
  • 另有 20 % 20\% 20% 的数据,保证 a i = 1 a_i = 1 ai=1
  • 60 % 60\% 60% 的数据,保证 n ≤ 100 n \leq 100 n100
  • 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 1 0 3 1 \leq n \leq 10^3 1n103 1 ≤ a i ≤ 1 0 16 1 \leq a_i \leq 10^{16} 1ai1016

provider:一扶苏一

    #include <bits/stdc++.h>using namespace std;using LL = long long;#define endl "\n"int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<LL> nums(n);for(auto& x : nums) cin >> x;LL sum1 = 0, sum2 = 0;auto op = [&](LL& sum) -> void {int idx = -1;for(int i = 0; i < nums.size(); i ++) {if(nums[i] <= sum) {if(idx == -1 || nums[idx] < nums[i]) {idx = i;}}}if(idx == -1) {LL minn = *min_element(nums.begin(), nums.end());auto it = find(nums.begin(), nums.end(), minn);nums.erase(it);sum += minn;} else {sum += nums[idx];nums.erase(nums.begin() + idx); }};while(nums.size() != 0) {op(sum1);if(nums.size() == 0) break;op(sum2);}cout << sum1 << " " << sum2 << endl;return 0;}

启发:这段代码维护idx使用过多次,需要加深理解。

int idx = -1;
for(int i = 0; i < nums.size(); i ++) {if(nums[i] <= sum) {if(idx == -1 || nums[idx] < nums[i]) {idx = i;}}
}

题目六【惊蛰】:https://www.luogu.com.cn/problem/B3711

[语言月赛202302] 惊蛰

题目描述

给定一个正整数,规定一次操作为选定 l , r l,r l,r,删去所有从后往前数第 l ∼ r l\sim r lr 位的数字,并且将剩下的数字组成一个新的正整数。如 123456 123456 123456 删去从后往前数的第 2 ∼ 3 2\sim 3 23 位就会变成 1236 1236 1236

现在有 T T T 组询问,每次询问给定一个正整数 n n n,你需要回答:对于这个正整数,能否通过最多一次操作(不操作也算)将其变为 4 4 4 的倍数。

但是请注意,不能把所有的数位全都删完。

输入格式

输入共 T + 1 T+1 T+1 行。

输入的第一行,一个正整数 T T T

接下来 T T T 行,每行一个正整数 n n n。保证 n n n 不包含前导零。

输出格式

输出共 T T T 行。

对于 T T T 组数据,每组数据需要输出 1 1 1 行,表示问题的答案。若可以,输出 Yes,不可以,输出 No

样例 #1

样例输入 #1

3
234
1
286

样例输出 #1

Yes
No
Yes

样例 #2

样例输入 #2

1
2386

样例输出 #2

Yes

提示

样例 1 解释

对第一组数据:删去从后往前数第 2 ∼ 3 2\sim 3 23 位,剩下的数是 4 4 4,是 4 4 4 的倍数。

对第二组数据:可以证明没有任何一种方案能够达成目标。

对第三组数据:删去从后往前数第 1 1 1 位,剩下的数是 28 28 28,是 4 4 4 的倍数。

数据范围

对于前 10 % 10\% 10% 的数据,保证 1 ≤ n ≤ 9 1\le n\le 9 1n9
对于前 30 % 30\% 30% 的数据,保证 1 ≤ T ≤ 10 , 1 ≤ n ≤ 100 1\le T\le 10,1\le n\le 100 1T10,1n100
对于另外 10 % 10\% 10% 的数据,保证 T = 1 T=1 T=1
对于前 60 % 60\% 60% 的数据,保证 1 ≤ T ≤ 10 , 1 ≤ n ≤ 1 0 9 1\le T\le 10,1\le n\le 10^9 1T10,1n109
对于 100 % 100\% 100% 的数据, 1 ≤ T ≤ 1 0 2 , 1 ≤ n ≤ 1 0 18 1\le T\le 10^2,1\le n\le 10^{18} 1T102,1n1018

#include <bits/stdc++.h>using namespace std;using LL = long long;#define endl "\n"void solve() {LL n;cin >> n;vector<int> digits;if(n % 4 == 0) {cout << "Yes" << endl;return;}while(n) {digits.push_back(n % 10);n /= 10;}reverse(digits.begin(), digits.end());bool ok = false;for(int i = 0; i < digits.size() && !ok; i ++) {for(int j = i + 1; j <= digits.size() && !ok; j ++) {auto temp = digits;temp.erase(temp.begin() + i, temp.begin() + j);if(temp.size() == 0) {continue;}LL sum = 0;for(auto& x : temp) {sum = sum * 10 + x;}if(sum % 4 == 0) {ok = true;}}}if(ok) {cout << "Yes" << endl;} else {cout << "No" << endl;}return;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --) {solve();}return 0;
}

启发:对删除数位的枚举需要理解。且同时break掉两层循环只需bool found = false,并将found加入for循环的条件中。

题目七【超链接】:https://www.luogu.com.cn/problem/B3765

[语言月赛202305] 超链接

题目描述

在某局域网中,一共有 N N N 个网页,依次从 1 1 1 编号到 N N N

每个网页上都有一些超链接,第 i i i 个网页上一共有 T i T_i Ti 个超链接,依次指向 A i , 1 , ⋯ , A i , T i A_{i,1},\cdots,A_{i,T_i} Ai,1,,Ai,Ti 号网页。

某 E 现在从 1 1 1 号网页开始,点击不超过两次超链接,一共能到达多少网页?

输入格式

输入共 N + 1 N+1 N+1 行。

输入的第一行为一个整数 N N N

接下来第 i i i 行,第一个数为 T i T_i Ti。接下来 T i T_i Ti 个数,每个数代表一个超链接指向的网页。

输出格式

输出一行一个整数,代表你的答案。

样例 #1

样例输入 #1

6
2 2 3
3 3 4 1
2 4 5
1 6
1 6
1 5

样例输出 #1

5

提示

样例解释

  • 点击 0 0 0 次: 1 1 1 号页面;
  • 点击 1 1 1 次: 2 , 3 2,3 2,3 号页面;
  • 点击 2 2 2 次: 1 , 2 , 3 , 4 , 5 1, 2, 3, 4,5 1,2,3,4,5 号页面。

5 5 5 个页面。

数据规模与约定

  • 对于 30 % 30\% 30% 的测试数据, T i = 1 T_i = 1 Ti=1;
  • 对于 100 % 100\% 100% 的测试数据, 1 ≤ N ≤ 1000 1 \le N \le 1000 1N1000 0 ≤ T i ≤ 100 0 \le T_i \le 100 0Ti100 1 ≤ A i , j ≤ N 1 \le A_{i,j} \le N 1Ai,jN,同一个网页中不同超链接指向的网页编号不同,不保证不存在指向自己的超链接。
#include <bits/stdc++.h>using namespace std;using LL = long long;#define endl "\n"int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int n;cin >> n;vector<vector<int>> a(n);for(auto& x : a) {int m;cin >> m;x.resize(m);for(auto& y : x) {cin >> y;}}a.insert(a.begin(), vector<int>());vector<bool> st(n + 1, false);int cnt = 0;st[1] = true;cnt ++;for(int i = 0; i < a[1].size(); i ++) {int x = a[1][i];if(!st[x]) {st[x] = true;cnt ++;}for(int j = 0; j < a[x].size(); j ++) {int y = a[x][j];;if(!st[y]) {st[y] = true;cnt ++;}}}cout << cnt << endl;return 0;
}

启发:若需要输入的数据从索引为1处开始,可以输入完成之后在最前面insert。

题目八【洛谷评测机模拟器】:https://www.luogu.com.cn/problem/B3746

[语言月赛202304] 洛谷评测机模拟器

题目背景

现在假装你是洛谷评测机。这一天,洛谷同时进行了 PION 自测、SCP 自测、ION 自测等等比赛。成千上万的评测落到了你的身上!

题目描述

现在已经知道你有 n n n 个相同性能的评测节点,它们被分别标号为 1 , 2 , ⋯ , n 1, 2, \cdots, n 1,2,,n。一个评测节点在同一时间只能处理一个评测任务。

在某一时刻, m m m 个评测任务同时涌入了你。我们将这些任务分别标号为 1 , 2 , ⋯ , m 1, 2, \cdots, m 1,2,,m。这些评测任务需要的评测时间分别为 t 1 , t 2 , ⋯ , t m t _ 1 , t _ 2, \cdots, t _ m t1,t2,,tm。每个评测任务需要且仅需要一个评测节点来运行,因此你会按照如下方式按照 1 ∼ m 1 \sim m 1m 的顺序依次将这些评测任务分配到评测节点上:

对于某个耗时 t i t _ i ti 的评测任务,你需要找到目前累积评测时间最小的评测节点将任务放入。如果有多个评测节点累积评测时间相同且最小,则找一个标号最小的节点将任务放入。

「累积评测时间」定义:假设对于某个评测节点,其被分配了 a 1 , a 2 , ⋯ , a k a _ 1, a _ 2, \cdots, a _ k a1,a2,,ak k k k 个任务。那么这个评测节点的「累积评测时间」就是 t a 1 + t a 2 + ⋯ + t a k t _ {a _ 1} + t _ {a _ 2} + \cdots + t _ {a _ k} ta1+ta2++tak。显然的,如果某个评测节点从未被分配过这 m m m 个任务中的任何一个,那么这个评测节点的「累积评测时间」是 0 0 0

现在,你需要统计出,你的这 n n n 个评测节点分别接受了哪一些评测任务。

输入格式

输入共两行。

第一行为两个整数 n , m n, m n,m,代表评测节点数量和评测任务数量。
第二行为 m m m 个整数 t 1 , t 2 , ⋯ , t m t _ 1, t _ 2, \cdots, t _ m t1,t2,,tm,依次代表这 m m m 个评测任务的所需时间。

输出格式

输出共 n n n 行,每行若干个整数,两两之间以一个空格隔开。

对于第 i i i 行,输出第 i i i 个评测节点接受的评测任务编号从小到大排序后的结果。如果第 i i i 个评测节点没有被分配任务,那么输出一行一个 0 0 0

样例 #1

样例输入 #1

5 10
13 50 90 38 60 64 60 77 6 24

样例输出 #1

1 6
2 8
3
4 7
5 9 10

样例 #2

样例输入 #2

12 7
85 99 82 90 14 11 15

样例输出 #2

1
2
3
4
5
6
7
0
0
0
0
0

提示

数据规模与约定

对于 100 % 100\% 100% 的数据,保证 1 ≤ n , m ≤ 5 × 1 0 3 1 \leq n, m \leq 5 \times 10 ^ 3 1n,m5×103 0 ≤ t i ≤ 1 0 9 0 \leq t _ i \leq 10 ^ 9 0ti109

测试点编号 n ≤ n \leq n m ≤ m \leq m特殊性质
1 ∼ 2 1 \sim 2 12 10 10 10 10 10 10
3 ∼ 4 3 \sim 4 34 5 × 1 0 3 5 \times 10 ^ 3 5×103 5 × 1 0 3 5 \times 10 ^ 3 5×103 t i = 0 t _ i = 0 ti=0
5 ∼ 6 5 \sim 6 56 5 × 1 0 3 5 \times 10 ^ 3 5×103 5 × 1 0 3 5 \times 10 ^ 3 5×103 t i = 1 t _ i = 1 ti=1
7 ∼ 10 7 \sim 10 710 5 × 1 0 3 5 \times 10 ^ 3 5×103 5 × 1 0 3 5 \times 10 ^ 3 5×103

简短的代码:

#include <bits/stdc++.h>using namespace std;using LL = long long;#define endl "\n"int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int n, m;cin >> n >> m;vector<LL> sum(n);vector<vector<int>> assignment(n);int number = 1;while(m --) {int t;cin >> t;int idx = 0;for(int i = 1; i < sum.size(); i ++) {if(sum[i] < sum[idx]) idx = i;}sum[idx] += t;assignment[idx].push_back(number ++);} for(auto& x : assignment) {if(x.size() == 0) {cout << 0 << endl;}else {for(auto& y : x) {cout << y << " ";}cout << endl;}}return 0;
}

冗长的代码:

#include <bits/stdc++.h>using namespace std;using LL = long long;#define endl "\n"int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int n, m;cin >> n >> m;vector<LL> t(m);for(auto& x : t) cin >> x;t.insert(t.begin(), -1);vector<LL> node(n, 0);vector<vector<int>> assignment(n);for(int i = 1; i <= m; i ++) {LL time = t[i];vector<int> mini;LL mint = *min_element(node.begin(), node.end());for(int j = 0; j < node.size(); j ++) {if(node[j] == mint) mini.push_back(j);}int idx = *min_element(mini.begin(), mini.end());node[idx] += time;assignment[idx].push_back(i);}for(int i = 0; i < n; i ++) {int sz = assignment[i].size();if(sz != 0) {for(int j = 0; j < sz; j ++) {cout << assignment[i][j] << " ";}cout << endl;}else {cout << 0 << endl;}}return 0;
}

启发:我的方法较为繁琐。其实不用去存储t[m],而是去维护两个数组sum(n) assignment(n)就足够了。

其中对idx的维护需要加深理解。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/478211.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Flutter:SlideTransition位移动画,Interval动画延迟

配置vsync&#xff0c;需要实现一下with SingleTickerProviderStateMixinclass _MyHomePageState extends State<MyHomePage> with SingleTickerProviderStateMixin{// 定义 AnimationControllerlate AnimationController _controller;overridevoid initState() {super.…

svn 崩溃、 cleanup失败 怎么办

在使用svn的过程中&#xff0c;可能出现整个svn崩溃&#xff0c; 例如cleanup 失败的情况&#xff0c;类似于 这时可以下载本贴资源文件并解压。 或者直接访问网站 SQLite Download Page 进行下载 解压后得到 sqlite3.exe 放到发生问题的svn根目录的.svn路径下 右键呼出pow…

GPT系列文章

GPT系列文章 GPT1 GPT1是由OpenAI公司发表在2018年要早于我们之前介绍的所熟知的BERT系列文章。总结&#xff1a;GPT 是一种半监督学习&#xff0c;采用两阶段任务模型&#xff0c;通过使用无监督的 Pre-training 和有监督的 Fine-tuning 来实现强大的自然语言理解。在 Pre-t…

Linux线程(Linux和Windows的线程区别、Linux的线程函数、互斥、同步)

Linux线程&#xff08;Linux和Windows的线程区别、Linux的线程函数、互斥、同步&#xff09; 1. 线程介绍 线程的概念&#xff1a; 线程是 CPU 调度的基本单位。它被包含在进程之中&#xff0c;是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流&#xff0…

Large Spatial Model:End-to-end Unposed Images to Semantic 3D 论文解读

目录 一、概述 二、相关工作 1、SfM和可微神经表示 2、端到端的Image-to-3D 三、LSM 1、密集几何预测 2、2D信息特征提取 3、点特征融合 4、可微渲染 5、损失函数 四、实验 一、概述 该论文提出一种大型空间模型&#xff08;Larget Spatial Model,LSM&#xff09;…

Leetcode207. 课程表(HOT100)

链接 题解&#xff1a;先统计入度为0的点&#xff0c;如果一个节点入度为0&#xff0c;说明没有课程指向它&#xff0c;那么你就可以学习它了。反之说明还有先修课。 注意&#xff1a;图存在拓扑排序等价于图不存在环。其实可以想出&#xff1a;如果是一个环&#xff0c;那么…

JavaScript将至

JS是什么&#xff1f; 是一种运行在客户端&#xff08;浏览器&#xff09;的编程语言&#xff0c;实现人机交互效果 作用捏&#xff1f; 网页特效 (监听用户的一些行为让网页作出对应的反馈) 表单验证 (针对表单数据的合法性进行判断) 数据交互 (获取后台的数据, 渲染到前…

Centos-stream 9,10 add repo

Centos-stream repo前言 Centos-stream 9,10更换在线阿里云创建一键更换repo 自动化脚本 华为centos-stream 源 , 阿里云centos-stream 源 华为epel 源 , 阿里云epel 源vim /centos9_10_repo.sh #!/bin/bash # -*- coding: utf-8 -*- # Author: make.h

网络安全概论

一、 网络安全是一个综合性的技术。在Internet这样的环境中&#xff0c;其本身的目的就是为了提供一种开放式的交互环境&#xff0c;但是为了保护一些秘密信息&#xff0c;网络安全成为了在开放网络环境中必要的技术之一。网络安全技术是随着网络技术的进步逐步发展的。 网络安…

【Android】android compat理解

1&#xff0c;前提 即便是在同一手机上安装的不同apk&#xff0c;其编译的apk不同&#xff0c;也会导致行为上的差异。如SDK34有限制后台启动&#xff0c;但如果安装的apk所依赖的sdk是33&#xff0c;则不会表现出此差异。这是如何实现的呢&#xff1f;其实&#xff0c;本质是…

《数据结构》学习系列——图(中)

系列文章目录 目录 图的遍历深度优先遍历递归算法堆栈算法 广度优先搜索 拓扑排序定义定理算法思想伪代码 关键路径基本概念关键活动有关量数学公式伪代码时间复杂性 图的遍历 从给定连通图的某一顶点出发&#xff0c;沿着一些边访问遍图中所有的顶点&#xff0c;且使每个顶点…

【C++】static修饰的“静态成员函数“--静态成员在哪定义?静态成员函数的作用?

声明为static的类成员称为类的静态成员&#xff0c;用static修饰的成员变量&#xff0c;称之为静态成员变量&#xff1b;用 static修饰的成员函数&#xff0c;称之为静态成员函数。静态成员变量一定要在类外进行初始化 一、静态成员变量 1)特性 所有静态成员为所有类对象所共…

MySQL面试-1

InnoDB中ACID的实现 先说一下原子性是怎么实现的。 事务要么失败&#xff0c;要么成功&#xff0c;不能做一半。聪明的InnoDB&#xff0c;在干活儿之前&#xff0c;先将要做的事情记录到一个叫undo log的日志文件中&#xff0c;如果失败了或者主动rollback&#xff0c;就可以通…

JavaScript中的this指向绑定规则(超全)

JavaScript中的this指向绑定规则&#xff08;超全&#xff09; 1.1 为什么需要this? 为什么需要this? 在常见的编程语言中&#xff0c;几乎都有this这个关键字&#xff08;Objective-C中使用的是self),但是在JavaScript中的this和常见的面向对象语言中的this不太一样 常见面…

Linux---ps命令

​​​​​​Linux ps 命令 | 菜鸟教程 (runoob.com) process status 用于显示进程的状态 USER: 用户名&#xff0c;运行此进程的用户名。PID: 进程ID&#xff08;Process ID&#xff09;&#xff0c;每个进程的唯一标识号%CPU: 进程当前使用的CPU百分比%MEM: 进程当前使用的…

【Spiffo】环境配置:VScode+Windows开发环境

摘要&#xff1a; 在Linux下直接开发有时候不习惯快捷键和操作逻辑&#xff0c;用Windows的话其插件和工具都更齐全、方便&#xff0c;所以配置一个Windows的开发环境能一定程度提升效率。 思路&#xff1a; 自己本地网络内远程连接自己的虚拟机&#xff08;假定用的是虚拟机…

[ubuntu]编译共享内存读取出现read.c:(.text+0x1a): undefined reference to `shm_open‘问题解决方案

问题log /tmp/ccByifPx.o: In function main: read.c:(.text0x1a): undefined reference to shm_open read.c:(.text0xd9): undefined reference to shm_unlink collect2: error: ld returned 1 exit status 程序代码 #include <stdio.h> #include <stdlib.h> #…

Java基于Spring Boot框架的房屋租赁系统,附源码

博主介绍&#xff1a;✌Java老徐、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&…

librdns一个开源DNS解析库

原文地址&#xff1a;librdns一个开源DNS解析库 – 无敌牛 欢迎参观我的个人博客&#xff1a;无敌牛 – 技术/著作/典籍/分享等 介绍 librdns是一个开源的异步多功能插件式的解析器&#xff0c;用于DNS解析。 源代码地址&#xff1a;GitHub - vstakhov/librdns: Asynchrono…

CTFHUB--yeeclass-web

复现平台CTFHUB靶机为一个完整类论坛网页&#xff0c;题目给了服务端完整代码 代码审计 /src/submit.php Line56-63: 可以看到提交数据存入的时候将$_SESSION["username"]."_"作为前缀&#xff0c;生成了一个uniqid。uniqid的生成方式即{sec:08x}{usec:0…