康复训练

August_Light · 2024-04-06 14:02:45 · 个人记录

• P2902 [USACO08MAR] Pearl Pairing G【黄】
  • 优先队列。
  • AC 于 2024/4/4。
  • 死因：题意数据范围不清，不是我的锅。
• P2390 地标访问【黄】
  • 二分。
  • AC 于 2024/4/4。
  • 死因：
  • upper_bound() 返回第一个大于指定元素的迭代器。
  • lower_bound() 返回第一个大于等于指定元素的迭代器。
• P9463 [EGOI2023] Inflation / 通货膨胀【黄】
  • 桶。
  • AC 于 2024/4/4。
  • 一发入魂。
• P2661 [NOIP2015 提高组] 信息传递【黄】
  • 基环树。
  • AC 于 2024/4/4。
  • 死因：未考虑图不连通。
• P6067 [USACO05JAN] Moo Volume S【黄】
  • 拆贡献。
  • AC 于 2024/4/5。
  • 一发入魂。
• P1873 [COCI 2011/2012 #5] EKO / 砍树【黄】
  • 二分。
  • AC 于 2024/4/6。
  • 一发入魂。
• P3743 小鸟的设备【黄】
  • 二分。
  • AC 于 2024/4/6。
  • 一发入魂。
• P3015 [USACO11FEB] Best Parenthesis S【黄】
  • 表达式、栈。
  • AC 于 2024/4/6。
  • 死因：模意义下除以 2 没有用逆元。
• P1233 木棍加工【黄】
  • Dilworth 定理。
  • AC 于 2024/4/10。
  • 死因：排序忘记考虑第二关键字。
• P10246 Exciting Days【黄】
  • 模拟。
  • AC 于 2024/4/11。
  • 死因：CE 一次：log10() 传了 __int128。
• P9714 「QFOI R1」摸摸【黄】
  • AC 于 2024/4/11。
  • 死因：
  • 没有考虑除以 0。
  • 没有考虑方程的解为负数要舍去。
• P1736 创意吃鱼法【绿】
  • DP、前缀和、二分。
  • AC 于 2024/4/12。
  • 一发入魂。
• P8116 「Wdoi-1.5」魔理沙的计算器【绿】
  • 数学。
  • AC 于 2024/4/13。
  • 一发入魂。
  • 猜了最关键的结论。好题！
• P8148 声海 | Sea of Voices【绿】
  • 桶。
  • AC 于 2024/4/14。
  • 死因：作为桶的 unordered_map，能找到某个元素不代表这个元素的次数不为 0。
• P7870 「Wdoi-4」兔已着陆【黄】
  • 模拟。
  • AC 于 2024/4/15。
  • 一发入魂。
• P2357 守墓人【绿】
  • 树状数组。
  • AC 于 2024/4/16。
  • 一发入魂。
• P1774 最接近神的人【黄】
  • 树状数组。
  • AC 于 2024/4/16。
  • 死因：
  • 逆序对 tr.query(a[i]-1) 写成 tr.query(a[i]) 了。
  • i += lowbit(i) 写成 i++ 了（恼）。
• P2602 [ZJOI2010] 数字计数【绿】
  • 数位 DP。
  • AC 于 2024/4/17。
  • 一发入魂。
• P6538 [COCI2013-2014#1] LOPOV【绿】
  • 贪心。
  • AC 于 2024/4/17。
  • 死因：
  • 扫描线（？）的时候没判 ptr <= n RE 了。
  • 堆没判空 RE 了。
• P4939 Agent2【绿】
  • 树状数组。
  • AC 于 2024/4/18。
  • 一发入魂。
• P7871 「Wdoi-4」芙兰？姆Q！贤者与谜题【绿】
  • 序列并查集。（其实有简单的差分做法！）
  • AC 于 2024/4/18。
  • 死因：调试的时候因为栈上开不下数组把 MAXN 改到 1e2，然后忘记改回来了。
• P2216 [HAOI2007] 理想的正方形【绿】
  • 单调队列。
  • AC 于 2024/4/19。
  • 一发入魂。
• P2850 [USACO06DEC] Wormholes G【绿】
  • SPFA。
  • AC 于 2024/4/20。
  • 死因：不审题。
• P7224 [RC-04] 子集积【绿】
  • 01 背包变形、组合数。
  • AC 于 2024/4/21。
  • 死因：指数最多到二十几，不意味着逆元只要处理到二十几。
• B3624 猫粮规划【黄】
  • 01 背包。
  • AC 于 2024/4/21。
  • 一发入魂。
• P2657 [SCOI2009] windy 数【蓝】
  • 数位DP打表。
  • AC 于 2024/4/21。
  • 死因：题目范围是 2e9，打表的时候只打到 1e9 就停了。
• [ABC159F] Knapsack for All Segments【绿】
  • 分治（或 DP）、背包。
  • AC 于 2024/4/23。
  • 一发入魂。
• [ABC169F] Knapsack for All Subsets【绿】
  • 背包变式。
  • AC 于 2024/4/24。
  • 一发入魂。
  • 好题！
• [ARC169B] Subsegments with Small Sums【绿】
  • 二分。
  • AC 于 2024/4/25。
  • 一发入魂。
• P1122 最大子树和【黄】
  • 树上 DP。
  • AC 于 2024/4/27。
  • 死因：不审题。
• P3398 仓鼠找 sugar【绿】
  • LCA。
  • AC 于 2024/4/28。
  • 死因：判断"点 w 是否在 u 到 v 的路径上"的函数写错了。
  • 结论积累：
  • 两条路径 a \rightsquigarrow b 与 c \rightsquigarrow d 有交，当且仅当 \text{LCA}(a,b) 在 c \rightsquigarrow d 上或 \text{LCA}(c,d) 在 a \rightsquigarrow b 上。
  • 判断点 c 是否在路径 a \rightsquigarrow b 上，可以用 dis(a,c) + dis(c,b) = dis(a,b)。
• P3193 [HNOI2008] GT考试【紫】
  • KMP 自动机、矩阵快速幂。
  • AC 于 2024/4/29。
  • 一发入魂。