芜湖，起飞~

许愿OC

三面结束，许愿通过

Solution 尝试把转换一下：先对两边开次方根，得到；再对两边开次方根，得到；显然，若、，那么有。所以这题就是个变形的"上升子序列个数"，直接dp即可。 n, mod = int(input()), int(1000000007) a = list(map(int, input().split())) dp = [ 1 for i in range(n) ] for i in range(1, n): for j in range(i): # 这里也可以用取log的做法来比较，就不会涉及大数运算了。 if (a[j] ** (i + 1)) <...

Solution 二分答案，考虑如何判定是否符合要求： 若一个区间里有个以上的数大于等于，那么这个区间的第大数大于等于； 若有个以上的区间的第大数大于等于，那么答案； 否则，答案。 双指针扫一遍数组，统计一下第大数大于等于的区间个数即可。复杂度。 Code: #include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e5 + 5; int n, k, a[N]; ll m; // long long bool check(int v) { ll total =...

A - 聚会 容易想到，两个传送门放在不同半轴肯定不如放在同一半轴好，所以其中一个门肯定是放在处的；设为正半轴上的朋友们的坐标，为负半轴上的朋友们的坐标；设为另一个门放在正半轴时，正半轴的朋友全都走到处需要的时间；设为另一个门放在负半轴时，负半轴的朋友全都走到处需要的时间；那么答案即为 怎么求和？ 考虑二分答案，以正半轴为例，假设为正半轴上距离处最远的朋友的坐标(即)： 首先二分得到一个， 若对任意，均满足和中的至少一个，则， 否则。 负半轴的做法类似。 Code: here B - 密码系统 先将复制一遍连在后面得到()，然后用后缀数组求得的sa，基于sa求出后缀的rank。 把~...

Solution 设为长度取时，能得到的木棍数。因为长度为的木棍最多能分成根长度为的木棍，所以。显然这个函数是单调下降的，所以可以二分找到最大的满足的。 Code #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { cin.sync_with_stdio(false), cin.tie(nullptr); int n, k; cin >> n >> k; vector<int> a(n); for (int i ...

Solution 当<>时，其他个位置的取值方案都有种，所以<>会出现在个长度为的01串中；同理可得<>、<>、...、<>都出现在个长度为的01串中。所以答案即为。 Code n, mod = int(input()), int(1e9 + 7) print(0 if n < 2 else (pow(2, n - 2, mod) * (n * (n - 1) // 2 % mod) % mod))

A - 相反数 Solution 签到题，直接std::stoi即可。 Code #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { cin.sync_with_stdio(false), cin.tie(nullptr); string s; cin >> s; string t(s.rbegin(), s.rend()); cout << stoi(s) + stoi(t) << "\n"; } B - M...

Solution 简单的树形dp。 设为点的子树中，以为端点且长度模为的路径数量。 考虑如何合并点的孩子的结果，因为从的子树内走到的路程比到的路程长个单位， 所以有： 其中、为合并后的结果； 原先已有条以为端点长度为偶数的路径，与条以为端点长度为奇数的路径合并可以得到条长度为偶数的路径； 同理，原先已有条以为端点长度为奇数的路径，与条以为端点长度为偶数的路径合并可以得到条长度为偶数的路径。 做一遍dfs即可求得结果，总复杂度。 Code #include <bits/stdc++.h> using namespace std; using ll = long long; vec...

Solution (用表示异或运算) 因为当且仅当时才有，所以题目要求的就是有多少对区间的异或和相等且不重叠。 设为右端点小于且异或和为的区间的个数，此时，若区间的异或和为，那么它对答案的贡献为。 枚举，首先对所有左端点为的区间计算贡献，然后利用右端点为的区间来更新。 总复杂度。 Code #include <bits/stdc++.h> using namespace std; using ll = long long; int a[1005], sum[1 << 17]; vector<int> add[1005], query[1005]; in...

Solution 普通的树形dp。 首先设为从点向的子树推流，所能达到的最大流量； 那么有： 其中为的孩子，为和之间的边的流量上限。 设为从向整棵树推流，所能达到的最大流量，那么有： 作两遍dfs，分别求出和的值，取输出即可，复杂度。 Code #include <bits/stdc++.h> using namespace std; using ll = long long; struct edge { int v, cap; }; vector<edge> G[200005]; ll dp[200005]; ll f(int v, int cap) {...