20191030测试总结
T1：WOJ4780
求个前缀和之后就是个二位偏序的板子，送分题。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, len, ans, a[5000005], b[5000005], c[5000005];
long long cc[5000005];
struct node
{
long long a;
int b;
long long bb;
int w;
} s[5000005];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
int read()
{
int x = 0, f = 1;
char c = gc();
while (!isdigit(c))
{
if (c == '-')
f = -1;
c = gc();
}
while (isdigit(c))
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = gc();
}
return x * f;
}
bool cmp(node aa, node bb)
{
if (aa.a != bb.a)
return aa.a < bb.a;
if (aa.b != bb.b)
return aa.b < bb.b;
return aa.w < bb.w;
}
int lowbit(int x)
{
return x & -x;
}
void add(int x, int val)
{
while (x <= len)
{
c[x] = min(c[x], val);
x += lowbit(x);
}
return;
}
int query(int x)
{
int num = 0x7f7f7f7f;
while (x >= 1)
{
num = min(c[x], num);
x -= lowbit(x);
}
return num;
}
int main()
{
n = read();
for (int i = 1; i <= n; ++i)
{
s[i].w = i;
a[i] = read();
s[i].a = s[i - 1].a + a[i];
}
for (int i = 1; i <= n; ++i)
{
b[i] = read();
s[i].bb = s[i - 1].bb + b[i];
cc[i] = s[i].bb;
}
sort(cc + 1, cc + n + 1);
len = unique(cc + 1, cc + n + 1) - cc - 1;
for (int i = 1; i <= n; ++i)
s[i].b = lower_bound(cc + 1, cc + len + 1, s[i].bb) - cc;
sort(s + 1, s + n + 1, cmp);
memset(c, 0x7f, sizeof(c));
for (int i = 1; i <= n; ++i)
{
ans = max(ans, s[i].w - query(s[i].b));
add(s[i].b, s[i].w);
if (s[i].a >= 0 && s[i].bb >= 0)
ans = max(ans, s[i].w);
}
printf("%d", ans);
return 0;
}
T2：WOJ4781
求出DP方程之后发现是n^3方的，然后就不会推了。结果发现题解上说决策点具有单调递增的性质，又看了看发现是个四边形不等式优化。不说了滚去学了。
#include <iostream>
#include <cstdio>
using namespace std;
int n, g[5005][5005];
long long sum[5005], f[5005][5005];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read()
{
int x = 0, f = 1;
char c = gc();
while (!isdigit(c))
{
if (c == '-')
f = -1;
c = gc();
}
while (isdigit(c))
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = gc();
}
return x * f;
}
int main()
{
n = read();
for (register int i = 1; i <= n; ++i)
{
sum[i] = read();
sum[i] += sum[i - 1];
}
for (register int i = 1; i <= n; ++i)
{
f[i][i] = sum[i] - sum[i - 1];
g[i][i] = i;
}
for (register int i = 1; i < n; ++i)
for (register int j = 1; j + i <= n; ++j)
{
int k = j + i;
f[j][k] = 0x7f7f7f7f7f7f7f7f;
for (register int l = g[j][k - 1]; l <= g[j + 1][k]; ++l)
if (f[j][l - 1] + f[l + 1][k] < f[j][k])
f[j][k] = f[j][l - 1] + f[l + 1][k], g[j][k] = l;
f[j][k] += sum[k] - sum[j - 1];
}
printf("%lld\n", f[1][n]);
return 0;
}
T3：WOJ4782
极其自闭的一道题
首先推出期望方程，然后高斯消元求解，但是这里要求多次，显然会达到n^4复杂度而t掉，因此需要分治消元。
分治消元的具体做法是：先用前一半的方程进行消元，然后递归后一半；（恢复原矩阵后）再用后一半的方程进行消元，然后递归前一半。这样当区间缩小到单点时，这个方程并没有拿来消其它的方程，我们可以直接修改它并求出所有f_i。复杂度就优化到n^3了（虽然这个复杂度看起来很假但确实是对的）。
#include <iostream>
#include <cstdio>
#define mod 998244353
using namespace std;
int n, m, f[305][305], ans[305][305], p[305][305], g[10][305][305];
int ksm(int a, int k)
{
int b = 1;
while (k)
{
if (k & 1)
b = (long long)b * a % mod;
a = (long long)a * a % mod;
k >>= 1;
}
return b;
}
void dfs(int l, int k)
{
ans[l][k] = f[k][0];
for (int i = 1; i <= n; ++i)
if (i != k && f[k][i])
{
if (!p[l][i])
dfs(l, i);
ans[l][k] = (ans[l][k] - (long long)f[k][i] * ans[l][i]) % mod;
}
p[l][k] = 1;
return;
}
void solve(int l, int r, int num)
{
if (l == r)
{
p[l][r] = 1;
for (int i = 1; i <= n; ++i)
if (!p[l][i])
dfs(l, i);
return;
}
int mid = (l + r) >> 1;
for (int i = l; i <= r; ++i)
{
g[num][i][0] = f[i][0];
for (int j = l; j <= r; ++j)
g[num][i][j] = f[i][j];
}
for (int i = l; i <= mid; ++i)
{
int k = ksm(f[i][i], mod - 2);
f[i][0] = (long long)f[i][0] * k % mod;
for (int j = i; j <= r; ++j)
f[i][j] = (long long)f[i][j] * k % mod;
for (int j = i + 1; j <= r; ++j)
if (f[j][i])
{
f[j][0] = (f[j][0] - (long long)f[i][0] * f[j][i]) % mod;
for (int k = r; k >= i; --k)
f[j][k] = (f[j][k] - (long long)f[i][k] * f[j][i]) % mod;
}
}
solve(mid + 1, r, num + 1);
for (int i = l; i <= r; ++i)
{
f[i][0] = g[num][i][0];
for (int j = l; j <= r; ++j)
f[i][j] = g[num][i][j];
}
for (int i = r; i > mid; --i)
{
int k = ksm(f[i][i], mod - 2);
f[i][0] = (long long)f[i][0] * k % mod;
for (int j = l; j <= i; ++j)
f[i][j] = (long long)f[i][j] * k % mod;
for (int j = i - 1; j >= l; --j)
if (f[j][i])
{
f[j][0] = (f[j][0] - (long long)f[i][0] * f[j][i]) % mod;
for (int k = l; k <= i; ++k)
f[j][k] = (f[j][k] - (long long)f[i][k] * f[j][i]) % mod;
}
}
solve(l, mid, num + 1);
for (int i = l; i <= r; ++i)
{
f[i][0] = g[num][i][0];
for (int j = l; j <= r; ++j)
f[i][j] = g[num][i][j];
}
return;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
++f[u][u];
++f[u][0];
--f[u][v];
}
solve(1, n, 0);
for (int i = 2; i <= n; ++i)
printf("%d\n", (ans[i][1] + mod) % mod);
return 0;
}
评论
发表评论