算法竞赛入门经典习题3-9子序列(uva10340)

发布网友 发布时间：2022-04-10 23:17

我来回答

共2个回答

懂视网 时间：2022-04-11 03:38

（二）样例输出

NO
2 3　　//这两行中出现数据冗余
2 3　　//冗余出现在上面两行的这两列中
YES

二：代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> split(string source, string pattern)
{
 vector<string> res;
 int spos = 0, epos, p_len = pattern.length() - 1,s_len = source.length()-1;
 source += pattern;
 char col = ‘1‘;
 while (spos<s_len && (epos = source.find(pattern,spos))&&epos!=string::npos)
 {
 stringstream stream;
 stream << col++;　　//在末尾加上列号，可以防止出现因为不同列数据重复现象
 res.push_back((source.substr(spos, epos - spos)).append(stream.str()));
 spos = epos + 1;
 }
 return res;
}

int main()
{
 FILE *fp = freopen("data5_9.in", "r", stdin);
 freopen("data5_9.out", "w", stdout);

 string line;
 int row, col;

 while ((cin >> row)&&row!=0)
 {
 //获取行列数
 cin >> col;

 vector<string> str_vec;
 set<string> str_set;
 map<string, int> str_map;
 vector<int> res; //保存两行，一列重复

 for (int r = 1; r <= row; r++)
 {
  getchar();
  getline(cin, line); //重点使用
  
  str_vec = split(line, ","); //由于没有split字符串分割函数，使用find和substr进行分割
  
  vector<string>::iterator iter = str_vec.begin(); //进行迭代插入
  int c = 1;
  for (; iter != str_vec.end(); iter++)
  {
  if (!str_set.count(*iter))
  {
   str_set.insert(*iter);
   str_map[*iter] = r * 10 + c++;
  }
  else //出现同一列重复
  {
   int r_r = (str_map[*iter] / 10)*10 + r;　　//23表示第2,3行重复
   res.push_back(r_r*10+c++); //将重复的行列添加到res映射中
  }
  }
 }

 if (res.empty()) //进行结果输出
  cout << "YES" << endl;
 else
 {
  cout << "NO" << endl;
  int r_r = res.front();
  cout << r_r / 100 << ‘ ‘ << r_r / 10 % 10 << endl; //输出行
  for (vector<int>::iterator it = res.begin(); it != res.end(); it++)
  cout << *it % 10 << " "; //输出列
  cout << endl;
 }
 }

 freopen("CON", "r", stdin);
 freopen("CON", "w", stdout);
 return 0;
}

算法习题---5.9数据库（Uva1592）

标签：不同   int   cin   iostream   begin   检测   算法   append   mpi   

热心网友 时间：2022-04-11 00:46