简单的模拟，小贪心。其实只要求max (ans, t + f);
#include <bits/stdc++.h>
using namespace std; #define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
typedef 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说做多了这些题目都是同一个套路。
#include <bits/stdc++.h>
using namespace std; #define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
typedef 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;
}
题意：在最后面多一个becaon，问在某一个地方某一个能量能使最后死掉的becaon最少。
分析：假设会杀掉j的becaon，那么找出j位置会杀掉的位置，那么j到n都死完了，pos到j也死完了，再加上kill[pos]的求最小值，kill[]是dp，从后往前能更新。
#include <bits/stdc++.h>
using namespace std; #define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
typedef 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;
}