The 2021 ICPC Asia Shenyang Regional Contest（EFBJHLI）
2025.8.24
单挑，5题，Cu
E. Edward Gaming, the Champion
签到。
F. Encoded Strings I
签到，模拟。
但是我糖丸了，做了很久，还wa了一发。
B. Bitwise Exclusive-OR Sequence
根据样例2，发现只有01会很好找到无解的情况，而注意到每位是独立的，于是考虑按位做。
#include <bits/stdc++.h>
using namespace std;
// #define int long long
using i64 = long long;
using i128 = __int128;
using u64 = unsigned long long;
const int mod = 998244353;
const int N = 1e5 + 9;
const int iinf = 1e9;
const i64 linf = 1e18;int fa[N];
int find(int x) {if (x==fa[x]) return x;return fa[x]=find(fa[x]);
}
void merge(int x,int y) {int fx=find(x),fy=find(y);if (fx==fy) return ;fa[fx]=fy;
}void solve() {int n,m;cin>>n>>m;vector<vector<array<int,2>>> G(n+1);for (int i=1;i<=n;++i) fa[i]=i;for (int i=1;i<=m;++i) {int u,v,w;cin>>u>>v>>w;G[u].push_back({v,w});G[v].push_back({u,w});merge(u,v);}bool ok=true;vector<bool> vis(n+1),a(n+1);int cnt1=0,cnt0=0,w;function<void(int,int)> dfs=[&](int x,int val) {if (!ok) return ;a[x]=val;vis[x]=1;if (val==0) cnt0++;else cnt1++;for (auto [y,z]:G[x]) {int nv=(z>>w)&1;if (vis[y]) {if ((val^nv)!=a[y]) ok=false;}else {dfs(y,val^nv);}}};i64 ans=0;for (w=0;w<30;++w) {for (int i=1;i<=n;++i) vis[i]=false;for (int i=1;i<=n;++i) {if (i!=find(i)) continue;cnt1=0,cnt0=0;dfs(i,0);if (ok==false) {cout<<"-1\n";return ;}else {ans+=(1ll<<w)*min<i64>(cnt1,cnt0);}}}cout<<ans<<"\n";
}signed main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGEfreopen("C:\\ACM\\code\\test.in", "r", stdin);// freopen("C:\\ACM\\code\\test2.in", "r", stdin);
#endifint Case = 1;// cin >> Case;while (Case--) solve();return 0;
}J. Luggage Lock
~铜牌题
容易想到根据差值处理，发现状态只有\(10000\)，直接暴力预处理即可。
又糖了，导致后面没时间写L了。
#include <bits/stdc++.h>
using namespace std;
// #define int long long
using i64 = long long;
using i128 = __int128;
using u64 = unsigned long long;
const int mod = 998244353;
const int N = 1e6 + 9;
const int iinf = 1e9;
const i64 linf = 1e18;map<array<int,4>,int> f;void init() {array<int,4> now={0,0,0,0};f[now]=0;queue<array<int,4>> q;q.push((now));while (q.size()) {auto ar=q.front();q.pop();for (int l=0;l<4;++l) for (int r=l;r<4;++r) {auto ar0=ar,ar1=ar;for (int i=l;i<=r;++i) ar0[i]=(ar0[i]+1)%10;for (int i=l;i<=r;++i) ar1[i]=(ar1[i]+9)%10;if (!f.count(ar0)) q.push(ar0),f[ar0]=f[ar]+1;if (!f.count(ar1)) q.push(ar1),f[ar1]=f[ar]+1;}}
}void solve() {string a,b;cin>>a>>b;array<int,4> ar;for (int i=0;i<4;++i) {int x=b[i]-a[i];if (x<0) x+=10;ar[i]=x;}cout<<f[ar]<<"\n";
}signed main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGEfreopen("C:\\ACM\\code\\test.in", "r", stdin);// freopen("C:\\ACM\\code\\test2.in", "r", stdin);
#endifint Case = 1;init();cin >> Case;while (Case--) solve();return 0;
}H. Line Graph Matching
铜~银牌题，图论。
容易发现就是每次可以获得同一个点的两条边的权值和，然后去掉，问最大权值和。
一开始以为贪心，写出来发现有问题，然后看了看样例，猜到一个结论就是一个联通块的边数是偶数的话，一定可以获得全部边。奇数就要去掉一些边（假设一定是去掉一条边），正着不好做。我们考虑按照边权递减的顺序连边。记录每个连通块边数，和去掉了的权值，用并查集维护。有以下情况。
- 联通块内部加边，如果原来是奇数，那么加上后，去掉的权值为0，否则为这条边的权值。
- 联通两个不同奇偶性的块，这个时候合并后为偶数，为0。
- 偶数和偶数，为这条边的权值。
- 奇数和奇数，首先若原来的奇数块去掉边没有分开，那么权值就为原来的值，若分成了两个块，根据归纳假设，由于只去掉一条边，那么两个块一定为偶数，因此还是可以删除这一条边。
这里补充上面那个性质的证明，即无向联通图，相邻边两两匹配，若边为偶数，则一定有完美匹配。
找出所有的奇度数点，连向一个新的节点，根据握手引理，点数量为偶数，此时新图所有点度数为偶数，那么存在一条欧拉回路，对于这条路径，将进入某个点和离开某个点的边配对即可。
#include <bits/stdc++.h>
using namespace std;
// #define int long long
using i64 = long long;
using i128 = __int128;
using u64 = unsigned long long;
const int mod = 998244353;
const int N = 1e5 + 9;
const int iinf = 1e9;
const i64 linf = 1e15;int fa[N],e[N],los[N];
int find(int x) {if (x==fa[x]) return x;return fa[x]=find(fa[x]);
}void solve() {int n,m;cin>>n>>m;vector<array<int,3>> E;i64 ans=0;for (int i=1;i<=m;++i) {int u,v,w;cin>>u>>v>>w;ans+=w;E.push_back({w,u,v});}sort(E.begin(),E.end(),greater<array<int,3>>());for (int i=1;i<=n;++i) fa[i]=i,e[i]=0,los[i]=0;for (auto [w,x,y]:E) {int fx=find(x),fy=find(y);if (fx==fy) {if (e[fx]&1) {los[fx]=0;}else {los[fx]=w;}e[fx]++;}else {if ((e[fx]&1)^(e[fy]&1)) {los[fy]=0;}else {if (e[fx]&1) {los[fy]=min(los[fx],los[fy]);}else {los[fy]=w;}}fa[fx]=fy;e[fy]+=1+e[fx];}}for (int i=1;i<=n;++i) {if (i==find(i))ans-=los[i];}cout<<ans<<"\n";
}signed main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGEfreopen("C:\\ACM\\code\\test.in", "r", stdin);// freopen("C:\\ACM\\code\\test2.in", "r", stdin);
#endifint Case = 1;// cin >> Case;while (Case--) solve();return 0;
}
比赛结束后发现，图是联通的，那就只需要找到奇数边时删哪条边即可。显然可以枚举边，如果该边是割边，就要判断两边联通块边数：若不是偶数，就跳过，否则继续判断。可以用tarjan找桥，边数可根据dfs处理出度数和计算。
#include <bits/stdc++.h>
using namespace std;
// #define int long long
using i64 = long long;
using i128 = __int128;
using u64 = unsigned long long;
const int mod = 998244353;
const int N = 1e5 + 9;
const int iinf = 1e9;
const i64 linf = 1e15;struct Q {int v, w,in;
};
multiset<int> st;
vector<vector<int>> ans;
vector<int> cur;
vector<Q> e[N];
int dfn[N], low[N], ed[N],sz[N];
int id;
void tarjan(int u, int fin) {dfn[u]=low[u]=++id;for (auto [v,w,in]:e[u]) {if (in!=fin) {if (!dfn[v]) {tarjan(v,in);sz[u]+=sz[v];low[u]=min(low[u],low[v]);if (low[v]>dfn[u] and ((sz[v]-1)/2)&1) st.erase(w);}else{low[u]=min(low[u],dfn[v]);}}}
}void solve() {int n, m;cin >> n >> m;i64 ans = 0;id=0;for (int i = 1; i <= m; ++i) {int u, v, w;cin >> u >> v >> w;e[u].push_back({v,w,i});e[v].push_back({u,w,i});sz[u]++,sz[v]++;st.insert(w);ans+=w;}if (m&1) tarjan(1,0),ans-=*st.begin();cout<<ans<<"\n";
}signed main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGEfreopen("C:\\ACM\\code\\test.in", "r", stdin);// freopen("C:\\ACM\\code\\test2.in", "r", stdin);
#endifint Case = 1;// cin >> Case;while (Case--) solve();return 0;
}L. Perfect Matchings
银牌题。dp
赛时没看到会形成一颗树。最眼瞎的一集
用集合去容斥时间复杂度过高，但发现只用考虑两类边，因此只用考虑树上使用边（点）的数量。
一个显然的思路是维护边不含交点，对禁止的边进行容斥，因为边全在一颗树上，那么我们就很方便进行dp。
而去掉选定的点后，还是是一个完全图，\(2n\)个点完全图的完美匹配数是
\[\frac{\binom{2n}{n} n!}{2^n}=\prod_{i=1}^{n} 2i-1
\]
然后就是计算一颗树上，选出k条边的方案数。
\(f_{i,j,0/1}\) 表示以\(i\)为根，选出来\(j\)条边，根节点是否被选的方案数量，然后就是树上背包问题。
void dfs(int x,int pre) {siz[x]=1;for (auto y:ver[x]) {if (y==pre) continue;dfs(y,x);for (int i=siz[x]/2;i>=0;--i) for (int j=siz[y]/2;j>=0;--j) {if (j) {f[x][i+j][0]=(1ll*f[x][i+j][0]+1ll*f[x][i][0]*(1ll*f[y][j][0]+f[y][j][1])%mod)%mod;f[x][i+j][1]=(1ll*f[x][i+j][1]+1ll*f[x][i][1]*(1ll*f[y][j][0]+f[y][j][1])%mod)%mod;}f[x][i+j+1][1]=(1ll*f[x][i+j+1][1]+1ll*f[x][i][0]*f[y][j][0]%mod)%mod;}siz[x]+=siz[y];}
}
实际上这是\(O(n^2)\)的，不太会算树上背包的复杂度，感觉做树上背包问题多注意调整一下边界，大胆写就行了。
I. Linear Fractional Transformation
金牌题。数学
3个方程，4个未知数，并且是齐次的，因此我们考虑先定一个数。
如果\(c=0\)，那么\(f(z)=\frac{a}{d} z+\frac{c}{d}\)，再设\(d=1\)，然后解出\(a,c\)，再验证第3个，若满足，就可以直接带入计算即可。
不满足就设\(c=1\)，解出\(a,b,d\)即可。
#include <bits/stdc++.h>
using namespace std;
// #define int long long
using i64 = long long;
using i128 = __int128;
using u64 = unsigned long long;
const int mod = 998244353;
const int N = 1e6 + 9;
const int iinf = 1e9;
const i64 linf = 1e18;using cd=complex<long double>;
cd ar[10][10];
const double eps = 1e-8;int gauss(int n) {int c, r;for (c = 0, r = 0; c < n; ++c) {int t = r;for (int i = r; i < n; ++i) {if (std::abs(ar[i][c]) > std::abs(ar[t][c])) t = i;}if (std::abs(ar[t][c]) < eps) continue;for (int j = c; j < n + 1; ++j) std::swap(ar[t][j], ar[r][j]);for (int j = n; j >= c; --j) ar[r][j] /= ar[r][c];for (int i = r + 1; i < n; ++i) {if (std::abs(ar[i][c]) > eps) {for (int j = n; j >= c; --j) {ar[i][j] -= ar[r][j] * ar[i][c];}}}r++;}if (r < n) {for (int i = r; i < n; ++i) {if (std::abs(ar[i][n])>eps) return 2;}return 1;}for (int i = n - 1; i >= 0; --i) {for (int j = i + 1; j < n; ++j) {ar[i][n] -= ar[i][j] * ar[j][n];}}return 0;
}bool myequal(cd z1,cd z2) {return std::abs(z1-z2)<eps;
}void solve() {cd z0,a,b,d;array<cd,3> z,w;for (int i=0;i<3;++i) {int x,y;cin>>x>>y;z[i]=cd(x,y);cin>>x>>y;w[i]=cd(x,y);}int x,y;cin>>x>>y;z0=cd(x,y);for (int i=0;i<2;++i) ar[i][0]=z[i],ar[i][0]=z[i],ar[i][1]=1,ar[i][2]=w[i];gauss(2);a=ar[0][2],b=ar[1][2];if (myequal(a*z[2]+b,w[2])) {cd ans=a*z0+b;cout<<fixed<<setprecision(12)<<ans.real()<<" "<<ans.imag()<<"\n";return ;}for (int i=0;i<3;++i) ar[i][0]=z[i],ar[i][0]=z[i],ar[i][1]=1,ar[i][2]=-w[i],ar[i][3]=w[i]*z[i];gauss(3);a=ar[0][3],b=ar[1][3],d=ar[2][3];cd ans=(a*z0+b)/(z0+d);cout<<fixed<<setprecision(12)<<ans.real()<<" "<<ans.imag()<<"\n";
}signed main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGEfreopen("C:\\ACM\\code\\test.in", "r", stdin);// freopen("C:\\ACM\\code\\test2.in", "r", stdin);
#endifint Case = 1;cin >> Case;while (Case--) solve();return 0;
}
或者利用线性分式变换的保交比性
分式线性变换
\[f(z)=\frac{az+b}{cz+d} (ad-bc \neq 0)
\]
交比是四个复数 z, z1, z2, z3 的一种组合，定义为：
\[(z,z_1,z_2,z_3)=\frac{(z-z_1)(z_2-z_3)}{(z-z_3)(z_2-z_1)}
\]
而
\[(z,z_1,z_2,z_3)=(f(z),f(z_1),f(z_2),f(z_3))
\]
从而
\[w_0=\frac{\omega_3(z_0-z_1)(z_2-z_3)(\omega_2-\omega_1)-\omega_1(z_0-z_3)(z_2-z_1)(\omega_2-\omega_3)}{(z_0-z_1)(z_2-z_3)(\omega_2-\omega_1)-(z_0-z_3)(z_2-z_1)(\omega_2-\omega_3)}
\]
void solve() {cd z0,a,b,d;array<cd,4> z,w;for (int i=1;i<=3;++i) {int x,y;cin>>x>>y;z[i]=cd(x,y);cin>>x>>y;w[i]=cd(x,y);}int x,y;cin>>x>>y;z[0]=cd(x,y);cd A=(z[0]-z[1])*(z[2]-z[3])*(w[2]-w[1]),B=(z[0]-z[3])*(z[2]-z[1])*(w[2]-w[3]);cd ans=(w[3]*A-w[1]*B)/(A-B);cout<<fixed<<setprecision(12)<<ans.real()<<" "<<ans.imag()<<"\n";
}