2022115828

分类

学习笔记(4) 题解(9)

/ 注册

全部文章（共13篇）

牛客周赛 Round 38

A：小红的正整数自增 void solve(){ ll n; cin >> n; for(int i = 0; i <= 9; i ++){ ll y = n + i; if(y % 10 == 0){ ...

C++

2024-03-25

0 297

最大子段和问题

P1115 最大子段和思路：经典线性DP，dp[i]表示前i个元素的最大子段和，最后输出max(ma, dp[i])即可 void solve(){ int n; cin >> n; vector<int> a(n + 1), dp(n + 1); for(int...

C++ 动态规划双指针

2023-11-19

0 300

DP问题之背包问题

1：01背包问题问题：给出n个物品，每个物品只能使用一次，每个物品有相应的体积与价值，你可以选择总体积不超过m的物品放入背包，求能得到的最大价值思路：建立一个二维的DP矩阵，dp[i][j]表示把前i个物品装入体积为j的背包能得到的最大价值，从小问题扩展到大问题朴素版： int n, m; i...

C++ 动态规划

2023-10-20

0 278

KMP算法

KMP算法的作用：给你一个长为n的字符串s和一个长为m的字符串p，求s中等于p的连续子串的出现位置或者出现次数原理：当我们进行字符串匹配失配之后我们回溯到k，k满足从当前i位置的一个后缀等于适配字符串的一个k前缀，我们预先用nxt数组处理并且存储k的值，我们用p存储的是在当前位置能够适配字符串p的...

字符串匹配

2023-10-02

0 318

位运算技巧之拆位

1：Codeforces Round 900 (Div. 3) ：E. Iva & Pav 题意：给出一个长度为n的数组，给出一个l和k，求连续与运算之后找出最大的一个r，使得f(l,r)运算之后得出的结果大于等于k 思路：这里使用拆位的技巧，根据数据范围可知数字表示为二进制后最大不会超过3...

C++

2023-09-27

0 416

Square

思路：枚举pow(10,k)，然后y = sqrt(x * pow(10,k))，取l = sqrt(y),r = sqrt(y) + 1即可，注意ll问题以及y的范围是 1~1e9 #include<bits/stdc++.h> using namespace std; #define...

C++

2023-07-22

1 336

多重背包

思路：模板题，利用二进制优化 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=100010; int w[N],v[N],dp[N]; int main(){ ios::sy...

C++ 动态规划

2023-07-14

0 349

马踏棋盘

思路：dfs或者bfs均可 bfs解法： #include<bits/stdc++.h> using namespace std; const int N = 100010; typedef long long ll; typedef pair<int,int> PII; ...

深度优先搜索广度优先搜索

2023-07-12

1 472

小红的数组操作(easy version)

思路：枚举所有可能即可，分别计算往下减n个y所对应的结果，取最小值即可 #include<bits/stdc++.h> using namespace std; #define int long long const int N=100010; int n,p,x,q,y; void...

C++

2023-07-09

2 633

值周

思路：把每一个区间的左端点作为key值排序即可，然后更新l,r,注意这里是包括两端端点的，所以每次更新ans += (l - r + 1),同时注意长为n的路其实有n + 1个点，因为包括第0个点，更新右端点记得用max(r,b),在这里被坑了一发 #include<bits/stdc++.h...

C++ 贪心模拟

2023-07-03

0 372