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 i = 1; i <= n; i ++) cin >> a[i]; dp[1] = a[1]; int ma = a[1]; for(int i = 2; i <= n; i ++){ dp[i] = max(dp[i - 1] + a[i], a[i]); ...

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

KMP算法的作用：给你一个长为n的字符串s和一个长为m的字符串p，求s中等于p的连续子串的出现位置或者出现次数 原理：当我们进行字符串匹配失配之后我们回溯到k，k满足从当前i位置的一个后缀等于适配字符串的一个k前缀，我们预先用nxt数组处理并且存储k的值，我们用p存储的是在当前位置能够适配字符串p的第几位，当p[i]==m的时候也就是一次适配成功 复杂度：O(n + m) 板子： int n, m; int nxt[N], f[N]; string s, p; void kmp(){ int j = 0; nxt[1] = 0; for(int i = 2; i <= n; i ...

1：Codeforces Round 900 (Div. 3) ：E. Iva & Pav 题意：给出一个长度为n的数组，给出一个l和k，求连续与运算之后找出最大的一个r，使得f(l,r)运算之后得出的结果大于等于k 思路：这里使用拆位的技巧，根据数据范围可知数字表示为二进制后最大不会超过32位，那我们预处理记录出每一位的1的数量，然后求前缀和，只有(r - l + 1)这个区间的1的数量为（r - l + 1)的时候这个位才会产生贡献，贡献也就是2^k(k指的是所处的位置），然后就可以求出这个[l, r]区间的与运算之后的值。 我们根据与运算的性质可知结果是有单调性的，所以我们可以通...

A： World Fragments I 题意：给定两个数字的二进制表示，每次可以用x减去本身的一个1或者0，直到x变成y最少多少步，可知只要x大于0其中必定存在1，也就是 x可以转化为y，求|x - y|即可 #include<bits/stdc++.h> using namespace std; #define int long long typedef long long ll; typedef pair<int,int> PII; const int N = 100010; int ptt(string s,int p){ int x = 0; for(i...

A： Bobo String Construction 题意：构造给你一个字符串s,你需要构造一个长度为n的字符串s1,使得s + s1 + s中s只在首位两端出现。 思路：枚举全为0或者全为1两种情况看哪种符合即可 #include<bits/stdc++.h> using namespace std; //#define int long long typedef long long ll; const int N = 200010; void solve(){ int n; string s; cin >> n >> s; string s1...

思路：枚举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 int long long const int INF = 1e9; typedef long long ll; typedef pair<int,int> PII; int b[15]; void solve(){ int x; cin >> x; for(in...

思路：模板题，利用二进制优化 #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::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n,m; cin >> n >> m; int cnt = 0; for(int i = 1; i <= n; i ++){ int a,b,c; cin ...

思路：dfs或者bfs均可 bfs解法： #include<bits/stdc++.h> using namespace std; const int N = 100010; typedef long long ll; typedef pair<int,int> PII; int n,m; int ans = 0; int l[5] = {1,2,1,2}; int r[5] = {2,1,-2,-1}; void bfs(){ queue<PII> q; q.push({1,1}); while(!q.empty()){ auto t = ...

思路：枚举所有可能即可，分别计算往下减n个y所对应的结果，取最小值即可 #include<bits/stdc++.h> using namespace std; #define int long long const int N=100010; int n,p,x,q,y; void solve(){ vector<int> v(n); int sum = 0; for(int i = 0; i < n; i ++){ cin >> v[i]; sum += v[i]; } int ans = 1e18; for(int i =...

思路：把每一个区间的左端点作为key值排序即可，然后更新l,r,注意这里是包括两端端点的，所以每次更新ans += (l - r + 1),同时注意长为n的路其实有n + 1个点，因为包括第0个点，更新右端点记得用max(r,b),在这里被坑了一发 #include<bits/stdc++.h> using namespace std; const int N=1000010; #define int long long #define x first #define y second typedef long long ll; typedef pair<int,int&g...

思路：题目很简单，设年份为n以及m，我们只需要看从n-1到m+1有几个年份满足要求就行了 #include<bits/stdc++.h> using namespace std; const int N=100010; typedef long long ll; typedef pair<int,int> PII; int mon1[15] = {0,31,29,31,30,31,30,31,31,30,31,30,31}; int mon2[15] = {0,31,28,31,30,31,30,31,31,30,31,30,31};//平 int a,b,a_1,b_...

思路：按照行来dfs，同时使用col,dg,udg三个数组来记录列，对角线和反对角线是否有棋子。 当我们的u，也就是棋子数等于n的时候，就是我们把棋子安放完成，返回即可。 这里我们的u也同时是行数，这里i则可以理解为列数，从0到n-1列，也就是n列。 我们可以发现一个规律，一条对角线上面的x,y坐标之和相同，例如(1,3),(2,2)或者(2,3)(3,2)。 那么我们把每个点的对应对角线就是dg[u+i]。 这样看来对角线像从左上角依次向下，而反对角线则是从右上角开始。 我们可以发现我们用(i-u)也就是列数减去行数可以表示反对角线的下标，因为这可能会导致为负数，所以我们来加上一个n杜绝这种...

思路：先将所有数字读入num，然后计算每个数字后面的最大的数字，存储在p数组。 接着遍历num，将每个数字入栈，如果当前num[i]等于p[i]说明找到最大数字，将它直接输出。 接着我们要看栈顶元素是否大于后面即将要入栈的元素，如果大于我们要把它优先输出。 代码实现： #include<bits/stdc++.h> using namespace std; const int N=2000010; typedef long long ll; typedef pair<int,int> PII; int num[N],p[N]; int main(){ ios::sy...