D Duration
| D | Duration |
题目大意
给你两个 AA:BB:CC 格式的时间，请你计算它们直接的时间插值（秒）
解题思路
模拟
代码示例
#include<bits/stdc++.h>
using namespace std;
int h, m, s;
int main(){
scanf("%d:%d:%d", &h, &m, &s);
int cnt_1 = h * 3600 + m * 60 + s;
scanf("%d:%d:%d", &h, &m, &s);
int cnt_2 = h * 3600 + m * 60 + s;
cout << abs(cnt_1 - cnt_2) << '\n';
}F Fake Maxpooling
| F | Fake Maxpooling |
题目大意
构造一个矩阵，每个位置的值是 lcm(i，j)，请你计算每个 k * k 的子矩阵中最大值的总和
解题思路
目前看到了两种解法
解法一：
首先构造出来矩阵数组，为了维护子矩阵的最大值，我们可以利用两次单调队列维护矩阵最大值。一次维护所有行最大值，一次维护所有列最大值并更新此矩阵的最大值。
解法二：
打表找规律猜结论
发现最大值一般就在右下角的三个点 (k + i, k + j), (k + i - 1, k + j), (k + i, k + j - 1)
代码示例
解法一：
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, m, k;
int a[N][N];
int mat[N][N];
deque<int> dq;
int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b){
return a * b / gcd(a, b);
}
int main(){
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
mat[i][j] = lcm(i, j);
}
}
// 维护第 i 行的最大值
for(int i = 1; i <= n; i++){
dq.clear();
dq.push_back(0);
for(int j = 1; j <= m; j++){
if(j - dq.front() >= k) dq.pop_front();
while(!dq.empty() && mat[i][j] >= mat[i][dq.back()]) dq.pop_back();
dq.push_back(j);
a[i][j] = mat[i][dq.front()];
}
}
long long ans = 0;
// 维护第 i 列的最大值 同时更新答案
for(int j = k; j <= m; j++){
dq.clear();
dq.push_back(0);
for(int i = 1; i <= n; i++){
if(i - dq.front() >= k) dq.pop_front();
while(!dq.empty() && a[i][j] >= a[dq.back()][j]) dq.pop_back();
dq.push_back(i);
if(i >= k) ans += a[dq.front()][j];
}
}
cout << ans << '\n';
}解法二：
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, m, k;
int a[N][N];
int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
int main(){
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(k == 1) a[i][j] = i * j / gcd(i, j);
else a[i][j] = max(i * j / gcd(i, j), max(a[i - 1][j], a[i][j - 1]));
}
}
long long ans = 0;
for(int i = k; i <= n; i++){
for(int j = k; j <= m; j++){
ans += a[i][j];
}
}
cout << ans << '\n';
}C Cover the tree
| C | Cover the Tree |
题目大意
给定一棵无根树，选择最少链数（至少一个）覆盖树中所有边。打印最小数量和一个解决方案。如果有多个解决方案，请打印其中任何一个。
解题思路
将树建成一个无向图，然后对度不为1的某个点进行深搜遍历，记录度为1的叶子节点的序号，如果叶子节点为奇数，那么在数组最后加上一个根节点的序号。然后将数组第一个点与后半部分的第一个节点配对，依次下去
首先设叶子节点个数为 s，那么答案就是 s / 2 向下取整
取任意一个非叶子节点作为根，然后求一个dfs序，并把所有叶子节点按dfs序排序，记为 l1, l2...ls 先假设 s 为偶数，那么构造的 s / 2 可以为 i -> s / 2 + i，能保证每条链都会被覆盖到
证明：
不妨设某条边的儿子节点所覆盖的叶子节点区间为 [L, R]
- 如果 R <= s / 2，则这条边会被 l(R) -> l(s / 2 + R) 覆盖
- 否则如果 L > s / 2，则这条边会被 l(L - s / 2) -> l(L) 覆盖
- 否则因为根节点度数不为 1，所以 L ≠ 1，R ≠ s 中必有一个是满足的，如果 L ≠ 1 则这条边会被 l(1) -> l(s / 2 + 1) 覆盖。否则如果 R ≠ s 则这条边会被 l(s / 2) -> l(s) 覆盖
如果 s 是奇数，只需要给根节点再接一个叶子节点，按照上述方法构造完后再把新加的这条边删去即可，代码实现可以跳过这一步
所以我们只要求一个dfs序，然后根据根左子树的叶子节点和根右子树的叶子节点逐一配对，如果叶子节点是奇数时，随便找个节点与其匹配就可以了
参考资料
Cover the Tree
代码示例
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
int ans[N];
int tot;
int cnt;
int head[N];
int in[N];
struct edge{
int to;
int nxt;
}e[2 * N];
void add(int x, int y){
tot++;
e[tot].to = y;
e[tot].nxt = head[x];
head[x] = tot;
}
void dfs(int x, int f){
if(in[x] == 1) ans[++cnt] = x;
for(int i = head[x]; i; i = e[i].nxt){
int y = e[i].to;
if(y == f) continue;
dfs(y, x);
}
}
int main(){
cin >> n;
int x, y;
for(int i = 1; i < n; i++){
cin >> x >> y;
in[x]++;
in[y]++;
add(x, y);
add(y, x);
}
int root = 1;
while(in[root] == 1) root++;
dfs(root, -1);
cout << (cnt + 1) / 2 << '\n';
if(cnt & 1) ans[++cnt] = root;
for(int i = 1; i <= (cnt + 1) / 2; i++) cout << ans[i] << " " << ans[i + (cnt + 1) / 2] << '\n';
}B Boundary
| B | Boundary |
题目大意
给定二维平面上的 n 个点。考虑原点 (0,0) 在其边界上的所有圆，找出其边界上给定点最大的圆。打印最大点数。
解题思路
1 ≤ n ≤ 2000，所以可以暴力枚举两个点算出来圆心，然后用map统计个数，然后输出map最大值
代码示例
#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int ans;
int n;
map<pair<double, double>, int> mp;
struct point{
double x;
double y;
}p[N];
struct line{ // ax + by + c = 0
double a;
double b;
double c;
};
void solve(point o, point a, point b){
line OA = line{a.x, a.y, -(a.x * a.x + a.y * a.y) / 2.0}; // OA 中垂线
line OB = line{b.x, b.y, -(b.x * b.x + b.y * b.y) / 2.0}; // OB 中垂线
double x = (OA.b * OB.c - OA.c * OB.b) / (OA.a * OB.b - OA.b * OB.a);
double y = (OA.a * OB.c - OA.c * OB.a) / (OA.a * OB.b - OA.b * OB.a);
ans = max(ans, ++mp[make_pair(x, y)]);
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y;
for(int i = 1; i < n; i++){
mp.clear();
for(int j = i + 1; j <= n; j++){
if(p[i].x * p[j].y == p[i].y * p[j].x) continue;
solve(point{0,0}, p[i], p[j]);
}
}
cout << ans + 1 << '\n';
}G Greater and Greater
| G | Greater and Greater |
题目大意
给一个长度为 n 的数组 a，和长度为 m 的字符串 b，求 a 有多少个长度与 b 串相等的子串，使每个位置大于 b 串的对应位置。
解题思路
代码示例
A All with Pairs
| A | All with Pairs |
题目大意
解题思路
代码示例
J Just Shuffle
| J | Just Shuffle |
题目大意
前缀知识
首先我们要了解一个重要概念 - 置换
非空有限集A到A本身的一个可逆映射称为A的一个置换。
假设我们有一个含有 n 个元素的集合可以写为
{a1, a2, ..., an}
则其置换表达式为
注意这里 P(x) 是一个到自己的可逆映射，所以 P(ai) 其实就是 ai 的一种排列顺序
这里我们再扩展一点
置换比较重要的性质
如果 P(1), P(2), ..., P(n) 中存在两个数，较大的数排在较小的数之前，那么这两个数就构成了一个反序。反序的个数称为反序数。如果反序数是奇数，这个置换就是一个奇置换，如果反序数是偶数，这个置换就是一个偶置换。
参考资料
抽象代数学习笔记（4）置换
题目
给你一个大小为 n 的数组 B, 是数组 A 的 k 次置换后的结果，请你求出原数组。k 保证是质数
解题思路
通过题目我们可以推出 ，等式两边同时乘 t 次幂，变成
，此时如果 t 为 k 的逆元时，上述式子就变成了
，所以求出每个环的大小并且每个让K取逆（欧几里得算法），分别求出逆的大小后环里一循环就可以了。
参考资料
环+逆——牛客多校赛第二场J题
代码示例
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n, k;
int num;
int a[N];
int vis[N];
int change[N];
void exgcd(int a, int b, int &x, int &y){ // 扩展欧几里得算法
if(!b){
x = 1;
y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
signed main(){
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
if(!vis[i]){
vis[i] = 1;
int tmp = a[i];
num = 0;
change[num++] = i;
while(tmp != i){
vis[tmp] = 1;
change[num++] = tmp;
tmp = a[tmp];
}
int x, y, t;
exgcd(k % num, num, x, y);
x = (x + num) % num;
for(int i = 0; i < num; i++) a[change[i]] = change[(i + x) % num];
}
}
for(int i = 1; i <= n; i++) cout << a[i] << " ";
}
