Preliminaries for Benelux Algorithm Programming Contest 2019
A. Architecture
purpose：给你第一行的值表示m列的最大值，给你第m行的值表示n行的最大值，问是否会行列冲突。
Solve:求出行列最大值，如果一样即possible，否则impossible。
B. Bracket Sequence
purpose：给你一串字符串，最外面数字之间全用+，一层括号用*，两层用+，三层用*，以此类推。
Solve1: 每一层括号里的数字之间使用的符号相同，用栈存每一层的数字计算即可，需要手写栈，否则空间不够。
Solve2: 栈中记录使用 * 或者 + ，遇到非‘(’计算即可。
C. Canyon Crossing
Purpose：现在可以建k座桥，建桥后山的高度忽略不计，求从底部(第r行)走到顶部(第1行)的路线中最小值最大是多少。
Solve：二分答案，用bfs跑图即可，因为每一个单元格会重复走，对于走的距离循环来优化bfs。
D. Deceptive Dice
Purpose：有一个n面的骰子，现在最多可以玩k轮，如果在i(i<=k)轮达到了期望水平（即期望的骰子分数），那么就会终止，否则继续，问最终游戏的期望分数。
Solve：求出第i轮的期望分数为socre1，对于第i + 1轮来说，进行第i + 1轮的条件是第i轮没有到达期望分数score1，那么第i + 1轮的期望分数为
E. Exits in Excess
Purpose：移除最多一半的边使得图没有环。
Solve：将所有边分成两部分，第一部分为u < v，第二部分为v > u，将小的边集合删去。
F. Floor Plan
Purpose：给你n, 求 n = m2 - k2
Solve：
1. 对于n 为奇数时，有(x + 1)2 - x2 = 2x + 1。
2. 对于n 为4的倍数时，有(x + 2)2 - x2 = 4(x + 1)。
3. Impossible。
证明：若n % 2 == 0且n % 4 != 0，n = (m - k)(m + k)，∵n为偶数，∴(m - k)或者(m + k)必有一项是偶数，若(m-k)是偶数，那么(m+k)也是偶数，反之同理。
G. Greetings!
Purpose：复杂字符串中的e。
Solve：略。
Std:略
H. Hexagonal Rooks
Purpose：给你起始位置的行(数字1~11)和列(字母a~k)和末位置的行和列，求两步(一步的长度不一定是1)走到末位置的中间点的数量。
Solve：枚举所有棋的格子，同时满足从起始位置一步到所枚举的格子和所枚举的格子一步到末位置即答案 + 1。
I. Inquiry I
Purpose：给你数组a，求公式的最大值。
Solve：求a数组平方的前缀和和求a数组后缀和，遍历一遍即可。
J. Jumbled Journey
Purpose：给你i到j路线长度的平均值(1 <= i, j <= n)，求出原始DAG路径图。
Solve：拓扑排序给你的平均路径图，建立新的拓扑图，设置相邻顶点间的边数为1，边值为平均路径。枚举起始点和终点，统计间接到达终点的路数和路径总长，算出是否要添加一条新的从起始点到终点的直接路径，同时如果有间接路径时要保证新添的路径长度小于平均值。
/*
给你i到j路线长度的平均值，求出原始DAG路径图
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n, in[105], toposort_v[105], toposort_p[105], num[105][105];
LL dag_ans[105][105];
LL dag_ave[105][105], dag_new[105][105];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
scanf("%lld", &dag_ave[i][j]);
if(dag_ave[i][j] > 0) in[j]++;
}
}
// toposort to new dag
queue<int> q;
int cnt = 0;
for (int i = 1; i <= n; i++) if(!in[i]) q.push(i), toposort_v[++cnt] = i;
while(q.size()){
int u = q.front();
q.pop();
for (int v = 1; v <= n; v++){
if(dag_ave[u][v] > 0){
in[v]--;
if(in[v] == 0) q.push(v), toposort_v[++cnt] = v;
}
}
}
for (int i = 1; i <= n; i++) toposort_p[toposort_v[i]] = i;
// new dag
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
dag_new[i][j] = dag_ave[toposort_v[i]][toposort_v[j]];
}
}
// orginal ans_dag
memset(dag_ans, -1, sizeof(dag_ans));
for (int i = 1; i < n; i++){
if(dag_new[i][i + 1] > 0) dag_ans[i][i + 1] = dag_new[i][i + 1], num[i][i + 1] = 1;
}
for (int len = 2; len <= n; len++){
for (int i = 1; i + len <= n; i++){
int j = i + len;
// i -> k -> j ways' number and weight
LL sum = 0;
for (int k = i + 1; k < j; k++){
if(dag_ans[i][k] > 0 && num[k][j] > 0){
num[i][j] += num[k][j];
sum += dag_ans[i][k] * num[k][j] + dag_new[k][j] * num[k][j];
}
}
// if add a path, ave = (sum + x) / (num[i][j] + 1), x is new path's weight
LL x = dag_new[i][j] * (num[i][j] + 1) - sum;
if((num[i][j] == 0 && dag_new[i][j] > 0) || (num[i][j] && x > 0 && dag_new[i][j] > x)){ // 保证直连的线长度小于间接连得线，所以直连的线小于平均值
dag_ans[i][j] = x;
num[i][j]++;
}
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
int x = toposort_p[i], y = toposort_p[j];
printf("%lld%c", dag_ans[x][y], j == n ? '\n' : ' ');
}
}
return 0;
}
/**/
K. Knapsack Packing
Purpose：给你n件物品和他们的重量以及所有组合重量，求是否存在这n件物品的重量来满足这些组合。
Solve：将所有重量存入multiset中，每次考虑最大的次大的，必能得到n个物品中一个物品的重量，从multiset中删除与此重量有关的所有组合，若找不到，输出impossible。
L. Lifeguards
Purpose：学员被离两个教练最近的一个教练管理。找到两个教练的坐标，使得教练管理学员数量相同，最多有一个人离两个教练距离相同。
Solve：同https://ac.nowcoder.com/acm/contest/883/H，将所有学员根据坐标排序，用一线划分成两部分，线的两个无穷远处为端点，若学员数量为奇数，那么此线需经过中间点。
设中间点为(x,y)
Max设为无穷大
例: n 为偶数 (x - Max, y - 1), (x + Max, y)
n 为奇数 (x - Max, y - 1), (x + Max, y + 1)
查看8道真题和解析
