Mio_qh

算法题

27 篇文章

一些小玩意

1 篇文章

比赛记录

4 篇文章

杂谈

0 篇文章

补题

2 篇文章

记录

0 篇文章

2026-04-17 3k 字 17 分钟

2026 年中国传媒大学程序设计大赛

比赛传送门 A 不难发现,在已有"CUC"上,增加一个"UC"即可使"CUC"子串的数量 $+1$ Code 1234567void solve() { int n; cin >> n; cout <<"CUC"; for (int i=2;i<=n;i++) cout <<"UC"; cout <<el;} B 简单dp 记 $dp_{i,j}$ , $i$ 表示当前走到第几阶, $

2026-04-14 389 字 3 分钟

Java实现选择按钮,绘制相应图形

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576import javax.swing.*;import java.awt.*;import java.awt.event.ItemEvent;import java.awt.event.ItemListener;public class temp extends JFrame { private

2026-03-14 252 字 2 分钟

贡献法贪心

题目传送门 N题大致思路比较相邻两个操作对答案的贡献,记下标 $i,j$ $i$的贡献:$a_j(a_i*x+b_i)+b_j$ $j$的贡献:$a_i(a_j*x+b_j)+b_i$ 即比较 $a_j*b_i+b_j$ 和 $a_i*b_j+b_i$ 写一个自定义排序即可,注意 $a==1$ 和 $a==0$要特判(放在最前面) Code 123456789101112131415161718192021222324252627bool cmp (const array<int,2> &a,const array<i

2026-03-11 370 字 2 分钟

单调队列优化dp

题目传送门大致思路很明显各行的最小花费相互独立,可以分别计算,最后求前缀和,枚举端点即可得出答案,主要难点在于求单独一行的最小花费: 记 $dp_{i}$ 为只考虑前 $i$ 列,且第 $i$ 列建桥墩的最小花费 $$dp_{i}=a_i+1+\sum_{j=i-d-1}^{i-1}min\{dp_j\} $$直接一点时间复杂度为$O(nmd)$,考虑单调队列优化,优化后 $O(nm)$ 优化具体细节看代码 123456789101112131415161718192021222324252627void solve() { int n,m,k,d;

2026-03-08 350 字 2 分钟

CF1974E Money Buys Happiness

题目传送门大致思路注意到题目限制条件快乐值总和$≤10^{5}$ 又 $(1≤m≤50)$,可以想到 $dp$: 记$dp_{i,j}$为在第 $i$ 天获得 $j$ 快乐值的最小花费,于是有: $dp_{i,j}=min(dp_{i-1,j},dp_{i,{j-h_i}}+c_i)$ 对于第二项,当且仅当 $h_i≤j$ 且 $c_i+dp_{i,{j-h_i}}≤cur$ 时可以取到特别地,当 $j==h_i$ 时额外判断一下 $dp_{i,h_i}=min(c_i,dp_{i,h_i})$ 然后就是细节:花费可能会超出 $int$ ,要用

2026-03-08 613 字 4 分钟

观察数学关系找到突破口

题目传送门大致思路已知 $q=[\frac{x}{y}]$ 和 $r=x\%y$ $$q=\frac{x-r}{y} $$$$x=qy+r $$$x$ 有上限 $k$ , $y$越小,对于该 $q$ 能取到的 $r$ 越大那么就让 $y=r+1$ 取到最小对于所有 $q$ 二分得到能取到的最大 $r$ ,然后在 $r$ 集合中二分找到小于等于这个最大的 $r$ 的最大值,将其与该 $q$ 组合,即删去 Code 123456789101112131415161718192021222324252627282930313233343

2026-03-06 372 字 2 分钟

CF2037F Ardent Flames

题目传送门大致思路显然随着攻击次数增多,击败的敌人会更多,满足单调性,考虑二分接下来问题就是在确定攻击次数为 $x$ 的情况下,能否击败超过 $k$ 个敌人对于每个敌人在的位置 $pos$ 和血量 $hp$ ,以及其与攻击的位置 $p$ 的距离 $dis$,可以得出: $$hp≤x(m-dis) $$$$dis≤m-hp/x $$记$d=m-hp/x$ ,也就是攻击位置 $p$ 在$[pos-d,pos+d]$内,则该敌人会被击败这里用到差分,将 $[pos-d,1]$ 和 $[pos+d+1,-1]$加入数组 $a$ 前者表示攻击位置到达 $po

2026-03-06 506 字 3 分钟

贪心地走到最顶或最底端dp

题目传送门大致思路要想路径最短,肯定在 $x$ 轴上不会走回头路 $y$ 轴上只会走到当前 $x$ 坐标的最顶端或最底端,否则会出现重复走一段路的情况记$dp_{i,0},dp_{i,1}$分别为 $x$ 坐标为 $i$ 且走到最顶端 , 或最底端的最小步数那么有 $dp_{i,0}=min(dp_{[i-1][0]}+abs(a_{[i-1][0]}-a_{[i][1]}),dp_{[i-1][1]}+abs(a_{[i-1][1]}-a_{[i][1]}))+a_{[i][0]}-a_{[i][1]}$ $dp_{i,1}=min(dp_{[i-1][0]}

2026-02-23 984 字 6 分钟

牛客周赛 Round 132(比赛记录)

第一次AK周赛比赛传送门 A 开始时间 +$5$(mod24) 即可 Code 12345void solve() { int n; cin >> n; cout << (n+5)%24 <<el;} B 五的倍数,即末位数字为 $0$ 或 $5$ 且数字本身不为 $0$ 但据数据范围可知 $n$ 不为 $0$ ,无需特判直接判断每一位看看是不是 $5$ 或 $0$即可 Code 12345678910111213void solve() { int n; cin >> n;

2025-12-22 971 字 5 分钟

牛客周赛 Round 123(补题)

比赛传送门 D 可以注意到,由于飞机中两个三个相同的数必须是相邻的,所以只用枚举一个数便可知道另一个三个相同的数是什么接下来就该考虑如何分配后面两个对子: 对于一个点数,如果该点数有 $2$ 或 $3$ 张,那么该点数可以拿去凑到其中一对 (记这种情况的点数有 c2 个) 如果 $≥4$ 张,那么该点数可以自成两对或者是拿去凑到其中一对 (记这种情况的点数有 c4 个) 于是可以这样组合: c2中自取不同的两对: c2*(c2-1)/2 c4中自取不同的两对: c4*(c4-1)/2 c2和c4中各取一对: c2*c4 c4中自取相同的两对: c4 在每次枚举三个相同的数时更新 c2 和