360笔试编程交流（第二题没A，求解）

想问下楼主，第三题，这么用LIS处理，还是没明白，可以的话，给贴个代码

献上我一次性AC的代码，第二题看花的题目 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); int m = scanner.nextInt(); int[] watch = new int[n+1]; int i = 1; while (i < n+1) { watch[i++] = scanner.nextInt(); } int q = scanner.nextInt(); i = 0; int[][] questions = new int[q][2]; while (i < q) { questions[i][0] = scanner.nextInt(); questions[i][1] = scanner.nextInt(); i++; } processData(watch, questions, n); } } public static void processData(int[] watch, int[][] ques, int n) { Set<Integer> flours = null; for (int i = 0; i < ques.length; i++) { int start = ques[i][0]; int end = ques[i][1]; if (start < 1) start = 1; if (end > n) end = n; flours = new HashSet<>(); while (start <= end) { flours.add(watch[start++]); } System.out.println(flours.size()); } }

第二题看数据量直接暴力就可以过啊2000×2000的预处理

 #include <iostream>  #include <vector>  #include <algorithm>  using namespace std;  bool is_had(vector<int> v, size_t i, size_t j) {     for (size_t m = i; m < j; ++m) {        if (v[m] == v[j])         return true;      }      return false;  }  int dp[2000][2000] = { 0 };  int main()   {      int n = 0;      int m = 0;      cin >> n >> m;      vector<int> v;      int tmp = 0;      for (size_t i = 0; i < n; ++i) {          cin >> tmp;          v.push_back(tmp);      }      size_t q = 0;      cin >> q;      vector<vector<int> >res;      int tmp2;      for (size_t i = 0; i < q; ++i) {          vector<int> t;          cin >> tmp >> tmp2;          t.push_back(tmp);          t.push_back(tmp2);          res.push_back(t);      }      for (size_t i = 0; i < n; ++i)          dp[i][i] = 1;      for (size_t i = 0; i < n; ++i) {          for (size_t j = i + 1; j < n; ++j) {              if (is_had(v, i, j))                  dp[i][j] = dp[i][j - 1];              else                  dp[i][j] = dp[i][j - 1] + 1;          }      }      for (size_t i = 0; i < q; ++i) {          cout << dp[res[i][0] - 1][res[i][1] - 1] << endl;      }      return 0;  } 有什么问题啊。。。。求告知

第二题一开始和老哥想的一样，只过了29%，然后发现这是个假算法。。。 比如 4 3 1 2 2 2 3 1 3 3 按照这个思路得到的结果是 0，但是答案显然是 1 所以。。还是直接暴力吧。。 我选择题花太长时间了，然后第三题。。刚写了个 lcs 还没来得及交就到时间了。。 心酸。。

第二题不要用***树麽。。。

第二题set去重直接A了 public class Main2 { private static Scanner sc = new Scanner(System.in); public static void main(String[] args) { String[] str1 = sc.nextLine().split(" "); int n = Integer.valueOf(str1[0]); int m = Integer.valueOf(str1[1]); String[] str2 = sc.nextLine().split(" "); int[] arrA = new int[n]; for(int i = 0; i < n; ++i) { arrA[i] = Integer.valueOf(str2[i]); } int Q = Integer.valueOf(sc.nextLine().split(" ")[0]); for(int i = 0; i< Q; ++i) { int l = sc.nextInt(); int r = sc.nextInt(); Set<Integer> set = new HashSet<>(); for(int j = l - 1; j < r; j++) { set.add(arrA[j]); } System.out.println(set.size()); } } }

哪里错了，提示是超时 int main() {     int n, m, q;     int count = 0;     set<int> s;     cin >> n >> m;     vector<int> vec;     for (int i = 0; i<n; ++i) {         int k = 0;         cin >> k;         if (s.count(k) == 0) {             s.insert(k);             ++count;         }         vec.push_back(count);     }     cin >> q;     for (int i = 0; i<q; ++i) {         int t1, t2;         cin >> t1 >> t2;         int res = 1 + vec[t2 - 1] - vec[t1 - 1];         cout << res << endl;     }     return 0; }

开始我一直86，但是如果花的种数是1的话可以直接输出1了。然后a了

第二题要考虑left和right中间，包含left左边的情况，去重可以a，但是感觉不对。

第二题用Set去重就A了啊

大佬，你可能把第二题想复杂了，就是个区间内不重复的值有几个的问题。map去重即可。

cin cout 改成 C 语言的输入输出。

第3题 是公共子串 还是最长公共子序列？ 求具体解释~

一样的第二个方法，没有A