[CSP-S模拟测试]:Read(数学)
题目描述
热爱看书的你有$N$本书,第$i$本书的种类为$A[i]$。你希望每天能够看一本书,但是不希望连续两天看种类相同的书。为了达成这个条件,你需要选择一些书不看,作为一个好学生,你希望不看的书尽可能少,求最少可以有多少书不看。
输入格式
为了避免输入文件过大,我们采取如下方式生成$A[i]$。
第一行读入两个个整数$M$,$K$。
接下来一行读入$M$个整数$count[i]$,其中$N=\sum count[i]$。
接下来一行读入$M$个整数$X[i]$。
接下来一行读入$M$个整数$Y[i]$。
接下来一行读入$M$个整数$Z[i]$。
然后按照下面这段代码生成。
int N = 0, S = (1 << K) - 1;
for (int i = 1; i <= M; ++i) {
N = N + 1;
A[N] = X[i];
long long last = X[i];
for (int j = 1; j < count[i]; ++j) {
last = (last * Y[i] + Z[i]) & S;
N = N + 1;
A[N] = last;
}
}
注意:因为生成$A[i]$的方法不好用语言描述,所以用代码来表达。直接照搬代码的话后果自负。
输出格式
输出一个整数表示答案。
样例
样例输入:
4 2
1 1 1 1
1 1 1 2
0 0 0 0
0 0 0 0
样例输出:
1
数据范围与提示
对于所有数据,$N\leqslant 50,000,000,M\leqslant 1,000,K\leqslant 30,X[i],Y[i]<2^k$。
$subtask\#1\ 10pts$:$N\leqslant 20$。
$subtask\#2\ 20pts$:$N\leqslant 1,000,000$。
$subtask\#3\ 20pts$:$K\leqslant 20$。
$subtask\#4\ 50pts$:无特殊限制。
题解
为方便,我们设每种书有$sum[i]$本。
首先,读不到的书的个数为$2\times \max(sum[i])-n-1$。
先来解释一下这个式子,最多的那种书显然有$\max(sum[i])$,那么剩下的书有$n-\max(sum[i])$种,我们进行插空,最多能插$n-\max(sum[i])+1$本,化简一下式子就好了。
那么问题就在于如何求出最多的那本书了。
注意空间只有$16MB$,我们显然不能都求出来,所以我们用两个变量$id,cnt$,$cnt$初始为$0$,然后生成每一个$A[i]$,如果$cnt=0$,那么就令$id=A[i],cnt=1$,否则如果$id=A[i]$则$cnt++$,如果不等于,$cnt--$。最后只要再扫一遍求出$id$的出现次数即可。
时间复杂度:$\Theta(n)$。
期望得分:$100$分。
实际得分:$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int zls,cnt,id;
int c[1001],x[1001],y[1001],z[1001];
long long last;
int main()
{
scanf("%d%d",&m,&k);
for(int i=1;i<=m;i++){scanf("%d",&c[i]);n+=c[i];}
for(int i=1;i<=m;i++)scanf("%d",&x[i]);
for(int i=1;i<=m;i++)scanf("%d",&y[i]);
for(int i=1;i<=m;i++)scanf("%d",&z[i]);
int S=(1<<k)-1;
for(int i=1;i<=m;i++)
{
last=x[i];
if(!cnt||id==last){cnt++;id=last;}
else cnt--;
for(int j=1;j<c[i];j++)
{
last=(last*y[i]+z[i])&S;
if(!cnt||id==last){cnt++;id=last;}
else cnt--;
}
}
cnt=0;
for(int i=1;i<=m;i++)
{
last=x[i];
if(last==id)cnt++;
for(int j=1;j<c[i];j++)
{
last=(last*y[i]+z[i])&S;
if(last==id)cnt++;
}
}
if(n&1)zls=n>>1+1;
else zls=n>>1;
if(cnt>zls)printf("%d",cnt*2-n-1);
else puts("0");
return 0;
}
rp++
最新文章
- C#开发微信门户及应用(10)--在管理系统中同步微信用户分组信息
- 微信小程序之ES6与事项助手
- 05:统计单词数【NOIP2011复赛普及组第二题】
- CentOS 7 php留言本网站的搭建
- 适合最新版docker自定义启动配置
- HTML中的一些常见的事件句柄
- Node.js Crypto 加密算法库
- php设计模式-------(1)策略模式
- Axure初体验:简单交互、通过按钮切换图片
- smarty练习:考试系统
- 29 内置方法 eval | exec 元类 单例
- jQuery获取相同元素下标
- 雷林鹏分享:jQuery EasyUI 数据网格 - 创建自定义视图
- JavaScript笔记基础版
- LoadRuner12.53教程(二)
- Android 虹软免费人脸识别App
- 第10章 网络安全(4)_网络层安全IPSec
- Space Ant(极角排序)
- DevOps Workshop 研发运维一体化(成都站) 2016.05.08
- Binary Indexed Tree-307. Range Sum Query - Mutable
热门文章
- 1、Laravel 环境配置及安装
- python的运算符和while循环
- Cookie/Session/Local Storage/IndexedDB
- Netty核心组件介绍及手写简易版Tomcat
- XML学习——java解析xml文件
- [CF960G]Bandit Blues(第一类斯特林数+分治卷积)
- 运输计划(题解)(Noip2015)
- linux php 中session 多站点共享session问题
- HDU 6315 Naive Operations 【势能线段树】
- 标签的增加、删除与复制,动态标签js不生效的解决