水
简单的模拟，小贪心。其实只要求max (ans, t + f);
#includeusing namespace std;#define lson l, mid, o << 1#define rson mid + 1, r, o << 1 | 1typedef long long ll;const int N = 1e5 + 5;const int INF = 0x3f3f3f3f;int n, s;struct Floor { int f, t; bool operator < (const Floor &r) const { return f > r.f || (f == r.f && t < r.t); }}a[105];int main(void) { scanf ("%d%d", &n, &s); for (int i=1; i<=n; ++i) { scanf ("%d%d", &a[i].f, &a[i].t); } sort (a+1, a+1+n); int ans = 0, now = s, i = 1; while (now > 0 && i <= n) { if (now > a[i].f) { now--; ans++; } else { if (ans < a[i].t) { ans = a[i].t; i++; while (i <= n && a[i].f == now && ans >= a[i].t) i++; } else { while (i <= n && a[i].f == now && ans >= a[i].t) i++; } } } while (now > 0) { now--; ans++; } printf ("%d\n", ans); return 0;}
组合
题意：都是01的a字符串在b字符串的所有连续子串不同的个数。
分析：看上去很难做。但是换一个思路，考虑a字符串的每一个字符最终会和b中哪些字符比较，求一个前缀就能解决了。多想想还是能想出来的，JayYe说做多了这些题目都是同一个套路。
#includeusing namespace std;#define lson l, mid, o << 1#define rson mid + 1, r, o << 1 | 1typedef long long ll;const int N = 2e5 + 5;const int INF = 0x3f3f3f3f;char s[N], t[N];int cnt0[N], cnt1[N];int main(void) { scanf ("%s%s", s + 1, t + 1); int lens = strlen (s + 1), lent = strlen (t + 1); memset (cnt0, 0, sizeof (cnt0)); memset (cnt1, 0, sizeof (cnt1)); int c1[2] = {0, 0}, c2[2] = {0, 0}; for (int i=1; i<=lens; ++i) if (s[i] == '0') c1[0]++; for (int i=1; i<=lent; ++i) { if (t[i] == '0') { c2[0]++; cnt0[i] = cnt0[i-1] + 1; cnt1[i] = cnt1[i-1]; } else { cnt1[i] = cnt1[i-1] + 1; cnt0[i] = cnt0[i-1]; } } c1[1] = lens - c1[0]; c2[1] = lent - c2[0]; ll ans = 0; for (int i=1; i<=lens; ++i) { if (s[i] == '0') { ans += cnt1[lent-lens+i] - cnt1[i-1]; } else { ans += cnt0[lent-lens+i] - cnt0[i-1]; } } printf ("%I64d\n", ans); return 0;}
DP
题意：在最后面多一个becaon，问在某一个地方某一个能量能使最后死掉的becaon最少。
分析：假设会杀掉j的becaon，那么找出j位置会杀掉的位置，那么j到n都死完了，pos到j也死完了，再加上kill[pos]的求最小值，kill[]是dp，从后往前能更新。
#includeusing namespace std;#define lson l, mid, o << 1#define rson mid + 1, r, o << 1 | 1typedef long long ll;const int N = 1e5 + 5;const int INF = 0x3f3f3f3f;struct Beacon { int a, b; bool operator < (const Beacon &r) const { return a < r.a; }}p[N];int kill[N];int bsearch(int l, int r, int k) { while (l <= r) { int mid = l + r >> 1; if (p[mid].a < k) l = mid + 1; else if (p[mid].a == k) return mid - 1; else { r = mid - 1; } } return r;}int main(void) { int n; scanf ("%d", &n); for (int i=1; i<=n; ++i) { scanf ("%d%d", &p[i].a, &p[i].b); } sort (p+1, p+1+n); int ans = n; for (int i=n-1; i>=0; --i) { //kill i bacon int j = n - i; if (j == 1) { ans = n - 1; kill[1] = 0; continue; } int pos = bsearch (1, j - 1, p[j].a - p[j].b); while (pos > 0 && p[j].a - p[j].b <= p[pos].a) pos--; if (pos == j - 1) kill[j] = kill[j-1]; else kill[j] = kill[pos] + j - pos - 1; ans = min (ans, kill[pos] + j - pos - 1 + i); } printf ("%d\n", ans); return 0;}