題目鏈接

http://codeforces.com/contest/1276/problem/C

題解

嗯，比賽結(jié)束前3min想到做法然后rush不出來了……比賽結(jié)束后又寫了15min才過……
以下是我的做法：
設(shè)最優(yōu)解的行數(shù)和列數(shù)分別是\(R\)和\(C\), 不妨設(shè)\(R\le C\). 那么顯然對于每個(gè)數(shù)我們只能選不超過\(R\)個(gè)。
考慮將所有數(shù)按出現(xiàn)次數(shù)從大到小排序，枚舉\(R\), 求出可用的數(shù)的個(gè)數(shù)，設(shè)為\(cnt\), 那么顯然\(C\le \frac{cnt}{R}\).
我們可以通過構(gòu)造的方式證明，\(C\)可以取到\(\lfloor\frac{cnt}{R}\rfloor\).
下面為了方便默認(rèn)\(cnt\)已經(jīng)去掉了\(\mod R\)的余數(shù)。
把所有數(shù)按出現(xiàn)次數(shù)從大到小的順序依次連成一個(gè)序列（一個(gè)數(shù)出現(xiàn)了多少次就復(fù)制多少個(gè)）。那么對于任意\(0\le x\lt R,0\le y\lt C\), 我們將序列的第\((xC+y)\)個(gè)數(shù)放到矩陣的第\(y\)行第\((x+y)\mod C\)列, 其中序列和矩陣的坐標(biāo)均從\(0\)開始。這樣我們可以證明一定滿足條件。
舉例解釋一下: 假設(shè)有\(12\)個(gè)數(shù)排成\(3\times 4\)的矩陣，那么矩陣中每個(gè)數(shù)在原序列中的下標(biāo)為:

0 3 6 9 10 1 4 7 8 11 2 5

正確性證明: 對于同一種數(shù)，顯然它在序列中的位置滿足要么所有的\(x\)都相同，要么是\(x\)的一個(gè)后綴和\((x+1)\)的一段前綴拼起來，且長度不超過\(R\).
如果是前者，正確性顯然。如果是后者，唯一可能影響正確性的情況就是\(x\)后綴部分的某個(gè)數(shù)和\(y\)前綴部分的某個(gè)數(shù)放到了同一列上。
顯然這種情況只有出現(xiàn)次數(shù)等于\(R\)時(shí)才會出現(xiàn)（因?yàn)槊看问钦w右移一列），而因?yàn)槲覀兪前闯霈F(xiàn)次數(shù)從大到小排序構(gòu)造排列，所以出現(xiàn)次數(shù)為\(R\)的都被放到了序列最前面，此時(shí)因?yàn)榍懊嬉呀?jīng)放了的個(gè)數(shù)都是\(R\)的倍數(shù)，所以這一個(gè)一定從第\(0\)行開始放，屬于第一種情況。因此第二種情況不會出現(xiàn)此問題，證畢。
故枚舉每個(gè)\(R\), 求出對應(yīng)的\(C\), 取最大值，再對取到最大值的\(R\)執(zhí)行上述構(gòu)造算法即可。
時(shí)間復(fù)雜度\(O(n\log n)\), 瓶頸在于離散化后統(tǒng)計(jì)每個(gè)數(shù)出現(xiàn)多少次。

代碼

由于是很不冷靜地rush出來的所以寫得比較亂……

#include<bits/stdc++.h> #define llong long long #define pii pair<int,int> #define mkpr make_pair using namespace std;inline int read() {int w=1,s=0;char ch=getchar();while(!isdigit(ch)) {if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)) {s=s*10+ch-'0';ch=getchar();}return w*s; }const int N = 1e6; pii num[N+3]; int cans[N+3]; int fans[N+3]; vector<int> disc; int a[N+3]; int n,wei;int gcd(int x,int y) {return y==0?x:gcd(y,x%y);}int main() {scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%d",&a[i]),disc.push_back(a[i]);sort(disc.begin(),disc.end()); disc.erase(unique(disc.begin(),disc.end()),disc.end());for(int i=1; i<=n; i++) a[i] = lower_bound(disc.begin(),disc.end(),a[i])-disc.begin()+1;for(int i=1; i<=n; i++) num[i].second = i;for(int i=1; i<=n; i++) num[a[i]].first++;sort(num+1,num+n+1);int l = 1,r = 0,cnt = 0,ans = 0,mxr = 1;for(int i=1; i<=n; i++){while(l<=n && num[l].first<i) {l++;}cnt += n-l+1;if(cnt/i<i) break;int cur = cnt/i*i;if(cur>ans) {ans = cur; mxr = i;}}int mxc = ans/mxr;printf("%d\n%d %d\n",ans,mxr,mxc);l = 1; while(l<=n && num[l].first<1) {l++;}int x = 0,y = 0; wei = 0;for(int i=n; i>=l; i--){int cnt = min(num[i].first,mxr);for(int j=1; j<=cnt&&wei<=ans; j++,wei++){cans[x*mxc+(x+y)%mxc] = disc[num[i].second-1]; x++; if(x==mxr) {y++,x=0;}}}for(int i=0; i<ans; i++){printf("%d ",cans[i]);if((i+1)%mxc==0) puts("");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces 1276C/1277F Beautiful Rectangle (构造)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。