Rain_Fly

分类

学习笔记(1) 日常练习(2) 题解(29)

/ 注册

全部文章（共32篇）

牛客周赛80-不公平对局

记忆化搜索dp #include <bits/stdc++.h> using namespace std; #define endl '\n' #define int long long int mod = 1e9 + 7; typedef long long ll; int qmi(i...

C++ 动态规划

2025-02-13

0 17

周赛 Round 63-小红的 red 计数（我爱前缀和）

这个题目赛时的时候没有想到要以red中间的e开始计算，每次可以通过计算：当前为‘e’的元素前面的r的数量*后面d的数量，这样就得到了一个式子，然后经过一系列的化简就可以以o(1)计算出每一个结果，具体化简请看https://www.bilibili.com/video/BV1xh2qYgESd?p...

C++

2024-10-14

1 81

小白月赛最短？路径

这道题的可以用分层图来理解，分层图就是同一个图在z轴多了一个一样的图，每一层可以代表休息的次数，最下面为0层，这样bfs的时候，在当前节点休息就相当于优先队列中的上一个点连接到第0层的当前点，在当前节点不休息，就相当于有限队列中的上一个点连接到更高一层的当前点，这样就建立了一个立体的图，在用最短路的...

C++

2024-10-12

8 116

cf B. Mashmokh and ACM

#include <bits/stdc++.h> using namespace std; #define endl '\n' #define int long long typedef long&...

C++

2024-10-09

0 53

周赛60-我们N个真是太厉害了

题目大意就是给n个数，任意组合，求n以内最小的不能组成的数，解题思路用的是动态规划的思想，先排序，维护一个区间[ 1 , sum ] ,表示该区间内的数都可以组成，如果当前a[ i ]大于sum + 1 , 当前sum + 1就是当前不能组成的数，因为当前a[ i ] 已经大于sum + ...

C++

2024-09-18

4 167

小白月赛-小苯的01背包

这道题其实是一道思维题目，我们可以观察到，价值&的越多，答案可能会越小，而体积&的越多反而对我们越有利，由于数据范围并不大，可以直接枚举答案，枚举每种价值，再枚举每个物品价值，如果&进来不会影响，就加进来，因为体积&是更有利的，意思就是把每个满足当前价值的物品体积&a...

C++ C

2024-05-25

2 282

J甜甜圈-河南省第十三届ICPC大学生程序设计竞赛

题目：https://ac.nowcoder.com/acm/contest/83372/J vp的时候就卡在如何求当前区间内，已经被吃掉的甜甜圈有几个。赛后学了学树状数组，我们可以让每个点为1代表当前位置有甜甜圈，然后初始化树状数组c[i]，然后在每次选取最大值过程中，更新c[i]单点也就是n...

C++

2024-05-18

1 282

牛客周赛

二维写法 ">typedef unsigned long long ull; typedef long long ll; using namespace std; const int N = 310; const int M = 2e5 + 10; const int mod = 99824435...

C++

2024-04-15

8 280

同余方程

求关于x的同余方程ax≡1(modb)的最小正整数解。用拓展欧几里得定理求解即可，证明参考：https://zhuanlan.zhihu.com/p/103410252 代码： #include<bits/stdc++.h> typedef long&nb...

C++

2024-03-27

0 237

【模板】01背包

这个题主要就是01背包的模版，对于恰好装满，我们需要初始化dp为某个值，在遍历更新过程中能够识别出dp[j-v[i]]是否被访问。 #include<bits/stdc++.h> typedef unsigned long long ull; ...

C++

2024-03-26

0 246