赞
踩
小蓝现在有一个长度为100 100100 的数组,数组中的每个元素的值都在0 00 到9 99 的范围之内。数组中的元素从左至右如下所示:
5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
现在他想要从这个数组中寻找一些满足以下条件的子序列:
子序列的长度为8;
这个子序列可以按照下标顺序组成一个yyyymmdd 格式的日期,并且要求这个日期是2023 年中的某一天的日期,例如20230902,20231223。yyyy 表示年份,mm 表示月份,dd 表示天数,当月份或者天数的长度只有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同的2023 年的日期。
对于相同的日期你只需要统计一次即可。
思路:我们可以把2023年的全部日期全部列出来,然后一次从数据中遍历,看是否可以组成这个日期,如果能组成就是答案
答案:235
#include <bits/stdc++.h> using namespace std; #define int long long int md[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int a[100]; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ret = 0; for (int i = 0; i < 100; i++) cin >> a[i]; for (int i = 1; i <= 12; i++) { for (int j = 1; j <= md[i]; j++) { string data = "2023"; if (i < 10) data += '0'; data += to_string(i); if (j < 10) data += '0'; data += to_string(j); int cur = 0; for (int k = 0; k < 100 && cur < 8; k++) { if (a[k] == data[cur] - '0') cur++; } if (cur >= 8) ret++; } } cout << ret << endl; return 0; }
问题描述
解析
这里解析一下就是:H(S) = -(0的个数 * 0的占比 * log2(0的占比)) - (1的个数 * 1的占比 * log2(1的占))
答案:11027421
#include <bits/stdc++.h> using namespace std; #define int long long const double db = 1e-4; const int val = 23333333; const double sh = 11625907.5798; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); for (int i = 0; i < val / 2; i++) { int k = val - i; double sum = -1.0 * i * i / val * log2(1.0 * i / val) - 1.0 * k * k / val * log2(1.0 * k / val); if (abs(sh - sum) <= db) { cout << i << endl; break; } } return 0; }
问题描述
小蓝有一个神奇的炉子用于将普通金属O 冶炼成为一种特殊金属X。这个炉子有一个称作转换率的属性V,V 是一个正整数,这意味着消耗V个普通金属O恰好可以冶炼出一个特殊金属X,当普通金属O的数目不足V时,无法继续冶炼。
现在给出了N条冶炼记录,每条记录中包含两个整数A 和B,这表示本次投入了A 个普通金属O,最终冶炼出了B个特殊金属X。每条记录都是独立的,这意味着上一次没消耗完的普通金属O不会累加到下一次的冶炼当中。
根据这N条冶炼记录,请你推测出转换率V的最小值和最大值分别可能是多少,题目保证评测数据不存在无解的情况。
输入格式
第一行一个整数N,表示冶炼记录的数目。
接下来输入N行,每行两个整数A 、B,含义如题目所述。
输出格式
输出两个整数,分别表示V可能的最小值和最大值,中间用空格分开。
样例输入
3
75 3
53 2
59 2
样例输出
20 25
代码解析
#include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int Max = INF; int Min = 0; int n, a, b; cin >> n; while (n--) { cin >> a >> b; Max = min(Max, a / b); Min = max(Min, a / (b + 1) + 1); } cout << Min << ' ' << Max << endl; return 0; }
题目描述
N 架飞机准备降落到某个只有一条跑道的机场。其中第i ii 架飞机在Ti 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋Di个单位时间,即它最早可以于Ti时刻开始降落,最晚可以于T i + Di时刻开始降落。降落过程需要Li个单位时间。
一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。
请你判断N架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数T,代表测试数据的组数。
对于每组数据,第一行包含一个整数N。以下N 行,每行包含三个整数:Ti,Di 和Li
输出格式
对于每组数据,输出YES 或者NO,代表是否可以全部安全降落。
样例输入
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
样例输出
YES
NO
样例说明
对于第一组数据,可以安排第3架飞机于0时刻开始降落,20时刻完成降落。安排第2架飞机于20时刻开始降落,30时刻完成降落。安排第1架飞机于30时刻开始降落,40时刻完成降落。
对于第二组数据,无论如何安排,都会有飞机不能及时降落。
评测用例规模与约定
代码解析
#include <bits/stdc++.h> using namespace std; #define int long long int k, n; int T[11], D[11], L[11]; int flag; bool chick[11]; void dfs(int x, int tim)//第机架飞机降落,降落时的时间 { if (x == n) { flag = 1; return; } for (int i = 0; i < n; i++) { if (!chick[i] && tim <= T[i] + D[i]) { chick[i] = true; dfs(x + 1, max(tim, T[i]) + L[i]); chick[i] = false; } } } void slove() { flag = 0; cin >> n; for (int i = 0; i < n; i++) chick[i] = false; for (int i = 0; i < n; i++) cin >> T[i] >> D[i] >> L[i]; dfs(0, 0); if (flag) cout << "YES" << endl; else cout << "NO" << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> k; while (k--) slove(); return 0; }
样例输入
5
11 121 22 12 2023
样例输出
1
**解析:**既然是让我们找删除最少的数,是的它是一个接龙数列,也就是说我们只要找出最长的接龙数列即可。
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 10; int a[N]; int dp[9]; int get_t(int k) { while (k) { if (k / 10 == 0) return k; k /= 10; } return 0; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int num; for (int i = 0; i < n; i++) { cin >> num; int t = get_t(num); int w = num % 10; dp[w] = max(dp[t] + 1, dp[w]); } int ans = 0; for (int i = 0; i <= 9; i++) ans = max(ans, dp[i]); cout << n - ans << endl; return 0; }
输入格式
第一行一个整数T,表示有T组测试数据。
接下来输入T TT 组数据。对于每组数据,第一行包含两个用空格分隔的整数M、N表示地图大小;接下来输入M行,每行包含N个字符,字符只可能是‘ 0 ’ 或‘ 1 ’ 。
输出格式
对于每组数据,输出一行,包含一个整数表示答案
样例输入:
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
样例输出:
1
3
样例说明
对于第一组数据,包含两个岛屿,下面用不同的数字进行了区分:
01111
11001
10201
10001
11111
岛屿2在岛屿1的“环” 内部,所以岛屿2是岛屿1的子岛屿,答案为1。
对于第二组数据,包含三个岛屿,下面用不同的数字进行了区分:
111111
100001
020301
100001
111111
注意岛屿3并不是岛屿1或者岛屿2的子岛屿,因为岛屿1和岛屿2中均没有“环”。
解题思路:
这里的大概意思就是,如果一个环岛里面有其他岛屿的话,只算最外面的岛屿,前提是最外面的岛屿是一个环岛.所以我们的解题思路就是,我们要从外海开始寻找岛屿,(外海就是岛屿以外的海域).那那些地方海一定是外外海呢?是不是二维数组的最外面一圈的海域一定是外海啊.所以我们就可以用dfs一次遍历外海,如果遇到岛屿了在用一次dfs遍历岛屿,将所有的岛屿都标记.这样从外海开始dfs,找到岛屿后在一个dfs就可以将最外层的岛屿找到.因为如果这个岛屿是环岛的话,我们的找海的dfs就进不去环岛里面的海域,就自然不会遍历环岛里面的岛屿.而题目给出的只有(x, y)这坐岛屿的上下左右都有岛屿的话才是同一个岛屿,而遍历海则有八个方向遍历,这里要注意了.
代码实现
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 51; int T; int n, m; int ret = 0; int grap[N][N]; bool sea_grap[N][N]; bool land_grap[N][N]; int sx[8] = {0, 0, -1, 1, 1, 1, -1, -1}; int sy[8] = {-1, 1, 0, 0, -1, 1, -1, 1}; int lx[4] = {0, 0, -1, 1}; int ly[4] = {-1, 1, 0, 0}; bool chick(int x, int y) { return (x >= 0 && x < n && y >= 0 && y < m); } void land_dfs(int i, int j) { land_grap[i][j] = true; for (int k = 0; k < 4; k++) { int x = i + lx[k], y = j + ly[k]; if (chick(x, y) && grap[x][y] == 1 && !land_grap[x][y]) land_dfs(x, y); } } void sea_dfs(int i, int j) { sea_grap[i][j] = true; for (int k = 0; k < 8; k++) { int x = i + sx[k], y = j + sy[k]; if (chick(x, y) && grap[x][y] == 0 && !sea_grap[x][y]) sea_dfs(x, y); if (chick(x, y) && grap[x][y] == 1 && !land_grap[x][y]) { ret++; land_dfs(x, y); } } } void slove() { cin >> n >> m; ret = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) sea_grap[i][j] = land_grap[i][j] = false; for (int i = 0; i < n; i++) { string s; cin >> s; for (int j = 0; j < m; j++) grap[i][j] = s[j] - '0'; } for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if ((i == 0 || i == n - 1 || j == 0 || j == m - 1) && grap[i][j] == 0) sea_dfs(i, j); } cout << ret << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> T; while (T--) slove(); return 0; }
程序猿圈子里正在流行一种很新的简写方法:对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。例如internationalization简写成i18n,Kubernetes 简写成K8s, Lanqiao 简写成L5o 等。
在本题中,我们规定长度大于等于K KK 的字符串都可以采用这种简写方法(长度小于K KK 的字符串不配使用这种简写)。给定一个字符串S和两个字符c1和c2,请你计算S有多少个以c1开头c2
结尾的子串可以采用这种简写?
输入格式
第一行包含一个整数K。
第二行包含一个字符串S和两个字符c1和c2
输出格式
一个整数代表答案。
输入样例:
4
abababdb a b
输出样例:
6
样例说明
符合条件的子串如下所示,中括号内是该子串:
[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]
代码实现:
#include <bits/stdc++.h> using namespace std; #define int long long signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int k; char a, b; string s; cin >> k; cin >> s >> a >> b; int ans = 0, sum = 0; int left = 0, right = k - 1; while (right < s.size()) { if (s[left++] == a) ans++; if (s[right++] == b) sum += ans; } cout << sum; return 0; }
给定一个长度为N NN 的整数数列:A1,A2,…,AN你要重复以下操作K KK 次:
每次选择数列中最小的整数(如果最小值不止一个,选择最靠前的),将其删除。并把与它相邻的整数加上被删除的数值。
输出K KK次操作后的序列。
输入格式
第一行包含两个整数N和K。
第二行包含N个整数,A1,A2,…,AN
输出格式
输出N − K个整数,中间用一个空格隔开,代表K KK次操作后的序列。
样例输入:
5 3
1 4 2 8 7
样例输出:
17 7
样例说明
数列变化如下,中括号里的数是当次操作中被选择的数:
[1] 4 2 8 7
5 [2] 8 7
[7] 10 7
17 7
代码解析:
#include <bits/stdc++.h> using namespace std; #define int long long #define val first #define key second const int N = 5e5 + 10; typedef pair<int, int> ppi; int n, k; int a[N]; int l[N], r[N]; priority_queue<ppi> q; void slove() { ppi num; do { num = q.top(); num.val = -num.val; num.key = -num.key; q.pop(); } while (num.val != a[num.key]); int prev = l[num.key]; int next = r[num.key]; if (prev != -1) { a[prev] += a[num.key]; r[prev] = r[num.key]; q.push({ -a[prev], -prev }); } if (next != -1) { a[next] += a[num.key]; l[next] = l[num.key]; q.push({ -a[next], -next }); } a[num.key] = -1; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //创建链表 cin >> n >> k; for (int i = 0; i < n; i++) { cin >> a[i]; l[i] = i - 1; r[i] = i + 1; q.push({ -a[i], -i }); } l[0] = -1; r[n - 1] = -1; while (k--) slove(); for (int i = 0; i < n; i++) { if (a[i] != -1) cout << a[i] << " "; } return 0; }
样例输入:
6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1
样例输出:
10 7 13 14
**解题思路:**这是可以说是模板题,主要用到的就是图的遍历,LCA找公共祖先,以及树上前缀和
代码解析:
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 10; typedef pair<int, int> ppi; int n, k; vector<ppi> e[N]; int fa[N], son[N], sz[N], dep[N], top[N]; int sum[N]; int a[N]; void dfs1(int u, int father) { fa[u] = father, dep[u] = dep[father] + 1, sz[u] = 1; for (int i = 0; i < e[u].size(); i++) { int s = e[u][i].first; if (s == father) continue; dfs1(s, u); sz[u] += sz[s]; if (sz[son[u]] < sz[s]) son[u] = s; } } void dfs2(int u, int t) { top[u] = t; if (son[u] == 0) return; dfs2(son[u], t); for (int i = 0; i < e[u].size();i++) { int s = e[u][i].first; if (s == fa[u] || s == son[u]) continue; dfs2(s, s); } } int cla(int u, int v) { while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); u = fa[top[u]]; } return dep[u] < dep[v] ? u : v; } void cal_sum(int u) { for (int i = 0; i < e[u].size(); i++) { int s = e[u][i].first; if (s == fa[u]) continue; int w = e[u][i].second; sum[s] = sum[u] + w; cal_sum(s); } } void slove() { //创建无向图 int u, v, t; for (int i = 0; i < n - 1; i++) { cin >> u >> v >> t; e[u].push_back({v, t}); e[v].push_back({u, t}); } //为LCA做准备 dfs1(1, 0); dfs2(1, 1); //树上前缀和,每个节点到根节点的距离 cal_sum(1); //计算总路长 for (int i = 0; i < k; i++) cin >> a[i]; int ans = 0; for (int i = 0; i < k - 1; i++) { ans += sum[a[i]] + sum[a[i + 1]] - 2 * sum[cla(a[i], a[i + 1])]; } for (int i = 0; i < k; i++) { int tmp = ans; if (i == 0) tmp -= sum[a[i]] + sum[a[i + 1]] - 2 * sum[cla(a[i], a[i + 1])]; else if (i == k - 1) tmp -= sum[a[i]] + sum[a[i - 1]] - 2 * sum[cla(a[i], a[i - 1])]; else { tmp -= sum[a[i]] + sum[a[i + 1]] - 2 * sum[cla(a[i], a[i + 1])]; tmp -= sum[a[i]] + sum[a[i - 1]] - 2 * sum[cla(a[i], a[i - 1])]; tmp += sum[a[i - 1]] + sum[a[i + 1]] - 2 * sum[cla(a[i - 1], a[i + 1])]; } cout << tmp << " "; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; slove(); return 0; }
输出格式
一行一个整数,表示答案,如有多个答案,输出编号最大的一个。
输入样例:
6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5
输出样例:
4
**解题思路:**本题同样要使用到LCA找公共祖先的算法,以及树上差分
代码实现:
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 10; typedef pair<int, int> ppi; map<ppi, int> mp; vector<int> e[N]; int w[N]; int n, m; int fa[N], son[N], sz[N], top[N], dep[N]; void dfs1(int u, int father) { fa[u] = father, sz[u] = 1, dep[u] = dep[father] + 1; for (auto s : e[u]) { if (s == father) continue; dfs1(s, u); sz[u] += sz[s]; if (sz[son[u]] < sz[s]) son[u] = s; } } void dfs2(int u, int t) { top[u] = t; if (!son[u]) return; dfs2(son[u], t); for (auto s : e[u]) { if (s == fa[u] || s == son[u]) continue; dfs2(s, s); } } int cla(int u, int v) { while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); u = fa[top[u]]; } return dep[u] < dep[v] ? u : v; } void cal_sum(int u) { for (auto s : e[u]) { if (s == fa[u]) continue; cal_sum(s); w[u] += w[s]; } } void slove() { cin >> n >> m; int x, y; for (int i = 0; i < n - 1; i++) { cin >> x >> y; e[x].push_back(y); e[y].push_back(x); mp[{x, y}] = mp[{y, x}] = i + 1; } dfs1(1, 0); dfs2(1, 1); //树上差分 int a, b; for (int i = 0; i < m; i++) { cin >> a >> b; w[a]++; w[b]++; w[cla(a, b)] -= 2; } //再做一次树上前缀和 cal_sum(1); //遍历每个点 int ret = 0; for (int i = 1; i <= n; i++) { if (w[i] == m) { ret = max(ret, mp[{i, fa[i]}]); } } cout << ret; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); slove(); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。