首页 > 代码库 > UVa 1597-Searching the Web
UVa 1597-Searching the Web
这个题比较长,如果按照题目要求一步一步做的话。也不是很难。但是如果想提高代码精简度和可读性高效性确实不容易,想轻松AC还是用C++,C语言的输入输出。Java很容易超时。普通算法要10s左右。
Java代码 :
import java.util.*; public class Main1597 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int t = scan.nextInt(); String s = scan.nextLine(); String[][] str = new String[105][1500]; int[] row = new int[t]; Arrays.fill(row, 0); for(int i=0; i<t; i++) { while(true) { str[i][row[i]] = scan.nextLine(); if(str[i][row[i]].equals("**********")) { break; } row[i] ++; } } int n = scan.nextInt(); String ss = scan.nextLine(); for(int j=0; j<n; j++) { String line = scan.nextLine(); String[][] ans = new String[t][1000]; int[] cnt = new int[1000]; Arrays.fill(cnt, 0); if(line.contains(" AND ")) { int end = 0; while(line.charAt(end)!=' ')end ++; String A = line.substring(0, end); String B = line.substring(end+5, line.length()); for(int i=0; i<t; i++) { int a = 0, b = 0; for(int r=0; r<row[i]; r++) { if(str[i][r].toLowerCase().contains(A)) { a = 1; } if(str[i][r].toLowerCase().contains(B)) { b = 1; } } if(a==1 && b==1) { for(int r=0; r<row[i]; r++) { if(str[i][r].toLowerCase().contains(A) || str[i][r].toLowerCase().contains(B)) { ans[i][cnt[i]++] = str[i][r]; } } } } }else if(line.contains(" OR ")) { int end = 0; while(line.charAt(end)!=' ')end ++; String A = line.substring(0, end); String B = line.substring(end+4, line.length()); for(int i=0; i<t; i++) { for(int r=0; r<row[i]; r++) { if(str[i][r].toLowerCase().contains(A) || str[i][r].toLowerCase().contains(B)) { ans[i][cnt[i]++] = str[i][r]; } } } }else if(line.contains("NOT ")) { int end = 0; while(line.charAt(end)!=' ')end ++; //String A = line.substring(0, end); String B = line.substring(4, line.length()); for(int i=0; i<t; i++) { int con = 0; for(int r=0; r<row[i]; r++) { if(!str[i][r].toLowerCase().contains(B)) { //ans[i][cnt[i]++] = str[i][r]; con ++; } } if(con == row[i]) { for(int r=0; r<row[i]; r++) { ans[i][cnt[i]++] = str[i][r]; } } } }else { for(int i=0; i<t; i++) { for(int r=0; r<row[i]; r++) { if(str[i][r].toLowerCase().contains(line)) { ans[i][cnt[i]++] = str[i][r]; } } } } int flag = 0, m = 0; for(int k=0; k<t; k++) { if(m > 0 && cnt[k] != 0) System.out.println("----------"); for(int l=0; l<cnt[k]; l++) { //System.out.println("----------"); System.out.println(ans[k][l]); flag = 1; m ++; } } if(flag == 0) System.out.println("Sorry, I found nothing."); System.out.println("=========="); } } }
来自互联网的C++代码 :
//{头文件模板 #include <algorithm> #include <bitset> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> using namespace std; //}头文件模板 #define rep(i,b) for(int i=0; i<(b); i++) #define foreach(i,a) for(__typeof((a).begin()) i=a.begin(); i!=(a).end(); ++i) #define FOR for (int j = limit[i]; j < limit[i + 1]; j++) typedef bool Bit[1505]; int n, lines, m; // n文档数, lines行数, m请求数 int limit[105]; // limit[i]: 第i篇文档从第几行开始 string doc[1505]; // 存储内容 map<string, Bit> Index; // Index[单词]: B标记了哪些行出现过 // 用s来更新Index void upDate(string s, int p) { string word; foreach(it, s) { if (isalpha(*it)) *it = tolower(*it); // 变小写 else *it = ' '; // 非字母变空白 } stringstream ss(s); while (ss >> word) Index[word][p] = true; } int main() { //{section: 文档数据输入 scanf("%d ", &n); rep(i, n) { limit[i] = lines; while (getline(cin, doc[lines]), doc[lines] != "**********") { upDate(doc[lines], lines); lines++; } } limit[n] = lines;//} //{section: 对获取的请求输出对应的内容 string s; // s存储每次得到的请求 Bit mark; //{记录哪些行应该输出 //}mark的解释: 因为每篇文档要用10个'-'隔开,比较麻烦,最后统一处理 bool *A, *B; scanf("%d ", &m); for (int iii = 0; iii < m; iii++) { getline(cin, s); //{subsection: 计算出mark中介 if (s[0] == 'N') { A = Index[s.substr(4)]; rep(i, n) { bool logo = true; FOR if (A[j]) { logo = false; break; } FOR mark[j] = logo; } } else if (s.find("AND") != string::npos) { int p = s.find(" AND "); A = Index[s.substr(0, p)]; B = Index[s.substr(p + 5)]; memset(mark, 0, sizeof(mark)); bool hasA, hasB; // 在同一文章中, 两个词是否都出现 rep(i ,n) { hasA = hasB = false; // 默认没出现 FOR if (A[j]) { hasA = true; break; } FOR if (B[j]) { hasB = true; break; } if (!(hasA&&hasB)) continue; FOR mark[j] = (A[j] || B[j]); } } else if (s.find("OR") != string::npos) { int p = s.find(" OR "); A = Index[s.substr(0, p)]; B = Index[s.substr(p + 4)]; rep(i, lines) mark[i] = (A[i] || B[i]); } else memcpy(mark, Index[s], sizeof(mark));//} //{subsection: 输出mark bool hasOut = false, needOut = false; // 记录上一轮是否有输出文档 rep(i, n) { if (hasOut) needOut = true; hasOut = false; FOR if (mark[j]) { if (needOut) { cout << "----------\n"; needOut = false; } cout << doc[j] << "\n"; hasOut = true; } } if (!(needOut||hasOut)) cout << "Sorry, I found nothing.\n"; cout << "==========\n";//} }//} return 0; }
UVa 1597-Searching the Web
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。