Nowcoder 2020 寒假算法基础训练

一共六场云比赛，据官方声称大约是cf-div3的难度，然而我做的并不顺畅就是了。首先是它们的题解链接，放在前面备用。

第一场：https://ac.nowcoder.com/discuss/364600
第二场：https://ac.nowcoder.com/discuss/364961
第三场：https://ac.nowcoder.com/discuss/365306
第四场：https://ac.nowcoder.com/discuss/365889
第五场：https://ac.nowcoder.com/discuss/366644
第六场：https://ac.nowcoder.com/discuss/367149

然后对一些题目做一些笔记吧，毕竟自己也确实是菜的真实（）

第四场

所有题目的链接：https://ac.nowcoder.com/acm/contest/3005
官方的题解帖子：https://ac.nowcoder.com/discuss/365889

为什么这场宣称没有难题没有毒瘤题我只A了一个啊噫呜呜噫我好菜啊哭哭==

不过这一场题目确实，不仅整体相对偏向思维的考察，也非常考察写代码细节注意的程度。像我好多题目对着答案的思路敲也是WA不可避== 这套题补下来还是觉得想法会开拓不少，但是之后遇到类似的题目不知道能不能做出来就是了……

这整个就是一个概率题。看懂之前真的连一个式子都列不出来，更别说怎么写代码求解了== 不过我只看了一眼就放弃了，真不愧是我（）所以在上这个题目的代码之前先进行~~不那么~~简单的数学推导：

首先，我们设第 $i$ 个同学的总分是 $S$ ，其中包含 $s\geq90$ 分的平时分以及 $r\leq90$ 分的随机论文得分，随机的得分在总得分中占比 $p$ 。显然，同学 $i$ 优秀的概率是 $P_i(S\geq90)$ ，这个总分满足等式 $S = s\cdot(1-p)+r\cdot p$ 。

仅仅这样我们也什么都不知道，还需要进行一些变换。首先将总分的等式带入到概率的不等式中，可以得到：

$P_i:s\cdot(1-p)+r\cdot p\geq90$ 将不等式的两侧同时减去90，可以得到：$P_i:S-90=s\cdot(1-p)+r\cdot p-90\geq0$$(s-90)\cdot(1-p)+(r-90)\cdot p\geq0$ 又因为$r$本来就是一个范围是[0,90]的随机数，所以$r-90$是一个[-90,0]的随机数，和$-r$是等价的。因此上式可以变成：$(s-90)\cdot(1-p)-r\cdot p\geq0$ 整理可得：$P_i: \frac{(s-90)\cdot(1-p)}{p} \geq r$ 又因为$r$是一个范围是[0,90]的随机数，易得$P(r\leq x)=\frac{x}{90}$，所以上述不等式成立的概率$\frac{(s-90)\cdot(1-p)}{p} \geq r$等于$P(r\leq \frac{(s-90)\cdot(1-p)}{p})=\frac{(s-90)\cdot(1-p)}{90p}$。至此，我们求出了第$i$位学生优秀的概率：$P_i:\ \frac{(s-90)\cdot(1-p)}{90p}$

设班级内一共有 $n$ 名同学，要求优秀率恰好为10%，也就是说：

$E = \sum _{i=1}^n P_i = \sum _{i=1}^n \frac{(s_i-90)\cdot(1-p)}{90p} = 0.1n$ 解这个方程可得：$p = \frac{\sum _{i=1}^n (s_i-90)}{9n+\sum _{i=1}^n (s_i-90)}$

但是除此之外，出题人称还可以使用二分的方法求解。这也许是一种数值计算方法，等我弄明白了再在这里补充好了。

#include <iostream>
#include <iomanip>

using namespace std;
typedef long long longs;
typedef long double longd;

int n,ss;
int in[100010];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(2);

    while(cin>>n)
    {
        ss = 0;
        for(int i=0;i<n;++i)
        {
            cin>>in[i];
            ss += in[i]-90;
        }
        cout<<(longd)ss/(9.0l*n+ss)*100.0l<<'%'<<endl;
    }

    return 0;
}

属于这种只要你把它推出来了，写代码并不是很难的题目。但是像我就直接被吓死了==

~~此外，通过这个题目，我熟练了使用MathJax和LaTeX的技巧~~

H - 坐火车

题目链接：https://ac.nowcoder.com/acm/contest/3005/H

I - 匹配星星

题目链接：https://ac.nowcoder.com/acm/contest/3005/I

J - 二维跑步

题目链接：https://ac.nowcoder.com/acm/contest/3005/J

第五场

所有题目的链接：https://ac.nowcoder.com/acm/contest/3006
官方的题解帖子：https://ac.nowcoder.com/discuss/366644

这次的题目里有大量的浮点数……就容易出现各种各样的小麻烦。印象里这里还有严格的卡了IO的题目（指ios::sync_with_stdio不管用）和超级模拟的毒瘤题=== 总而言之这绝对是一套极其麻烦的题目。

B - 牛牛战队的比赛地

题目链接：https://ac.nowcoder.com/acm/contest/3006/B

看起来就知道这是一个极其麻烦的题目。直接求解想必是十分困难的，但是验证一个点距离最远基地的最小值是可以一定时间内完成的——这样就要考虑到二分算法的可能性。此外，答案的取值范围是确定的，因此更应该想到使用二分解题。

题解使用了三分查找的方法，声称这样比二分查找更加的简单。二分查找最值就是一个比较麻烦的事情……大约需要对每一个区间继续二分然后递归……下次知道的话再做一个专题吧。

#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>

#define vi vertex[i]

using namespace std;
typedef long long longs;
typedef long double longd;

struct point{int x,y;};

int n,x,y;
point vertex[100050];

longd distance(longd xpos)          // 这里也用longd就能AC了
{
    longd tmp = 0.0l;
    longd x2,y2;
    for(int i=1;i<=n;++i)
    {
        y2 = vi.y*vi.y;
        x2 = (vi.x-xpos)*(vi.x-xpos);
        tmp = max(tmp,sqrtl(x2+y2));
    }
    return tmp;
}

longd triple_search(longd left, longd right)
{
    longd midl,midr;
    for(int i=0;i<=100;++i)     // 因为浮点，所以只能通过搜索次数提高精度
    {
        midl = left + (right-left)/3;
        midr = left + 2*(right-left)/3;
        if(distance(midl)>distance(midr))
            left = midl;
        else right = midr;
    }
    return midl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(4);

    while(cin>>n)
    {
        for(int i=1;i<=n;++i)
        {
            cin>>x>>y;
            vertex[i] = {x,y};
        }
        cout<<distance(triple_search(-10000,10000))<<endl;
    }

    return 0;
}

这道题目对于二分/三分查找的最大疑惑就是这个最小值和坐标的x值之间构成的函数关系是不是成单调关系或者是严格凹凸函数关系——至少在这个题里并没有明显的这样的关系的存在，可是笔记里也确实记录了这样的内容：

节选自我的笔记
那么单峰函数和使用三分到底有什么关系呢？它比二分的效率要高？不是的，你写一下二分就知道二分会暴毙再极端情况的。因为二分查找对应的是单调函数，而三分查找对应单峰函数极值点的寻找。
因为是单峰函数，所以最大值的获得只需要使用三分查找就可以了。但是三分查找仅对于严格凹/凸函数有效。如果出现可行域中连续的函数导数为0的情况可能会暴毙。

但是，题目的函数条件虽然写的很复杂，不要忘记你的基础数学知识啊：

凹凸序列：
如果一个函数是若干个开口向上的二次函数的最大值，这个函数就是先减后增的凹形序列了，相应地：
如果一个函数是若干个开口向下的二次函数的最小值这个函数就是先增后减的凸形序列。

因为对于每一个点，距离所求点的距离都是一个凹函数，所以它们最大值构成的函数也是一个凹函数。这样求最小值极值三分法就毫无疑问了。

F - 碎碎念

这题是个DP是真的万万没想到== 没做出来的原因大概就是读题的时候RJ->AC这个条件根本就没有有效利用。因为一发RJ之后必定AC，所以必不会出现连续RJ，一发RJ后必连AC。这样就规定了一种转移关系：AC由AC和RJ转移来，RJ由AC转移来。可设dp[x][0/1]是x句话时最后一个是AC或者RJ的可能性，即可得到推导公式。

然后是多次询问，这种询问区间大多都是要使用前缀和这种东西进行优化的。所以dp的时候记得加一下就好。询问的时候直接两个前缀和求差就行了。

#include <iostream>

using namespace std;
typedef long long longs;
typedef long double longd;

const longs MOD = 1000000007ll;

int x,q,l,r;
int dp[2][100010];
int pre[100010];

inline void preProcess(int x)
{
    const int AC=1,RJ=0;
    dp[RJ][0] = 0;
    dp[AC][0] = 1; 
    pre[0] = 1;
    for(int i=1;i<=100010;++i)
    {
        dp[RJ][i] = (i>=x)?dp[AC][i-x]:0;
        dp[AC][i] = ((longs)dp[RJ][i-1]+dp[AC][i-1])%MOD;
        pre[i] = ((longs)dp[AC][i]+dp[RJ][i]+pre[i-1])%MOD;
    }
}

int solution(int l,int r)
{
    return (pre[r]-pre[l-1]+MOD)%MOD;   
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(cin>>x>>q)
    {
        preProcess(x);
        while(q--)
        {
            cin>>l>>r;
            cout<<solution(l,r)<<endl;
        }
    }

    return 0;
}

交题目的时候出现了奇怪的问题，本地测试通过但是上传却连样例都无法通过，后来把Nowcoder的编译器从 clang++ 换成 GNU g++ 就好了，现在也不知道是什么原因==

G - 街机争霸

因为是题目数据范围不大，大概可以用一些简单的算法。比较麻烦的就是僵尸会动来动去，不然的话直接BFS就完事了。但是僵尸动的周期是一致的，所以可以再输入的时候预处理僵尸不同时刻所在的位置，然后在这样的基础之上进行BFS，这个题目就可以做出来了。

#include <iostream>
#include <string>
#include <utility>
#include <cstring>
#include <queue>

using namespace std;
typedef long long longs;
typedef long double longd;
struct coord{int x,y;coord operator+(const coord& rhs);};
static const coord mov[4] = {{-1,0},{1,0},{0,-1},{0,1}};
struct node {coord p;int t;};

const int N = 500+5;
const string ohno = "Oh no";

int n,m,p,k;
char map[N][N];
bool zmbmap[N][N][50];
coord inpos,st,ed;
string instr;
int T;
int vis[N][N][20];
queue<node> q;

bool judge(coord pos,int now)
{
    if(pos.x<=0||pos.y<=0||pos.x>n||pos.y>m)return false;
    else if(map[pos.x][pos.y]=='&')return false;
    else if(zmbmap[pos.x][pos.y][now])return false;
    else return true;
}

inline int bfs()
{
    int ans = -1;
    while(!q.empty())q.pop();
    vis[st.x][st.y][0] = 0;
    q.push({st,0});
    node n;coord c;
    int nt;

    while(q.size())
    {
        n = q.front(); q.pop();
        if(n.p.x==ed.x&&n.p.y==ed.y)
        {
            ans = vis[ed.x][ed.y][n.t];
            break;
        }
        nt = (n.t+1)%T;
        for(int i=0;i<4;++i)
        {
            c = n.p+mov[i];
            if(judge(c,nt)&&vis[c.x][c.y][nt]==-1)
            {
                vis[c.x][c.y][nt] = vis[n.p.x][n.p.y][n.t]+1;
                q.push({c,nt});
            }
        }
    }
    
    return ans;
}

inline int parseDir(string &s)
{
    switch(s[0])
    {
        case 'R':return 3;
        case 'U':return 0;
        case 'L':return 2;
        case 'D':return 1;
        default:exit(-1);break;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(cin>>n>>m>>p>>k)
    {
        memset(zmbmap,0,sizeof(zmbmap));
        memset(vis,-1,sizeof(vis));
        T = 2 * k - 2;

        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
            {
                cin>>map[i][j];
                if(map[i][j]=='A') ed={i,j};
                else if(map[i][j]=='L') st={i,j};
            }
        for(int i=1;i<=p;++i)
        {
            cin>>inpos.x>>inpos.y;
            cin>>instr;
            zmbmap[inpos.x][inpos.y][0] = true;
            int dir = parseDir(instr);
            for(int x=1,j=2*k-3;x<k;++x,--j)
            {
                inpos = inpos+mov[dir];
                zmbmap[inpos.x][inpos.y][x] = zmbmap[inpos.x][inpos.y][j] = true;
            }
        }

        int res = bfs();
        if(~res)cout<<res<<endl;
        else cout<<ohno<<endl;
    }

    return 0;
}

coord coord::operator+(const coord& rhs)
{
    return {x+rhs.x,y+rhs.y};
}

建议写代码还是尽可能的言简意赅，能不要花里胡哨就不要花里胡哨，不然出错就非常的吃亏。之前包装了一堆函数还给我整了一个段错误出来就非常的离谱== 所以说少麻烦点就少麻烦点。现在感觉这似乎也是某种意义上的多层图：固有障碍每层都有，僵尸不同时间在不同的层的不同位置。

第六场

所有题目的链接：https://ac.nowcoder.com/acm/contest/3007
官方的题解帖子：https://ac.nowcoder.com/discuss/367149

总的来说这一次的题目还是比较的常规的——指的不是简单易懂，就是比较的……正常？毕竟比第五场谜之写错要舒服的多，看完了所有题目，只要思路没什么大问题基本写出来就不会有问题。

B - 图

题目链接：https://ac.nowcoder.com/acm/contest/3007/B

看到这样的题目描述很容易就能知道这个图大概是长什么样子：可能有多个连通块，每个连通块都是一个环外面续着几根链（太阳形），看了题解知道这种图叫做基环内向树森林。这样，从一个点出发一定能到一个环。

如果是在学tarjan判环时期说不定我就直接tarjan了找环然后找最长链了，但是这个题目似乎没有那么麻烦，DFS就好了。因为直接DFS会超时所以要使用记忆化搜索。但是问题就是我没想好这个记忆化具体的实现方法== gg

自己写的版本还特别统计了每个入度。大概能想到的用场就是从入度为0的点开始，利用入度大于1的点寻找链和环的交接处吧。虽然看起来题解没有这么做便是了。能想到的退化点大概就是太阳形的图，大量的入点会导致道面好多遍这个图然后T。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;
typedef long long longs;
typedef long double longd;

int n,v[1000010];
bool vis[1000010],in[1000010];
stack<int> t;
int ans = 0,mem[1000010];
int cur,c,cnt;

int mem_dfs(int x)
{
    if(mem[x]) return mem[x];
    else return mem[x] = 1+mem_dfs(v[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(cin>>n)
    {
        for(int i=1;i<=n;++i) cin>>v[i];
        memset(vis,0,sizeof(bool)*(n+1));
        memset(in,0,sizeof(bool)*(n+1));
        memset(mem,0,sizeof(int)*(n+1));

        for(int i=1;i<=n;++i)
        {
            if(!vis[i])
            {
                cur = i;
                while(!vis[cur])        // 找点
                {
                    t.push(cur);
                    vis[cur] = in[cur] = true;
                    cur = v[cur];
                }
                if(in[cur])             // 找到环
                {
                    c=v[cur],cnt=1;
                    while(c!=cur)       // 求环的大小
                    {
                        c = v[c];
                        ++cnt;
                    }
                    do                  // 存储环的大小
                    {
                        c = v[c];
                        mem[c] = cnt;
                    } while (c!=cur);
                }
                while(t.size())
                {
                    in[t.top()] = false;
                    t.pop();
                }
            }
        }
        for(int i=1;i<=n;++i)
            ans = max(ans,mem_dfs(i));
        cout<<ans<<endl; 
    }

    return 0;
}

注意细节……这样的代码还能写炸就不太象话了（）所谓记忆化主要还是记录环的大小。一次遍历得到环的大小之后，无论有什么样的链都不会重复走环，速度就快了。

C - 汉诺塔

题目链接：https://ac.nowcoder.com/acm/contest/3007/C

显然必然是要先按照一边进行排序的。之后就变成了在已经按照x排序的数列中寻找y边长尽可能少的若干组单调子序列。这个单调的方向和按照x排序的顺序一致。然后就是离散数学里的比较常见的Dilworth定理。

Dilworth定理：偏序集的最少反链划分数等于最长链的长度。

这指出了可以通过求出另一个单调方向的最长链长度来求出这个最小划分的组数。

至于这个最长单调序列的经典求法，可以去看一下洛谷P1020。其实这个最长单调序列问题还是挺经典的，又很多可以做的优化。

但是仅仅是这样是不行的，题目还要让我们输出这个划分的具体方式。所以需要开数组记录每个木板的分组组号和每个分组当前在“栈顶”的木板的宽度。将每一块木板放在使用二分找到的最大的比它小的（sort默认升序）木板上就好。

#include <iostream>
#include <utility>
#include <algorithm>
#include <functional>
#include <cstring>

#define x first.first
#define y first.second
#define num second

using namespace std;
typedef long long longs;
typedef long double longd;
typedef pair<pair<int,int>,int> it;

it in[100010];
int n;
int ans[100010];    // 0是组数，1~n记录分组情况
int stack[100010];  // 维护最长的下降子序列

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(cin>>n)
    {
        ans[0] = 0;
        memset(stack,0,sizeof(int)*(n+1));
        for(int i=1;i<=n;++i)
        {
            cin>>in[i].x>>in[i].y;
            in[i].num = i;
        }
        sort(in+1,in+1+n);
        for(int i=1;i<=n;++i)
        {           // 使用STL二分找出第一个小于当前木板宽的组号
            int lb = upper_bound(stack+1,stack+ans[0]+1,in[i].y,greater<int>())-stack;
            stack[lb] = in[i].y;
            if(lb>ans[0]) ans[0]=lb;
            ans[in[i].num] = lb;
        }
        cout<<ans[0]<<endl;
        for(int i=1;i<=n;++i)
        cout<<ans[i]<<' ';
    }
 
    return 0;
}

其实就是谁都能想到的朴素n²算法的二分优化……我已经什么都不会了（大悲）

E - 立方数

题目链接：https://ac.nowcoder.com/acm/contest/3007/E

这是这套题目里一个比较令我上头的题目。很显然答案就在 1~³√n之间，验证起来的话倒也不是那么麻烦。看起来极其的像二分找答案== 但是实在不知道拿什么当作判别二分的标准……遂作罢。想着分治但是这看起来不是可以轻易分治的样子，没有想到一种确实可以加快速度的分治方案== gg。

之后用先提取2然后跳奇数的方法分解因数然后也妥妥T了，转念一想就算是数据的极限情况，有价值尝试的质因数范围也不过1e6，比之前的1e8好多了== 如果用欧拉筛的话1e6的质数也不是事，况且还要多次查询而预处理只需要一次……稳赚不赔啊（）遂尝试欧拉筛选出质数进行分解但是最终谜之WA了，遂作罢。

看了题解，这是题解中题目作者的进一步分析:

作者：珩月
链接：https://ac.nowcoder.com/discuss/367149?type=101&order=0&pos=1&page=1
来源：牛客网
先做简单一点的优化，容易发现其实只要枚举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)))，不卡常数。

其实我一开始没怎么看懂…… 使用⁴√n作为测试的素数范围的话，最大的问题就是⁴√n~³√n这个区间范围内的可能性了。筛之后的数字确实不再包含任何小于³√n的因子，也就是说如果它不是完全立方数且对答案有贡献，设贡献的因子为k，那么这个剩下来的数一定会大于k³·m，其中k,m>³√n。但是若这样的k存在，那么这个剩下的数字会大于(³√n)⁴>n，这必然是不可能的。所以只需要判断剩下来的部分是不是完全立方数就好了，而这部操作是可以使用二分查找的。

#include <iostream>
#include <cmath>

using namespace std;
typedef long long longs;
typedef long double longd;

int t;
longs n;

bool is[1000100]{0};
int prime[100000]{0};           // 1e6内质数大约是7.2w个
longs tri[100000],qua[1000000];

inline void preProcess()        // 欧拉筛 + 预先计算幂
{
    int tmp;
    for(int i=2;i<=1000010;++i)
    {
        if(!is[i]) 
        {
            prime[++prime[0]]=i;
            tri[prime[0]] = i*i*i;
            qua[prime[0]] = tri[prime[0]]*i;
        }
        for(int j=1;j<=prime[0]&&(tmp=i*prime[j])<=1000010;++j)
        {
            is[tmp]=1;
            if(i%prime[j]==0) break;
        }
    }
}

inline longs solve(longs n)
{
    if(!(n&1ll))                // 处理因数2
    {
        int cnt = 0;
        while(!(n&1ll))
        {
            ++cnt;
            n>>=1;
        }
        return (1ll<<(cnt/3))*solve(n);
    }
    longs ans = 1;
    for(int i=1;qua[i]<=n;++i)  // i<=prime[0]没有必要
        if(n%prime[i]) continue;
        else                    // 完全去除这个因数
        {
            while(!(n%tri[i]))
            {
                ans *= prime[i];
                n /= tri[i];
            }
            while(!(n%prime[i])) n/=prime[i];
        }
    int lb = 1, rb = 1000000;
    while(lb<=rb)               // 可以二分查找
    {
        int mid = lb+rb >> 1;
        if((longs)mid*mid*mid<n) lb = mid+1;
        else rb = mid-1;
    }
    if((longs)lb*lb*lb==n) ans*=lb;
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    preProcess();
    while(cin>>t)
        while(t--)
        {
            cin>>n;
            cout<<solve(n)<<endl;
        }

    return 0;
}

现在想想，最开始想到二分但是不能二分的原因是因为无法确定判据：如果是用大于/小于n的话，只会让二分结果更加趋向于³√n，但是实际上很多数字的答案是1，显然这不合理；如果使用除数/余数作为判据，那就比较的麻烦，甚至可能要考虑它们的变化，就不像是二分了…… 也就是说二分最大的障碍是那些比较小的因数，而这可以先行筛去。之后可能的因数在⁴√n~³√n内，因为这个数一定是小于等于n的，所以要不是立方数要不是倍数，就转化的可以二分了…… 妙啊。

简单的说，就是：如果n有大于⁴√n~³√n的因子且有贡献，那么必然会有小于³√n的因子，筛去这部分因子之后剩下的就是（有奉献的）完全立方数或者（无奉献的）质因数乘积。

这么一想，之前写的³√n的时候细节也不怎么注意，常数必然很大，被卡掉也是自然（）而且对于1e18的数据来说两种复杂度差距很大的啊……确实也是根本没有向⁴√n的方向去想吧== 学到了学到了。

I - 导航系统

题目链接：https://ac.nowcoder.com/acm/contest/3007/I

这应该是这次最麻烦的题目。最开始看到n-1条边、看到两点距离、再看到判断最短距离的正误，第一反应是并查集和树上LCA（虽然板子用的并不熟练）。但是仔细一看发现题目并没有指明点之间的关系用来建图，遂作罢。

看了题解才想着：n个节点n-1条边就是一棵树，如果数据合法，那么这棵树就是输入的完全图的最小生成树（草怎么就没想到==）。因为边权是非负数的，可以使用Kruskal算法构建最小生成树再进行验证即可。

~~如果忘记了以贪心为基本思想的Kruskal算法的话，那自裁，请（无慈悲）~~我爬了

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long longs;
typedef long double longd;
struct edge
{
    int from,to,val;
    bool operator<(const edge& rhs) const;
};

const string yes = "Yes";
const string no = "No";
const int N = 505;

int n;
int map[N][N];
edge elist[N*N];
int cur = 0;        // 输入的完全图边光标
bool fall = false;
int dis[N][N];      
int ufs[N];         // Kruskal用并查集

int head[N];        // 前向星存最小生成树
edge fstree[N*2];
int nextptr[N*2];
int tot;

int father(int x)
{
    if(!ufs[x]) return x;
    else return ufs[x]=father(ufs[x]);
}

inline int unite(int u,int v)
{
    return ufs[u] = v;
}

inline void addedge(edge& e)
{
    nextptr[tot] = head[e.from];
    head[e.from] = tot;
    fstree[tot] = e;
    ++tot;
    nextptr[tot] = head[e.to];
    head[e.to] = tot;
    fstree[tot] = {e.to,e.from,e.val};
    ++tot;
}

void dfs(int now,int prev,int sp,int leng)
{
    dis[sp][now] = leng;
    int c = head[now];
    while(~c)
    {
        edge& ce = fstree[c];
        if(ce.to^prev)
            dfs(ce.to,now,sp,leng+ce.val);
        c = nextptr[c];
    }
}

inline void init()
{
    fall = false;
    memset(ufs,0,sizeof(int)*(n+1));
    tot = 0;
    memset(head,-1,sizeof(int)*(n+1));
    cur = 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(cin>>n)
    {
        init();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                cin>>map[i][j];

        for(int i=1;i<=n;++i)
        {
            for(int j=i+1;j<=n;++j)
                if(map[i][j]!=map[j][i])    // 简单筛查
                {
                    cout<<no<<endl;
                    fall = true;
                    break;
                }
                else elist[cur++] = {i,j,map[i][j]};
            if(fall) break;
        }
        if(fall) continue;

        sort(elist,elist+cur);
        const int ne = n-1<<1;

        for(int i=0;i<cur&&tot<ne;++i)      // Kruskal找树
        {
            int fu=father(elist[i].from),fv=father(elist[i].to);
            if(fu!=fv)
            {
                unite(fu,fv);
                addedge(elist[i]);
            }
        }
        for(int i=1;i<=n;++i) dfs(i,0,i,0); // 找i到所有点的距离

        for(int i=1;i<=n;++i)
        {
            for(int j=i+1;j<=n;++j)
                if(map[i][j]!=dis[i][j])    // 二度核对
                {
                    cout<<no<<endl;
                    fall = true;
                    break;
                }
            if(fall) break;
        }
        if(fall) continue;

        cout<<yes<<endl;
        for(int i=0;i<tot;i+=2)
            cout<<fstree[i].val<<endl;
    }

    return 0;
}

bool edge::operator<(const edge& rhs) const
{
    return val<rhs.val;
}

简单的说一下这个题目的具体实现：首先简单排查双向边的两个方向是否长度相等——因为题目只是保证了自环为0，而且确实需要这么扫一遍来构建题目所说的完全图；建图之后使用并查集跑一边Kruskal找到最小生成树的边存到新图（树）中。之后再以每一个顶点作为树根进行DFS，计算出所有定点对之间的距离并与输入进行核对即可。

主要就是想到这个最小生成树。完全图的点对之间，最短距离的路径一定在最小生成树上。想到这个之后写代码仔细点基本就没什么问题了…… 虽然说流程比较复杂，但是图论题，数据范围1e2，很显然复数算法折腾没毛病…… 不要怕啊。

后记

说是说写代码，但是这几轮真正考察到的算法硬知识都比较少，主要就是思维和……代码能力吧。而且有的题目即使可以想到可能的算法Tag，自己的实现也会是和答案千差万别，就还是缺乏训练，题目做少了的表现吧== 虽然说学习某些高级算法的时候有那样的万能感，实际上不会运用，连基本的题目也会卡住，大概就是现在的状态吧。毕竟高级算法可以看板子，解题能力和代码能力才是真正要训练的东西啊（）害！路漫漫啊==

虽说不太喜欢nowcoder这个网站但是这种感觉也还不错。认真的学习这几套题之后要尝试补一补Codeforces的div2/div3以及AtCoder的ABC/ARC了。用之前学化学的感觉来说，就是之前只是在瞎玩，现在大概来感觉了吧。虽然时间很迟，但是是时候做出努力了（）这方面来说我还是期待nowcoder之后的题的，下次还来==

不说了，一个寒假宅在家里都没碰luogu，名字都绿了，该刷题力（大悲