【题解】2020牛客寒假算法基础集训营第六场
写在题解前：
这次比赛的10道题，std的代码量都非常小，但是需要一点点思维来做保障。
相信能活跃大家的思路，以及优化大家的切题体验。（认真.jpg）
以及即使场上不会做，补完这套题还是会给大家收获的~
槽点举例：
Q：J我怎么随便写就过了？
A：这题真的怎么写都是对的，即使你没想清楚所有细节。（滑稽）
Q：怎么B题就是个Tarjan模板题？
A：我不是我没有，强行用Tarjan明显要比std难很多嘛。
A 配对
我们要使得第K大的和尽可能大，显然可以贪心：
首先，组成这K对数字的显然是A中最大的K个数字和B中最大的K个数字。
问题转化为怎样配对使得最小的和最大：
我们发现，如果A1<A2,B1<B2，那么一定是由A1和B2配对较优。
经过简单的归纳可以得到，倒序配对是最优的，这样就解决了问题。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100050;
int a[N], b[N], n, k, ans = 2e8;
int main()
{
int i, j;
scanf("%d%d", &n, &k);
for(i = 1; i <= n; i ++)
scanf("%d", &a[i]);
for(i = 1; i <= n; i ++)
scanf("%d", &b[i]);
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for(i = n; i > n - k; i --)
ans = min(ans, a[i] + b[n - k + n + 1 - i]);
printf("%d\n", ans);
return 0;
} B 图
这是一个简单的有关基环树的问题。
可以证明，每个点出度都为1的有向图是一个基环内向树森林。
关于这一部分的内容，可以自行查阅资料。
这里我们要用到的结论是：从一个点出发，沿着出边一路走下去，一定会走到一个环。
所以我们选择dfs，当遍历到一个已在dfs栈中的节点时，就说明找到了环，可以结束统计。
但这样是会超时的，于是我们选择带“记忆化”的dfs，从一个点开始沿着出边走下去，每当走到一个在之前某次dfs中经过的点时，就可以利用上一次的答案完成求解。
实现上有一些细节，要注意不要让复杂度退化。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1000050;
int to[N], siz[N], n, vis[N], ins[N], sta[N];
int dfs(int x){
if(siz[x]) return siz[x];
return siz[x] = 1 + dfs(to[x]);
}
int main()
{
int i, j, k, h;
scanf("%d", &n);
for(i = 1; i <= n; i ++)
scanf("%d", &to[i]);
for(i = 1; i <= n; i ++){
if(vis[i] == 0){
j = i;
while(vis[j] == 0){
sta[++ sta[0]] = j;
vis[j] = ins[j] = 1;
j = to[j];
}
if(ins[j]){
k = j, h = 0;
do{
k = to[k];
h ++;
}while(k != j);
do{
k = to[k];
siz[k] = h;
}while(k != j);
}
while(sta[0]){
ins[sta[sta[0]]] = 0;
sta[0] --;
}
}
}
for(i = 1, h = 0; i <= n; i ++)
h = max(h, dfs(i));
printf("%d", h);
return 0;
} C 汉诺塔
将木板按照Xi从小到大排序，将这时的Yi数列记为Zi数列，则问题变成将Zi划分为尽可能少的若干组上升子序列。
根据Dilworth定理，最小组数等于Zi的最长下降子序列长度。
要求最长下降子序列的长度，我们有一种经典的二分优化dp的方法，在这里不再详述。 借助这种做法我们能给出一种构造方法，在求出最小组数的同时得出方案。
将状态数组的每个位置变为栈，用入栈操作代替修改元素操作，即可在求出组数的同时，用这些栈来完成对数列的划分。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100050;
struct node{
int x, y, loc;
inline bool operator < (const node &b)const{
return x < b.x;
}
}a[N];
int n, m, ot[N], S[N];
int main()
{
int i, j, k;
scanf("%d", &n);
for(i = 1; i <= n; i ++){
scanf("%d%d", &a[i].x, &a[i].y);
a[i].loc = i;
}
sort(a + 1, a + n + 1);
for(i = 1; i <= n; i ++){
int lb = 1, rb = m;
while(lb <= rb){
int md = lb + rb >> 1;
if(S[md] < a[i].y)
rb = md - 1;
else
lb = md + 1;
}
S[lb] = a[i].y;
if(lb > m) m = lb;
ot[a[i].loc] = lb;
}
printf("%d\n", m);
for(i = 1; i <= n; i ++)
printf("%d ", ot[i]);
return 0;
} D 重排列
容易知道按升序将A和B排序不影响结果。
按标号从小到大考虑A的每个位置填什么数。
例：A（1,2,3）；B（1,3,4）
则考虑第一个位置时，只能填1。
考虑第二个位置时，可以填2或3。
但是由于2和3在这里是完全等价的，也就是说我们并不关心填了谁。
那么我们只需要记录每一步有多少个数可填就好了，这个答案与之前填入的方案无关。
具体实现的时候只需要用双指针进行一轮扫描就可以了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 100050;
const LL mod = 1000000007;
int a[N], b[N], ans = 1, n;
int main()
{
int i, j, k;
cin >> n;
for(i = 1; i <= n; i ++)
scanf("%d", &a[i]);
for(i = 1; i <= n; i ++)
scanf("%d", &b[i]);
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for(i = 1, j = 0; i <= n; i ++){
while(j < n && a[j + 1] <= b[i])
j ++;
ans = (LL)ans * max(0ll, j - i + 1ll) % mod;
}
printf("%d", (ans + mod) % mod);
return 0;
}
E 立方数
考虑直接一些的做法
尝试对每个N作质因数分解，经简单的统计可得出答案，复杂度O(TN^(1/2))
我们先做简单一点的优化，容易发现其实只要枚举10^6(N^(1/3)以内)的质数就好，复杂度O(TN^(1/3)/ln(N^(1/3)))
再作进一步的分析，如果我们仅使用N^(1/4)(记为W)以内的质数去试除，那么最后余下的数X仅具有大于W的因子
此时X要么是一个完全立方数，要么对答案没有任何贡献，只需要使用二分法来验证X是不是一个完全立方数即可
复杂度O(TN^(1/4)/ln(N^(1/4)))，不卡常数，真的！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <time.h>
using namespace std;
typedef long long LL;
const int N = 31700;
int is[N], n, pri[N]; LL x, p_tri[N], p_ss[N];
int main()
{
int i, j, k;
for(i = 2; i < N; i ++){
if(is[i] == 0){
pri[++ pri[0]] = i;
p_tri[pri[0]] = (LL)i * i * i;
p_ss[pri[0]] = (LL)i * i * i * i;
for(j = i * i; j < N; j += i)
is[j] = 1;
}
}
scanf("%d", &n);
while(n --){
int ans = 1;
scanf("%lld", &x);
for(i = 1; p_ss[i] <= x; i ++){
if(x % pri[i] == 0){
while(x % p_tri[i] == 0){
ans *= pri[i];
x /= p_tri[i];
}
while(x % pri[i] == 0)
x /= pri[i];
}
}
int lb = 1, rb = 1000000;
while(lb <= rb){
int md = lb + rb >> 1;
if((LL)md * md * md < x)
lb = md + 1;
else
rb = md - 1;
}
if((LL)lb * lb * lb == x)
ans *= lb;
printf("%d\n", ans);
}
return 0;
} F 十字阵列
设3个数组a[]，b[]和ab[][]，分别统计对行，列和每格造成的伤害
进行操作(xi,yi,zi)时，a[xi]，b[yi]，ab[xi][yi]都加上zi
每次询问一格的答案时，只要查询a[x]+b[y]-ab[x][y]就好了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2010;
const int mod = 1000000007;
int x[N], y[N], xy[N][N], n, m, H, ans;
int main()
{
int i, j, k, h;
scanf("%d%d%d", &n, &m, &H);
for(i = 1; i <= H; i ++){
scanf("%d%d%d", &j, &k, &h);
x[j] += h, y[k] += h, xy[j][k] += h;
}
for(i = 1; i <= n; i ++)
for(j = 1; j <= m; j ++)
ans = (ans + (long long)(x[i] + y[j] - xy[i][j]) * (i + j) % mod) % mod;
printf("%d", (ans + mod) % mod);
return 0;
} G 括号序列
括号序列合法的一个充要条件是：
设'('为1，')'为-1，则：①序列所有位置前缀和非负；②'('与')'数量相等
为了保证条件1，我们可以用栈模拟括号序列的匹配过程
碰到一个'('就加入栈中，碰到一个')'就消去栈顶的一个'('
如果栈中没有没有'('则这个')'必须要删去
在这个过程结束之后，如果'('比')'多，则从后向前删去多余的'('，直到序列合法即可
可以证明这样一定能得到满足要求的括号序列：两个步骤中删除的括号都是必须删去的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1000050;
int T, n, l, r, sum, ans; char s[N];
int main()
{
int i, j, k;
scanf("%d", &T);
while(T --){
scanf("%d", &n);
scanf("%s", s + 1);
l = r = sum = ans = 0;
for(i = 1; i <= n; i ++){
if(s[i] == '(')
l ++, sum ++;
else if(sum > 0)
r ++, sum --;
else ans ++;
}
printf("%d\n", ans + l - r);
}
return 0;
} H 云
直接考虑问题较难，因为两种云都在运动。
但是我们可以考虑相对运动，将这个过程等效为左下角的云朝右上方移动。
在这个背景下我们容易发现：将所有的云投影成y=-x这条直线上的一条线段，则两朵云会相遇当且仅当他们的投影有交点。
这是一个简单的扫描线问题，将线段拆成端点后排序统计即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 400050;
struct node{
int loc, lr, typ;
inline bool operator < (const node &b)const{
if(loc == b.loc && lr == b.lr)
return typ < b.typ;
if(loc == b.loc)
return lr > b.lr;
return loc < b.loc;
}
}A[N];
int n, m, a, b, c, d, k;
LL cnt[2], ans;
int main()
{
for(scanf("%d%d", &n, &m); n --;){
scanf("%d%d%d%d", &a, &b, &c, &d);
A[++ k] = (node){d - c, 1, 0};
A[++ k] = (node){b - a, -1, 0};
}
while(m --){
scanf("%d%d%d%d", &a, &b, &c, &d);
A[++ k] = (node){d - c, 1, 1};
A[++ k] = (node){b - a, -1, 1};
}
sort(A + 1, A + k + 1);
for(int i = 1; i <= k; i ++){
cnt[A[i].typ] += A[i].lr;
if(A[i].lr == 1)
ans += cnt[A[i].typ ^ 1];
}
printf("%lld\n", ans);
return 0;
} I 导航系统
显然数据给出的原图是一棵树。
容易发现，如果将输入的N(N-1)个距离看做N(N-1)条无向边的话，那么如果数据合法，原树就是这张新图的最小生成树。
证明：由于边权是非负的，可以考虑Kruskal算法的过程，每一次引入的边都是尽可能短的，所以一定是树中的边，通过简单的归纳即证。
所以求出最小生成树之后再进行验证就好了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 510;
struct edge{
int u, v, c;
bool operator < (const edge &b)const{
return c < b.c;
}
}w[N * N], ans[N];
int a[N][N], n, m = 0, T[N], to[N][N], siz[N], len[N][N], dis[N][N];
int path(int x){
if(T[x] == 0)
return x;
return T[x] = path(T[x]);
}
void dfs(int x, int fa, int st, int d){
dis[st][x] = d;
for(int i = 1; i <= siz[x]; i ++)
if(to[x][i] != fa)
dfs(to[x][i], x, st, d + len[x][i]);
}
int main()
{
int i, j, k;
scanf("%d", &n);
for(i = 1; i <= n; i ++)
for(j = 1; j <= n; j ++)
scanf("%d", &a[i][j]);
for(i = 1; i <= n; i ++){
for(j = 1; j <= n; j ++){
if(a[i][j] != a[j][i]){
puts("No");
return 0;
}
if(i < j){
m ++;
w[m].u = i;
w[m].v = j;
w[m].c = a[i][j];
}
}
}
sort(w + 1, w + m + 1);
for(i = 1, j = 0; i <= m && j < n - 1; i ++){
int x = path(w[i].u), y = path(w[i].v);
if(x != y){
T[x] = y;
ans[++ j] = w[i];
siz[ans[j].u] ++, siz[ans[j].v] ++;
to[ans[j].u][siz[ans[j].u]] = ans[j].v;
to[ans[j].v][siz[ans[j].v]] = ans[j].u;
len[ans[j].u][siz[ans[j].u]] = len[ans[j].v][siz[ans[j].v]] = ans[j].c;
}
}
for(i = 1; i <= n; i ++)
dfs(i, 0, i, 0);
for(i = 1; i <= n; i ++){
for(j = 1; j <= n; j ++){
if(a[i][j] != dis[i][j]){
puts("No");
return 0;
}
}
}
puts("Yes");
for(i = 1; i < n; i ++)
printf("%d\n", ans[i].c);
return 0;
} J 签到题
对没错它就是签到题，只要会解一个简单的方程就好了。
可以证明“No”是不存在的，所以不论怎么写都能对。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
double a[3], b[3];
int main()
{
cin >> a[0] >> a[1] >> a[2];
sort(a, a + 3);
if(a[0] + a[1] <= a[2]){
puts("wtnl");
return 0;
}
puts("Yes");
b[1] = (a[2] - a[1] + a[0]) / 2;
b[0] = a[0] - b[1], b[2] = a[2] - b[1];
printf("%.2lf %.2lf %.2lf", b[0], b[1], b[2]);
return 0;
} 到此整个集训营就结束啦！祝大家的AK姿势都能有进步！ 如果这场比赛给你带来了收获，就是坠吼的！
