T1.序列问题
盯了T1二十分钟，发现只会\(O(n!)\)的暴力，于是溜了。最后一小时想到了\(O(n^2)\)的dp，拿到了（骗到）50分，而且因为我的dp定义比较原始，所以没有办法优化。
首先定义\(b[i]=i-a[i]\)，表示这个数能产生贡献当且仅当前面删除了\(b[i]\)个数。即：定义\(dp[i][j]\)为前i个数，删了j个数的最大值，转移为\(dp[i][j] = max[ dp[i-1][j-1],dp[i-1][j]+(j==b[i]) ]\)，就是分为留下和删去两种情况。
那么只能换一种dp定义了，定义\(dp[i]\)为前i个数，以i结尾的最大值，类似于最长上升子序列的方式转移\(当b[i]>=0, dp[i]=max(dp[j]+1)，j < i, a[j] < a[i], b[j] <= b[i]\)，含义即为前j个数里留下的一定小于前i个数里留下的，删去的一定小于等于。很明显这是一个偏序问题，可以使用CDQ优化，但是效率是\(O(nlog^2n)\)的，但是我们发现通过a与b的不等式关系，能够推导出i与j的关系，也就是说只需要满足后两个偏序关系。我们按a排序，就把问题转化为了求一个数列的最长不下降子序列，排序上有一个细节，当a相等时按b降序，就保证了i不会从\(a[i]=a[j]\)的j转移过来。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
using namespace std;
const int Z = 5e5 + 100;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f = c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
inline int max(int a, int b) { return a > b ? a : b; } inline int min(int a, int b) { return a < b ? a : b; }
int n, m, ans;
struct seq
{
int a, b;
friend bool operator <(seq A, seq B)
{
if (A.a == B.a) return A.b > B.b;
return A.a < B.a;
}
}; seq s[Z];
int c[Z];
inline int lbt(int x) { return x & (-x); }
inline void add(int x, int y) { while (x <= n) c[x] = max(c[x], y), x += lbt(x); }
inline int ask(int x) { int res = 0; while (x) res = max(res, c[x]), x -= lbt(x); return res; }
sandom main()
{
fre(sequence, sequence);
n = read();
for (re i = 1; i <= n; i++) s[i].a = read(), s[i].b = i - s[i].a + 1;
sort(s + 1, s + 1 + n);
for (re i = 1; i <= n; i++)
{
if (s[i].b <= 0) continue;
int dp = ask(s[i].b) + 1;
add(s[i].b, dp);
ans = max(ans, dp);
}
cout << ans << endl;
return 0;
}
T2.钱仓
不到半小时就切了……环上问题，考虑转化为链。一定存在某一个位置，钱只从左侧转移向右侧，而不存在钱从右侧经环转移向左侧。为了方便，我们断环成链，找到一个合适的断点，使得左边的钱整体多于右边，这样钱顺时针从左流到右。还发现到一个性质：\((x+y)^2>x^2+y^2\)，所以让不要让某短路程过长。这一部分用队列从后往前扫一下就结束了，每次往离自己最远的地方运，这样能保证后面的钱仓的路程小一点（牺牲自我）。问题就只剩下了找到合适的断点。联想到括号序列的思想，我们不妨把c数组减一，合适的一段序列即为前缀和始终非负，这样能保证左边的钱足以运给右边。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
#define int long long
using namespace std;
const int Z = 2e5 + 100;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f = c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
inline int max(int a, int b) { return a > b ? a : b; } inline int min(int a, int b) { return a < b ? a : b; }
int n, m, k, ans;
int c[Z], s[Z];
#define lk (rt << 1)
#define rk (rt << 1 | 1)
#define mid (l + r >> 1)
int Min[Z << 2];
void build(int rt, int l, int r)
{
if (l == r) { Min[rt] = s[l]; return; }
build(lk, l, mid), build(rk, mid + 1, r);
Min[rt] = min(Min[lk], Min[rk]);
}
int query(int rt, int l, int r, int L, int R)
{
if (L <= l && R >= r) return Min[rt];
int res = 1e9;
if (L <= mid) res = min(res, query(lk, l, mid, L, R));
if (R > mid) res = min(res, query(rk, mid + 1, r, L, R));
return res;
}
queue <int> q;
sandom main()
{
fre(barn, barn);
n = read(); m = n << 1;
for (re i = 1; i <= n; i++) c[i] = read(), c[i + n] = c[i];
for (re i = 1; i <= m; i++) s[i] = s[i - 1] + c[i] - 1;
build(1, 1, m);
for (re i = 0; i < n; i++)//保证都是从前往后转移
if (query(1, 1, m, i + 1, i + n) >= s[i])
{
for (re j = 1; j <= n; j++) c[j] = c[i + j];
break;
}
for (re i = n; i >= 1; i--)
{
if (c[i])//有的话就往后运
{
while (c[i] && !q.empty())
{
ans += (q.front() - i) * (q.front() - i);
c[i]--; q.pop();
}
}
if (!c[i]) q.push(i);
}
cout << ans << endl;
return 0;
}
T3.自然数
先做的这个题，然后搞了六个容斥数组……还不如打个\(O(n^2)\)暴力呢，s3的部分分因为没开long long挂了。这种区间问题很常见，都是用线段树维护，但是之前的都是往里面插入，而这个不行，插入会改变多个区间的数值，并且变动不一样。所以考虑每次删除一个点。先预处理出每一个\([1, i]\)的mex。从左开始依次删除，容易发现，把删除的这个点的数值记为v，则它到下一个v之间的区间没有v，如果这些区间里的mex大于等于v，则这些区间的mex都会变为v，所以问题转化为，对于每一个删除的v，记下一个v的位置为nxt，每一次删除要把\([v, nxt)\)中所有的\(mex\)与v取\(min\)，还要支持区间求和，吉司机线段树的板子。但由于\(mex\)是有单调性的，所以可以在线段树上二分找到需要修改的区间，直接区间覆盖。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
#define int long long
using namespace std;
const int Z = 2e5 + 100;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f = c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
inline int max(int a, int b) { return a > b ? a : b; } inline int min(int a, int b) { return a < b ? a : b; }
int n, m, k, ans;
int pos[Z], nxt[Z], mex[Z], a[Z];
bool vs[Z];
struct tree
{
int l, r;
int sum, max, lz;
#define lk (rt << 1)
#define rk (rt << 1 | 1)
#define mid (tr[rt].l + tr[rt].r >> 1)
}; tree tr[Z << 2];
inline void add(int rt, int val)
{
tr[rt].sum = (tr[rt].r - tr[rt].l + 1) * val;
tr[rt].max = val; tr[rt].lz = val;
}
inline void pushup(int rt)
{
tr[rt].sum = tr[lk].sum + tr[rk].sum;
tr[rt].max = max(tr[lk].max, tr[rk].max);
}
inline void pushdown(int rt) { if (tr[rt].lz != -1) add(lk, tr[rt].lz), add(rk, tr[rt].lz), tr[rt].lz = -1; }
void build(int rt, int l, int r)
{
tr[rt].l = l, tr[rt].r = r, tr[rt].lz = -1;
if (l == r) { tr[rt].sum = tr[rt].max = mex[l]; return; }
build(lk, l, mid), build(rk, mid + 1, r);
pushup(rt);
}
void update(int rt, int l, int r, int val)
{
if (l <= tr[rt].l && r >= tr[rt].r) { add(rt, val); return; }
pushdown(rt);
if (l <= mid) update(lk, l, r, val);
if (r > mid) update(rk, l, r, val);
pushup(rt);
}
int query(int rt, int l, int r)
{
if (l <= tr[rt].l && r >= tr[rt].r) return tr[rt].sum;
pushdown(rt);
int res = 0;
if (l <= mid) res += query(lk, l, r);
if (r > mid) res += query(rk, l, r);
return res;
}
int find(int rt, int val)
{
if (tr[rt].l == tr[rt].r) return tr[rt].max > val ? tr[rt].l : n + 1;
pushdown(rt);
if (tr[lk].max > val) return find(lk, val);
else return find(rk, val);
}
sandom main()
{
fre(mex, mex);
n = read();
for (re i = 1; i <= n; i++)
{
a[i] = read();
if (a[i] > n) continue;
nxt[pos[a[i]]] = i;
pos[a[i]] = i;
}
for (re i = 0; i <= n; i++) nxt[pos[i]] = n + 1;
int num = 0;
for (re i = 1; i <= n; i++)
{
if (a[i] <= n) vs[a[i]] = 1;
while (vs[num]) num++;
mex[i] = num;
}
build(1, 1, n);
for (re i = 1; i <= n; i++)
{
ans += query(1, i, n);
if (a[i] > n) continue;
int pos = find(1, a[i]);//与区间取min，由于有单调性，可以先二分找到需要进行修改的直接覆盖
if (pos < nxt[i]) update(1, pos, nxt[i] - 1, a[i]);
}
cout << ans << endl;
return 0;
}
T4.环路
我甚至没有往矩阵乘法上想，一直在想dp，但是发现dp是错的，因为需要不断迭代更新。但是题解让我得到了升华，我看着自己的原始式子\(dp[i][j]+=dp[i][k]*dp[k][j]\)，这tm不就是矩阵乘吗，而且\(n<=100\)，那么直接把给出的矩阵设为初始矩阵A，表示走1步到达每个点的方案数，\(A[i][i]\)即为环，给A每乘上一个A，就表示多走一步。那么最后的答案矩阵就是\(A+A^2+A^3+…+A^{k-1}\)，\(k<=1e6\)，显然不能递推，这个类似于等比数列，我们可以递归分治处理，每次/2处理，对于偶数/奇数分别讨论。时间复杂度\(O(n^3logk)\)
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
#define int long long
#define fir first
#define sec second
using namespace std;
const int Z = 110;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f = c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
inline int max(int a, int b) { return a > b ? a : b; } inline int min(int a, int b) { return a < b ? a : b; }
int n, m, k, ans;
char mp[Z][Z];
struct Matrix
{
int a[Z][Z];
Matrix () { memset(a, 0, sizeof(a)); }
friend Matrix operator +(Matrix x, Matrix y)
{
Matrix z;
for (re i = 1; i <= n; i++)
for (re j = 1; j <= n; j++)
z.a[i][j] = (x.a[i][j] + y.a[i][j]) % m;
return z;
}
friend Matrix operator *(Matrix x, Matrix y)
{
Matrix z;
for (re i = 1; i <= n; i++)
for (re k = 1; k <= n; k++)
for (re j = 1; j <= n; j++)
(z.a[i][j] += 1ll * x.a[i][k] * y.a[k][j]) %= m;
return z;
}
}; Matrix base, x, y;
pair<Matrix, Matrix> z, res;
pair<Matrix, Matrix> solve(int k)
{
if (k == 1) return make_pair(base, base);
z = solve(k >> 1);
x = z.fir * z.fir, y = z.sec + z.fir * z.sec;
if (k & 1) x = x * base, y = y + x;
return make_pair(x, y);
}
sandom main()
{
fre(tour, tour);
n = read();
for (re i = 1; i <= n; i++)
{
scanf("%s", mp[i] + 1);
for (re j = 1; j <= n; j++)
if (mp[i][j] == 'Y') base.a[i][j] = 1;
}
k = read(), m = read();
res = solve(k - 1);
for (re i = 1; i <= n; i++) (ans += res.sec.a[i][i]) %= m;
cout << ans << endl;
return 0;
}