烂。Rank
A. 好数（number）
签，唐，没签上。
考虑之前几次类似的题方法都是选 \(k-1\) 的方案存起来以使总复杂度除以一个 \(n\)，故考虑记共 \(n^2\) 个两两组合之和，枚举当前点 \(i\) 前面的点，找是否有值为它们的差的组合，复杂度 \(\mathcal{O(n^2)}\)，用 map 记再挂个 \(\log n\)。
赛时唐氏枚举反了，使复杂度成为 \(\mathcal{O(n^3\log n)}\)，然后被 hack 10pts。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch = getchar();lx x = 0 , f = 1;
for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e4 + 5, M = 3e7 + 5;
int n, ans;
int a[N], nc[M], tot;
unordered_map<int,int> st;
namespace Wisadel
{
short main()
{
// freopen(".in", "r", stdin) , freopen(".out", "w", stdout);
// freopen(".err", "w", stderr);
freopen("number.in", "r", stdin) , freopen("number.out", "w", stdout);
n = qr;
fo(i, 1, n) a[i] = qr;
st[2 * a[1]] = 1;
fo(i, 2, n)
{
fo(j, 1, i - 1)
if(st[a[i] - a[j]]){ans++; break;}
fo(j, 1, i) st[a[i] + a[j]] = 1;
}
printf("%d\n", ans);
return Ratio;
}
}
int main(){return Wisadel::main();}
B. SOS字符串（sos）
不难想的分讨型 dp，但赛时脑子被卡住了一点没想 dp。
发现转移只用到后串的最后几个字符，且只用到两种状态：
- \(S\rightarrow SO\)
- \(SO\rightarrow SOS\)
故 dp 数组设为 \(f_{i,0/1/2}\)，0/1 对应上面两种，2 表示除上述两种以外的状态，SOS 也计入状态 2。题目要求 SOS 出现三次及以上数量，我们再开一维 0/1/2/3 表示目前已经出现了几次 SOS，超过 3 次计入 3 状态内。然后就可以开始分讨状态转移方程了。
- 对于 \(f_{i,0,j}\)，\(i-1\) 为 S，第 \(i\) 位仍为 S；\(i-1\) 为状态 2，第 \(i\) 位也可放 S，故有：
- 对于 \(f_{i,0,j}\)，\(i-1\) 为 S，\(i\) 位放 O，故有：
- 对于 \(f_{i,2,j}\)，\(i-1\) 为 S，\(i\) 位放除 S、O 以外的 24 种字母；\(i-1\) 为 SO，\(i\) 位放除 S、O 以外的 24 种字母；\(i-1\) 为状态 2，\(i\) 位放除 S 以外的 25 种字母，故有：
- 考虑当 \(j\gt 0\) 时，SOS 可由 SO 加 S 转移而来，故有：
- 考虑当 \(j= 3\) 时，由于 3 次及以上都计入 3 内，SOS 可由 SO 加 S 转移而来，故有：
最终答案为 \(\sum_{i=0}^2\ f_{n,i,3}\)。复杂度线性，有 4 的常数。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch = getchar();lx x = 0 , f = 1;
for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n;
ll f[N][3][4];
namespace Wisadel
{
short main()
{
// freopen(".in", "r", stdin) , freopen(".out", "w", stdout);
// freopen(".err", "w", stderr);
freopen("sos.in", "r", stdin) , freopen("sos.out", "w", stdout);
n = qr;
f[0][2][0] = 1;
fo(i, 1, n)
{
fo(j, 0, 3)
{
f[i][0][j] = (f[i][0][j] + f[i - 1][2][j] + f[i - 1][0][j]) % mod;
f[i][1][j] = (f[i][1][j] + f[i - 1][0][j]) % mod;
f[i][2][j] = (f[i][2][j] + f[i - 1][0][j] * 24 + f[i - 1][1][j] * 25 + f[i - 1][2][j] * 25) % mod;
if(j > 0) f[i][2][j] = (f[i][2][j] + f[i - 1][1][j - 1]) % mod;
if(j == 3) f[i][2][j] = (f[i][2][j] + f[i - 1][1][j]) % mod;
}
}
printf("%lld\n", (f[n][0][3] + f[n][1][3] + f[n][2][3]) % mod);
return Ratio;
}
}
int main(){return Wisadel::main();}
C. 集训营的气球（balloon）
很好的 trick：退背包。
先考虑部分分，发现存在修改与查询，故考虑线段树。发现 \(c\le 20\)，我们可以求出每一个子段内不同 \(c\) 的方案数，超过 \(c\) 计入 \(c\) 内。
证明
证：\(f_{rt,k}=\sum_{i+j=k}f_{ls,i}\times f_{rs,j} (k\lt c)\)，\(f_{rt,c}=\sum_{i+j\ge c} f_{ls,i}\times f_{rs,j}\)。
对于前一个式子是比较显然的：左选 \(i\) 个，右选 \(j\) 个得出共选 \(i+j\) 个的方案数。主要考虑第二个式子。
已知 \(i+j\ge c\)，即左中所有子方案都选 \(i\) 个，右中所有子方案都选 \(j\) 个，依据乘法原理，得出左右子方案两两相乘得到总方案的所有子方案，每个子方案都选 \(i+j\ge c\) 个，显然计入 \(c\) 中不重不漏。
这样做时间复杂度是 \(\mathcal{O(nc^2\log n+q)}\) 的，空间复杂度按四倍空间算是 \(\mathcal{O(4nc^2)}\) 的，无论时间还是空间都过不去 \(n=10^6\) 的点。这样算上前三个 Subtask 的背包得分，最高可获得 80pts。
考虑正解。正解需要由前三个 Subtask 所推的 01 背包做法优化得来，考虑怎么背包。将题目视为容量为 \(c\)，每个人体积为 1 并将 \(a_i\)，\(b_i\) 看作权重计入，发现需要算大于 \(c\) 的所有容量的方案数，复杂度是 \(\mathcal{O(n^2)}\) 的，显然不可行。
发现容量不超过 \(c\) 的情况很小，故正难则反考虑容斥，用总方案数减去容量小于 \(c\) 的方案数求解。这样在不带修的情况下，我们的复杂度就降到 \(\mathcal{O(nc)}\) 了。
考虑带修改怎么做。我们将修改操作视为删除与添加，删除时直接在 dp 数组中删去该需求的全部贡献，其实就是反着做 01 背包，然后在插入一个新需求，即给它单独做一个 01 背包。这就是退背包。这样我们的总复杂度就是 \(\mathcal{O(nc+qc)}\) 了。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch = getchar();lx x = 0 , f = 1;
for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e6 + 1, M = 1e6;
const int mod = 1e9 + 7;
int n, c, m;
ll a[N], b[N];
ll f[21], tot;
namespace Wisadel
{
ll Wqp(ll x, int y)
{
ll res = 1;
while(y){if(y & 1) res = res * x % mod; x = x * x % mod; y >>= 1;}
return res;
}
void Wjin(int x)
{
fu(i, c - 1, 1) f[i] = (f[i - 1] * a[x] % mod + f[i] * b[x] % mod) % mod;
f[0] = f[0] * b[x] % mod;
tot = tot * (a[x] + b[x]) % mod;
}
void Wtui(int x)
{
ll ny = Wqp(b[x], mod - 2);
f[0] = f[0] * ny % mod;
fo(i, 1, c - 1) f[i] = (f[i] - f[i - 1] * a[x] % mod + mod) % mod * ny % mod;
tot = tot * Wqp(a[x] + b[x], mod - 2) % mod;
}
short main()
{
// freopen(".in", "r", stdin) , freopen("a.out", "w", stdout);
// freopen(".err", "w", stderr);
freopen("balloon.in", "r", stdin) , freopen("balloon.out", "w", stdout);
n = qr, c = qr;
fo(i, 1, n) a[i] = qr;
fo(i, 1, n) b[i] = qr;
f[0] = tot = 1;
fo(i, 1, n) Wjin(i);
m = qr;
fo(i, 1, m)
{
int x = qr, aa = qr, bb = qr;
Wtui(x);
a[x] = aa, b[x] = bb;
Wjin(x);
ll ans = tot;
fo(j, 0, c - 1) ans = (ans - f[j] + mod) % mod;
printf("%lld\n", ans);
}
return Ratio;
}
}
int main(){return Wisadel::main();}
D. 连通子树与树的重心（tree）
别急
标签：fo,ch,05,int,模拟,freopen,define,NOIP2024,mod From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18459018