250112

思路：题目中有提到，一头牛总是有可能在所有牧场之间穿梭，也就是说一头牛从任意一个放牧地点出发，都能在所有牧场之间穿梭。那么考虑将每次吃草事件按 t 从小到大排序。一头牛的不在场证明成立，仅当它无法在所有牧场与自己的不在场证明地点之间穿梭。假设某头牛在第 $t_i$ 时刻有不在场证明，离 $t_i$ 最近且早于 $t_i$ 的吃草事件的时刻为 $k_1$，离 $t_i$ 最近且晚于 $t_i$ 的吃草事件的时刻为 $k_2$。分析一下会发现，只要它不可能在 $(t_i-k_1)$ 的时间内从上一次吃草事件发生地点赶到不在场证明地点，或不可能在 $(k_2-t_i)$ 的时间内从不在场证明地点赶到下一次吃草事件发生地点，它的不在场证明就成立。那么问题就变成了，找到比不在场证明时间早的最晚发生的吃草事件。因为吃草事件已经按发生顺序排序，所以这次吃草事件的下次吃草事件就是比不在场证明时间晚的最早发生的吃草事件。该如何找到这次吃草事件呢？可以很容易地想到二分。那么问题也就迎刃而解了。

参考 C++ 版本

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int g,n,ans;
struct point {
    ll x,y,t;
    friend bool operator <(const point tmp1,const point tmp2) {
        return tmp1.t<tmp2.t;
    }
};
point p[100005];
ll tim[100005];
bool check(int i,ll t,ll x,ll y) {
    return (x-p[i].x)*(x-p[i].x)+(y-p[i].y)*(y-p[i].y)<=(t-p[i].t)*(t-p[i].t);
}
int main() {
    scanf("%d%d",&n,&g);
    for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].t);
    sort(p+1,p+1+n);
    for(int i=1;i<=n;i++) tim[i]=p[i].t;
    for(int i=1;i<=g;i++) {
        ll x,y,t;
        scanf("%lld%lld%lld",&x,&y,&t);
        int pos=lower_bound(tim+1,tim+1+n,t)-tim;
        if(pos==1) ans+=check(pos,t,x,y)?1:0;
        else if(pos-1==n) ans+=check(pos-1,t,x,y)?1:0;
        else ans+=(check(pos,t,x,y)&&check(pos-1,t,x,y))?1:0;
    }
    printf("%d\n",g-ans);
    return 0;
}

https://usaco.org/index.php?page=viewproblem2&cpid=1087

由于每次询问都会不染其中的一段区间，可以考虑使用前缀、后缀记录答案的方法来预处理数据。预处理方法: 使用数组 ans(i) 记录第 i 位需要多少次染色。使用数组 v[i] 记录之前是否有第 i 个字母出现。假设当前字符串为 "ABAB"。对于每个位置 i 进行处理：当 i = 1 时，v('A') == 0，ans(1)++，v('A') = 1 （赋值）。当 i = 2 时，v('B') == 0，ans(2)++，v('B') = 1。当 i = 3 时，v('A') == 1，ans(3) 不变（可以从上一个 'A' 继续延伸）。当 i = 4 时，发现一个问题，上一个 'B' 不能延续下来，因为中间有一个 'A'。

https://usaco.org/index.php?page=viewproblem2&cpid=1351

首先没有出现过的编号是一定可以分配相同的，这一部分要先记上。之后问题转化为一个环可以移动若干位，求和另一个环对应位置相同的最多个数。直接枚举环移动的位数暴力判断是 O (n²) 的，考虑优化这个过程。编号是一个排列，所以环内元素两两不同，则第一个环内一个数至多对应第二个环中的一个数。求出第一个环的每个数要向右平移多少位才能和第二个环对应相同，取最大值即可。要正反做一遍，因为可以翻转方向。