题意：略。 题记：取区间最大值的情况：取维护一个双端队列，每当a[i]进入队尾时，在a[i]之前进入队列且比a[i]小的数是不可能成为区间最大值了，所以这些数可以在队列中删掉。取最小值同理。 #include<bits/stdc++.h> using namespace std; const int N=1e6+10; int a[N]; deque<int>q; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n,k; cin>>n&...

题意：找出两个长度为k的区间和最大。 题记：前缀和处理一下数组，然后枚举区间的右端点，mmax记录下第一个区间和的最大值，再取第二个区间和mmax的最大值即是答案。 #include<bits/stdc++.h> using namespace std; #define int long long const int N=2e5+10; int a[N]; signed main(){ int T; cin>>T; while(T--){ int n,k; cin>>n>>k; ...

题意：略 题记：由于m的范围在1 ≤ m ≤ 2。所以很容易就想到dp。dp[i][j][k]表示的是在第一列的前i个数，第二列的前j个数选k个矩阵的最大值。 那么dp过程中大致有两种情况：1、不需要重新选一个新矩阵dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][k]); 2、需要重新选一个新矩阵：首先矩阵也分为两种（l为矩阵长度）（1）1乘l的矩阵 dp[i][j][k]=max(dp[i][l][k-1]+sum[j][2]-sum[l][2],dp[i][j][k]);dp[i][j][k]=max(dp[l][j][k-1]+sum[i][1]-sum...

题意：略。 题记：将小A和小B做为起点BFS两次，分别记录下小A和小B到每个位置的时间，最后枚举小A和小B相遇的位置，取小A和小B到当前位置的时间的最大值（相当于小A和小B在这个位置相遇）。 #include<bits/stdc++.h> using namespace std; const int N=1010,INF=0x3f3f3f3f; int n,m,dx1,dx2,dy1,dy2; int dis[][2]={1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,-1,-1,1}; //八个方向 char s[N][N]; bool vis[N][N]; int...

题意：略 题记：dp[i][j]表示前i张彩票能组成总金额为j元的方案数第i张彩票有1,2,3,4元四种选择，所以总金额为j的情况可以由四种情况转移过来。dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]; 总方案数是4的n次方种，所有方案数中总金额大于等于3*n的就是不亏本的，将数量记录下来，最后将两个数约分之后输出即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=200; ll dp[N][N...

参考题解 题意：略。 题记：dp[i][j][k][0/1]表示为前i条j段涂k次，最后一段涂红/蓝的最多正确格子数。 可以理解为将所有木条分成了n*m的木块。然后一块一块地填。那么可以分成两种情况：1、当前木块是整条木板的第一块，一定要进行一次新的涂色。（即j为1的情况）由上一条木条的最后一块木板转移过来 当前木块涂红色：dp[i][j][k][0]=max(dp[i−1][m][k−1][0],dp[i−1][m][k−1][1])+(mp[i][j]==0); 当前木块涂蓝色：dp[i][j][k][1]=max(dp[i−1][m][k−1][0],dp[i−1][m][k−1][1]...

题意：求出1-n所有数的最小质因子之和。 题记：筛质数的模板题。用每一个数的最小质因子取筛掉这个数，同时把这个质数加到答案中。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e7+10; bool st[N]; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n; cin>>n; ll sum=0; for(int i...

题目大意：有一个n*m的大陆，在大陆上有三个州（1、2、3），现在需要三个州相连，求最少需要修建多少个单元格作为道路。 题记：首先要了解一下01BFS。bfs可以O（V+E）求解边权全为1的图上的最短路，但是当边权只有0或者1时，可以使用01BFS来快速求解。 01BFS维护一个双端队列，当边权为0时，是利用push_front()放在队头，边权为1时使用push_back()放在队尾。 以每个国家的任意一格为起点，对整张图跑一遍01BFS，就得到了三个国家到所有各自的距离。最后遍历所有各自，找到三个国家与这个格子的距离之和即是答案。 #include<bits/stdc++.h>...