试题 G: 外卖店优先级（A,B组G题）
时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
【问题描述】
“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0;而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中;如果 优先级小于等于 3，则会被清除出优先缓存。
给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优 先缓存中。
【输入格式】
第一行包含 3 个整数 N、M 和 T。
以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到
一个订单。
【输出格式】
输出一个整数代表答案。
【样例输入】
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
【样例输出】
1
【样例解释】
6 时刻时，1 号店优先级降到 3，被移除出优先缓存;2 号店优先级升到 6， 加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。
【评测用例规模与约定】
对于 80% 的评测用例，1 ≤ N, M, T ≤ 10000。 对于所有评测用例，1 ≤ N,M,T ≤ 100000，1 ≤ ts ≤ T，1 ≤ id ≤ N。
AC代码：
import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class Main
{
static class Node implements Comparator<Node>
{
int number, value;
public Node() {}
public Node(int number, int value)
{
this.number = number;
this.value = value;
}
public boolean equals(Node o1)
{
return this.number == o1.number && this.value == o1.value;
}
@Override
public int compare(Node o1, Node o2)
{
if (o1.number < o2.number) return -1;
else if (o1.number > o2.number) return 1;
else
{
if (o1.value < o2.value) return -1;
else if (o1.value > o2.value) return 1;
else return 0;
}
}
}
static final int N = 100001;
static int n, m, t;
static int prev[] = new int[N];
static int values[] = new int[N];
static int state[] = new int[N];
static List<Node> arr = new ArrayList<>();
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException
{
// System.setIn(new FileInputStream("/Users/huangweixuan/testdata.txt"));
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
n = (int) st.nval;
st.nextToken();
m = (int) st.nval;
st.nextToken();
t = (int) st.nval;
for (int i = 0; i < m; ++i)
{
st.nextToken();
int a = (int) st.nval;
st.nextToken();
int b = (int) st.nval;
arr.add(new Node(b, a));
}
arr.sort(new Node());
for (int i = 0; i < m && arr.get(i).value <= t; )
{
int j = i;
while (j < m && arr.get(j).equals(arr.get(i))) ++j;
Node curr = new Node(arr.get(i).number, arr.get(i).value);
values[curr.number] -= curr.value - prev[curr.number] - 1;
if (values[curr.number] < 0) values[curr.number] = 0;
if (values[curr.number] < 4) state[curr.number] = 0;
values[curr.number] += j - i << 1;
if (values[curr.number] > 5) state[curr.number] = 1;
prev[curr.number] = curr.value;
i = j;
}
for (int i = 1; i <= n; ++i)
{
if (prev[i] < t)
{
values[i] -= t - prev[i];
if (values[i] < 4) state[i] = 0;
}
}
int res = 0;
for (int i = 1; i <= n; ++i)
res += state[i];
pw.printf("%d", res);
pw.close();
}
}
试题 H: 人物相关性分析（B组H题）
时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
【问题描述】
小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。
更准确的说，小明定义 Alice 和 Bob“同时出现”的意思是:在小说文本 中 Alice 和 Bob 之间不超过 K 个字符。
例如以下文本:
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
假设 K = 20，则 Alice 和 Bob 同时出现了 2 次，分别是”Alice and Bob”
和”Bob. Alice”。前者 Alice 和 Bob 之间有 5 个字符，后者有 2 个字符。
注意:
1. Alice 和 Bob 是大小写敏感的，alice 或 bob 等并不计算在内。
2. Alice 和 Bob 应为单独的单词，前后可以有标点符号和空格，但是不能
有字母。例如 Bobbi 並不算出现了 Bob。
【输入格式】
第一行包含一个整数 K。 第二行包含一行字符串，只包含大小写字母、标点符号和空格。长度不超
过 1000000。
【输出格式】
输出一个整数，表示 Alice 和 Bob 同时出现的次数。
【样例输入】
20
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
【样例输出】
2
【评测用例规模与约定】
对于所有评测用例，1 ≤ K ≤ 1000000。
AC代码：
package com;
import java.io.*;
import java.util.ArrayList;
import java.util.List;
public class Main
{
static int k;
static String str;
static String base[] = {"Alice", "Bob"};
static List<Integer> arrA = new ArrayList<>();
static List<Integer> arrB = new ArrayList<>();
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static boolean check(char a)
{
return a >= 'A' && a <= 'Z' || a >= 'a' && a <= 'z';
}
public static void main(String[] args) throws IOException
{
// System.setIn(new FileInputStream("/Users/huangweixuan/testdata.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer st = new StreamTokenizer(br);
st.nextToken();
k = (int) st.nval;
str = br.readLine();
for (int i = 0; i + base[0].length() <= str.length(); ++i)
{
if ((i == 0 || !check(str.charAt(i - 1))) &&
(i + base[0].length() == str.length() || !check(str.charAt(i + base[0].length()))))
{
if (str.substring(i, i + base[0].length()).equals(base[0])) arrA.add(i);
}
}
for (int i = 0; i + base[1].length() <= str.length(); ++i)
{
if ((i == 0 || !check(str.charAt(i - 1))) &&
(i + base[1].length() == str.length() || !check(str.charAt(i + base[1].length()))))
{
if (str.substring(i, i + base[1].length()).equals(base[1])) arrB.add(i);
}
}
long res = 0;
for (int i = 0, left = 0, right = -1; i < arrA.size(); ++i)
{
while (right + 1 < arrB.size() && arrB.get(right + 1) < arrA.get(i)) ++right;
while (left <= right && arrA.get(i) - arrB.get(left) - base[1].length() > k) ++left;
res += right - left + 1;
}
for (int i = 0, left = 0, right = -1; i < arrB.size(); ++i)
{
while (right + 1 < arrA.size() && arrA.get(right + 1) < arrB.get(i)) ++right;
while (left <= right && arrB.get(i) - arrA.get(left) - base[0].length() > k) ++left;
res += right - left + 1;
}
pw.printf("%d", res);
pw.close();
}
}
试题 I: 等差数列（B组H题）
时间限制: 1.0s 内存限制: 512.0MB 本题总分:25 分
【问题描述】
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有 几项?
【输入格式】
输入的第一行包含一个整数 N。 第二行包含N个整数A1,A2,···,AN。(注意A1 ∼AN并不一定是按等差数
列中的顺序给出) 【输出格式】
输出一个整数表示答案。
【样例输入】
5
2 6 4 10 20
【样例输出】
10
【样例说明】
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。
【评测用例规模与约定】
对于所有评测用例，2 ≤ N ≤ 100000，0 ≤ Ai ≤ 109。
AC代码：
import java.io.*;
import java.util.ArrayList;
import java.util.List;
public class Main
{
static int n;
static List<Integer> arr = new ArrayList<>();
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) throws IOException
{
// System.setIn(new FileInputStream("/Users/huangweixuan/testdata.txt"));
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
n = (int) st.nval;
for (int i = 0; i < n; ++i)
{
st.nextToken();
arr.add((int) st.nval);
}
arr.sort(((o1, o2) -> o1 - o2));
int d = 0;
for (int i = 1; i < arr.size(); ++i)
d = gcd(d, arr.get(i) - arr.get(0));
if (d == 0) pw.printf("%d", n);
else pw.printf("%d", (arr.get(arr.size() - 1) - arr.get(0)) / d + 1);
pw.close();
}
}
试题 J: 扫地机器人（G组G题）
时间限制: 1.0s 内存限制: 512.0MB 本题总分:25 分
【问题描述】
小明公司的办公区有一条长长的走廊，由 N 个方格区域组成，如下图所示。
走廊内部署了 K 台扫地机器人，其中第 i 台在第 Ai 个方格区域中。 已知扫地机器人每分钟可以移动到左右相邻的方格中，并将该区域清扫干净。
请你编写一个程序，计算每台机器人的清扫路线，使得
1. 它们最终都返回出发方格，
2. 每个方格区域都至少被清扫一遍，
3. 从机器人开始行动到最后一台机器人归位花费的时间最少。
注意多台机器人可以同时清扫同一方块区域，它们不会互相影响。
输出最少花费的时间。
在上图所示的例子中，最少花费时间是 6。第一台路线:2-1-2-3-4-3-2，清 扫了 1、2、3、4 号区域。第二台路线 5-6-7-6-5，清扫了 5、6、7。第三台路线 10-9-8-9-10，清扫了 8、9 和 10。
【输入格式】
第一行包含两个整数 N 和 K。 接下来 K 行，每行一个整数 Ai。
【输出格式】
输出一个整数表示答案。
【样例输入】
10 3
5
2
10
【样例输出】
6
【评测用例规模与约定】
对于30%的评测用例，1 ≤ K < N ≤ 10。 对于60%的评测用例，1 ≤ K < N ≤ 1000。 对于所有评测用例，1≤K<N≤100000，1≤Ai ≤N。
AC代码：
import java.io.*;
import java.util.ArrayList;
import java.util.List;
public class Main
{
static int n, k;
static List<Integer> arr = new ArrayList<>();
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static boolean check(int p, int size)
{
for (int i : arr)
{
if (i - size <= p) p = i <= p ? i + size - 1 : p + size;
else return false;
}
return p >= n;
}
public static void main(String[] args) throws IOException
{
// System.setIn(new FileInputStream("/Users/huangweixuan/testdata.txt"));
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
n = (int) st.nval;
st.nextToken();
k = (int) st.nval;
for (int i = 0; i < k; ++i)
{
st.nextToken();
arr.add((int) st.nval);
}
arr.sort((o1, o2) -> o1 - o2);
int size = n / k > arr.get(0) ? n / k : arr.get(0);
if (size != n)
{
while (size < n)
{
int p = 0;
if (check(p, size)) break;
++size;
}
}
pw.printf("%d", (size << 1) - 2);
pw.close();
}
}
