题意 :已知用长度相同 的两个由 0 和 1 组成的 a 序列和 b 序列生成 d 序列的方法是先每个位置上的数相加,然后合并相同连续的子串用其一个数表示,例如
0110 和 1101 生成 1211,合并后得到 d 序列 121
011000 和 011000 生成 022000,合并后得到 d 序列 020
也就是说 d 只会由 0、1和 2 组成,可能存在前导零,现在给出 a 序列,请你帮忙给出对应的 b 序列来使 d 序列表示的整数数值最大
思路 :为了 d 最大肯定尽量先保证 d 序列的长度最长其次位置上的数越大越好,首先第一个位置没有限制是放 1,后面的位置我们就每次尝试在位置上放 1,如果和前面的数不相同就可以放,相同为了保证长度只能放 0
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const int maxn = 1e5 + 100 ;int d[maxn];int ans[maxn];int cal (char ch) { return ch - '0' ; } void solve () { int n; cin >> n; string b; cin >> b; ans[0 ] = 1 ; d[0 ] = cal(b[0 ]) + ans[0 ]; for (int i = 1 ; i < n; ++i) { if (1 + cal(b[i]) == d[i - 1 ]) ans[i] = 0 ; else ans[i] = 1 ; d[i] = ans[i] + cal(b[i]); } for (int i = 0 ; i < n; ++i) cout << ans[i]; cout << endl ; } signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int t; cin >> t; while (t--) { solve(); } return 0 ; }
题意 :给出一个数 d,请找到最小的整数 a 满足以下条件:
a 的除数个数至少为 4
对于 a 的任意两个除数 ,他们之间的差不小于 d
1 2 d=1 a=6 [1 ,2 ,3 ,6 ] d=2 a=15 [1 ,3 ,5 ,15 ]
思路 :注意第二个条件,为什么 d=2 a=12 [1,3,6,12]
不行是因为 12 还有除数 2 不满足条件二对于任意两个除数,对于 a 而言肯定有除数 1 和本身,也就是说我们只需再找两个除数并且避免上述的情况,所以就是找两个满足条件的最小的质数这样 a 就是最小的同时也不会有其他更小的除数了
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;bool check (int x) { int t = sqrt (x); if (x == 2 ) return 1 ; for (int i = 2 ; i <= t + 1 ; ++i) { if (x % i == 0 ) return 0 ; } return 1 ; } signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int t; cin >> t; while (t--) { int d; cin >> d; int a, b; for (int i = 1 + d;; ++i) { if (check(i)) { a = i; break ; } } for (int i = a + d;; ++i) { if (check(i)) { b = i; break ; } } cout << a * b << endl ; } return 0 ; }
题意 :有一个数列有 2*n 个数(可能存在相同的数),请判断能够完成下述操作:
开始的时候你随便指定一个整数 x
然后进行 n 次如下操作:
选择数列中加和等于 x 的两个数
从数列中删除这两个数并用更新 x 为这两个数中的较大值
问能否通过这个操作成功删除数列,能请输出 YES、开始选的 x 值和 n 次删除操作中每次选的两个数,不能输出 NO
思路 :每次删除操作 x 都会变小也就是说这是个整体递减操作,我们肯定是每次选择删除数列中最大值,否则的就再也删不掉它了。那么初始选的值 x 应该是数列中最大的数和另一个数,所以我们从数组中枚举另一个数确定 x 模拟 n 次删除操作对当前 x 进行判断:
每次选择删除数组中最大值,查看另一个数 x-最大值
是否也在数组中,存在说明可以继续进行操作更新最大值并将这两个数从数组中删除
如果删除不了数组中最大值则不能成功进行 n 次操作删除整个数组,退出判断尝试下一个枚举的数
因为枚举另一个数和对 x 的判断复杂度为 O(n2 ),所以判断过程中每次删除操作获取数组最大值和查找 x-最大值
复杂度需要低于 O(n),使用 multiset 既可以存储相同的数复杂度也降到 O(logn) 一举两得解决问题
比赛时竟然菜到没有想到树的结构来存储查找,还在手写三重循环从数组中暴力查找,写了 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 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 58 59 60 61 62 63 64 65 66 67 68 69 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const int maxn = 2e3 + 100 ;int a[maxn];int n, sum;vector <int > ans;bool cmp (int x, int y) { return x > y; } bool check (int maxx) { ans.clear(); multiset <int > seta; for (int i = 0 ; i < sum; ++i) seta.insert(a[i]); for (int i = 0 ; i < n; ++i) { auto it1 = seta.end(); --it1; int sheng = maxx - *it1; seta.erase(it1); auto it2 = seta.find(sheng); if (it2 == seta.end()) { return 0 ; } else { seta.erase(it2); ans.push_back(maxx-sheng), ans.push_back(sheng); maxx = max(maxx-sheng, sheng); } } return 1 ; } void solve () { cin >> n; sum = 2 * n; for (int i = 0 ; i < sum; ++i) cin >> a[i]; sort(a, a + sum, cmp); for (int i = 1 ; i < sum; ++i) { int tot = a[0 ] + a[i]; if (check(tot)) { cout << "YES" << endl ; cout << tot << endl ; for (int i = 0 ; i < sum; i += 2 ) cout << ans[i] << ' ' << ans[i + 1 ] << endl ; return ; } } cout << "NO" << endl ; } signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int t; cin >> t; while (t--) { solve(); } return 0 ; }