笔试-360-180827

• 40 道选择题，范围包括大学所有课程...
• 3 道编程题

城市修建

题目描述

有一个城市需要修建，给你N个民居的坐标X,Y，
问把这么多民居全都包进城市的话，城市所需最小面积是多少
（注意，城市为平行于坐标轴的正方形）

输入
  第一行为N，表示民居数目（2≤N≤1000）
  下面为N行，每行两个数字Xi，Yi，表示该居民的坐标（-1e9≤xi,yi≤1e9）
输出
  城市所需最小面积

样例输入
2
0 0
2 2
样例输出
4

思路

• 找出最大长/宽即可

Python（AC）

n = int(input())

xs = []
ys = []
for i in range(n):
    x, y = list(map(int, input().split()))
    xs.append(x)
    ys.append(y)

min_x = min(xs)
max_x = max(xs)
xx = max_x - min_x

min_y = min(ys)
max_y = max(ys)
yy = max_y - min_y

tt = max(xx, yy)
print(tt ** 2)

看花

题目描述

小明有一个花园，花园里面一共有m朵花，对于每一朵花，都是不一样的，小明用1～m中的一个整数表示每一朵花。
他很喜欢去看这些花，有一天他看了n次，并将n次他看花的种类是什么按照时间顺序记录下来。
记录用a[i]表示，表示第i次他看了a[i]这朵花。
小红很好奇，她有Q个问题,问[l,r]的时间内，小明一共看了多少朵不同的花儿，
小明因为在忙着欣赏他的花儿，所以想请你帮他回答这些问题。

输入
  输入两个数n,m;(1<=n<=2000,1<=m<=100);分别表示n次看花，m表示一共有m朵花儿。
  接下来输入n个数a[1]~a[n]，a[i]表示第i次，小明看的花的种类;
  输入一个数Q(1<=Q<=1000000);表示小红的问题数量。
  输入Q行 每行两个数 l,r(1<=l<=r<=n); 表示小红想知道在第l次到第r次，小明一共看了多少不同的花儿。
输出
  一共Q行
  每一行输出一个数 表示小明在[l,r]的时间内看了多少种花。

样例输入
5 3
1 2 3 2 2
3
1 4
2 4
1 5
样例输出
3
2
3

思路

• 打表

Python（29%）

n, m = list(map(int, input().split()))

ns = list(map(int, input().split()))

Q = int(input())
lrs = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    print(len(set(ns[l - 1: r - 1])))

C++（57%）

Java 相同做法可 AC

#include <bits/stdc++.h>
using namespace std;

int main() {

int n, m;
cin >> n >> m;
vector<int> ns(n+1, 0);
for (int i=1; i<=n; i++)
      cin >> ns[i];

int Q;
cin >> Q;
set<int> tmp;
for (int i=0; i<Q; i++) {
    int l, r;
    cin >> l >> r;
    for (int k=l; k<=r; k++)
        tmp.insert(ns[k]);
    cout << tmp.size() << endl;
    tmp.clear();
}

return 0;

}

## Array（选做）
**题目描述**

小红有两个长度为n的排列A和B。每个排列由[1,n]数组成，且里面的数字都是不同的。 现在要找到一个新的序列C，要求这个新序列中任意两个位置(i,j)满足: 如果在A数组中C[i]这个数在C[j]的后面，那么在B数组中需要C[i]这个数在C[j]的前面。 请问C序列的长度最长为多少呢？

输入 第一行一个整数，表示N。 第二行N个整数，表示A序列。 第三行N个整数，表示B序列。 满足:N<=50000 输出 输出最大的长度

样例输入 5 1 2 4 3 5 5 2 3 4 1 样例输出 2（正确答案好像应该为 4）

**思路**
- 最长上升子序列（？）
- 最长公共子序列：将第二个序列逆转后，相当于求两个序列的最长公共子序列

1 2 4 3 5 1 4 3 2 5 <- 5 2 3 4 1

最长公共子序列 {1 4 3 5}

**Python**（18%）

print(0) # 0% print(2) # 18% print(3) # 0% print(4) # 9%