UVA 1592 Database

布满荆棘的人生 2021-11-01 06:18 249阅读 0赞

题目链接：[https://vjudge.net/problem/UVA-1592][https_vjudge.net_problem_UVA-1592]

题目翻译摘自《算法禁赛入门经典》

### 题目大意 ###

输入一个 n 行 m 列的数据库（1 ≤ n ≤ 10000，1 ≤ i ≤ 10），是否存在两个不同行 r1，r2 和两个不同列 c1，c2，使得每列的两个单元格相同（即（r1，c1）和（r2，c1）相同，（r1，c2）和 （r2，c2）相同）。

### 分析 ###

暴力枚举复杂度为$O(n^2 \* m^2)$，会超时，这里我们可以只枚举列，然后把每一行对应的两个单元格放到有序表里，如果有重复，就说明找到了，时间复杂度为$O(n \* \\log n \* m^2)$。

### 代码如下 ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 using namespace std;
      3  
      4 #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
      5 #define Rep(i,n) for (int i = 0; i < (n); ++i)
      6 #define For(i,s,t) for (int i = (s); i <= (t); ++i)
      7 #define rFor(i,t,s) for (int i = (t); i >= (s); --i)
      8 #define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i)
      9 #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i)
     10 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
     11 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)
     12  
     13 #define pr(x) cout << #x << " = " << x << "  "
     14 #define prln(x) cout << #x << " = " << x << endl
     15  
     16 #define LOWBIT(x) ((x)&(-x))
     17  
     18 #define ALL(x) x.begin(),x.end()
     19 #define INS(x) inserter(x,x.begin())
     20  
     21 #define ms0(a) memset(a,0,sizeof(a))
     22 #define msI(a) memset(a,inf,sizeof(a))
     23 #define msM(a) memset(a,-1,sizeof(a))
     24 
     25 #define MP make_pair
     26 #define PB push_back
     27 #define ft first
     28 #define sd second
     29  
     30 template<typename T1, typename T2>
     31 istream &operator>>(istream &in, pair<T1, T2> &p) {
     32     in >> p.first >> p.second;
     33     return in;
     34 }
     35  
     36 template<typename T>
     37 istream &operator>>(istream &in, vector<T> &v) {
     38     for (auto &x: v)
     39         in >> x;
     40     return in;
     41 }
     42  
     43 template<typename T1, typename T2>
     44 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) {
     45     out << "[" << p.first << ", " << p.second << "]" << "\n";
     46     return out;
     47 }
     48 
     49 inline int gc(){
     50     static const int BUF = 1e7;
     51     static char buf[BUF], *bg = buf + BUF, *ed = bg;
     52     
     53     if(bg == ed) fread(bg = buf, 1, BUF, stdin);
     54     return *bg++;
     55 } 
     56 
     57 inline int ri(){
     58     int x = 0, f = 1, c = gc();
     59     for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
     60     for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
     61     return x*f;
     62 }
     63 
     64 template<class T>
     65 inline string toString(T x) {
     66     ostringstream sout;
     67     sout << x;
     68     return sout.str();
     69 }
     70  
     71 typedef long long LL;
     72 typedef unsigned long long uLL;
     73 typedef pair< double, double > PDD;
     74 typedef pair< int, int > PII;
     75 typedef pair< int, PII > PIPII;
     76 typedef pair< string, int > PSI;
     77 typedef pair< int, PSI > PIPSI;
     78 typedef set< int > SI;
     79 typedef set< PII > SPII;
     80 typedef vector< int > VI;
     81 typedef vector< VI > VVI;
     82 typedef vector< SI > VSI;
     83 typedef vector< PII > VPII;
     84 typedef map< int, int > MII;
     85 typedef map< int, string > MIS;
     86 typedef map< int, PII > MIPII;
     87 typedef map< PII, int > MPIII;
     88 typedef map< string, int > MSI;
     89 typedef map< string, string > MSS;
     90 typedef map< PII, string > MPIIS;
     91 typedef map< PII, PII > MPIIPII;
     92 typedef multimap< int, int > MMII;
     93 typedef multimap< string, int > MMSI;
     94 //typedef unordered_map< int, int > uMII;
     95 typedef pair< LL, LL > PLL;
     96 typedef vector< LL > VL;
     97 typedef vector< VL > VVL;
     98 typedef priority_queue< int > PQIMax;
     99 typedef priority_queue< int, VI, greater< int > > PQIMin;
    100 const double EPS = 1e-10;
    101 const LL inf = 0x7fffffff;
    102 const LL infLL = 0x7fffffffffffffffLL;
    103 const LL mod = 1e9 + 7;
    104 const int maxN = 1e4 + 7;
    105 const LL ONE = 1;
    106 const LL evenBits = 0xaaaaaaaaaaaaaaaa;
    107 const LL oddBits = 0x5555555555555555;
    108 
    109 struct Line{
    110     int id;
    111     VI a;
    112     
    113     Line() {}
    114     Line(int x) : id(x) {}
    115     
    116     int operator[] (const int x) const {
    117         return a[x];
    118     }
    119 };
    120 
    121 int n, m;
    122 MSI str_id;
    123 int len;
    124 string str;
    125 
    126 int main(){
    127     //freopen("MyOutput.txt","w",stdout);
    128     //freopen("input.txt","r",stdin);
    129     //INIT();
    130     while(~scanf("%d %d\n", &n, &m)) {
    131         vector< Line > vL;
    132         bool ans = true;
    133         
    134         For(i, 1, n) {
    135             Line t(i);
    136             
    137             For(j, 1, m) {
    138                 getline(cin, str, ",\n"[j == m]);
    139                 if(str_id.find(str) == str_id.end()) {
    140                     str_id[str] = ++len;
    141                     t.a.PB(len);
    142                 }
    143                 else t.a.PB(str_id[str]);
    144             }
    145             vL.PB(t);
    146         }
    147         
    148         PII r, c;
    149         // 枚举列，保存成映射 
    150         For(i, 1, m) {
    151             For(j, i + 1, m) {
    152                 MPIII mpii;
    153                 For(k, 1, n) {
    154                     PII tmp = MP(vL[k - 1][i - 1], vL[k - 1][j - 1]);
    155                     if(mpii.find(tmp) != mpii.end()) {
    156                         r = MP(mpii[tmp], k);
    157                         c = MP(i, j);
    158                         ans = false;
    159                         goto Dark_Souls;
    160                     }
    161                     else mpii[tmp] = k;
    162                 }
    163             }
    164         }
    165         
    166         Dark_Souls: {
    167             if(ans) cout << "YES" << endl;
    168             else {
    169                 cout << "NO" << endl;
    170                 cout << r.ft << " " << r.sd << endl;
    171                 cout << c.ft << " " << c.sd << endl;
    172             }
    173         }
    174     }
    175     return 0;
    176 }

转载于:https://www.cnblogs.com/zaq19970105/p/11052883.html

[https_vjudge.net_problem_UVA-1592]: https://vjudge.net/problem/UVA-1592
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/eadff12404f947c5aa12a06d5da7c8c6.png