A 老夫
题目大意 ： n个人，如果能忍受广告就广告，如果能支付的起就交钱，问商家在每个播放广告数是能获得的最大利益
-
按忍受广告数量从小到大排序，那么就是前面的人去交钱或是推出，后面的人看广告
-
不看广告的人如果从大到小排序后，交钱的就是一段前缀，这样，贡献就是 (a_ii) 的最大值
-
以a为下标，分块维护凸包，找最大值的时候单调队列即可
Code
Show Code
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, M = 320;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
int n, k, ma, mb, a[N], b[N], p[N];
int c[N], tag[M], R[M], q[M][M], l[M], r[M];
ll w[N], ans;
bool Cmp(int x, int y) {
return b[x] < b[y];
}
ll Cal (int x) {
return w[x] + 1ll * tag[c[x]] * x;
}
bool Judge(int x, int y, int z) {
return (w[y] - w[x]) * (z - x) < (w[z] - w[x]) * (y - x);
}
void Solve(int x) {
int cx = c[x];
for (int i = 1; i < cx; ++i) {
tag[i]++;
while (l[i] < r[i] && Cal(q[i][l[i]]) < Cal(q[i][l[i]+1])) l[i]++;
ans = max(ans, Cal(q[i][l[i]]));
}
int &tp = r[cx] = 0; l[cx] = 1;
for (int i = R[cx-1] + 1; i <= R[cx]; ++i) {
w[i] += 1ll * tag[cx] * i;
if (i <= x) w[i] += i;
ans = max(ans, w[i]);
while (tp && w[i] >= w[q[cx][tp]]) tp--;
while (tp > 1 && Judge(q[cx][tp-1], q[cx][tp], i)) tp--;
q[cx][++tp] = i;
}
tag[cx] = 0;
}
int main() {
freopen("laofu.in", "r", stdin);
freopen("laofu.out", "w", stdout);
n = read(), k = read();
for (int i = 1; i <= n; ++i) {
a[i] = read(); b[i] = read(); p[i] = i;
ma = max(ma, a[i]), mb = max(mb, b[i]);
}
int sq = sqrt(ma);
for (int i = 1; i <= ma; ++i) {
c[i] = (i - 1) / sq + 1;
R[c[i]] = i; l[c[i]] = 1;
q[c[i]][++r[c[i]]] = i;
}
sort(p + 1, p + n + 1, Cmp);
for (int i = 1, j = 1; i <= mb + 1; ++i) {
for (; j <= n && b[p[j]] < i; ++j) Solve(a[p[j]]);
printf("%lld ", ans + 1ll * k * i * (n - j + 1));
}
return 0;
}
B 打算
题目大意 ： 机器人会按照一段指令循环的运动，给出n个时刻观测到的位置，问这段指令可能是什么
-
把坐标系旋转45度，让(x,y)变为(x+y,x-y)这样每次移动横纵坐标都会改变，就可以分开计算
-
然后推个式子，找到一个合法的解就行了
Code
Show Code
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define double long double
using namespace std;
typedef long long ll;
const int N = 2e6 + 5;
ll read(ll x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
int n, m;
ll t[N], x[N], y[N];
struct Node {
ll t, a, b;
}a[N];
bool operator < (const Node &x, const Node &y) {
return x.t < y.t;
}
void Solve(ll *x) {
ll l = -1e18, r = 1e18;
for (int i = 1; i <= n; ++i)
a[i] = (Node) {t[i] % m, -t[i] / m, x[i]};
sort(a + 1, a + n + 1); a[n+1] = (Node) {m, 1, 0};
for (int i = 0; i <= n; ++i) {
ll T = a[i+1].t - a[i].t, A = a[i+1].a - a[i].a, B = a[i+1].b - a[i].b;
if (!A) {
if (abs(B) > T) { puts("NO"), exit(0); }
else continue;
}
double L = (double)(-T - B) / A, R = (double)(T - B) / A;
if (L > R) swap(L, R);
l = max(l, (ll)ceil(L)); r = min(r, (ll)floor(R));
}
if (l+m & 1) l++;
if (r+m & 1) r--;
if (l > r) { puts("NO"), exit(0); }
int cnt = 0;
for (int i = 0; i <= n; ++i) {
a[i+1].b += a[i+1].a * l;
int tmp = a[i+1].b - a[i].b;
while (tmp > 0) x[++cnt] = 1, tmp--;
while (tmp < 0) x[++cnt] = 0, tmp++;
if (abs(a[i+1].t - cnt) & 1) { puts("NO"), exit(0); }
while (cnt < a[i+1].t) x[++cnt] = 1, x[++cnt] = 0;
}
}
int main() {
freopen("dasuan.in", "r", stdin);
freopen("dasuan.out", "w", stdout);
n = read(); m = read();
for (int i = 1; i <= n; ++i) {
t[i] = read();
ll a = read(), b = read();
x[i] = a + b; y[i] = a - b;
}
Solve(x); Solve(y);
for (int i = 1; i <= m; ++i)
putchar(x[i] ? (y[i] ? 'R' : 'U') : (y[i] ? 'D' : 'L'));
return 0;
}
C (Unaccepted)
题目大意 ：
Code
Show Code