A – 旷野大计算
嗯，是我这种菜鸡不会的类型。
这个题主要的思路就是用离线莫队算法，这个算法是我本人第一次打，所以我会尝试一处一处讲清楚。首先大致分析一下，这道题的本质其实就是查询区间最大的加权众数。那么，根据题解上讲的，有一个这样的结论：
给定集合\(A,B\)，则\(mode(A \cup B) \to mode(A) \cup B\)这两玩意本质一样。
所以就可以考虑进行区间增大的莫队了。首先，离散化后简单的分个块，把问答离线下来排个序搞一搞。针对每一个询问，如果可以从上个区间进行转移，就进行快速转移；否则，重新开始。
莫队算法的精髓就是：暴力的进行转移。
// A.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e6 + 2000;
int n, m, arr[MAX_N], blockId[MAX_N];
int currentId[MAX_N], bucket[MAX_N];
ll cnt[MAX_N], leftBucket[MAX_N], answer, anses[MAX_N];
struct query
{
int l, r, id;
bool operator<(const query &qu) const
{
return blockId[l] < blockId[qu.l] ||
(blockId[l] == blockId[qu.l] && r < qu.r);
}
} queries[MAX_N];
void update_left(int x)
{
leftBucket[currentId[x]]++;
answer = max(answer, (leftBucket[currentId[x]] + cnt[currentId[x]]) * 1LL * arr[x]);
}
int main()
{
scanf("%d%d", &n, &m);
int siz = sqrt(n * 1.0);
for (int i = 1; i <= n; i++)
scanf("%d", &arr[i]), bucket[i] = arr[i], blockId[i] = (i - 1) / siz + 1;
sort(bucket + 1, bucket + 1 + n);
int buckTot = unique(bucket + 1, bucket + 1 + n) - bucket;
for (int i = 1; i <= n; i++)
currentId[i] = lower_bound(bucket + 1, bucket + 1 + buckTot, arr[i]) - bucket;
for (int i = 1; i <= m; i++)
scanf("%d%d", &queries[i].l, &queries[i].r), queries[i].id = i;
sort(queries + 1, queries + 1 + m);
// Previous Information:
int L = 1, R = 0, tmd;
ll tmp = 0;
answer = 0;
queries[0].l = 0, blockId[0] = 0;
for (int i = 1; i <= m; i++)
{
// Validiate if this interval is able to be calced by the previous one;
if (blockId[queries[i - 1].l] != blockId[queries[i].l])
{
memset(cnt, 0, sizeof(cnt));
R = tmd = blockId[queries[i].l] * siz;
answer = tmp = 0;
}
L = min(tmd + 1, queries[i].r + 1);
// Calc;
while (L > queries[i].l)
update_left(--L);
while (R < queries[i].r)
{
R++;
tmp = max((++cnt[currentId[R]]) * 1LL * arr[R], tmp);
answer = max(answer, (cnt[currentId[R]] + leftBucket[currentId[R]]) * 1LL * arr[R]);
}
// Set the answer;
anses[queries[i].id] = answer;
// Set the bucket back;
for (int j = L; j <= queries[i].r && j <= tmd; j++)
leftBucket[currentId[j]]--;
answer = tmp;
}
// Print the answer;
for (int i = 1; i <= m; i++)
printf("%lld\n", anses[i]);
return 0;
}
B – 爬山
这是一道傻逼题，然后我强行搞了个拓扑序 DP 就 GG 了。现在想想非常后悔。
显然，把环全部缩成点就会形成一个 DAG （有向无环图），之后直接暴力 DP，然后再取出标记过的答案进行最大值比较即可。很傻逼的一道题。
哦，对了，记得开栈。（JZOJ 万年卡栈）
// B.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 602000;
extern int theMain(void) __asm__("theMain");
int head[MAX_N << 1], current, n, m, dfn[MAX_N], low[MAX_N], aff[MAX_N];
int tot, stk[MAX_N], cur, afftot, indeg[MAX_N << 1], tmpx, tmpy, s;
ll cnt[MAX_N << 1], dp[MAX_N << 1], answer;
bool inst[MAX_N], mark[MAX_N];
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
edges[current].to = dst;
edges[current].nxt = head[src], head[src] = current++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++tot, stk[++cur] = u, inst[u] = true;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (dfn[edges[i].to] == 0)
tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]);
else if (inst[edges[i].to])
low[u] = min(low[u], dfn[edges[i].to]);
if (low[u] == dfn[u])
{
int j, nd = ++afftot;
do
{
j = stk[cur], inst[j] = false;
aff[j] = nd;
} while (stk[cur--] != u);
}
}
void toposort()
{
queue<int> q;
q.push(aff[s]), dp[aff[s]] = cnt[aff[s]];
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
dp[edges[i].to] = max(dp[edges[i].to], dp[u] + cnt[edges[i].to]);
q.push(edges[i].to);
}
}
}
int theMain()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy);
afftot = n;
for (int i = 1; i <= n; i++)
if (aff[i] == 0)
tarjan(i);
for (int i = 1; i <= n; i++)
scanf("%lld", &cnt[i]);
for (int u = 1; u <= n; u++)
{
cnt[aff[u]] += cnt[u];
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (aff[u] != aff[edges[i].to])
addpath(aff[u], aff[edges[i].to]), indeg[aff[edges[i].to]]++;
}
scanf("%d%d", &s, &tmpx);
for (int i = 1; i <= tmpx; i++)
scanf("%d", &tmpy), mark[aff[tmpy]] = true;
toposort();
for (int i = 1; i <= n; i++)
if (mark[aff[i]])
answer = max(answer, dp[aff[i]]);
printf("%lld", answer);
return 0;
}
int main()
{
int size = 64 << 20;
char *p = (char *)malloc(size) + size;
__asm__ __volatile__("movq %0, %%rsp\n"
"pushq $exit\n"
"jmp theMain\n" ::"r"(p));
return 0;
}
C – 货仓选址 运输妹子
如题，然后秒切。
// C.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 101000;
ll n, l, w, pos[MAX_N], prefix[MAX_N], answer;
bool validiate(int l, int r)
{
int mid = (l + r) >> 1;
ll ans = pos[mid] * (mid - l + 1) - (prefix[mid] - prefix[l - 1]) + (prefix[r] - prefix[mid]) - pos[mid] * (r - mid);
return ans <= w;
}
int main()
{
scanf("%lld%lld%lld", &n, &l, &w);
for (int i = 1; i <= n; i++)
scanf("%lld", &pos[i]), prefix[i] = prefix[i - 1] + pos[i];
ll lcur = 1, rcur = 0;
while (rcur < n && lcur <= n)
{
rcur++;
while (lcur <= rcur && !validiate(lcur, rcur))
lcur++;
answer = max(rcur - lcur + 1, answer);
}
printf("%lld", answer);
return 0;
}
