此文章可以使用目录功能哟↑(点击上方[+])

许久不hack,连hack都hack不来了...

链接→BestCoder Round #86

 Problem 1001 Price List

 Problem Idea

解题思路:

【题意】
题意请看上述中文题面

【类型】
水题

【分析】
题目很关键的一句话是

Byteasar并不介意把花的钱记少(多么自欺欺人的一个人)

然后题目问是不是一定记多了

简单想想,什么情况下可以自欺欺人呢?

很简单,因为每个商店的商品最多买1件,那我全买的时候花的钱肯定是最多的

而只要记录的钱数比这个值小,那我都可以自欺欺人一波,反正你不能拿我怎么样

所以此题只需要求出所有商品价值之和,再与Byteasar每天记录的钱做比较即可

另外此题需要注意的就是数据大小了,我看到有人q定义了__int64,但是居然用%d输入,醉了,hack忘记回车,一直说我数据非法,难过

【时间复杂度&&优化】
O(nT)

题目链接→HDU 5804 Price List

 Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 10005;
const int M = 16;
const int inf = 1000000007;
const int mod = 110119;
int main()
{int t,n,m,s,i;__int64 ans,q;scanf("%d",&t);while(t--){ans=0;scanf("%d%d",&n,&m);for(i=0;i<n;i++){scanf("%d",&s);ans+=s;}for(i=0;i<m;i++){scanf("%I64d",&q);if(q>ans)printf("1");elseprintf("0");}puts("");}return 0;
}

 Problem 1002 NanoApe Loves Sequence

 Problem Idea

解题思路:

【题意】
长度为n的序列,等可能性地删除其中一个数,问得到的新数列的所有相邻两数的差的绝对值的最大值的期望为多少

【类型】
优化

【分析】
题目很贴心地帮我们将期望的分母去掉了

那此题就转化成了求所有可能的新序列的相邻两数的差的绝对值的最大值之和

新序列相对于原来的序列而言,就相当于挖掉了一个数,将该数的左边和右边拼凑成新序列

那我们只需知道左边的最大值与右边的最大值,再和拼接处产生的差值比较一下,就可以知道新序列的最大值

即令l[i]表示前i个数两两相邻差值的绝对值的最大值,r[i]表示i到n范围内两两相邻差值的绝对值的最大值

那么枚举删除第i个数,加上删除该数时的序列最大值即可

ans+=max(abs(s[i+1]-s[i-1]),max(l[i-1],r[i+1]))

注意,在删除序列首尾的数时,要特判一下

【时间复杂度&&优化】
O(nT)

题目链接→HDU 5805 NanoApe Loves Sequence

 Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100005;
const int M = 16;
const int inf = 1000000007;
const int mod = 110119;
int s[N],l[N],r[N];
int main()
{int t,n,i;__int64 ans;scanf("%d",&t);while(t--){ans=0;memset(l,0,sizeof(l));memset(r,0,sizeof(r));scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&s[i]);for(i=1;i<n;i++)l[i]=max(abs(s[i]-s[i-1]),l[i-1]);for(i=n-2;i>=0;i--)r[i]=max(abs(s[i+1]-s[i]),r[i+1]);for(i=0;i<n;i++)if(i==0)ans+=r[i+1];else if(i==n-1)ans+=l[i-1];elseans+=max(abs(s[i+1]-s[i-1]),max(l[i-1],r[i+1]));printf("%I64d\n",ans);}return 0;
}

 Problem 1003 NanoApe Loves Sequence Ⅱ

 Problem Idea

解题思路:

【题意】
给定一个长度为n的数列

问有多少个区间的第k大数>=m

【类型】
尺取法

【分析】
看到区间第k大,貌似是个很常见的问题

然而这跟那些区间第k大问题并没有直接关系

首先,要先知道,第k大,是从大到小排序后第k个(不去重)

那简单了,我们只要记录以第i个数作为区间左端点时,右端点延伸到何处能够满足区间内有k个数>=m即可,因为右端点再往右延伸必定满足区间内有k个数>=m

这点可以通过尺取法实现,异或者叫做双指针

那么最终结果只需枚举左端点,加上右端点可以取的个数即可

【时间复杂度&&优化】
O(nT)

题目链接→HDU 5806 NanoApe Loves Sequence Ⅱ

 Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 200005;
const int M = 16;
const int inf = 1000000007;
const int mod = 110119;
int s[N],r[N];
int main()
{int t,n,m,k,i,j,c;__int64 ans;scanf("%d",&t);while(t--){ans=0;c=0;scanf("%d%d%d",&n,&m,&k);for(i=0;i<n;i++){scanf("%d",&s[i]);r[i]=n;}for(j=i=0;i<n;i++){if(s[i]>=m)c++;while(c==k){r[j]=i;if(s[j]>=m)c--;j++;}}for(i=0;i<n;i++)ans+=(n-r[i]);printf("%I64d\n",ans);}return 0;
}