提高组杂题训练1
A [USACO22DEC] Breakdown P
首先 \(N\le300\) \(k\le8\) 看样子复杂度是个 3 次的东西。一些套路的东西比如删边改加边不说了。这个 \(K\le8\) 很有讲究。
首先，不妨折半一下，算出从 1 经过一半条边到 \(u\) 的最短路径和 \(u\) 到 \(n\) 的最短路径，那么答案就可以 \(\mathcal{O}(n)\) 合并。对于 \(k'\le 4\) ，可以维护两个数组 \(f[u][v]\) 和 \(g[u][v]\)，分别表示 \(u\sim v\) 走一条边和走两条边的最短路，维护 \(h[u]\) 数组表示从起始节点到 \(u\) 经过 \(k'\) 条边的最短路径。可以惊人的发现 1 和 2 可以凑出所有 4 以内的情况！！当加入边 \(u, v\) 时，当且仅当 \(u\) 为 \(bg\) 的时候需要枚举所有断点维护 \(h\)，所以加边操作均摊 \(\mathcal{O}(n)\)。总复杂度 \(\mathcal{O}(N^3)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 305;
int n, k, x[N*N], y[N*N], ans[N*N], edge[N][N];
struct XiaoLe{
int f[N][N], g[N][N], h[N], fk, bg;
const int& operator [](const int x) const { return h[x]; }
inline void build(int kf, int gb){
fk = kf; bg = gb;
memset(f, 0x3f, sizeof(f));
if(fk > 1) memset(g, 0x3f, sizeof(g));
memset(h, 0x3f, sizeof(int)*(n+1));
if(!fk) h[bg] = 0;
}
inline void add(int u, int v, int val){
if(!fk) return;
if(fk == 1){
if(u ^ bg) return;
h[v] = min(h[v], val);
return;
}
f[u][v] = val;
for(int i=1; i<=n; ++i){
g[i][v] = min(g[i][v], f[i][u] + val);
g[u][i] = min(g[u][i], val + f[v][i]);
}
if(fk == 2){
for(int i=1; i<=n; ++i)
h[i] = min(h[i], g[bg][i]);
} else if(fk == 3){
if(u == bg){
for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j)
h[i] = min(h[i], f[bg][j] + g[j][i]);
} else{
for(int i=1; i<=n; ++i){
h[i] = min({h[i], g[bg][u] + f[u][i], g[bg][v] + f[v][i]});
h[u] = min(h[u], f[bg][i] + g[i][u]);
h[v] = min(h[v], f[bg][i] + g[i][v]);
}
}
} else{
if(u == bg){
for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j)
h[i] = min(h[i], g[bg][j] + g[j][i]);
} else {
for(int i=1; i<=n; ++i){
h[i] = min({h[i], g[bg][u] + g[u][i], g[bg][v] + g[v][i]});
h[u] = min(h[u], g[bg][i] + g[i][u]);
h[v] = min(h[v], g[bg][i] + g[i][v]);
}
}
}
}
} m1, mn;
signed main(){
ios::sync_with_stdio(0), cout.tie(0), cout.tie(0);
cin>>n>>k; int nn = n * n;
for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j)
cin>>edge[i][j];
m1.build(k >> 1, 1), mn.build((k + 1) >> 1, n);
memset(ans, 0x3f, sizeof(int)*(nn+1));
for(int i=1; i<=nn; ++i) cin>>x[i]>>y[i];
for(int i=nn, u, v; i>=1; --i){
for(int j=1; j<=n; ++j)
ans[i] = min(ans[i], m1[j] + mn[j]);
ans[i] = ans[i] > 1e9 ? -1 : ans[i];
u = x[i], v = y[i];
m1.add(u, v, edge[u][v]);
mn.add(v, u, edge[u][v]);
}
for(int i=1; i<=nn; ++i) cout<<ans[i]<<'\n';
return 0;
}
B [USACO22DEC] Making Friends P
按时间模拟，对每个节点维护 set 表示当前节点都和谁是朋友关系，每次删掉一个节点之后，ans 就加上 size，并把新建立的朋友关系加到下一个最先走掉的节点的 set 里。相当于维护一个集合，也可以使用线段树合并。最后 ans -= m。
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 5;
int n, m; long long ans;
set<int> st[N];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m; ans = -m;
for(int i=1, u, v; i<=m; ++i){
cin>>u>>v; if(u > v) swap(u, v);
st[u].insert(v);
}
for(int i=1; i<=n; ++i){
if(st[i].empty()) continue;
ans += st[i].size();
int u = *st[i].begin(), v = i;
st[i].erase(st[i].begin());
if(st[u].size() < st[v].size()) swap(st[u], st[v]);
for(int it : st[v]) st[u].insert(it);
} return cout<<ans<<'\n', 0;
}
C [USACO22DEC] Palindromes P
分析一下回文串的性质，因为只有两种字符，所以很好分析，这两种字符就用 \(0\) \(1\) 代替了，并且只要 \(1\) 满足性质，\(0\) 必然满足，所以只分析 \(1\) 即可。
对于一个串 \([L,R]\) ，它是轴对称的，并且对称中心为一个或者两个 \(1\)，不妨枚举所有对称中心并扩展。假如扩展的两个 \(1\) 分别为 \(l\) 和 \(r\)，那么这俩关于对称中心的充要条件即为 \(l+r=L+R\)，那么移动步数为 \(|L+R-(l+r)|\)。那么每次扩展两个 \(1\)，就把它的权值加到树状数组里维护即可。复杂度 \(\mathcal{O}(N^2\log N)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 7505;
string s; int n, ans, g[N], cnt;
struct BIT{
#define lb ((i) & (-i))
int t[N<<1];
inline void add(int x, int val){
for(int i=x; i<=n*2; i+=lb) t[i] += val;
}
inline int qry(int x){
int ans = 0;
for(int i=x; i; i-=lb) ans += t[i];
return ans;
}
} t1, t2;
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>s; n = s.size();
for(int i=1; i<=n; ++i) if(s[i-1] == 'G') g[++cnt] = i;
g[cnt+1] = n+1;
for(int i=1, x=1, y=1; i<=cnt; ++i, x=i, y=i){
int sum = 0, nm = 0;
while(1 <= x && y <= cnt){
int tot = g[x] + g[y];
if(x != i) t1.add(tot, tot), t2.add(tot, 1), sum += tot, ++nm;
for(int l=g[x]; l>g[x-1]; --l) for(int r=g[y]; r<g[y+1]; ++r){
if((r - l) & 1){ --ans; continue; }
tot = l + r;
int val = t1.qry(tot-1), num = t2.qry(tot-1);
ans += llabs((tot >> 1) - g[i]);
ans += num * tot - val + sum - val - tot * (nm - num);
} --x, ++y;
}
memset(t1.t, 0, sizeof(int) * (2*n + 1));
memset(t2.t, 0, sizeof(int) * (2*n + 1));
}
for(int i=1, x=1, y=2; i<cnt; ++i, x=i, y=i+1){
int sum = 0, nm = 0;
while(1 <= x && y <= cnt){
int tot = g[x] + g[y];
t1.add(tot, tot), t2.add(tot, 1), sum += tot, ++nm;
for(int l=g[x]; l>g[x-1]; --l) for(int r=g[y]; r<g[y+1]; ++r){
tot = l + r;
int val = t1.qry(tot-1), num = t2.qry(tot-1);
ans += (num * tot - val) + sum - val - tot * (nm - num);
} --x; ++y;
}
memset(t1.t, 0, sizeof(int) * (2*n + 1));
memset(t2.t, 0, sizeof(int) * (2*n + 1));
} return cout<<ans, 0;
}
D [USACO23JAN] Tractor Paths P
神一样的倍增，屎一样的题面，对着题目瞪了有半个多小时……
不会倍增，看了题解，太™强拉！！！
首先，这些区间的左端点和右端点单调递增，所以如果想知道一个区间最远能到达哪里，就贪心地往最右边走就好了。所以可以使用倍增优化此过程。这是第一个答案求法。
对于第二问，维护特殊拖拉机的前缀和的倍增数组，沿着你倍增过来的路线加贡献即可。
#include<bits/stdc++.h>
using namespace std;
#define p pair<int, int>
constexpr int N = 2e5 + 5;
int n, m, L[N], R[N], lt[20][N], rt[20][N], sl[20][N], sr[20][N], sum[N];
string s1, s2;
inline int Dis(int u, int v){
if(u == v) return 0;
int dis = 0;
for(int i=__lg(n); i>=0; --i) if(lt[i][u] != -1 && lt[i][u] < v)
dis |= (1<<i), u = lt[i][u];
return dis + 1;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m>>s1>>s2;
for(int i=1, cnt=0, now=1; i<=n<<1; ++i){
if(s1[i-1] == 'L') ++cnt;
else R[now++] = cnt;
}
for(int i=n<<1, cnt=n+1, now=n; i>=1; --i){
if(s1[i-1] == 'R') --cnt;
else L[now--] = cnt;
}
for(int i=1; i<=n; ++i) sum[i] = sum[i-1] + s2[i-1] - '0';
memset(lt, 0xff, sizeof(lt)); memset(rt, 0xff, sizeof(rt));
for(int i=1; i<=n; ++i) lt[0][i] = R[i], sl[0][i] = sum[R[i]];
for(int i=1; i<=n; ++i) rt[0][i] = L[i], sr[0][i] = sum[L[i]-1];
for(int i=1; i<=__lg(n); ++i) for(int j=1; j<n; ++j) if(lt[i-1][j] > 0){
lt[i][j] = lt[i-1][lt[i-1][j]];
if(lt[i][j] > 0) sl[i][j] = sl[i-1][j] + sl[i-1][lt[i-1][j]];
}
for(int i=1; i<=__lg(n); ++i) for(int j=n; j>1; --j) if(rt[i-1][j] > 0){
rt[i][j] = rt[i-1][rt[i-1][j]];
if(rt[i][j] > 0) sr[i][j] = sr[i-1][j] + sr[i-1][rt[i-1][j]];
}
while(m--){
int u, v, dis; cin>>u>>v;
cout<<(dis = Dis(u, v))<<' '; --dis;
int ans = s2[u-1] - '0' + s2[v-1] - '0';
if(u == v){ cout<<ans; continue; }
for(int i=__lg(n); i>=0; --i) if(dis & (1<<i))
ans += sl[i][u], u = lt[i][u];
for(int i=__lg(n); i>=0; --i) if(dis & (1<<i))
ans -= sr[i][v], v = rt[i][v];
cout<<ans<<'\n';
} return 0;
}
E [USACO23JAN] Mana Collection P
很巧妙的一道题
首先可以发现，当走过的点集确定之后，答案的大小仅与每个节点最后走到的时间有关，即为（\(d_i\) 为最后遍历的时间）：
而贪心的说，对于每个节点的最后遍历时间越大，答案也就越大。一个节点的最短最后遍历时间即为 \(d_i=s-\sum_\limits{j=i}^{k-1}dis_{j,j+1}\)，其中 \(dis\) 为两点间最短路径。那么带入刚才的狮子可得：
右边那一坨拿状压爆搞即可。
维护凸包或者使用李超线段树即可。复杂度 \(\mathcal{O}(N^3+N^22^N+q\log n)\)。说句闲话：我想用离线查询 + 单队维护凸包搞，于是调了一个下午和晚上（还没调出来）。有李超这么nb玩意，凸包🐶都不用！！！
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 5e6 + 5, S = 1 << 18, Inf = 1e18;
int n, m, q, tot, val[20], dis[20][20], sum[S], f[19][S], cnt[19], rt[19];
inline void init(){
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j) if(i ^ j) dis[i][j] = Inf;
for(int j=0; j<tot; ++j) f[i][j] = Inf;
}
}
namespace LCST{
struct Seg{
int k, b;
int operator () (const int x) const{ return k * x + b; }
}s[N];
int cnt, tot, t[N], ls[N], rs[N];
inline void modify(int& id, int l, int r, int w){
if(!id) return void(t[id = ++cnt] = w);
if(l == r) return void(s[w](l) > s[t[id]](l) ? t[id] = w : 0);
int mid = (l + r) >> 1;
if(s[w](mid) > s[t[id]](mid)) swap(w, t[id]);
if(s[w](l) >= s[t[id]](l)) modify(ls[id], l, mid, w);
if(s[w](r) >= s[t[id]](r)) modify(rs[id], mid+1, r, w);
}
inline int query(int id, int l, int r, int x){
if(!id) return 0;
int ans = s[t[id]](x), mid = (l + r) >> 1;
if(x <= mid) ans = max(ans, query(ls[id], l, mid, x));
else ans = max(ans, query(rs[id], mid+1, r, x));
return ans;
}
inline void push_in(int &rt, int k, int b){
s[++tot] = Seg{k, b};
modify(rt, 1, 1e9, tot);
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m; tot = 1 << n; init();
for(int i=1; i<=n; ++i) cin>>val[i];
for(int i=1, u, v, w; i<=m; ++i)
cin>>u>>v>>w, dis[u][v] = w;
for(int k=1; k<=n; ++k) for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j)
if((k ^ i) && (k ^ j) && (i ^ j))
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
for(int s=1; s<tot; ++s){
for(int i=1; i<=n; ++i) if(s & (1<<(i-1))){
sum[s] += val[i];
int tmp = s ^ (1 << (i-1));
if(!tmp){ f[i][s] = 0; break; }
for(int k=1; k<=n; ++k) if(tmp & (1<<(k-1))){
if(dis[k][i] == Inf) continue;
f[i][s] = min(f[i][s], f[k][tmp] + sum[tmp] * dis[k][i]);
}
}
}
for(int i=1; i<=n; ++i){
for(int s=1; s<tot; ++s) if(s & (1<<(i-1))){
if(f[i][s] >= Inf) continue;
LCST::push_in(rt[i], sum[s], -f[i][s]);
}
} cin>>q; while(q--){
int s, e; cin>>s>>e;
cout<<LCST::query(rt[e], 1, 1e9, s)<<'\n';
} return 0;
}
F [USACO23JAN] Subtree Activation P
这道题很好手模，很好发现的是：如果你想完成 \(u\) 和 \(v\) 节点以及他们的公共祖先 \(w\)，那么存在最有策略是依次点亮 \(u\sim w\sim v\) 及其子树，然后依次灭掉 \(u\sim w\sim v\) 的子树，这样同时完成了 \(u,w,v\) 的要求，可以得到的是，这样的最优操作次数恰好为 \(2siz_w\)。
当我还在苦逼找规律的时候，大神已经开始设计 DP 了。令 \(f_{u,0}\) 表示覆盖 \(u\) 的子树的最小操作次数。\(f_{u,1}\) 表示有且仅有一条从 \(u\) 到 \(u\) 的子树内某节点 \(v\) 的链没有被点亮，而 \(u\) 子树其他节点都被覆盖的最小次数。这样设计有个显而易见的好处：合并链的代价变得可计算。
-
对于 \(f_{u,1}\)，可以看成在 \(u\) 的儿子节点里找一个儿子并把它的链向上延长到 \(u\)，相应地，其它儿子及其子树都应该被覆盖过了。于是有：
\[\begin{split} f_{u,1}&=\min_{v\in son_u}(f_{v,1}+\sum_{v'\in son_u,v'\not=v}f_{v',0}) \\ &=\sum_{v\in son_u}f_{v, 0}+\min_{v'\in son_u}(f_{v',1}-f_{v',0}) \end{split} \] -
对于 \(f_{u,0}\)，分为两种情况：
-
假设 \(u\) 的所有儿子及其子树都已经被覆盖过了，那么就找个儿子并把它的链延长至 \(u\) 并加上额外贡献。
\[f_{u,0}=\sum_{v\in son_u}f_{v,0}+2(siz_u-\max_{v\in son_u}(siz_v)) \] -
假设 \(u\) 还有两个儿子没被覆盖，那么将这两个儿子的链延长到 \(u\) 然后一并统计一下贡献：
\[\begin{split} f_{u,0}&=2siz_u+\min_{v_1\in son_u,v_2\in son_u,v1\not=v_2}(f_{v1,1}+f_{v2,1}+\sum_{v_3\in son_u,v_3\not=v_1,v_3\not=v_2}f_{v_3,0})\\ &=2siz_u+\sum_{v\in son_u}f_{v,0}+\min_{v_1\in son_u,v_2\in son_u,v1\not=v_2}(f_{v1,1}-f_{v1,0}+f_{v2,1}-f_{v2,0}) \end{split} \]
-
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 2e5 + 5, Inf = 1e18;
int n, f[2][N], siz[N];
vector<int> G[N];
inline void dfs(int u){
siz[u] = 1; if(!G[u].size()) return void(f[0][u] = 2);
int mn1 = Inf, mn2 = Inf, sum = 0, mx = 0;
for(int v : G[u]){
dfs(v); siz[u] += siz[v];
mx = max(mx, siz[v]);
sum += f[0][v];
int res = f[1][v] - f[0][v];
if(mn1 > res) mn2 = mn1, mn1 = res;
else if(mn2 > res) mn2 = res;
}
if(mn1 != Inf) f[1][u] = sum + mn1;
f[0][u] = sum + 2*(siz[u] - mx);
if(mn1 != Inf && mn2 != Inf)
f[0][u] = min(f[0][u], 2*siz[u] + sum + mn1 + mn2);
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n; for(int i=2, fa; i<=n; ++i)
cin>>fa, G[fa].push_back(i);
dfs(1); return cout<<f[0][1], 0;
}
性质分析、题目转换、构造 DP一条龙。
G [USACO23FEB] Hungry Cow P
一眼线段树分治，但不知道如何实现把大的数改小的操作。动态开点维护每个节点的有干草的节点数和贡献不用说了，还要维护从左边传进来的干草数，以及右儿子的贡献。
因为修改每一天的干草数可能增大可能减小，所以标记是不能永久打在节点上面的。这是最重要的一点。
感觉这种题就是逢山开路，遇水搭桥那种的。在写的过程中，需要什么就维护什么。
#include<bits/stdc++.h>
using namespace std;
#define it __int128
#define int long long
constexpr int N = 5e6 + 5, M = 1e9 + 7, Inv2 = 5e8 + 4;
int q, rt;
namespace ST{
int cnt;
struct node{ int ls, rs, sum, num, rgt, pas; }t[N];
inline int query(int id, int l, int r, int val){
if(!val) return t[id].sum;
if(l == r) return val ? l % M : t[id].sum;
int mid = (l + r) >> 1, ls = t[id].ls, rs = t[id].rs;
if(t[ls].num + val <= mid + 1 - l)
return (query(ls, l, mid, val) + t[id].rgt) % M;
int ans = (it)(l + mid) * (mid - l + 1) % M * Inv2 % M;
ans = (ans + query(rs, mid+1, r, t[ls].num + val - (mid - l + 1) + t[ls].pas)) % M;
return ans;
}
inline void pushup(int id, int l, int r){
int ls = t[id].ls, rs = t[id].rs, mid = (l + r) >> 1;
t[id].num = t[ls].num + min(t[rs].num + t[ls].pas, r - mid);
t[id].pas = t[rs].pas + max(t[ls].pas + t[rs].num - (r - mid), 0ll);
t[id].rgt = query(rs, mid+1, r, t[ls].pas);
t[id].sum = (t[ls].sum + t[id].rgt) % M;
}
inline void modify(int &id, int l, int r, int pos, int val){
if(!id) id = ++cnt;
if(l == r){
if(val) t[id].sum = l % M, t[id].num = 1, t[id].pas = val - 1;
else t[id].sum = t[id].num = t[id].pas = 0;
return;
} int mid = (l + r) >> 1;
if(pos <= mid) modify(t[id].ls, l, mid, pos, val);
else modify(t[id].rs, mid+1, r, pos, val);
pushup(id, l, r);
}
} using namespace ST;
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>q; while(q--){
int x, y; cin>>x>>y;
modify(rt, 1, 2e14, x, y);
cout<<t[rt].sum<<'\n';
} return 0;
}
双倍经验 楼房重建
H [USACO23FEB] Problem Setting
感觉题意很好转化，就是先放一大堆 E 再放一大堆 H，当然，每一道题对于每一个验题人的难度不一定都相同。当放置一道题 \(i\) 的时候，第 \(i+1\) 道题必须是认为 \(i\) 题难的所有人都认为难的题。再联系到 \(m\le 20\)，我们可以找到一个点集 \(s\) 表示所有状态为 \(1\) 的验题人都觉得这道题难，那么 \(s\) 的上一个集合一定是 \(s\) 的一个子集。考虑维护出所有的点集 \(s\) 以及其对应的所有题目，然后状压 DP 转移，所有状态的方案数之和即为答案。拼尽全力也只能想到枚举子集的暴力 DP……
Warning：枚举子集一定要等枚举到 \(0\) 之后再 break 掉！！！
暴力 \(\mathcal{O}(3^m)\) 60pts
#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N = 1e5 + 5, S = 1 << 20, M = 1e9 + 7;
int n, m, num[S], tot, sum[N], ans, f[S];
string str[21];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m; tot = 1 << m; sum[1] = 1;
for(int i=2; i<=n; ++i) sum[i] = ((ll)i + (ll)sum[i-1] * i % M) % M;
for(int i=1; i<=m; ++i) cin>>str[i];
for(int i=1; i<=n; ++i){
int tmp = 0;
for(int j=1; j<=m; ++j) if(str[j][i-1] == 'H')
tmp |= 1 << (j-1);
++num[tmp];
}
for(int s=0; s<tot; ++s) num[s] = sum[num[s]];
ans = f[0] = num[0];
for(int s=1; s<tot; ++s){
f[s] = 1;
for(int tmp=(s-1) & s; tmp>=0; tmp = (tmp-1) & s){
f[s] = ((ll)f[s] + (ll)f[tmp]) % M;
if(!tmp) break;
}
f[s] = (ll)f[s] * num[s] % M;
ans = ((ll)ans + (ll)f[s]) % M;
} return cout<<ans, 0;
}
官方正解 FMT，于是我就去学了一下。好的，这篇博客正式变成 FMT 学习笔记！
FMT 快速莫比乌斯变换（Fast Möbius Transform）
要求：
不知道咋读）定义：
于是有 \(\hat{f}(S,0)=f(s)\) 、\(\hat{f}(S,|S|)=f(\varnothing)\)
设 \(S \cap \{i\}=\varnothing\)，所以 \(\hat{f}(S,i)=\hat{f}(S,i-1)\)。因为 \(\hat{f}(S,i)\) 表示 \(\{i+1,i+2,\dots,n\}\) 一定包含于 \(T\)，并且一定没有选 \(i\)，\(\hat{f}(S\cup \{i\},i-1)\) 表示 \(\{i+1,i+2,\dots,n\}\) 一定包含于 \(T\)，并且一定选择了 \(i\)。依据加法原理，那么有：
可以用 \(\mathcal{O}(n2^n)\) 的复杂度递推求解子集和。当然也可以求解单个 \(f(S)\)：
WC，刚看一篇博客说它可以理解为高维前缀和状物，一下子变得清晰了。我上面写的是 屎 (偏数学一点)。
对于求解一维前缀和，我们有：
for(int i=1; i<=n; ++i) s[i] += s[i-1];
对于二维，一般来说用的最多的是容斥，不过仍然可以一维一维地处理：
for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) s[i][j] += s[i-1][j];
for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) s[i][j] += s[i][j-1];
对于更高的维度也是如此。对于每一维都为 \(0,1\) 的维度，有：
for(int i=1; i<2; ++i) for(int j=1; j<2; ++j) ... s[i][j]... += s[i^1][j]...
...
不妨使用状压完成此过程，就有：
for(int i=0; i<(1<<n); ++i) for(int j=0; j<n; ++j)
if(i & (1<<j)) s[i] += s[i^(1<<j)];
这不就是求子集和吗？FMT 正是利用此性质将复杂度大大的优化。
回到此题，那我们就可以在递推 \(\hat{f}\) 的同时处理出 \(f\) 数组，大大降低了枚举子集的复杂度。总复杂度 \(\mathcal{O}(m2^m)\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N = 1e5 + 5, S = 1 << 20, M = 1e9 + 7;
int n, m, num[S], tot, sum[N], ans, f[S], sf[21][S];
string str[21];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m; tot = 1 << m; sum[1] = 1;
for(int i=2; i<=n; ++i) sum[i] = ((ll)i + (ll)sum[i-1] * i % M) % M;
for(int i=1; i<=m; ++i) cin>>str[i];
for(int i=1; i<=n; ++i){
int tmp = 0;
for(int j=1; j<=m; ++j) if(str[j][i-1] == 'H')
tmp |= 1 << (j-1);
++num[tmp];
}
for(int s=0; s<tot; ++s) num[s] = sum[num[s]];
for(int s=0; s<tot; ++s){
f[s] = 1;
for(int i=0; i<m; ++i) if(s & (1<<i))
f[s] = ((ll)f[s] + (ll)sf[i][s^(1<<i)]) % M;
f[s] = (ll)f[s] * num[s] % M;
ans = ((ll)ans + (ll)f[s]) % M; sf[0][s] = f[s];
for(int i=1; i<m; ++i){
sf[i][s] = sf[i-1][s];
if(s & (1<<(i-1))) sf[i][s] = ((ll)sf[i][s] + (ll)sf[i-1][s^(1<<(i-1))]) % M;
}
} return cout<<ans, 0;
}
I [USACO23FEB] Watching Cowflix P
一眼虚树好吧，然后不会。看了题解的虚树做法，对于我这种菜鸡不可做，考虑根号分治。
首先有树形 DP。令 \(f_{1/0,i}\) 表示 \(i\) 在或不在联通块内。那么有：
DP需要使用 DFS序优化。暴力巨好打。然后打表可知，答案是单调不降的，并且相邻两个答案之间的差值也是单调不降的。观察到对于 \(\sqrt n\) 以内的答案差值变化较大，直接暴力处理。当 \(k>\sqrt n\) 之后答案差值变化较小且连续，直接二分找到每一个差值相等的区间求解即可。码好打。这题还能这么做！！！
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 5, Inf = 1e9;
int n, f[2][N], rnk[N], tot, fa[N];
string str; vector<int> G[N];
inline void dfs(int u, int f){
rnk[++tot] = u;
for(int v : G[u]){
if(v == f) continue;
fa[v] = u; dfs(v, u);
}
}
inline int solve(int k){
for(int i=1; i<=n; ++i)
f[1][i] = 1, f[0][i] = str[i-1] == '0' ? 0 : Inf;
for(int i=n; i>1; --i){
int v = rnk[i], u = fa[v];
f[0][u] += min(f[0][v], f[1][v] + k);
f[1][u] += min(f[1][v], f[0][v]);
} return min(f[0][1], f[1][1] + k);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>str; int len = sqrt(n);
for(int i=1, u, v; i<n; ++i){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
} dfs(1, 0);
for(int i=1; i<=len; ++i) cout<<solve(i)<<'\n';
int l = len + 1, r = n, ans = solve(len + 1), bg, del = ans - solve(len);
do{
bg = l;
while(l < r){
int mid = (l + r + 1) >> 1;
if(solve(mid) - solve(mid - 1) < del) r = mid - 1;
else l = mid;
}
bg = l - bg + 1;
do{
cout<<ans<<'\n';
--bg; ans += del;
} while(bg);
l = l + 1, r = n, ans = solve(l), del = ans - solve(l - 1);
} while(l <= n);
return 0;
}
以后这种题暴力打完先找找规律再去想正解。
J [USACO23OPEN] Pareidolia P
8 pts 的 \(\mathcal{O}(N^3)\) 暴力还是很好打的。若想优化到 \(\mathcal{O}(N^2)\) 查询 \(\mathcal{O}(N)\) 需要用到 DP。令 \(f_{i,0\sim5}\) 表示所有以第 \(i\) 个字符为末尾的字符串中匹配到了 bessie 第 \(0\sim5\) 的位置的数量，类似于一个桶，很好写出 20 pts暴力。
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 2e5 + 5;
string str;
int n, q, f[N][6];
inline int solve(){
for(int i=1; i<=n; ++i) for(int j=0; j<6; ++j) f[i][j] = 0;
int ans = 0, res = 0;
for(int i=1; i<=n; ++i){
for(int j=0; j<6; ++j) f[i][j] = f[i-1][j];
switch(str[i]){
case 'b': f[i][1] += f[i][0], f[i][0] = 0; break;
case 'e': f[i][2] += f[i][1], f[i][1] = 0;
res += f[i][5], f[i][0] += f[i][5], f[i][5] = 0; break;
case 's': f[i][4] += f[i][3], f[i][3] = 0;
f[i][3] += f[i][2], f[i][2] = 0; break;
case 'i': f[i][5] += f[i][4], f[i][4] = 0; break;
}
++f[i][str[i] == 'b' ? 1 : 0];
ans += res;
} return ans;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>str>>q; n = str.size(); str = ' ' + str;
cout<<solve()<<'\n';
while(q--){
int x; char ch;
cin>>x>>ch; str[x] = ch;
cout<<solve()<<'\n';
}
}
正解动态 DP。黑科技。就是线段树 + 矩阵乘法。把 DP 的递推过程转化为矩阵乘法，线段树每一个节点都是一个矩阵。唯一难点在于转移矩阵的设计。剩下的就是个绿。注意卡空卡时。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i) for(int i=0; i<9; ++i)
constexpr int N = 2e5 + 5;
string str; int n, q;
struct Matrix{ int m[9][9]; } bas;
Matrix operator * (const Matrix &a, const Matrix &b){
Matrix c; memset(c.m, 0, sizeof(c.m));
f(i) f(j) f(k) c.m[i][j] += a.m[i][k] * b.m[k][j];
return c;
}
inline Matrix get(char ch){
Matrix a; memset(a.m, 0, sizeof(a.m));
f(i) a.m[i][i] = 1; a.m[1][0] = 1;
switch(ch){
case 'i': a.m[6][6] = 0, a.m[6][7] = 1; break;
case 's': a.m[4][4] = a.m[5][5] = 0, a.m[4][5] = a.m[5][6] = 1; break;
case 'b': a.m[2][2] = 0, a.m[2][3] = 1; break;
case 'e': a.m[3][3] = a.m[7][7] = 0; a.m[7][0] = a.m[7][1] = a.m[7][2] = a.m[3][4] = 1; break;
} a.m[8][ch == 'b' ? 3 : 2] = 1;
return a;
}
namespace ST{
#define ls (id << 1)
#define rs (id << 1 | 1)
Matrix t[N<<2];
inline void pushup(int id){
t[id] = t[ls] * t[rs];
}
inline void build(int id, int l, int r){
if(l == r) return void(t[id] = get(str[l]));
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid+1, r);
pushup(id);
}
inline void modify(int id, int l, int r, int pos){
if(l == r) return void(t[id] = get(str[l]));
int mid = (l + r) >> 1;
if(pos <= mid) modify(ls, l, mid, pos);
else modify(rs, mid+1, r, pos);
pushup(id);
}
}
inline int getans(){
Matrix ans = bas * ST::t[1];
return ans.m[0][0];
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>str>>q; n = str.size(); str = ' ' + str;
bas.m[0][8] = 1;
ST::build(1, 1, n); cout<<getans()<<'\n';
while(q--){
int x; char ch; cin>>x>>ch;
str[x] = ch; ST::modify(1, 1, n, x);
cout<<getans()<<'\n';
} return 0;
}
K [USACO23OPEN] Good Bitstrings P
观察了一会儿性质，发现 \(S\) 每 \((a+b)/\gcd(a,b)\) 一个循环，感觉和 \(\gcd\) 有关，找了半天规律也没找出个啥。学习一下题解。
考虑将所有时刻的 \(ia,ib\) 作为坐标画到平面直角坐标系上，然后分析性质。
-
那么有射线 \((a,b)\)，如果某一点在 \((a,b)\) 下方，那么下一步一定是往上走的，如果在上方，那么下一步一定是往右走的。
可以对题目代码的判断式进行移项：\(\frac{ia}{ib}\le\frac{a}{b}\) 往右走，反之往左走。
-
点 \((x,y)\) 合法当且仅当所有 \(0\le x'<x，0\le y' < y\) 的点都在射线 \((a,b)\) 和 \((x,y)\) 同侧。
反证法证明：假设 \((a,b)\times (x,y)>0，k_{a,b}>k_{x,y}\)，点 \((x',y')\) 在异侧，那么对于射线 \((a,b)\)，这个点要往上走，而对于射线 \((x,y)\)，这个点要往右走，矛盾。
-
对于满足 \(f_1\times f_2=1\) 的整点 \(f_1,f_2\)，任意满足 \(f_1\times f > 0\) 并且 \(f\times f_2>0\) 的整点 \(f\) 都有 \(f=k_1f_1+k_2f_2\)。\(k_1,k_2\) 皆为正整数。
怎么理解呢？就是任意整点（向量） \(f\) 都可以被分解为两个满足叉乘为 \(1\) 的整点（向量）之和。
必要性证明：构造 \(k_2=f_1\times f, k_1=f\times f_2\)，于是有 \(f_1\times f=f_1 \times (k_1f_1+k_2f_2),f\times f_2=(k_1f_1+k_2f_2)\times f_2\)，从而 \(f=(f\times f_2)f_1+(f_1\times f)f_2\)。由于 \(f_1,f_2,f\) 均为整点，所以 \(k_1,k_2\) 均为正整数。又因为向量分解为两个非平行向量的分解方式唯一，所以必要性得证。
有了这一条性质，就可以考虑递推求所有合法点：
- 初始令 \(f_1=(0,1),f_2=(1,0)\)，满足 \(f_1\times f_2=1\)，过程保证射线 \(f_1,f_2\) 之间的点都被统计过，并且 \(f_1,f_2\) 均为合法点。
- 记 \(f=f_1+f_2\)，则 \(f\) 为合法点。接下来按照 \(f\) 对于 \((a,b)\) 的位置决定令 \(f_1=f\) 或 \(f_2=f\) 继续向下递归。
- 若 \(f_2\times f=0\)，结束算法。
但是这个算法漏统计了若干个形如 \(kf_2\) 的点，考虑完善一下。
-
若当前的 \(f\) 满足 \(f\times (a,b)>0\)，记在此之前 \(f_1\) 已经连续变化了 \(k\) 次，则 \((k+2)f_2\) 合法。
到这里已经看不懂了……😵
-
算法结束时一定有 \(f_2=(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)})\)，且 \(f_1\times (a,b)=\gcd(a,b)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int T, a, b;
inline int solve(int a, int b){
int f1 = b, f2 = a, ans = 0, co = 1;
while(f2){
if(f1 > f2) ans += co * ((f1 - 1) / f2), f1 = (f1 - 1) % f2 + 1;
else ans += f2 / f1, f2 %= f1, co = 2;
} return ans + 2 * (f1 - 1);
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>T; while(T--)
cin>>a>>b, cout<<solve(a, b)<<'\n';
return 0;
}
大坑待补。
L [USACO23OPEN] Triples of Cows P
黑的。