U130826 括号匹配2
利用前缀和的思想即可，这道题没什么营养就不讲了。
另外本题有另一种做法，即利用栈括号匹配的性质。考虑一般的括号序列 dp：设 (f_i) 表示以 (i) 结尾的括号匹配串数量， 那么 (f_i = f_{pre_{i}-1} + 1). 也就是硬塞一个。那么只需要根据这段区间内有几个 * 号转移即可。复杂度也是 (O(n)) 的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5, CONST = 1e6;
int n;
char s[N];
int pre[N], sum[N], pool[N];
int op(char x) {
if (x == '(') return 1;
else return -1;
}
void solve() {
scanf ("%s", s + 1);
n = strlen(s + 1);
ll ans = 0;
for (int i = 1; i <= n; ++i) if (s[i] == '*') {
int l = i - 1, r = i + 1;
while (l >= 1 && s[l] != '*') --l;
while (r <= n && s[r] != '*') ++r;
pre[i] = sum[i] = 0;
for (int j = i + 1; j < r; ++j) {
sum[j] = sum[j - 1] + op(s[j]);
pre[j] = min(pre[j - 1], sum[j]);
if (pre[j] >= sum[j]) pool[sum[j] + CONST]++;
}
for (int j = i - 1; j > l; --j) {
pre[j] = min(pre[j + 1] + op(s[j]), op(s[j]));
sum[j] = sum[j + 1] + op(s[j]);
if (pre[j] < 0) continue;
ans += pool[-sum[j] + CONST];
}
for (int j = i + 1; j < r; ++j) pool[sum[j] + CONST] = 0;
}
cout << ans << '
';
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}
U131044 关押罪犯
首先将所有数排序，那么接下来就是一个 trivial 的 dp: 设 (black_{i, x}, white_{i, x}) 表示 (i) 这个人进入了黑队/白队，上一个与我颜色不同的人数值是 (x) 的方案数，线段树优化 (dp) 转移即可。
不过发现这个优化转移是一个区间清零，前缀求和的操作，而且之前清零的位置并不会动，那么只需要顺带记录一下之前清零清到了哪里，就可以直接减掉来维护了。复杂度 (O(n log n)) 或 (O(n)).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N = 500505, P = 1e9 + 7;
int add(int a, int b) {
return (a += b) >= P ? a - P : a;
} int sub(int a, int b) {
return (a -= b) < 0 ? a + P : a;
}
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int n, Ga, Gb, x[N], y[N], cnt;
struct BIT {
int sum[N];
void ADD(int p, int val) {
for (; p <= cnt; p += p & -p) sum[p] = add(sum[p], val);
}
int qry(int p) {
int ans = 0;
for (; p; p -= p & -p) ans = add(ans, sum[p]);
return ans;
}
}I, II;
int getpos(int t) {
return upper_bound(y + 1, y + cnt + 1, t) - (y + 1);
}
int real(int i) {
return y[x[i]];
}
int main() {
cin >> n >> Ga >> Gb;
for (int i = 1; i <= n; ++i) x[i]=read(),y[++cnt] = x[i];
sort (x + 1, x + n + 1);
y[++cnt] = -1e9;
sort (y + 1, y + cnt + 1);
cnt = unique(y + 1, y + cnt + 1) - (y + 1);
for (int i = 1; i <= n; ++i) x[i] = lower_bound(y + 1, y + cnt + 1, x[i]) - y;
I.ADD(1, 1);
II.ADD(1, 1);
int posI = 0, posII = 0;
for (int i = 1; i < n; ++i) {
int L = getpos(real(i + 1) - Ga), LL = getpos(real(i + 1) - Gb);
int for2 = sub(I.qry(L), posI), for1 = sub(II.qry(LL), posII);
if (real(i + 1) - real(i) < Gb) posI = I.qry(x[i] - 1);
if (real(i + 1) - real(i) < Ga) posII = II.qry(x[i] - 1);
II.ADD(x[i], for2);
I.ADD(x[i], for1);
}
// cout << posI << " " << posII << '
';
cout << sub(add(I.qry(cnt), II.qry(cnt)), add(posI, posII)) << '
';
return 0;
}
U131060 最后的球
这题是代表元计数法的一个 Bonus.
首先需要注意到对于任意一个后缀，颜色数肯定是小于黑球数量的。那么记 (dp_{i, j}) 为当前放了 (i) 个黑球，(j) 个颜色的方案数。
决策下一个位置放黑球还是放颜色，如果放颜色的话相当于就是后缀进行一波插板。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N = 2000 * 2000 + 100, P = 1e9 + 7;
int n, k;
int f[2005][2005];
int fac[N], ifac[N];
int qpow(int a, int b) {
int res(1);
for (; b; b >>= 1) {
if (b & 1) res = (ll)res * a % P;
a = (ll)a * a % P;
}
return res;
}
int C(int a, int b) {
if (a < b) return 0;
// cout << a << " " << b << ": " << (ll)fac[a] * ifac[a - b] % P * ifac[b] % P << '
';
return (ll)fac[a] * ifac[a - b] % P * ifac[b] % P;
}
int main() {
fac[0] = 1;
for (int i = 1; i < N; ++i) fac[i] = (ll)fac[i - 1] * i % P;
ifac[N - 1] = qpow(fac[N - 1], P - 2);
for (int i = N - 2; i >= 0; --i) ifac[i] = (ll)ifac[i + 1] * (i + 1) % P;
cin >> n >> k;
if (k == 1) return cout << 1, 0;
f[0][0] = 1;
for (int SUM = 0; SUM <= 2 * n; ++SUM) {
for (int i = 0; i <= min(n, SUM); ++i) {
int j = SUM - i;
if (j > n) continue;
// case 1
if (i + 1 >= j) (f[i + 1][j] += f[i][j]) %= P;
// case 2
if (i >= j + 1) (f[i][j + 1] += (ll)f[i][j] * (n - j) % P * C(n * k - i - j * (k - 1) - 1, k - 2) % P) %= P;
}
}
cout << f[n][n] << '
';
return 0;
}