今天的题目比较简单~ 题意：有一个数字序列长度为N，现在有一个长度为K的窗口。每次窗口可以查看到序列中连续的K个数字，求窗口在不同位置时候查看的K个数字序列中的最大值和最小值。 类型：单调队列 思路：首先可能会考虑线段树，虽然存在频繁的查询，但是10^6的话nlogn应该还是可以碰一碰的，不过好像会MLE？可以使用单调队列解决。单调队列是维护一个单调递增（递减、不递增、不递减）的数据结构，主要通过双端队列进行维护。在本题中，我们以求最小值为例，维护一个单调不减的队列。假设逐个读入的数字是1 3 -1 -3 5 3 6 。窗口长度K=3第一次读入1，入队[1].最小值1第二次读入3，判断3与队尾...

这题乍一看还挺简单的，仔细一看，好像还有那么点意思。 题意：从n个数中选出两个不相交的区间，且区间长度都为K，求这两个区间的和的最大值。(n<=200000) 题目类型：前缀和、动态规划、线段树 思路：由于区间长度是固定的，很容易想到枚举区间的起点。如果分别枚举两个区间的起点的话，我们需要O(n^2)复杂度，中间的求和可以通过预处理前缀和获得，但是显然会超时。我一开始的做法是，预处理出所有长度为K的区间和，然后丢进线段树里。接着枚举其中一个区间的起点，那么剩下的一个区间的最大值直接从线段树里去查就好了，这样的话O(nlogn)就可以解决。嗯，写起来还是比较快的。 #include<...

今天做的是合并回文子串虽说看到题目就知道是个dp，无奈写不出来。 首先来看题意：给两个字符串A和B，现在将A和B进行合并，要求两个字符串中原有的相对位置不发生变化，问合并的可能中最长的回文子串长度？这里A和B的长度都不超过50. 题目类型：区间DP 题解已经讲的很好了，这里做个总结：  1.最长回文序列问题 给一个字符串，求一个最长的回文子序列（不要求连续）。我们用dp[i][j]表示一个字符串从i-j的最长子序列长度。那么对于dp[i][j]若a[i]=a[j]则dp[i][j]=dp[i+1][j-1]+2若a[i]!=a[j]则dp[i][j]=max(dp[i+1][j],dp[i][...

看到牛客的每日一题挺有意思，决定刷一刷看看。本来想从后往前的，一看发现有点难，还是从头开始吧，应该前面简单点吧。先做第一期的第一题tokitsukaze and Soldier（3月25日） 题目是这样的，从N个士兵中挑选一些组成一个团，每个士兵有一个战力v[i]和一个要求s[i]，这里的s[i]表示第i个士兵要求团里最多只有s[i]个人他才参加。问最高战力是多少？士兵人数n<=10^5 题目类型：贪心、堆（优先队列） 思路：一开始是想着能不能排个序贪心看看，结果发现不行。让我们分析一下，假设参加的人数为k,那么我们只需要从满足s[i]>=k的人中挑选战力最高的k个人就可以了。这个...

本场实力爆炸了，由于时间和能力关系，这里只订正了3题。  A 校园活动 算是签到题，还是Wa了好多发。题目是要我们对给出的数字序列进行分组，要求每组的和相同，而且每组是连续的。由于数据比较小,n<=1000，我们可以直接暴力枚举组数然后check一下就好了。注意特判全0的时候。#include<bits/stdc++.h> using namespace std; int n,sum[1004],tot,a[1004]; string s; bool check(int x,int z){ int tmp=0; int k=0; for(int i=1;i<=n;){ ...

算是在牛客网参加的第一场比赛。是小白月赛，难度应该是很低的。一共10题，时间是3小时。结果我打了3题，果然不给力。比赛的时候过的题目是D、H、I，比较简单，就不花时间赘述。这里简单说下D题，反正就是写了个暴力，发现好像随便哪个点最后都可以变回（0,0），那么直接统计一共有多少个点就行。注意开Long long。 贴下比赛链接：https://ac.nowcoder.com/acm/contest/10746 下面把我补的几个题目按照AC的顺序，简单写下题解:  G 简单题的逆袭 比赛时候死磕的是G题，题目很简单，输入x,y,求x^k<=y中最大的k。显然分类讨论就可以了，我讨论的比较麻烦...