【题解】给你一次AK的机会，你会好好把握吗bulid by [正牌管理员]萌萌哒管理员 at 2015-08-10 13:16
 Rating:978 | A题神水不解释。要注意的是题目给定的序列已经是有序的了。 B题维护总数，+x 的时候+1，-x的时候减一，如果遇见没出现过的-x则答案加一。动态维护每个操作后的总数的最大值。 C题dp。dp[i][j]表示利用前i个数组合成j的拼法数。则dp[i][j]=∑（dp[i-1][j-a[i]*k]） (k>=0 && j-a[k]>=0) D题。可以二分枚举i表示询问了前i个，每次枚举判断当前是否可以判断出有撒谎。如果有撒谎则往前查找，没有撒谎则往后查找。也可以用set动态维护每个区间搜索。复杂度都是O（nlogn） E题。从后往前预处理出每个位置以后的不同的数的个数。查询时候直接输出即可。 |
Rating:978 | C题记忆化搜索和dp都可以，做DP可以先从记忆化搜索开始，比较好理解。 |
Rating:978 | D题set解法
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
#include<math.h>
using namespace std;
#define CIN(x) scanf("%d",&x)
#define FOR(i,n) for(i=0;i<(n);i++)
int A[200005];
set<int> s;
int main(){
int n,k,m,i,a;
s.clear();
CIN(n);
CIN(k);
CIN(a);
CIN(m);
FOR(i,m){
CIN(A[i]);
}
s.insert(0);
s.insert(n+1);
int ans=(n+1)/(a+1);
FOR(i,m){
s.insert(A[i]);
set<int>::iterator it=s.find(A[i]);
it++;
int r=*it;
it--;
it--;
int l=*it;
ans-=(r-l)/(a+1);
ans+=(r-A[i])/(a+1);
ans+=(A[i]-l)/(a+1);
if(ans<k) break;
}
if(i<m)
printf("%d\n",i+1);
else printf("-1\n");
return 0;
} |
Rating:978 | D题二分 http://blog.csdn.net/nike0good/article/details/47319837 |
4
此处有一条回复被隐藏
回复
要回复，请先登录