江苏华柯建设发展有限公司网站,云服务器 做网站,seo 新老网站替换 域名不变,公司网站建设费怎么写分录题意#xff1a;给出m个n的全排列#xff0c;求一个n的全排列#xff0c;满足对于ij#xff0c;至少存在一半的全排列中#xff0c;ai排在aj的前面#xff0c;求字典序最小方案#xff0c;或者是无解。 (1)首先我们对 vis[ a[i] ][ a[j] ] ,求出a[i] 对 a[j] 的贡献…题意给出m个n的全排列求一个n的全排列满足对于ij至少存在一半的全排列中ai排在aj的前面求字典序最小方案或者是无解。 (1)首先我们对 vis[ a[i] ][ a[j] ] ,求出a[i] 对 a[j] 的贡献。对vis[i][j] 和 vis[j][i]是否大于 一半 ,若大于就建立一条边最后跑一边拓扑排序 (2)比赛的时候将大于j 的数插入 s[j] 的集合中然后对每一位进行筛选若当前位置的数没有比他大的则当前位置的数就为该数然后将这个数从s[i] (i 1 - n)中删除这个数 依次循环算的时间复杂度是0k*n*n n*n*log(n)没想到超时了 比赛结束后改成用树状数组维护AC .... 没想到STL 时间复杂度真的是高 拓扑排序 AC code #include bits/stdc.husing namespace std;const int N 1e3 10;int vis[N][N],a[N],in[N],ans[N],n;vectorintedge[N];int topu()
{int cont0;priority_queueint,vectorint,greaterint Q;for(int i1; in; i)if(in[i]0)Q.push(i);while(!Q.empty()){int uQ.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(contn)return false;return true;
}
int main()
{int m;while(~scanf(%d%d,n,m)nm){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 j1;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超时代码 #include bits/stdc.husing namespace std;const int N 1e3 10;int vis[N][N],a[N],vised[N];
setints[N];
int main()
{int n,m;while(~scanf(%d%d,n,m)nm){for (int i1;in;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 j1;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;
} 树状数组AC code: #include bits/stdc.h
#define IT setint::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)nm){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 j1;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;
} 转载于:https://www.cnblogs.com/lemon-jade/p/9600802.html
