2017-9-14 NOIP模拟赛
送分题
(songfen)
e Time Limit: 10 00ms y Memory Limit:128MB
题目描述
LYK 喜欢干一些有挑战的事, 比如说求区间最大子段和。 它知道这个题目有 O(n)的做法。
于是它想加强一下。
也就是说,LYK 一开始有 n 个数,第 i 个数字是 ai,它找来了一个新的数字 P,并想将
这 n 个数字中恰好一个数字替换成 P。要求替换后的最大子段和尽可能大。
LYK 知道这个题目仍然很简单,于是就扔给大家来送分啦~
注:最大子段和是指在 n 个数中选择一段区间[L,R](L<=R)使得这段区间对应的数字
之和最大。
输入格式(songfen.in)
第一行两个数 n,P。
接下来一行 n 个数 ai。
输出格式(songfen.out)
一个数表示答案。
输入样例
5 3
-1 1 -10 1 -1
输出样例
5
样例解释
将第三个数变成 3 后最大子段和为[2,4]。
数据范围
对于 30%的数据 n<=100。
对于另外 30%的数据 ai,P>=0。
对于 100%的数据 n<=1000,-1000<=ai,P<=1000。
Note:提前 AK 的同学可以想一想 O(n)的做法。
/*
先用前缀和维护原序列
然后将p与序列中的每个数做差形成新的序列,用st表维护新序列的区间最大值
枚举序列的左右端点,然后用原序列的区间和加上新序列的区间最大值更新答案
*/
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 1010
int n,p,a[maxn],q[maxn],mx[maxn][],sum[maxn];
int query(int l,int r){
int k=;
while(<<k+<=(r-l+))k++;
return max(mx[l][k],mx[r-(<<k)+][k]);
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("songfen.in","r",stdin);
freopen("songfen.out","w",stdout);
scanf("%d%d",&n,&p);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-]+a[i];
q[i]=p-a[i];
mx[i][]=q[i];
}
int ans=-0x7fffffff;
for(int j=;(<<j)<=n;j++)
for(int i=;i<=n;i++)
mx[i][j]=max(mx[i][j-],mx[i+(<<(j-))][j-]);
for(int i=;i<=n;i++){
for(int j=i;j<=n;j++){
ans=max(ans,sum[j]-sum[i-]);
int now=sum[j]-sum[i-]+query(i,j);
ans=max(ans,now);
}
}
cout<<ans;
return ;
}
100分 前缀和+st表
树状数组
(lowbit)
e Time Limit:1 1 000ms y Memory Limit:128MB
题目描述
这天,LYK 在学习树状数组。
当它遇到一个叫 lowbit 的函数时有点懵逼。 lowbit(x)的意思是将 x 分解成二进制, 它的
值就是?
? ,其中 k 是最小的满足(x & ? ? )>0 的数。 (&是二进制中的 and 运算)
LYK 甚至知道 lowbit(x)=(x&-x)。但这并没什么用处。
现在 LYK 有了 n 个数字,为了使自己更好的理解 lowbit 是什么意思。它想对所有 n^2
个二元组求 lowbit。具体的,对于一个二元组(ai,aj),它的值为 lowbit(ai xor aj) (xor 表示
异或的意思),那么总共有 n^2 对二元组,LYK 想知道所有二元组的值加起来是多少。
这个答案可能很大,你只需输出这个值对 1000000007 取模后的结果就可以了。
输入格式(lowbit.in)
第一行一个数 n,表示有 n 个这样的数字。
第二行 n 个数 ai。
输出格式(lowbit.out)
一个数表示答案。
输入样例
5
1 2 3 4 5
输出样例
32
数据范围
对于 30%的数据 n<=1000。
对于另外 10%的数据 ai<=1。
对于再另外 10%的数据 ai<=3。
对于再再另外 20%的数据 ai<1024。
对于 100%的数据 1<=n<=100000,0<=ai<2^30。
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 100010
#define mod 1000000007
int n;
long long a[maxn];
long long ans;
long long qread(){
long long i=;
char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}
return i;
}
int main(){
freopen("lowbit.in","r",stdin);
freopen("lowbit.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)a[i]=qread();
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
long long x=a[i]^a[j];
ans=(ans+(x&-x))%mod;
}
}
ans=(ans+ans)%mod;
cout<<ans;
return ;
}
30分 暴力
/*
分治
二进制最后一位是0的放左边,最后一位是1的放右边,对答案的贡献为两者个数的乘积* 2^0
对于左边的和右边的,分别做:
二进制倒数第二位是0的放左边,倒数第二位是1的放右边,对答案的贡献为两者个数的乘积* 2^1
……
边界条件1: 没有数了
边界条件2:二进制位数>30 (非常重要,他保证了最多分治30层,高效解决应重复出现的数)
*/
#include<iostream>
#include<cstdio>
#define mod 1000000007
#define N 100001
using namespace std;
int n;
int a[N],b[N];
long long ans;
void divide(int l,int r, int k){
if(l>=r || k>) return;
int L=l,R=r;
for(int i=l;i<=r;i++)
if(a[i] & (<<k)) b[L++]=a[i];
else b[R--]=a[i];
ans=(ans+1ll*(L-l)*(r-R)*(<<k))%mod;
for(int i=l;i<=r;i++) a[i]=b[i];
if(l!=L) divide(l,L-,k+);
if(r!=R) divide(R+,r,k+);
}
int main(){
freopen("lowbit.in","r",stdin);
freopen("lowbit.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
divide(,n,);
printf("%I64d",(ans<<)%mod);
}
100分 分治
防 AK 好题
(fangak)
e Time Limit: 10 00ms y Memory Limit:128MB
题目描述
LYK 觉得,这场比赛到目前为止,题目都还太简单了。
于是,它有意在最后一题为难一下大家。它定义了一个非常复杂的运算。具体的,一开
始它有 n 个数 ai。令 c 表示最大的相邻两个数的差。也就是说 c=max{|a[i]-a[i-1]|}(i∈
[2,n])。这个值显然是一个常数。
但是问题来了,LYK 为了刁难你们,它想改变其中 k 个数,也就是说将其中至多 k 个数
变成任意的数,并且 LYK 要求这么做完后 c 的值尽可能小。
输入格式(fangak.in)
第一行两个数 n,k。
接下来一行 n 个数表示 ai。
输出格式(fangak.out)
一个数表示最小的 k 的值。
输入样例
6 3
1 2 3 7 8 9
输出样例
1
数据范围
对于 20%的数据 n<=8。1<=ai<=8。
对于另外 20%的数据 k=1。
对于再另外 20%的数据 ai 一开始是单调递增的。
对于再再另外 20%的数据 n<=100。
对于 100%的数据 1<=k<=n<=1000,-10^9<=ai<=10^9。
/*
二分+DP
dp[i] 表示 到第i个数, 在满足条件(任意两个相邻的数,差<=mid)的情况下,并且i没有被改变,最少改变多少数字。
状态转移: dp[i]=dp[k]+(i-k-1) k=0~i-1 表示 k+1~i-1 都被改变了
转移条件:mid*(k-i)>=abs(a[k]-a[i]) k~i这段区间能满足条件 只管修改了多少个数,至于改成了什么,不关心
最大的差最小,就是让数均匀分布,那么二分最大的差,条件就是差*个数>= | 区间右边-左边 |
也就是假设区间左右端点都不改变,而区间内部都改变
区间内部都改变是最差的情况,他会随着区间左端点的移动而变小
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1001
using namespace std;
int n,k,maxn=-2e9,minn=2e9;
int a[N],dp[N+];
bool check(int mid){
dp[]=;
for(int i=;i<=n;i++){
dp[i]=n+;
for(int j=i-;j>=;j--)
if(!j || mid*(i-j)>=abs(a[i]-a[j])) dp[i]=min(dp[i],dp[j]+i-j-);
}
for(int i=;i<=n;i++)
if(dp[i]+n-i<=k) return true;
return false;
}
int main(){
freopen("fangak.in","r",stdin);
freopen("fangak.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++) scanf("%d",&a[i]),maxn=max(maxn,a[i]),minn=min(minn,a[i]);
int l=,r=maxn-minn,mid,ans;
while(l<=r){
mid=l+r>>;
if(check(mid)) ans=mid,r=mid-;
else l=mid+;
}
printf("%d",ans);
}
还不会呢
最新文章
- C算法编程题系列
- 用ant组建测试框架
- python 练习 5
- 第四章 CSS基础
- short-path problem (Spfa) 分类: ACM TYPE 2014-09-02 00:30 103人阅读 评论(0) 收藏
- SOAP消息的传递
- Xamarin.Forms DataGrid
- Uva227.Puzzle
- JQuery 选择器 *很重要 多记
- 《CSS网站布局实录》读书笔记
- 数据库sql语句为什么要用绑定形式?
- 从durable谈起,我是如何用搜索引擎抓住技术的关键字学习新姿势打开敏捷开发的大门
- Java中的集合框架(下)
- 使用VSCode 编译调试QT程序
- 连接mysql(建表和删表)
- java.util.Stack类中的peek()方法
- 深入解析Java AtomicInteger 原子类型
- R语言实战实现基于用户的简单的推荐系统(数量较少)
- NYOJ 1073 最大值 (模拟)
- mysql 分类
热门文章
- 【python】使用python发送文本内容邮件
- 在pycharm中执行脚本没有报错但输出显示Redirection is not supported.
- PAT 天梯赛 L2-025. 分而治之 【图】
- PAT 乙级 1085. PAT单位排行 (25) 【结构体排序】
- 现代JS中的流程控制:详解Callbacks 、Promises 、Async/Await
- css3立体旋转菜单
- 使用IE11的F12开发人员工具进行网页前端性能测试
- [算法]Trie树
- Enum定义位域, 即可以通过位操作来产生未命名的值
- sql 的基础语句