首页 > 代码库 > topcoder srm 702 div1 -23

topcoder srm 702 div1 -23

2024-09-14 22:39:08   207人阅读

1、给定一个$n*m$的矩阵，里面的数字是1到$n*m$的一个排列。一个$n*m$矩阵$A$对应一个$n*m$ 的01字符串，字符串的位置$i*m+j$为1当且仅当$A_{i,j}=i*m+j+1$。现在可以交换矩阵的两列或者两行。在任意多次操作后使得矩阵对应的字符串最大？

思路：从1到$n*m$，依次枚举。每次将当前数字填回正确位置。比较该次操作前后是否变大。不变大则不做本次操作。

#include <stdio.h>#include <vector>#include <string>using namespace std;class GridSortMax{    int a[55][55];    int b[55][55];    int N,M;    void reset(int t) {        for(int i=0;i<N;++i) for(int j=0;j<M;++j) {            if(t==0) b[i][j]=a[i][j];            else a[i][j]=b[i][j];        }    }    pair<int,int> get(int t) {        for(int i=0;i<N;++i) {            for(int j=0;j<M;++j) {                if(a[i][j]==t) return make_pair(i,j);            }        }    }    void swapCol(int y1,int y2) {        for(int i=0;i<N;++i) swap(a[i][y1],a[i][y2]);    }    void swapRow(int x1,int x2) {        for(int i=0;i<M;++i) swap(a[x1][i],a[x2][i]);    }    string getAns() {        string s="";        for(int i=0;i<N;++i) for(int j=0;j<M;++j) {            if(a[i][j]==i*M+j+1) s+="1";            else s+="0";        }        return s;    }public:    string findMax(int n,int m,vector<int> grid)    {        for(int i=0;i<n;++i) {            for(int j=0;j<m;++j) {                a[i][j]=grid[i*m+j];            }        }        N=n;        M=m;        for(int i=1;i<=n*m;++i) {            pair<int,int> p=get(i);            int x=p.first;            int y=p.second;            int xx=(i-1)/m;            int yy=(i-1)%m;            if(x==xx&&y==yy) continue;            string s0=getAns();            reset(0);            if(x!=xx) swapRow(x,xx);            if(y!=yy) swapCol(y,yy);            string s1=getAns();            if(s1<s0) reset(1);        }        return getAns();    }};

　　

topcoder srm 702 div1 -23


联系
我们