当前位置: 首页 > news >正文

2021 ICPC 沈阳 BEFHJLM(待补

B - Bitwise Exclusive-OR Sequence

种类并查集。

根据每一对的异或关系,可以得到二进制中每一位是否互斥关系,涉及到两种关系的处理用种类并查集更好维护;另外再维护两个点之间是否有关系,之后可能形成多个关系的集合,每个集合又分成了互斥的两个部分,对少的那一堆赋值为 \(1\) 即可。

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;struct DSU {std::vector<int> f, siz;DSU() {}DSU(int n) {init(n);}void init(int n) {f.resize(n);std::iota(f.begin(), f.end(), 0);siz.assign(n, 1);for (int i = n / 2 + 1; i < n; i += 1) {siz[i] = 0;}}int find(int x) {while (x != f[x]) {x = f[x] = f[f[x]];}return x;}bool same(int x, int y) {return find(x) == find(y);}bool merge(int x, int y) {x = find(x);y = find(y);if (x == y) {return false;}siz[x] += siz[y];f[y] = x;return true;}int size(int x) {return siz[find(x)];}
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<DSU> dsu(30, DSU(2 * n + 1));vector<array<int,3>> e(m);vector g(n + 1, vector<int>());for (auto &[u, v, w] : e) {cin >> u >> v >> w;for (int i = 29; i >= 0; i -= 1) {if (w >> i & 1) {if (dsu[i].same(u, v) || dsu[i].same(u + n, v + n)) {cout << "-1\n";return 0;}dsu[i].merge(u + n, v);dsu[i].merge(u, v + n);}else {if (dsu[i].same(u, v + n) || dsu[i].same(u + n, v)) {cout << "-1\n";return 0;}dsu[i].merge(u, v);dsu[i].merge(u + n, v + n);}}g[u].push_back(v);g[v].push_back(u);}i64 ans = 0;for (int i = 29; i >= 0; i -= 1) {i64 k = 0;vector<int> vis(2 * n + 1), has(2 * n + 1);auto bfs = [&](int x)->int{queue<int> Q;Q.push(x);int res = n, cnt = 0;while (Q.size()) {auto u = Q.front();Q.pop();if (vis[u]) {continue;}vis[u] = 1;if (!has[dsu[i].find(u)]) {cnt += 1;has[dsu[i].find(u)] = 1;res = min(res, dsu[i].size(u));}for (auto &v : g[u]) {if (!vis[v]) {Q.push(v);}}}return (cnt > 1 ? res : 0);};for (int j = 1; j <= n; j += 1) {if (vis[j]) {continue;}k += bfs(j);}ans += (1LL << i) * k;}cout << ans << "\n";return 0;
}

E - Edward Gaming, the Champion

模拟。

签到题,一个典型的错法是:

string s; cin >> s;
for (int i = 0; i < s.size() - 4; i++) { ... }

\(\text{str.size()\ <\ 4}\) 会导致 \(\text{size\_t}\) 类型的下溢出,并且在 \(\text{for}\) 循环判断退出条件时 \(\text{int}\) 会被 \(\text{static\_cast}\)\(\text{size\_t}\) 类型进行比较从而导致访问越界。

点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long longvoid solve() {string s;cin>>s;int ans=0;for (int i = 0; i <s.size() ; ++i) {string g=s.substr(i,5);if(g=="edgnb")ans++;}cout<<ans<<endl;}signed main() {ios::sync_with_stdio(0);cin.tie(0);int t=1;
//    cin >> t;while (t--) {solve();}
}

F - Encoded Strings I

模拟。

没读,队友写的,看起来直接模拟就行。

点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int mod = 998244353;
#define endl '\n'void solve() {int n;cin >> n;string g;cin >> g;string s;string res = "";s = "";for (int i = 0; i < g.size(); ++i) {
//        s += g[i];string s=g.substr(0,i+1);vector<int>vis(26,-1);int dq=-1;std::reverse(s.begin(), s.end());for(auto &x:s) {if (vis[x - 'a'] == -1) {vis[x - 'a'] = ++dq;
//                dq++;x = 'a' + dq;} else {x = 'a' + vis[x-'a'];}}std::reverse(s.begin(), s.end());res= max(res,s);}cout << res << endl;
}signed main() {ios::sync_with_stdio(0);cin.tie(0);int t=1;
//    cin >> t;while (t--) {solve();}}

H - Line Graph Matching

边双联通分量。

容易发现偶数条边总是可以通过贪心匹配完的,奇数条边会有一条边不能被匹配;再进一步分析,如果奇数条边中删的边是割边,那么分成的两个联通块中边数有奇数的就会缺少匹配,所以要保证割掉这条边后两个联通块都是偶数边才会更优。

具体地,用边双联通分量缩点后,对于每个子树内是偶数边数时,可以删掉割边计算答案;非割边的情况可以预处理即可。

点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int mod = 998244353;
#define endl '\n'
const int N=5e5+3;
#define endl '\n'
int  cnt;
int dfn[N], low[N];
vector<array<int,3>> g[N];
vector<int>ans[N];
stack<int> st;
int dcc;
///c[x]表示x所属的边双联通分量编号
int c[N];
int s = 0;void tarjan(int x, int las) {low[x] = dfn[x] = ++cnt;st.push(x);for (auto f: g[x]) {pair<int,int>i={f[0],f[1]};if (i.second == (las ^ 1)) continue;if (!dfn[i.first]) {tarjan(i.first, i.second);low[x] = min(low[x], low[i.first]);} else low[x] = min(low[x], dfn[i.first]);}if (dfn[x] == low[x]) {vector<int> vec;dcc++;ans[dcc].push_back(x);c[x]=dcc;while (st.top() != x) {ans[dcc].push_back(st.top());c[st.top()] = dcc;st.pop();}st.pop();}
}
void init(int n) {cnt = 0;dcc = 0;while (st.size())st.pop();for (int i = 0; i <= n; ++i) {g[i].clear();ans[i].clear();low[i] = dfn[i] = 0;c[i] = 0;}
}
vector<array<int,2>>mp[N];
int a[N];
int res=0;
int f[N];
void dfs(int u,int fa) {f[u] = a[u];for (auto [v, w]: mp[u]) {if (v == fa)continue;dfs(v, u);f[u] += f[v]+1;if (f[v] % 2 == 0) {res = max(res, s - w);}}
}
void solve() {int n, m;cin >> n >> m;vector<int> du(n + 1);vector<array<int, 3>> edge;for (int i = 1; i <= m; ++i) {int u, v, w;cin >> u >> v >> w;s += w;g[u].push_back({v, i << 1, w});g[v].push_back({u, i << 1 | 1, w});}if (m % 2 == 0) {cout << s << endl;return;}for (int i = 1; i <= n; ++i) {if (!dfn[i]) tarjan(i, 0);}for (int i = 1; i <= n; ++i) {for (auto [v, id, w]: g[i]) {if (c[v] != c[i]) {mp[c[i]].push_back({c[v], w});}}}for (int i = 1; i <= dcc; ++i) {std::sort(mp[i].begin(), mp[i].end());mp[i].erase(unique(mp[i].begin(), mp[i].end()), mp[i].end());}vector<int> vis(n + 1);for (int i = 1; i <= n; ++i) {if (vis[i] == 0) {int sum = 0;queue<int> q;q.push(i);while (q.size()) {auto u = q.front();q.pop();vis[u] = 1;for (auto [v, idx, w]: g[u]) {if (c[v] == c[u]) {res= max(res,s-w);sum++;if (vis[v] == 0) {vis[v] = 1;q.push(v);}}}}a[c[i]] = sum;}}
//    cout<<res<<endl;
//    for (int i = 1; i <= dcc; ++i) {
//        for (auto x: ans[i]) {
//            cout << x << ' ';
//        }
//        cout << endl;
//    }
//    cout << endl;for (int i = 1; i <= dcc; ++i) {a[i] /= 2;
//        cout << a[i] << ' ';}dfs(1, 0);cout << res << endl;
}signed main() {ios::sync_with_stdio(0);cin.tie(0);int t=1;
//    cin >> t;while (t--) {solve();}}

J - Luggage Lock

最短路。

发现给定的两个字符串可能有 \(1\times 10^4\) 种状态,又是多源,复杂度是难以承受的;但是两个不同状态之间有相对关系,将一个状态调整到全 \(0\) 状态后,另外一个状态也调整相应步数,这时候它们的最短路程和未调整前是一样的,即对于 \(u\rightarrow v\) 来说,将 \(u\) 都调整到全 \(0\) 的状态,\(v\) 调整相应的步数,那么在一开始用全 \(0\) 跑完 \(\text{dijkstra}\) 就可以 \(O(1)\) 回答。

点击查看代码
#include <bits/stdc++.h>
#define PII pair<int,int>
#define endl '\n'
using namespace std;using i64 = long long;
const int N=1e4+10,M=1e5+10;
string a, b;vector<PII>g[N];
int vis[N],mn[N];
int ans[M];
void solve() {int m;cin>>a>>b;int s=0;for(int i=0;i<4;i++){int p=(b[i]-a[i]+10)%10;s*=10;s+=p;}
//	cout<<s<<endl;cout<<mn[s]<<endl;
}
int main() {
//	freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(nullptr);queue<PII>q;for(int l=0;l<1;l++){int pp=l;q.push({0,pp});for(int i=0;i<1e4;i++){vis[i]=0;mn[i]=1e9;}mn[pp]=0;while(q.size()){auto [s,x]=q.front();q.pop();if(vis[x]){continue;}vis[x]=1;for (int i = 1; i <= 4; i += 1) {for (int j = 0; j + i - 1 < 4; j += 1) {int nxt = x;for (int k = j; k <= j + i - 1; k += 1) {int p=pow(10,3-k);if (nxt/p%10 == 9) {nxt+=p;nxt-=p*10;}else {nxt+=p;}}if(s+1<mn[nxt]){mn[nxt]=s+1;q.push({s+1,nxt});}nxt = x;for (int k = j; k <= j + i - 1; k += 1) {int p=pow(10,3-k);if (nxt/p%10 == 0) {nxt-=p;nxt+=p*10;}else {nxt-=p;}}if(s+1<mn[nxt]){mn[nxt]=s+1;q.push({s+1,nxt});}}}}}int t=1;cin >> t;while (t--) {solve();}return 0;
}
http://www.hskmm.com/?act=detail&tid=22584

相关文章:

  • Docker容器完全操控指南
  • 【Groovy】Groovy环境搭建
  • 2025年TAB拉链制造商权威推荐榜:创新设计与耐用品质口碑
  • 变量类型
  • 10.1
  • VMware Cloud Foundation 9.0.1.0 发布 - 领先的多云平台
  • velero 备份及使用方法
  • 洛谷月赛T1 P14081 「CZOI-R7」炸弹游戏
  • VMware NSX 4.2.3.1 发布,新增功能概览
  • Claude Code V2集成KAT-Coder
  • Ubuntu 软件源
  • Ceph 分布式存储学习笔记(一):介绍、部署与集群设置(上)
  • 数学学习总结
  • VMware Aria Suite Lifecycle 8.18 Patch 5 发布,新增功能概览
  • P3977 [TJOI2015] 棋盘题解
  • 03. 基本元素
  • 基础整理01:Bode图、PM、GM、极点零点 - 教程
  • [已解决]CUDA error: CUBLAS_STATUS_EXECUTION_FAILED when calling cublasSgemmStridedBatched
  • VMware vCenter Server 7.0U3w 发布 - 集中管理 vSphere 环境
  • VMware Aria Operations 8.18.5 发布,新增功能概览
  • VMware Aria Operations for Logs 8.18.5 发布,新增功能概览
  • 专题:2025医药行业数智赋能与AI应用全景研究报告|附200+份报告PDF、数据仪表盘汇总下载
  • 喵之勇者败北录
  • Windows 作为 Ansible 节点的完整部署流程(含 Docker 部署 Ansible) - 实践
  • 软工
  • 10.1考试T4(swap)题解
  • 基本分段存储管理方式
  • 专题:2025零售数字化与即时零售竞争洞察报告|附130+份报告PDF、数据仪表盘汇总下载
  • 2025/10/1图论
  • 详细介绍:Python 豆瓣TOP250 爬虫类讲解