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

AtCoder Beginner Contest 424

A - Isosceles

核心代码

signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int a, b, c;cin >> a >> b >> c;if(a == b || b == c || a == c) cout << "Yes";else cout << "No";   return 0;
}

B - Perfect

核心代码

signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n, m, k;cin >> n >> m >> k;vector<int> ans, cnt(n + 1);while(k--){int a, b;cin >> a >> b;cnt[a] ++;if(cnt[a] == m) ans.push_back(a);}for(auto t: ans) cout << t << " ";return 0;
}

C - New Skill Acquired

思路

根据描述建图,从 \(A_i,B_i\) 指向 \(i\)

最后求的就是从 \(0\) 可以到达的节点

核心代码

signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n; cin >> n;vector<vector<int>> adj(n + 1);for(int i = 1; i <= n; i++){int a, b;cin >> a >> b;adj[a].push_back(i);adj[b].push_back(i);    	}queue<int> q;vector<int> vis(n + 1);q.push(0);int cnt = 0;while(q.size()){auto u = q.front();q.pop();for(auto v: adj[u]){if(vis[v]) continue;vis[v] = 1;q.push(v);cnt++;}}cout << cnt;return 0;
}

D - 2x2 Erasing 2

思路

tag:状压 dp

遍历每一行的状态,以及到达这种状态需要的染白次数(不需要管本来是白色,但是状态是黑色的情况)

核心代码

const int inf = 1e18;void solve()
{int n, m;cin >> n >> m;vector<string> g(n);for(int i = 0; i < n; i++) cin >> g[i];vector<int> dp(1 << m, 0);// 遍历每一行for(int i = 0; i < n; i++){// 遍历状态 如果 st 中的某一位是 1 那么这个格子就是黑色for(int st = 0; st < (1 << m); st++){for(int j = 0; j < m; j++){// 如果格子本来是黑色,但是状态要求是白色,那么就需要染白if(g[i][j] == '#' && ((st >> j) & 1) == 0){dp[st]++;}}}// 转移到下一行vector<int> ndp(1 << m, inf);for(int st1 = 0; st1 < (1 << m); st1++){for(int st2 = 0; st2 < (1 << m); st2++){int st = st1 & st2;bool ok = true;while(st){if((st & 3) == 3)// 存在两列都是 1 的情况{ok = false;break;}st >>= 1;}if(ok){ndp[st2] = min(ndp[st2], dp[st1]);}}}dp.swap(ndp);}cout << dp[0] << '\n';
}

E - Cut in Half

思路

因为 \(K\) 很大,所以不能直接模拟

优化:记录每个数和每个数出现的次数,每次取最大的数,如果它的个数比 \(k\) 小,那么可以全部砍半;否则,只取 \(k\)

核心代码

using PII = pair<double, int>;void solve()
{int n, k, x;cin >> n >> k >> x;priority_queue<PII> q;unordered_map<int, int> mp;for(int i = 0; i < n; i++){int x; cin >> x;mp[x]++;}	for(auto [x, ct] : mp) q.push({x, ct});while(q.size()){auto [x, ct] = q.top();q.pop();if(k >= ct){q.push({x / 2, ct * 2});k -= ct;}else{q.push({x, ct - k});q.push({x / 2, k * 2});k = 0;break;}}while(x){auto [v, ct] = q.top();q.pop();if(ct >= x){cout << setprecision(20) << fixed << v << '\n';return;}else x -= ct;}
}

F - Adding Chords

思路 1

对于圆上两个线段\([a, b],[c,d]\),线段相交的条件是 \(a < c < b < d\) 或者 \(c < a < d < b\)

所以问题变成了,对于新增的边 \([a, b]\),判断是否满足上述条件

那么对于每个区间:

  • 记录在这个区间的右端点的最小左端点,判断新增边的左端点是否小于最小左端点
  • 记录在这个区间的左端点的最大右端点,判断新增边的右端点是否大于最大右端点

核心代码

struct Info
{int minl, maxr;Info() : minl(1e9), maxr(0) {}
};Info operator+(const Info& a, const Info& b)
{Info c;c.minl = min(a.minl, b.minl);  c.maxr = max(a.maxr, b.maxr);return c;
}template<class Info>
struct SegmentTree
{int n;vector<Info> info;// 构造空线段树SegmentTree(int n) : n(n), info(4 << __lg(n)) {}// 利用数组构造线段树template<class T>SegmentTree(vector<T> v){n = v.size();info.resize(4 << __lg(n));//[l, r) 初始化线段树function<void(int, int, int)> build = [&](int p, int l, int r){// 叶子节点if(l + 1 == r){info[p] = v[l];return;}int mid = l + r >> 1;build(p << 1, l, mid);build(p << 1 | 1, mid, r);up(p);};build(1, 1, n + 1);};// 向上合并void up(int p){info[p] = info[p << 1] + info[p << 1 | 1];}// 修改左端点对应的最大右端点void modify_maxr(int pos, int val){modify_maxr(1, 1, n + 1, pos, val);}void modify_maxr(int p, int l, int r, int pos, int val){if(l + 1 == r){info[p].maxr = max(info[p].maxr, val);return;}int mid = (l + r) >> 1;if(pos < mid) modify_maxr(p << 1, l, mid, pos, val);else modify_maxr(p << 1 | 1, mid, r, pos, val);up(p);}// 修改右端点对应的最小左端点void modify_minl(int pos, int val){modify_minl(1, 1, n + 1, pos, val);}void modify_minl(int p, int l, int r, int pos, int val){if(l + 1 == r){info[p].minl = min(info[p].minl, val);return;}int mid = (l + r) >> 1;if(pos < mid) modify_minl(p << 1, l, mid, pos, val);else modify_minl(p << 1 | 1, mid, r, pos, val);up(p);}// 查询Info query(int l, int r){return query(1, 1, n + 1, l, r);}Info query(int p, int l, int r, int x, int y){if(x >= r || y <= l) return Info();if(l >= x && r <= y) return info[p];int mid = l + r >> 1;return query(p << 1, l, mid, x, y) + query(p << 1 | 1, mid, r, x, y);}
};signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n, q;cin >> n >> q;SegmentTree<Info> seg(n);for(int i = 1; i <= q; i++){int a, b;cin >> a >> b;auto [minl, maxr] = seg.query(a, b);if(minl < a || maxr > b) {cout << "No" << '\n';}else{cout << "Yes" << '\n';seg.modify_maxr(a, b);seg.modify_minl(b, a);}} return 0;
}

思路 2

利用异或哈希

核心代码

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());struct Fenwick
{vector<int> tree;int n;Fenwick(int size) : n(size + 1), tree(size + 2, 0) {}void update(int idx, int val){for(; idx <= n; idx += idx & -idx)tree[idx] ^=  val;} int query(int idx){int res = 0;for(; idx > 0; idx -= idx & -idx)res ^= tree[idx];return res; }bool query(int x, int y){return (query(y) ^ query(x - 1)) == 0;}
};signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n, q;cin >> n >> q;Fenwick fw(n);for(int i = 1; i <= q; i++){int a, b;cin >> a >> b;if(fw.query(a, b)){cout << "Yes" << '\n';int rd = rnd();fw.update(a, rd);fw.update(b, rd);}else cout << "No" << '\n'; }return 0;
}
http://www.hskmm.com/?act=detail&tid=17820

相关文章:

  • ClkLog埋点分析系统-私有化部署+轻量灵活
  • 级数 - Emi
  • 线性代数 - Emi
  • 基于 Docker 的 Nginx + OpenSSL 自签名证书启用 HTTPS
  • 基于STM32的正弦波逆变器设计
  • 高校固定资产管理高效的系统——Java EE毕业设计资源包
  • ======================================分割线======================================
  • 标准卷积和空洞卷积--适应不同尺寸的输入--ASPP模块
  • 游戏在高负载场景下,整机功耗控制在多少
  • 打印机状态错误,怎么恢复正常打印?
  • 使用Ollama 0.12.2本地部署大模型,友好界面对话,开启飞行模式数据完全存在本地
  • 牛客刷题-Day5
  • 用标准版平板干翻上代Pro,小米又想学苹果了?
  • VonaJS多租户同时支持共享模式和独立模式
  • 记录一下第一次为Dify贡献插件的经历
  • 物联网字节校验常用方法
  • STM32H743-ARM例程2-UART命令控制LED - 实践
  • 完整教程:Zookeeper与Kafka:分布式系统中的协调与消息队列
  • vite-vue3 项目优化首屏加载速度
  • 12_TCP和UDP实现服务端和客户端的通信
  • 各种软件的官方文档和安装包下载地址记录
  • 基于导频的OFDM系统的信道估计(使用LS估计算法)
  • Day22super详解
  • 外发图纸如何控制的最佳实践与注意事项
  • Gitee:中国开发者生态的数字底座正在重构技术格局
  • 快递100
  • 文件同步软件是什么?主要有哪几种类型?
  • “铸网2025”山东省工业和互联网CTF竞赛-web
  • 领嵌iLeadE-588网关AI边缘计算盒子一键部署二次开发
  • 2025年值得选的文件摆渡系统品牌解析