題意：給出m個(gè)n的全排列，求一個(gè)n的全排列，滿(mǎn)足對(duì)于i<j，至少存在一半的全排列中，ai排在aj的前面，求字典序最小方案，或者是無(wú)解。

?

(1)首先我們對(duì) vis[ a[i] ][ a[j] ]++ ,求出a[i] 對(duì) a[j] 的貢獻(xiàn)。對(duì)vis[i][j] 和 vis[j][i]是否大于 一半 ,若大于就建立一條邊，最后跑一邊拓?fù)渑判?/p>

(2)比賽的時(shí)候，將大于j 的數(shù)插入 s[j] 的集合中，然后對(duì)每一位進(jìn)行篩選，若當(dāng)前位置的數(shù)沒(méi)有比他大的，則當(dāng)前位置的數(shù)就為該數(shù)，然后將這個(gè)數(shù)從s[i] (i = 1 - > n)中刪除這個(gè)數(shù)

依次循環(huán)，算的時(shí)間復(fù)雜度是0（k*n*n + n*n*log(n)），沒(méi)想到超時(shí)了

?

?

比賽結(jié)束后，改成用樹(shù)狀數(shù)組維護(hù)，AC? ....? 沒(méi)想到STL 時(shí)間復(fù)雜度真的是高

?

拓?fù)渑判?AC code

#include <bits/stdc++.h>using namespace std;const int N = 1e3 + 10;int vis[N][N],a[N],in[N],ans[N],n;vector<int>edge[N];int topu() {int cont=0;priority_queue<int,vector<int>,greater<int> >Q;for(int i=1; i<=n; i++)if(in[i]==0)Q.push(i);while(!Q.empty()){int u=Q.top();Q.pop();cont++;ans[cont] = u;for(int i = 0 ;i < edge[u].size(); i++){int v = edge[u][i];if(--in[v]==0)Q.push(v);}}if(cont<n)return false;return true; } int main() {int m;while(~scanf("%d%d",&n,&m)&&n&&m){memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++)scanf("%d",&a[j]);for(int j = 1;j <= n;j++)for(int k = j+1;k <= n;k++)vis[a[j]][a[k]]++;}for(int i = 1; i <= n;i++)for(int j = i + 1;j <= n;j++){if(vis[i][j] > vis[j][i]) edge[i].push_back(j),in[j]++;else if(vis[i][j] < vis[j][i]) edge[j].push_back(i),in[i]++;}if(topu()){for(int i = 1;i <= n;i++)printf("%d%c",ans[i],i == n?'\n':' ');}elseputs("No solution");for(int i = 1;i <= n;i++)edge[i].clear();}return 0; }

?

set超時(shí)代碼：

#include <bits/stdc++.h>using namespace std;const int N = 1e3 + 10;int vis[N][N],a[N],vised[N]; set<int>s[N]; int main() {int n,m;while(~scanf("%d%d",&n,&m)&&n&&m){for (int i=1;i<=n;i++)s[i].clear();memset(vis,0,sizeof(vis));memset(vised,0,sizeof(vised));for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++)scanf("%d",&a[j]);for(int j = 1;j <= n;j++)for(int k = j+1;k <= n;k++)vis[a[j]][a[k]]++;}for(int i = 1; i <= n;i++)for(int j = i + 1;j <= n;j++){if(vis[i][j] > m/2) vis[i][j] = 1,vis[j][i] = 0,s[j].insert(i);else if(vis[j][i] > m/2) vis[j][i] = 1,vis[i][j] = 0,s[i].insert(j);else vis[i][j] = vis[j][i] = 0;}int ans[N],tot = 1;while(tot <= n){int flag = 0,now = 0;for(int i = 1;i <= n;i++){if(!vised[i]){if(s[i].empty()){flag = 1;now = i;break;}}}if(!flag) break;ans[tot] = now;vised[now] = 1;for(int i = 1;i <= n;i++)if(s[i].find(now) != s[i].end())s[i].erase(s[i].find(now));tot++;}if(tot <= n) puts("No solution");else{for(int i = 1;i <= n;i++)printf("%d%c",ans[i],i == n?'\n':' ');}}return 0; }

?

樹(shù)狀數(shù)組AC code:

#include <bits/stdc++.h> #define IT set<int>::iteratorusing namespace std;const int N = 1e3 + 10;int vis[N][N],a[N],vised[N],c[N][N],n;int lowbit(int x){ return x&(-x);} void update(int pos,int x,int y) {while(x <= n){c[pos][x] += y;x += lowbit(x);} }int query(int pos,int x) {int ans = 0;while(x){ans += c[pos][x];x -= lowbit(x);}return ans; } int main() {int m;while(~scanf("%d%d",&n,&m)&&n&&m){memset(c,0,sizeof(c));memset(vis,0,sizeof(vis));memset(vised,0,sizeof(vised));for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++)scanf("%d",&a[j]);for(int j = 1;j <= n;j++)for(int k = j+1;k <= n;k++)vis[a[j]][a[k]]++;}for(int i = 1; i <= n;i++)for(int j = i + 1;j <= n;j++){if(vis[i][j] > vis[j][i]) vis[i][j] = 1,vis[j][i] = 0,update(j,i,1);else if(vis[j][i] > vis[i][j]) vis[j][i] = 1,vis[i][j] = 0,update(i,j,1);else vis[i][j] = vis[j][i] = 0;}int ans[N],tot = 1;while(tot <= n){int flag = 0,now = 0;for(int i = 1;i <= n;i++){if(!vised[i]){if(!query(i,n)){flag = 1;now = i;break;}}}if(!flag) break;ans[tot] = now;vised[now] = 1;for(int i = 1;i <= n;i++){if(vis[now][i])update(i,now,-1);}tot++;}if(tot <= n) puts("No solution");else{for(int i = 1;i <= n;i++)printf("%d%c",ans[i],i == n?'\n':' ');}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lemon-jade/p/9600802.html

總結(jié)

以上是生活随笔為你收集整理的MicroRNA Ranking（Tehran2016）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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