浅浅的记录一下最近刷到的略难题，虽然但是黑题怎么可能刷得到。
又是最短路相关，仍然考虑魔改 dijkstra。
我们发现这个柿子等价于任意选择一条边不选任意一条边翻倍得到的最小距离。你可以贪心证明或者看错题意大法得到这个性质。
那么考虑拆点，每个点 $u$ 还要维护你是否没选过一条边和你是否翻倍过一条边。下一条边就直接往后直接走或不算贡献或翻倍讨论一下就好。
然后大力 dijkstra 即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
int n, m;
vector<pii> a[800020];
ll dis[800020];
bool vis[800020];
void dijk(int u)
{
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({0, u});
dis[u] = 0;
while (!q.empty())
{
u = q.top().second;
q.pop();
if (vis[u])
continue;
vis[u] = 1;
int x = u & 2;
int y = u & 1;
int z = u >> 2;
for (auto p : a[z])
{
int v = p.second;
ll w = p.first;
v += x + y;
if (dis[v] > dis[u] + w)
q.push({dis[v] = dis[u] + w, v});
if (!x && dis[v | 2] > dis[u])
q.push({dis[v | 2] = dis[u], v | 2});
if (!y && dis[v | 1] > dis[u] + (w << 1))
q.push({dis[v | 1] = dis[u] + (w << 1), v | 1});
}
}
}
int main()
{
memset(dis, 0x3f, sizeof(dis));
cin >> n >> m;
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
a[u].push_back({w, v << 2});
a[v].push_back({w, u << 2});
}
dijk(1 << 2);
for (int i = 2; i <= n; i++)
cout << min(dis[i << 2], dis[i << 2 | 3]) << " ";
cout << endl;
return 0;
}
···
- [CF 113D Museum](https://codeforces.com/problemset/problem/113/D)
把点拆开存到矩阵里，然后迭代 17 次，更小 WA，过大 TLE。
```cpp
#include <bits/stdc++.h>
using namespace std;
struct Matrix
{
double a[500][500];
} mtx;
int n, m;
int s, t;
double p[30];
int id[30][30];
vector<int> a[30];
int loveher;
Matrix operator*(const Matrix &x, const Matrix &y)
{
Matrix z;
for (int i = 1; i <= loveher; i++)
for (int j = 1; j <= loveher; j++)
z.a[i][j] = 0;
for (int i = 1; i <= loveher; i++)
for (int j = 1; j <= loveher; j++)
for (int k = 1; k <= loveher; k++)
z.a[i][j] += x.a[i][k] * y.a[k][j];
return z;
}
int main()
{
cin >> n >> m >> s >> t;
while (m--)
{
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
for (int i = 1; i <= n; i++)
cin >> p[i];
// for (int i = 1; i <= n; i++)
// cout << p[i] << " \n"[i == n];
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
id[i][j] = id[j][i] = ++loveher;
for (int i = 1; i <= n; i++)
mtx.a[id[i][i]][id[i][i]] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
mtx.a[id[i][j]][id[i][j]] += p[i] * p[j];
// cout << id[i][j] << " " << p[i] * p[j] << endl;
for (int k : a[i])
{
mtx.a[id[i][j]][id[k][j]] += (1.0 - p[i]) / a[i].size() * p[j];
for (int t : a[j])
mtx.a[id[i][j]][id[k][t]] += (1.0 - p[i]) / a[i].size() * (1.0 - p[j]) / a[j].size();
}
for (int k : a[j])
mtx.a[id[i][j]][id[i][k]] += p[i] * (1.0 - p[j]) / a[j].size();
}
}
for (int i = 1; i <= 20; i++)
mtx = mtx * mtx;
for (int i = 1; i <= n; i++)
printf("%.7f ", mtx.a[id[s][t]][id[i][i]]);
return 0;
}最暴力的 $f_{u,v,x,y}$ 表示左上 $(u,v)$ 右下 $(x,y)$ 的答案。
模拟赛场上打得类似这种，搜索过多爆栈而死，排名 -= inf，警钟长鸣。
注意到最多只有 $\log_2 n+\log_2 m=\log_2 n\times m$ 刀。
考虑 $f_{k,x,y,j}$ 表示切下 $k$ 刀后 $x$ 和 $y$ 行从 $j$ 开始能走到哪里。典型的答案与状态互换。
然后就很好转移啦。第一维可以直接压掉。
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void gmx(T &x, T y) { x = max(x, y); }
int n, m;
char mp[520][520];
int s[520][520];
int f[2][320][320][320];
int S(int u, int v, int x, int y) { return s[x][y] - s[u - 1][y] - s[x][v - 1] + s[u - 1][v - 1]; }
bool in(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m; }
bool same(int u, int v, int x, int y)
{
int sum = S(u, v, x, y);
return !(sum ^ (x - u + 1) * (y - v + 1)) || !sum;
}
int bs_mx(int op, int i, int j, int k)
{
int L = i, R = j, mid;
int ret = 0;
while (L <= R)
{
mid = L + R >> 1;
int p = f[op][i][mid][k];
int q = f[op][mid + 1][j][k];
gmx(ret, min(p, q));
if (p > q)
L = mid + 1;
else
R = mid - 1;
}
return ret;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> mp[i][j];
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (mp[i][j] == '#');
}
}
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
for (int k = 1; k <= m; k++)
{
int L = k - 1, R = m, mid;
int &t = f[0][i][j][k];
while (L <= R)
{
mid = L + R >> 1;
if (same(i, k, j, mid))
L = mid + 1, t = mid;
else
R = mid - 1;
}
}
}
}
int ans = 0;
int tmp = 0, lst = 1;
while (f[tmp][1][n][1] < m)
{
ans++;
tmp ^= 1;
lst ^= 1;
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
for (int k = 1; k <= m; k++)
{
int p = f[lst][i][j][k];
f[tmp][i][j][k] = (p ^ m ? max(f[lst][i][j][p + 1], bs_mx(lst, i, j, k)) : m);
}
}
}
}
cout << ans << endl;
return 0;
}dp。
https://www.luogu.com.cn/discuss/656534
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef __float128 fl;
const int p = 1000000007;
int n, m;
ll l;
ll a[120];
bool lst = 0, cur = 1;
template <typename T>
void out(T ans)
{
if (ans + 1e-14 >= 1)
{
cout << "1." << string(m, '0') << endl;
return;
}
cout << "0.";
ans *= 10;
for (int i = 1; i <= m; ++i)
{
cout << (int)(ans + (m == i) * 0.5);
ans = (ans - (int)ans) * 10;
}
}
int main()
{
cin >> n >> l >> m;
for (int i = 1; i <= n; i++)
a[i] = i;
if (n == 1)
return cout << 1 << endl, 0;
if (m <= 8)
{
ld f[2][120][5020][5] = {};
f[0][0][0][0] = 1;
for (int i = 1; i <= n; i++)
{
memset(f[cur], 0, sizeof(f[cur]));
for (int j = 0; j <= n; j++)
{
for (int k = 0; k <= l; k++)
{
for (int op = 0; op < 3; op++)
{
ll x = 2 * j - op;
ll y = x * (a[i] - a[i - 1]);
if (!f[lst][j][k][op] || x < 0 || y + k >= l)
continue;
f[cur][j][k + y][op + 1] += f[lst][j][k][op] * (2 - op) / i;
f[cur][j + 1][k + y][op + 1] += f[lst][j][k][op] * (2 - op) / i;
f[cur][j][k + y][op] += f[lst][j][k][op] * x / i;
f[cur][j + 1][k + y][op] += f[lst][j][k][op] * (x + 1 - j) / i;
if (!j)
continue;
f[cur][j - 1][k + y][op] += f[lst][j][k][op] * (j - 1) / i;
}
}
}
lst ^= 1, cur ^= 1;
}
ld ans = 0;
for (int i = 0; i < l; i++)
ans += f[lst][1][i][2];
out(1 - ans);
}
else
{
fl f[2][120][5020][5] = {};
f[0][0][0][0] = 1;
for (int i = 1; i <= n; i++)
{
memset(f[cur], 0, sizeof(f[cur]));
for (int j = 0; j <= n; j++)
{
for (int k = 0; k <= l; k++)
{
for (int op = 0; op < 3; op++)
{
ll x = 2 * j - op;
ll y = x * (a[i] - a[i - 1]);
if (!f[lst][j][k][op] || x < 0 || y + k >= l)
continue;
f[cur][j][k + y][op + 1] += f[lst][j][k][op] * (2 - op) / i;
f[cur][j + 1][k + y][op + 1] += f[lst][j][k][op] * (2 - op) / i;
f[cur][j][k + y][op] += f[lst][j][k][op] * x / i;
f[cur][j + 1][k + y][op] += f[lst][j][k][op] * (x + 1 - j) / i;
if (!j)
continue;
f[cur][j - 1][k + y][op] += f[lst][j][k][op] * (j - 1) / i;
}
}
}
lst ^= 1, cur ^= 1;
}
fl ans = 0;
for (int i = 0; i < l; i++)
ans += f[lst][1][i][2];
out(1 - ans);
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p = 1000000007;
int n;
ll l;
ll a[120];
ll f[2][120][1020][5];
bool lst = 0, cur = 1;
int main()
{
cin >> n >> l;
for (int i = 1; i <= n; i++)
cin >> a[i];
if (n == 1)
return cout << 1 << endl, 0;
sort(a + 1, a + n + 1);
f[0][0][0][0] = 1;
for (int i = 1; i <= n; i++)
{
memset(f[cur], 0, sizeof(f[cur]));
for (int j = 0; j <= n; j++)
{
for (int k = 0; k <= l; k++)
{
for (int op = 0; op < 3; op++)
{
ll x = 2 * j - op;
ll y = x * (a[i] - a[i - 1]);
if (!f[lst][j][k][op] || x < 0 || y + k > l)
continue;
(f[cur][j][k + y][op + 1] += f[lst][j][k][op] * (2 - op) % p) %= p;
(f[cur][j + 1][k + y][op + 1] += f[lst][j][k][op] * (2 - op) % p) %= p;
(f[cur][j][k + y][op] += f[lst][j][k][op] * x % p) %= p;
(f[cur][j + 1][k + y][op] += f[lst][j][k][op] * (x + 1 - j)) %= p;
if (!j)
continue;
(f[cur][j - 1][k + y][op] += f[lst][j][k][op] * (j - 1) % p) %= p;
}
}
}
lst ^= 1, cur ^= 1;
}
ll ans = 0;
for (int i = 0; i <= l; i++)
(ans += f[lst][1][i][2]) %= p;
cout << ans << endl;
return 0;
}好久没记了。
受不了了一拳把模拟赛干爆！受不了了一拳把模拟赛干爆！受不了了一拳把模拟赛干爆！
首先把结论搞出来，$\sum \limits_{i=1}^n\sum \limits_{j=1}^{i}\lvert a_i-a_j\rvert$。
然后数据结构维护。
typedef long long ll;
const int V = 1000000000;
const int p = 998244353;
int n, q;
int rt;
int a[300020];
struct Node
{
ll sum, tot, siz;
int lc, rc;
} Tree[50000020];
#define lc Tree[rt].lc
#define rc Tree[rt].rc
int cnt;
void add(int d, int val, int &rt, int l = 1, int r = V)
{
if (!rt)
rt = ++cnt;
if (!(l ^ r))
return (Tree[rt].tot += 1LL * l * val) %= p, (Tree[rt].siz += val) %= p, void();
int mid = l + r >> 1;
if (d <= mid)
add(d, val, lc, l, mid);
else
add(d, val, rc, mid + 1, r);
Tree[rt].sum = ((Tree[lc].sum - Tree[lc].tot * Tree[rc].siz) % p + p +
(Tree[rc].sum + Tree[rc].tot * Tree[lc].siz) % p + p) %
p;
// assert(Tree[rt].sum >= 0);
Tree[rt].tot = (Tree[lc].tot + Tree[rc].tot) % p;
Tree[rt].siz = (Tree[lc].siz + Tree[rc].siz) % p;
}
int main()
{
cin >> n >> q;
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
for (int i = 1; i <= n; i++)
add(a[i], 1, rt);
while (q--)
{
int x, y;
scanf("%d%d", &x, &y);
add(a[x], -1, rt);
add(a[x] = y, 1, rt);
printf("%lld\n", Tree[rt].sum * (p + 1 >> 1) % p);
}
return 0;
}看注释。
#include <bits/stdc++.h>
using namespace std;
int n, flag;
int pos1st;
long long ans, x, pos, val, k;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
if (flag == 0)
{
if (x == -1)
{
ans++;
flag = 1;
pos1st = i;
}
else
{
ans++;
flag = 2;
pos1st = i;
pos = i;
val = x;
}
}
else if (flag == 1)
{
if (x == -1)
{
}
else
{
flag = 2;
pos = i;
val = x;
}
}
else if (flag == 2)
{
if (x == -1)
{
}
else
{
if ((x - val) % (i - pos) == 0 && val - (x - val) / (i - pos) * (pos - pos1st) > 0)
{
flag = 3;
k = (x - val) / (i - pos);
}
else
{
ans++;
flag = 2;
pos1st = i;
pos = i;
val = x;
}
}
}
else if (flag == 3)
{
if (x == -1)
{
if (val + (i - pos) * k > 0)
{
}
else
{
ans++;
flag = 1;
pos1st = i;
}
}
else
{
if (val + (i - pos) * k == x)
{
}
else
{
ans++;
flag = 2;
pos1st = i;
pos = i;
val = x;
}
}
}
}
cout << ans << endl;
return 0;
}
/*
pos1st 当前等差数列第一项在哪里
pos 不是-1的那一项下标是什么
val 不是-1的那一项值是多少
k 最后一个等差数列的公差是多少
flag
0这是第一个数字
1最后一个等差数列全是-1
2最后一个等差数列只有1个不是-1
3最后一个等差数列有2个不是-1
*/最小值不够小调了一个下午自闭了，不想写笔记了。
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void gmx(T &x, T y) { x = max(x, y); }
int n;
int a[6020];
int ans;
int x, y;
int f[2020][2020];
int mx[2020];
int b[5];
struct node
{
int x, y, z;
};
int main()
{
memset(f, 128, sizeof(f));
memset(mx, 128, sizeof(mx));
mx[0] = 0;
cin >> n;
for (int i = 1; i <= 3 * n; i++)
cin >> a[i];
f[a[1]][a[2]] = f[a[2]][a[1]] = mx[a[1]] = mx[a[2]] = 0;
for (int i = 3; i + 2 <= 3 * n; i += 3)
{
if (a[i] == a[i + 1] && a[i + 1] == a[i + 2])
{
ans++;
continue;
}
b[1] = a[i], b[2] = a[i + 1], b[3] = a[i + 2];
vector<node> v;
for (int j = 1; j <= 3; j++)
{
for (int k = 1; k <= 3; k++)
{
if (!(j ^ k))
continue;
int x = b[j], y = b[k], z = (b[j] ^ b[k] ^ b[1] ^ b[2] ^ b[3]);
// cout << x << " " << y << " " << z << endl;
for (int t = 1; t <= n; t++)
{
int cur = mx[t];
if (!(y ^ z))
gmx(cur, f[t][y] + 1);
v.push_back({t, x, cur});
}
v.push_back({x, y, max(mx[0], f[z][z] + 1)});
}
}
for (auto j : v)
{
int x = j.x, y = j.y, z = j.z;
gmx(f[x][y], z);
gmx(f[y][x], z);
gmx(mx[x], z);
gmx(mx[y], z);
gmx(mx[0], z);
}
}
int fmx = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
gmx(fmx, f[i][j] + (i == j) * (j == a[3 * n]));
cout << ans + fmx << endl;
return 0;
}为啥我觉得这题难在判是否有解啊。
判是否有解题意可以转化为是否存在 $b$ 使得 $\sum_{i=1}\limits^{n}a_i\times k^{-b_i}=1$。
状态转移考虑一个经典问题：$0\leq x_1\leq x_2\leq x_3\leq\dots\leq x_{n-1}\leq x_n$，且 $\sum x_i=m$。
这个转移当 $x_1=1$ 时有 $f_{n,m}\gets f_{n,m-n}$。
回归这个问题你考虑 $f_{mask,s}$ 选集合为 $mask$ 和为 $s$ 是否可行。
那么当 $f_{mask,s}=\text{True}$ 时，有 $f_{mask\cup \{i\},s+a_i}=\text{True},f_{mask,\frac{s}{k}}=\text{True}$。
然后我们 bitset 优化一下就可以判出是否有解了。
判出了是否有解之后我们找一下每个数字应该在第几层合并即可，可以用大根堆维护。
int main()
{
cin >> n >> k;
m = (1 << n) - 1;
for (int i = 0; i < n; i++)
cin >> a[i], sum += a[i];
f[0][0] = 1;
for (int i = 0; i <= m; i++)
{
for (int j = sum / k; j >= 0; j--)
if (f[i][j * k])
f[i][j] = 1;
for (int j = 0; j < n; j++)
if (!(i >> j & 1))
f[i | (1 << j)] |= f[i] << a[j];
}
if (!f[m][1])
return puts("NO"), 0;
puts("YES");
int cnt = 1, dist = 0;
while (m)
{
if (cnt * k <= sum && f[m][cnt * k])
{
dist++, cnt *= k;
continue;
}
for (int i = 0; i < n; i++)
{
if ((m >> i & 1) && cnt >= a[i] && f[m ^ (1 << i)][cnt - a[i]])
{
dis[i] = dist;
m ^= (1 << i);
cnt -= a[i];
break;
}
}
}
for (int i = 0; i < n; i++)
q.push({dis[i], a[i]});
while (q.size() > 1)
{
pii u = q.top();
q.pop();
pii v = q.top();
pii w = u;
q.pop();
cout << u.second << " " << v.second << endl;
w.second += v.second;
while (w.second % k == 0)
{
w.second /= k;
w.first--;
}
q.push(w);
}
return 0;
}你考虑前面放 $1\sim 100$，后面手玩几个小的看一下答案与你插入字符的关系，然后乱搞即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans[520], top;
ll n;
int tmp;
int main()
{
cin >> n;
for (int i = 1; i <= 100; i++)
ans[++top] = i;
while ((1LL << tmp + 1) - 1 <= n)
tmp++;
for (int i = 1; i <= tmp; i++)
ans[++top] = i * 2;
n -= (1LL << tmp) - 1;
// cout << n << endl;
for (int i = tmp - 1; i >= 0; i--)
if (n >> i & 1)
ans[++top] = i * 2 + 1;
cout << top << endl;
for (int i = 1; i <= top; i++)
cout << ans[i] << " ";
cout << endl;
return 0;
}用 $f_{i,j}$ 表示已经排好了 $[1,i]$，最后一个没有改位置的值是 $j$ 的代价。
- 若 $a_i<j$，那么应该是需要往前挪，$f_{i,j}\gets f_{i-1,j}+B$
- 若 $a_i>j$，那么应该是需要往后挪，$f_{i,j}\gets f_{i-1,j}+A$
- 若 $a_i>j$，可以选择不动让后面的往前把自己推走，$f_{i,a_i}\gets f_{i-1,j}$
template <typename T>
void gmn(T &x, T y) { x = min(x, y); }
typedef long long ll;
int n;
ll A, B;
ll a[5020];
ll f[5020][5020];
int main()
{
memset(f, 0x3f, sizeof(f));
cin >> n >> A >> B;
for (int i = 1; i <= n; i++)
cin >> a[i];
f[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= n; j++)
if (a[i] < j)
gmn(f[i][j], f[i - 1][j] + B);
else
gmn(f[i][j], f[i - 1][j] + A), gmn(f[i][a[i]], f[i - 1][j]);
ll ans = 0x3f3f3f3f3f3f3f3f;
for (int i = 1; i <= n; i++)
ans = min(ans, f[n][i]);
cout << ans << endl;
return 0;
}$f_{l,r,cnt}$ 表示 $[l,r]$ 前有 $cnt$ 个 $a_l$ 颜色的珠子所耗费步数。
int dp(int l, int r, int cnt)
{
if (f[l][r][cnt] != -1)
return f[l][r][cnt];
if (l > r)
return f[l][r][cnt] = 0;
if (l == r)
return f[l][r][cnt] = m - cnt - 1;
int &ans = f[l][r][cnt] = (cnt == m - 1 ? dp(l + 1, r, 0) : (cnt < m - 1 ? dp(l, r, cnt + 1) + 1 : inf));
for (int k = l; k < r; k++)
if (a[l] == a[k + 1])
ans = min(ans, dp(l + 1, k, 0) + dp(k + 1, r, min(m - 1, cnt + 1)));
return ans;
}
int lowbit(int x) { return x & -x; }
const int p = 1000000007;
ll f[2][1 << 20];
int n, m, k;
int u, v, w;
int a[50][50];
int main()
{
n = read() - 1, m = read(), k = read();
memset(a, -1, sizeof(a));
for (int i = 0; i < k; i++)
{
u = read(), v = read(), w = read();
a[u][v] = w;
}
f[0][0] = 1;
int tmp = 0, lst = 1;
for (int i = 1; i <= m; i++)
{
for (int j = 0; j < n; j++)
{
tmp ^= 1, lst ^= 1;
memset(f[tmp], 0, sizeof(f[tmp]));
for (int msk = 0; msk < (1 << n); msk++)
{
if ((msk >> j) & 1)
{
if (a[i][j + 1] ^ 0)
(f[tmp][msk] += f[lst][msk]) %= p;
}
else
{
if (a[i][j + 1] ^ 1)
(f[tmp][msk] += f[lst][msk]) %= p;
if (a[i][j + 1] ^ 0)
(f[tmp][msk - (lowbit(msk >> j) << j) + (1 << j)] += f[lst][msk]) %= p;
}
}
}
}
int ans = 0;
for (int i = 0; i < (1 << n); i++)
(ans += f[tmp][i]) %= p;
cout << ans << endl;
return 0;
}考虑构造 $[4,5,7,9,11,13,17,19,23]$。
此时乘积 $>10^9$，和 $<110$。
然后 CRT 求解。
const ll a[] = {0, 4, 5, 7, 9, 11, 13, 17, 19, 23};
const ll s[] = {0, 4, 9, 16, 25, 36, 49, 66, 85, 108};
const ll p = 1338557220;
const ll n = 9;
ll cnt;
ll b[120];
ll N;
int main()
{
cout << 108 << endl;
for (int i = 1; i <= n; i++)
{
while (++cnt < s[i])
cout << cnt + 1 << " ";
cout << s[i - 1] + 1 << " ";
}
cout << endl;
cnt = 0;
for (int i = 1; i <= n; i++)
{
while (++cnt < s[i])
cin >> b[i];
cin >> b[i];
b[i] -= s[i - 1] + 1;
}
for (int i = 1; i <= n; i++)
{
int tmp = 0;
for (int j = 1; j < a[i]; j++)
{
if (p / a[i] * j % a[i] == 1)
{
tmp = p / a[i] * j;
break;
}
}
(N += tmp * b[i]) %= p;
}
cout << N + 1 << endl;
return 0;
}我们可以把题意转化为每次操作有 $\frac{1}{2}$ 的概率，求最后期望逆序对数。最后答案乘上 $2^Q$ 即可。
费马小定理永远的神，我们直接用 $2^{p-2}$ 当逆元就好。const int inv = qpow(2, p - 2);。
const int p = 1000000007;
int n, Q;
int l, r;
ll a[3020];
ll f[3020][3020];
ll qpow(ll x, ll y)
{
ll ret = 1;
for (; y; y >>= 1)
{
if (y & 1)
(ret *= x) %= p;
(x *= x) %= p;
}
return ret;
}
const int inv = qpow(2, p - 2);
int main()
{
cin >> n >> Q;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[i][j] = a[i] < a[j];
for (int i = 1; i <= Q; i++)
{
cin >> l >> r;
f[l][r] = f[r][l] = (f[l][r] + f[r][l]) * inv % p;
for (int j = 1; j <= n; j++)
{
if (j ^ l && j ^ r)
{
f[l][j] = f[r][j] = (f[l][j] + f[r][j]) * inv % p;
f[j][l] = f[j][r] = (f[j][l] + f[j][r]) * inv % p;
}
}
}
ll ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
(ans += f[i][j]) %= p;
(ans *= qpow(2, Q)) %= p;
cout << ans << endl;
return 0;
}考虑 $f_{i,j,k}$ 表示前 $i$ 个学生，有 $j$ 组还没定下来，总贡献为 $k$。
然后我们分类讨论当前学生的状态：
- 自己一组 $f_{i+1,j,k+tmp}\gets f_{i+1,j,k+tmp}+f_{i,j,k}$
- 新开一组 $f_{i+1,j+1,k+tmp}\gets f_{i+1,j+1,k+tmp}+f_{i,j,k}$
- 结束一组 $f_{i+1,j-1,k+tmp}\gets f_{i+1,j-1,k+tmp}+j\times f_{i,j,k}$
- 延续一组 $f_{i+1,j,k+tmp}\gets f_{i+1,j,k+tmp}+j\times f_{i,j,k}$
其中 $tmp$ 为 $j\times (a_{i+1}-a_i)$。
注意新开一组和结束一组的边界。
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
f[1][0][0] = f[1][1][0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= i; j++)
{
int tmp = j * (a[i + 1] - a[i]);
for (int k = 0; k <= m - tmp; k++)
{
(f[i + 1][j][k + tmp] += f[i][j][k]) %= p;
if (j ^ n)
(f[i + 1][j + 1][k + tmp] += f[i][j][k]) %= p;
if (j ^ 0)
(f[i + 1][j - 1][k + tmp] += 1LL * j * f[i][j][k] % p) %= p;
(f[i + 1][j][k + tmp] += 1LL * j * f[i][j][k] % p) %= p;
}
}
}
int ans = 0;
for (int i = 0; i <= m; i++)
(ans += f[n][0][i]) %= p;
cout << ans << endl;碰到一个不满足的就往外扔。扔的时候改变自己的编号。
void getOut(int u)
{
int cnt = 0;
for (int v : a[u])
if (!(team[u] ^ team[v]))
cnt++;
if (cnt > 1)
{
team[u] ^= 1;
for (int v : a[u])
getOut(v);
}
}$(^n_3)-\sum (^{d_i}_2)$ 即为答案，扫描线可以做到 $\mathcal O(n \log n)$。
要注意先离散化。非 + - * 的线段树要单独判 tag。
struct SegTree
{
int L, R;
ll sum;
bool tag;
} Tree[400020];
void pushdown(int id, int L, int R)
{
if (Tree[id].tag)
{
int mid = L + R >> 1;
Tree[id << 1].tag ^= 1;
Tree[id << 1 | 1].tag ^= 1;
Tree[id << 1].sum = mid - L + 1 - Tree[id << 1].sum;
Tree[id << 1 | 1].sum = R - mid - Tree[id << 1 | 1].sum;
Tree[id].tag = 0;
}
}
void build(int id, int L, int R)
{
Tree[id].L = L;
Tree[id].R = R;
Tree[id].tag = Tree[id].sum = 0;
if (L == R)
return;
int mid = L + R >> 1;
build(id << 1, L, mid);
build(id << 1 | 1, mid + 1, R);
Tree[id].sum = Tree[id << 1].sum + Tree[id << 1 | 1].sum;
}
ll query(int id, int L, int R, int qL, int qR)
{
if (qL <= L && R <= qR)
return Tree[id].sum;
pushdown(id, L, R);
int mid = L + R >> 1;
ll ans = 0;
if (Tree[id << 1].R >= qL)
ans += query(id << 1, L, mid, qL, qR);
if (Tree[id << 1 | 1].L <= qR)
ans += query(id << 1 | 1, mid + 1, R, qL, qR);
return ans;
}
void add(int id, int L, int R, int qL, int qR)
{
if (qL <= L && R <= qR)
return Tree[id].sum = R - L + 1 - Tree[id].sum, Tree[id].tag ^= 1, void();
pushdown(id, L, R);
int mid = L + R >> 1;
if (Tree[id << 1].R >= qL)
add(id << 1, L, mid, qL, qR);
if (Tree[id << 1 | 1].L <= qR)
add(id << 1 | 1, mid + 1, R, qL, qR);
Tree[id].sum = Tree[id << 1].sum + Tree[id << 1 | 1].sum;
}
int main()
{
n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i] = b[i] = read(), c[i] = -b[i];
sort(b + 1, b + n + 1);
sort(c + 1, c + n + 1);
for (int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
for (int i = 1; i <= m; i++)
p[i].first = lower_bound(b + 1, b + n + 1, read()) - b, p[i].second = n - (lower_bound(c + 1, c + n + 1, -read()) - c) + 1;
for (int i = 1; i <= m; i++)
{
if (p[i].first > p[i].second)
continue;
Left[p[i].first].push_back(p[i].second);
Right[p[i].second].push_back(p[i].first);
}
ans = 1LL * n * (n - 1) * (n - 2) / 6;
build(1, 1, n);
for (int i = 1; i <= n; i++)
{
for (int j : Left[i])
add(1, 1, n, i, j);
ll tmp = query(1, 1, n, 1, n) - query(1, 1, n, i, i);
ans -= tmp * (tmp - 1) >> 1;
add(1, 1, n, i, i);
for (int j : Right[i])
add(1, 1, n, j, i);
}
cout << ans << endl;
return 0;
}咋是个紫？
对角线不相交显然是选出来的行列之和一奇一偶。
然后考虑前缀和，$f_{i,j,0}$ 表示左上到右下，$f_{i,j,0}$ 表示右上到左下。
转移 $f_{i,j,0}\gets f_{i-1,j-1,0}+a_{i,j},f_{i,j,1}\gets f_{i-1,j+1,1}+a_{i,j}$。
查询就找到对应的结束位置即可。
ll S(int x, int y)
{
int p = min(n - x, n - y), q = min(n - x, y - 1);
return f[x + p][y + p][0] + f[x + q][y - q][1] - a[x][y];
}然后就做完了。
typedef long long ll;
int n;
ll f[2020][2020][2];
ll a[2020][2020];
int A, B, C, D;
ll mxA, mxB;
ll S(int x, int y)
{
int p = min(n - x, n - y), q = min(n - x, y - 1);
return f[x + p][y + p][0] + f[x + q][y - q][1] - a[x][y];
}
void F(int x, int y)
{
ll tmp = S(x, y);
if (tmp >= mxA)
A = x, B = y, mxA = tmp;
}
void G(int x, int y)
{
ll tmp = S(x, y);
if (tmp >= mxB)
C = x, D = y, mxB = tmp;
}
int main()
{
n = read();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
f[i][j][1] = f[i][j][0] = a[i][j] = read();
f[i][j][0] += f[i - 1][j - 1][0];
f[i][j][1] += f[i - 1][j + 1][1];
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i + j & 1)
G(i, j);
else
F(i, j);
cout << mxA + mxB << endl;
cout << A << " " << B << " " << C << " " << D << endl;
return 0;
}根据裴蜀定理，本题可以转化为选择若干个 $l_i$ 使得 $\sum c_i$ 最小。
考虑 STL 优化暴力 DP，掌握 STL 后比较简单。
cin >> n;
for (int i = 1; i <= n; i++)
cin >> l[i];
for (int i = 1; i <= n; i++)
cin >> c[i], f[l[i]] = (!f[l[i]] ? c[i] : min(f[l[i]], 1LL * c[i]));
for (int i = 1; i <= n; i++)
{
for (auto g : f)
{
int G = __gcd(l[i], g.first);
f[G] = !f[G] ? f[g.first] + c[i] : min(f[G], f[g.first] + c[i]);
}
}
cout << (f[1] ? f[1] : -1) << endl;或者转化为最短路，边权即为 $c_i$，邻居为 $\gcd(u,l_i)$。
void dijk()
{
f[0] = 0;
q.push(make_pair(0, 0));
while (!q.empty())
{
int u = q.top().second;
q.pop();
if (vis[u])
continue;
vis[u] = 1;
for (int i = 1; i <= n; i++)
{
int v = __gcd(l[i], u);
if (u == v)
continue;
if (!f.count(v) || f[v] > f[u] + c[i])
{
f[v] = f[u] + c[i];
q.push(make_pair(f[v], v));
}
}
}
}最短路计数，但是 dijkstra。
void dijk()
{
memset(dis, 0x3f, sizeof(dis));
priority_queue<pli, vector<pli>, greater<pli>> q;
q.push({0, 1});
dis[1] = 0;
while (!q.empty())
{
int u = q.top().second;
q.pop();
if (vis[u])
continue;
vis[u] = 1;
for (auto p : a[u])
{
int v = p.second;
ll w = p.first;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
q.push({dis[v], v});
cnt[v] = 1;
}
else if (!(dis[v] ^ dis[u] + w))
{
cnt[v]++;
}
}
}
}
dijk();
int ans = 0;
for (int i = 1; i <= k; i++)
{
int v = special[i].first;
ll w = special[i].second;
if (dis[v] < w)
ans++;
if (dis[v] == w && cnt[v] > 1)
{
ans++;
cnt[v]--;
}
}
cout << ans << endl;记录每个点最短路条数，参考 P1144 最短路计数。警察局显然摆放在 $n$ 最优。
memset(d1, -1, sizeof(d1));
memset(d2, -1, sizeof(d2));
d1[1] = 0;
f1[1] = 1;
q.push(1);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = 0; i < a[u].size(); i++)
{
int e = a[u][i];
if (d1[e] == -1)
{
d1[e] = d1[u] + 1;
f1[e] = f1[u];
q.push(e);
}
else if (d1[e] == d1[u] + 1)
{
f1[e] += f1[u];
}
}
}
d2[n] = 0;
f2[n] = 1;
q.push(n);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = 0; i < a[u].size(); i++)
{
int e = a[u][i];
if (d2[e] == -1)
{
d2[e] = d2[u] + 1;
f2[e] = f2[u];
q.push(e);
}
else if (d2[e] == d2[u] + 1)
{
f2[e] += f2[u];
}
}
}
ll cnt = f1[n];
for (int i = 2; i < n; i++)
if (d1[i] + d2[i] == d1[n])
cnt = max(cnt, f1[i] * f2[i] * 2);
cout << fixed << setprecision(6) << (double)cnt / f1[n] << endl;一眼即可得到留下边数一定是 $\min\{k,n-1\}$，考虑留哪些边。
最短路过程中输出松弛的边即可。链式前向星或者 map 记录连接 $u,v$ 的具体是第几条边。
void dijkstra(int u)
{
int v;
long long w;
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0;
q.push({{0, u}, 0});
while (!q.empty())
{
u = q.top().first.second;
w = q.top().first.first;
int id = q.top().second;
q.pop();
if (vis[u])
continue;
vis[u] = 1;
if (id)
cout << id << " ", k--;
if (!k)
return;
for (int i = 0; i < a[u].size(); i++)
{
v = a[u][i].v;
w = a[u][i].w;
if (dis[v] > dis[u] + w)
{
pre[v] = u;
sz[v] = sz[u] + 1;
dis[v] = dis[u] + w;
q.push({{dis[v], v}, mp[u][v]});
}
}
}
}考虑类似树的直径做法，我们这里找鬼的直径。第一个鬼开始找最远，最远的开始再找最远，正确性证明参考树的直径证明，而且这里边权为一好像更好证吧。
然后对于相隔最远的两个鬼，判断点到鬼的距离是不是 $\leq d$。
cin >> n >> m >> d;
for (int i = 1; i <= m; i++)
cin >> p[i], pos[p[i]] = 1;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
int x, y, z, ans = 0;
bfs(p[1], 0, x);
bfs(x, 1, y);
bfs(y, 2, z);
for (int i = 1; i <= n; i++)
{
if (dis[i][1] <= d && dis[i][2] <= d)
{
ans++;
}
}
cout << ans << endl;一眼区间 DP。枚举过渡点 $k$，做完了。
考虑到乘法的正负号带来的影响，我们需要记录每段区间最大值与最小值。
$f_{0,i,j}$ 表示 $\max\limits_{k\in[i,j]}\{a_k\}$，$f_{1,i,j}$ 表示 $\min\limits_{k\in[i,j]}\{a_k\}$。
加法最大最小很好转移，没有正负影响，乘法直接暴力枚举（确信）所有可能算最大最小。
cin >> n;
for (int i = 1; i <= n; i++)
cin >> c[i] >> a[i], c[n + i] = c[i], a[n + i] = a[i];
for (int i = 1; i <= n << 1; i++)
for (int j = 1; j <= n << 1; j++)
f[0][i][j] = -inf, f[1][i][j] = inf;
for (int i = 1; i <= n; i++)
f[0][i][i] = f[0][n + i][n + i] = f[1][i][i] = f[1][n + i][n + i] = a[i];
for (int len = 2; len <= (n << 1); len++)
{
for (int l = 1; l <= (n << 1) - len + 1; l++)
{
int r = l + len - 1;
for (int k = l; k < r; k++)
{
if (c[k + 1] == 't')
{
gmx(f[0][l][r], f[0][l][k] + f[0][k + 1][r]);
gmn(f[1][l][r], f[1][l][k] + f[1][k + 1][r]);
}
else
{
gmx(f[0][l][r], f[0][l][k] * f[0][k + 1][r]);
gmx(f[0][l][r], f[1][l][k] * f[1][k + 1][r]);
gmn(f[1][l][r], f[0][l][k] * f[0][k + 1][r]);
gmn(f[1][l][r], f[0][l][k] * f[1][k + 1][r]);
gmn(f[1][l][r], f[1][l][k] * f[0][k + 1][r]);
gmn(f[1][l][r], f[1][l][k] * f[1][k + 1][r]);
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
gmx(ans, f[0][i][i + n - 1]);
cout << ans << endl;
for (int i = 1; i <= n; i++)
if (f[0][i][i + n - 1] == ans)
cout << i << " ";
cout << endl;此题有很多种做法，可以考虑拆点，将每个点拆成 $(id,company)$ 的形式。也可以建虚点维护连通块，这些是比较常规的做法，码量也比较大。具体可以看我的 AT 提交记录。
这里提供一种炫酷的方法，用数据结构（例 C++ STL set）维护每个点最短路经历了哪些公司，动态处理边权。
void dij(int u)
{
memset(dis, 0x3f, sizeof(dis));
priority_queue<pii> pq;
pq.push({0, u});
dis[u] = 0;
while (!pq.empty())
{
u = pq.top().second;
pq.pop();
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i].second;
int w = !S[u].count(G[u][i].first);
if (dis[v] > dis[u] + w)
dis[v] = dis[u] + w, S[v].clear(), S[v].insert(G[u][i].first), pq.push({-dis[v], v});
else if (dis[v] == dis[u] + w)
S[v].insert(G[u][i].first);
}
}
}简单的状压，也可以维护一个数组记录。每次选一个难得给他找一个女朋友，然后继续搜索，当前已经到最后一个的时候判断是否所有人都有了女朋友。
mod_int 是网上抄的封装好的取模板子，可以忽略不计，算答案时候取模同效。
mod_int<p> dp(int i, int S)
{
if (f[i][S] != -1)
return f[i][S];
if (i == n - 1)
return (S == (1 << n) - 1);
mod_int<p> ret = 0;
for (int j = 0; j < n; j++)
if (a[i + 1][j] && !(S >> j & 1))
ret += dp(i + 1, S | (1 << j));
f[i][S] = ret.val();
return ret.val();
}
mod_int<p> ans;
int main()
{
memset(f, -1, sizeof(f));
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
for (int j = 0; j < n; j++)
if (a[0][j])
ans += dp(0, 1 << j);
cout << ans << endl;
return 0;
}显然的，考虑区间 DP。设 $f_{i,j}$ 表示 $i$ 是否能够遇上 $j$，枚举过渡点 $k$，显然有 $f_{i,k}=f_{j,k}=1$ 时可以推出 $f_{i,j}=1$。然后会喜提 WA。注意 $i,j$ 必须有一个人能干掉 $k$ 才可以转移。
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> c, a[i][j] = a[i + n][j] = a[i][j + n] = a[i + n][j + n] = c - '0';
for (int len = 1; len <= n; len++)
{
for (int i = 1; i + len <= n * 2; i++)
{
int j = i + len;
if (len == 1)
{
f[i][j] = 1;
continue;
}
for (int k = i; k <= j; k++)
{
if (f[i][k] && f[k][j] && (a[i][k] || a[j][k]))
{
f[i][j] = 1;
break;
}
}
}
}
vector<int> ans;
for (int i = 1; i <= n; i++)
if (f[i][i + n])
ans.push_back(i);
cout << ans.size() << endl;
for (int i : ans)
cout << i << endl;考虑两次最短路，一次多源处理两两最短路，一次知道了最短路后暴力加边，在新图上继续最短路即为答案。
cin >> n >> m >> x >> y;
while (m--)
{
cin >> u >> v >> w;
a[u].push_back({v, w});
a[v].push_back({u, w});
}
for (int i = 1; i <= n; i++)
dijkstra(i, dis[i]);
for (int i = 1; i <= n; i++)
a[i].clear();
for (int i = 1; i <= n; i++)
{
long long t, c;
cin >> t >> c;
for (int j = 1; j <= n; j++)
if (dis[i][j] <= t && (i ^ j))
a[i].push_back({j, c});
}
dijkstra(x, dis[0]);
cout << (dis[0][y] ^ inf ? dis[0][y] : -1) << endl;nxt[i][j] 表示「猫在 $i$ 鼠在 $j$ 猫的下一步」，注意猫同距离找编号最小。
然后是简单的期望，记忆化搜索完成会很方便。转移 $f_{u,v}\gets \sum\limits\frac{f{u^\prime,v^\prime}}{deg_v+1}+\frac{f{u^\prime,v}}{deg_v+1}$，其中 $u^\prime$ 表示 $u$ 的邻居， $v^\prime$ 表示 $v$ 的邻居。
$dis_{u,v}$ 因为边权为 $1$ 可以直接 bfs $n^2$ 预处理出来。
void initNext()
{
memset(nxt, 0x3f, sizeof(nxt));
for (int cat = 1; cat <= n; cat++)
{
for (int cat_neighbour : G[cat])
{
for (int mouse = 1; mouse <= n; mouse++)
{
if (dis[cat][mouse] - 1 == dis[cat_neighbour][mouse])
nxt[cat][mouse] = min(nxt[cat][mouse], cat_neighbour);
}
}
}
}
double dp(int cat, int mouse)
{
if (f[cat][mouse] != -1)
return f[cat][mouse];
if (cat == mouse)
return f[cat][mouse] = 0;
if (dis[cat][mouse] <= 2)
return f[cat][mouse] = 1;
int p = G[mouse].size() + 1;
f[cat][mouse] = 1;
for (int mouse_neighbour : G[mouse])
{
f[cat][mouse] += dp(nxt[nxt[cat][mouse]][mouse], mouse_neighbour) / p;
}
f[cat][mouse] += dp(nxt[nxt[cat][mouse]][mouse], mouse) / p;
// cout << cat << " " << mouse << " " << f[cat][mouse] << endl;
return f[cat][mouse];
}
3 条评论
Orz cyx
cyxakioi
fake