2020暑假牛客多校训练营第二场

F.Fake Maxpooling

题目描述
给定一个$n*m$的矩阵，矩阵的每个值为$a[i][j] = lcm(i,j)$，求该矩阵中所有 k∗k 子矩阵的最大值之和。
思路
k为固定长度，求滑动区间的最大值或最小值就是滑动窗口，用单调队列维护就行。这题先维护一遍$n$行的最值，把最值记录下来,再跑一遍$m$列刚才所记录的最值，同时输出最大值。
比赛的时候发现单调队列的队列用deque时被卡常了，改成手写队列就可以过。刚才开了O2优化交了一发deque写的单调队列，发现可以过emmm
代码
这里的代码贴的单调队列是O2优化+deque的

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 5010;
int a[N][N];
int b[N][N];
int n, m, k;
LL res;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

void get_max(int row) {
	deque<int> q;
	for(int i = 1; i <= m; i++) {
		while(!q.empty() && q.front() <= i - k) q.pop_front();
		while(!q.empty() && a[row][q.back()] <= a[row][i]) q.pop_back();
		q.push_back(i);
		if(i >= k) b[row][i] = a[row][q.front()];
	}
}

void get_col_max(int j) {
	deque<int> q;
	for(int i = 1; i <= n; i++) {
		while(!q.empty() && q.front() <= i - k) q.pop_front();
		while(!q.empty() && b[q.back()][j] <= b[i][j]) q.pop_back();
		q.push_back(i);
		if(i >= k) res += (LL)b[q.front()][j];
	}
}

void solve() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			a[i][j] = lcm(i, j);
		}
	}
	for(int i = 1; i <= n; i++) {
		get_max(i);
	}
	for(int i = k; i <= m; i++) {
		get_col_max(i);
	}
	printf("%lld\n", res);
}

int main() {
//	freopen("in.txt", "r", stdin);
	solve();
	return 0;
}

C .Cover the Tree

题目描述
给定一棵无根树，需要用最少的链覆盖整棵树，链可重叠，输出数量与方案。
思路
比赛的时候队友想到了dfs序的做法并ac了，但是无法给出严格证明。看了官方题解理解了证明。
整体想法就是需要连成覆盖尽可能多的链，这条链一定要穿过根节点。
做法：方案数很显然，设叶子数为s，答案就是$\frac{s+1}{2}$ 。方案就是找到一个非叶子结点当成根，然后跑一遍dfs对叶子结点建立dfs序，每次输出的点为$node_i$和$node_{i+s/2}$。
证明(对官方题解的理解):
如果对于一个有叶子结点的结点point，其叶子结点的结点序为$(L,R)$。
1、若$R\le\frac{s}{2}$, $L_r\rightarrow L_{r+\frac{s}{2}}$覆盖，就表示从这个结点下面所有的叶子结点出发，这条链一定经过根节点
2、若$L>\frac{s}{2}$,同理，这些叶子所出发的链一定经过根节点，所以一定覆盖。
3、如果$R\leq\frac{s}{2}$ 和 $L>\frac{s}{2}$ 的点都覆盖完了，中间还有一部分点分布在$\frac{s}{2}$左右两侧，这个时候一定就剩下中间的一部分区域了，就可以把这些叶子结点的父结点看成一个根节点来覆盖链。
如果s为奇数，那么多数来的一个点只要随便挑一个非自己的点就可以了。
代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 2e5 + 10;
vector<int> e[N];
int res[N], idx;

void dfs(int u, int fa) {
    if(e[u].size() == 1) res[++idx] = u;
    for(int i = 0; i < e[u].size(); i++) {
        int v = e[u][i];
        if(v == fa) continue;
        dfs(v, u);
    }
}

void solve() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) {
        if(e[i].size() > 1) {
            dfs(i, 0);
            break;
        }
    }
    if(n == 2) {
        puts("1 2");
        return;
    }
    printf("%d\n", (idx + 1) / 2);
    for(int i = 1; i <= (idx + 1) / 2; i++) {
        printf("%d %d\n", res[i], res[i + idx / 2]);
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    solve();
    return 0;
}

B.Boundary

题目描述
给定n个点，问最多有几个点在同一个圆上并且$(0, 0)$点一定在这个圆上。
思路
暴力。三个不共线的点可以确定一个圆，已知$(0,0)$点，那就只要枚举另外两个点就行。先假设一个点一定在圆上，那么对于其它所有点，只要判断有多少个圆心重合即可，最后输出最大值。每次用map记录一下圆心点，然后统计一下最大值即可。防止卡精度可以开long double。另外需要特判1，2两个条件即可。
如果精度卡的实在太高那就把分子分母记录下来就行。
这题比较可惜，因为水平不足自己被卡死在J题，队友没有简短的板子被卡在B题，队友的思路什么都是对的了，最后还剩下十几分钟的时候再来看这个题已经没什么状态了。应当在卡J题半小时左右的时候放弃J题来想B题，这类似的题目以前碰到过，牛客小白月赛21的A题就用到了这个计算几何的板子。
代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

typedef pair<long double, long double> PLDLD;
const int N = 2010;
struct point {
    double x, y;
}a[N];
map<PLDLD, int> cnt;
long double dx, dy, de;

bool cacl(int i, int j) {
    long double xa = 0, ya = 0, xb = a[i].x, yb = a[i].y, xc = a[j].x, yc = a[j].y;
	de = 2 * (xa - xb) * (yc - yb) - 2 * (ya - yb) * (xc - xb);
	if(de == 0) return false; // 三点共线
	dx = (yc - yb) * (xa * xa + ya * ya - xb * xb - yb * yb) - (ya - yb) * (xc * xc + yc * yc - xb * xb - yb * yb);
	dy = (xa - xb) * (xc * xc + yc * yc - xb * xb - yb * yb) - (xc - xb) * (xa * xa + ya * ya - xb * xb - yb * yb);
	dx /= de;
	dy /= de;
	return true;
}

void solve() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lf%lf", &a[i].x, &a[i].y);
    }
    if(n <= 2) {
        printf("%d\n", n);
        return;
    }
    int res = 0;
    long double x, y;
    for(int i = 1; i <= n; i++) {
        cnt.clear();
        for(int j = i + 1; j <= n; j++) {
            if(!cacl(i, j)) continue;
            cnt[{dx, dy}]++;
            res = max(res, cnt[{dx, dy}]);
        }
    }
    printf("%d\n", res + 1);
}

int main() {
//    freopen("in.txt", "r", stdin);
    solve();
    return 0;
}

J.Just Shuffle

题目描述
给定一个长度为 $n$ 的排列 $A$ , 一个质数 $k$，求一个排列变换P，使得在 $k$ 次对排列$\{1,2,...,n\}$ 变换以后形成$A$。
思路
学了hdu巨巨K0u1e的思路。
如果存在一个$P$满足题意，那么这个变换$P$一定存在一个或者多个环。
同时也可得排列$A$一定也存在环。只考虑一个环，设环内有$m$个数，那么对于这个环，就是求一个置换，使得在$k\mod m$ 次置换以后变成相对应的$A$。（如果想要求出环，先要预存一下每个数字的最终的位置。）
对于每一个置换，会把当前位置上的数换到下一个数上去。设置换数组为$t$, 一次置换就等价于将 $t_i$ 位置的数挪到了 $t_{i+1}$ 上。排列$A$中存在一个数$A_i=x$，数字$x$的初始位置一定是$t_j=x$，那么经过$k$次置换以后所表示的位置就到了$t_{(j+k)\mod m}=i$。找到这个相应的$i$后以$i$为起点把剩下的数一个个存入$t$中。如果中间存在异常直接返回。
最后把 $t$ 存入到结果当中去，其实就相当于一个从$t_i$到$t_{i+1}$的过程。
比赛中糊涂了，纠结于只寻找一个环，也没有和队友讨论自己的思路，在很晚的时候再和队友讨论被指出有多个环的时候差不多已经放弃了这题。还是水平太菜了。
代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, k;
int a[N], b[N], t[N], res[N];
bool vis[N];

bool check(int x) {
    int m = 0;
    // 确定环的长度
    while(!vis[x]) {
        vis[x] = 1;
        x = b[x];
        m++;
    }
    for(int i = 0; i < m; i++) t[i] = 0;
    int j = 0;
    while(vis[x]) {
        if(t[j]) return false;
        t[j] = x;
        vis[x] = 0;
        x = b[x];
        j = (j + k) % m;
    }
    for(int i = 0; i < m; i++) {
        res[t[(i + 1) % m]] = t[i];
    }
    return true;
}

void solve() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++) {
        b[a[i]] = i;
    }
    for(int i = 1; i <= n; i++) {
        if(!res[i] && !check(i)) {
            puts("-1");
            return;
        }
    }
    for(int i = 1; i <= n; i++) {
        printf("%d ", res[i]);
    }
}

int main() {
//    freopen("in.txt", "r", stdin);
    solve();
    return 0;
}

本文地址：https://blog.csdn.net/zx1020354953/article/details/107325292