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\) 为最后遍历的时间）：
\[ans=\sum_{i=1}^{k}val_i*d_i \]而贪心的说，对于每个节点的最后遍历时间越大，答案也就越大。一个节点的最短最后遍历时间即为 \(d_i=s-\sum_\limits{j=i}^{k-1}dis_{j,j+1}\)，其中 \(dis\) 为两点间最短路径。那么带入刚才的狮子可得：
\[ans = s{\large \sum_{i = 1}^{k}} val[i]-{\large \sum_{i = 1}^{k-1}}dis(c_i, c_{i+1})\sum_{j = 1}^{i}val[j] \]右边那一坨拿状压爆搞即可。
维护凸包或者使用李超线段树即可。复杂度 \(\mathcal{O}(N^3+N^22^N+q\log n)\)。说句闲话：我想用离线查询 + 单队维护凸包搞，于是调了一个下午和晚上（还没调出来）。有李超这么nb玩意，凸包
标签：训练,int,提高,ans,mid,long,组杂题,sum,id From： https://www.cnblogs.com/xiaolemc/p/18461142