傳送門

文章目錄

• 題意：
• 思路：

題意：

給$n$個數，讓你構造一個盡可能大的矩陣，其中每個點所在的行和列都不含相等元素。

思路：

假設構造的答案矩陣大小為$a\times b$且$a<=b$，那么我們可以知道其中最大的相等元素的個數一定$<=a$，否則一定不能保證每行每列都不相等。
那么我們就可以$[1,n]$枚舉最大的出現次數即$a$，讓后假設選出的元素個數為$tot$，那么$b=?\frac{tot}{a}?$，讓后取一個最大的就行了。
現在知道矩陣大小$a\times b$了，下面考慮怎么構造答案。
這里直接盜了題解的圖了，順便先把構造方法說了。假設當前位置在$(x,y)$，那么下一個位置就是$((x+1)\mathrm{m}\mathrm{o}\mathrm{d}a,(y+1)\mathrm{m}\mathrm{o}\mathrm{d}b)$，當然如果$a?a$的矩陣的話，這樣寫會一直在主對角線上跑，我們特判一下當前位是否填過了，如果填過的話就$x=(x+1)\mathrm{m}\mathrm{o}\mathrm{d}a$即可。
其實一開始想到了這樣按照斜著填，但是不知道怎么走才能保證自己的想法能實現出來。
題解$((x+1)\mathrm{m}\mathrm{o}\mathrm{d}a,(y+1)\mathrm{m}\mathrm{o}\mathrm{d}b)$這樣很巧妙，如下面$4\times 6$的矩陣，填完$5,6$再填$7,8$的時候正好保證了這四個元素在不同的行。可以證明每個點所在的行和列都不含相等元素。

總結

以上是生活随笔為你收集整理的Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4) 构造的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。