1．计数
(count.cpp/c/pas)
时间限制：1s
内存限制：256MB
【问题描述】
给出m个数a[1],a[2],…,a[m]
求1~n中有多少数不是a[1],a[2],…,a[m]的倍数。
【输入】
输入文件名为count.in。
第一行，包含两个整数：n,m
第二行，包含m个数，表示a[1],a[2],…,a[m]
【输出】
输出文件名为count.out。
输出一行，包含1个整数，表示答案
【输入输出样例】
|
count.in |
count.out |
|
10 2 2 3 |
3 |
【数据说明】
对于60%的数据，1<=n<=106
对于另外20%的数据，m=2
对于100%的数据，1<=n<=109,0<=m<=20,1<=a[i]<=109
题解：
#include<iostream>
#include<cstdio>
using namespace std; int cnt,n,m,x,vis[]; int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d",&x);
for(int j=;j*x<=n;j++){
if(!vis[j*x]){
vis[j*x]=true;
cnt++;
}
}
}
printf("%d\n",n-cnt);
return ;
}
60暴力
考试时用的map判重全T =…=
正解：容斥原理...考试时想到了..可是当时不会容斥..
一个区间内某个数倍数的个数=r/x-(l-1)/x，可是1--n中12既是3的倍数，又是4.6.的倍数
会被筛掉好几次，所以答案=n/一个数-n/两个数的lcm+n/三个数的lcm.....
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std; int n,m,ans,a[]; inline int read(){
char ch=getchar();int x=,f=;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';
return x*f;
} LL gcd(LL x,LL y){
return y==?x:gcd(y,x%y);
} void dfs(int now,int cnt,LL lcm){
if(lcm>n)return;//加上剪枝108ms，不加600ms
if(now==m+){
if(cnt&)ans+=n/lcm;
else if(cnt)ans-=n/lcm;
return;
}
dfs(now+,cnt,lcm);
LL p=lcm/gcd(lcm,a[now])*a[now];
dfs(now+,cnt+,p);
} int main(){
n=read();m=read();
for(int i=;i<=m;i++)a[i]=read();
dfs(,,);
printf("%d\n",n-ans);
return ;
}
AC
2．第k大区间
(kth.cpp/c/pas)
时间限制：1s
内存限制：256MB
【问题描述】
定义一个长度为奇数的区间的值为其所包含的的元素的中位数。
现给出n个数，求将所有长度为奇数的区间的值排序后，第K大的值为多少。
【输入】
输入文件名为kth.in。
第一行两个数n和k
第二行，n个数。（0<=每个数<231）
【输出】
输出文件名为kth.out。
一个数表示答案。
【输入输出样例】
|
kth.in |
kth.out |
|
4 3 3 1 2 4 |
2 |
【样例解释】
[l,r]表示区间l~r的值
[1,1]：3
[2,2]：1
[3,3]：2
[4,4]：4
[1,3]：2
[2,4]：2
【数据说明】
对于30%的数据，1<=n<=100；
对于60%的数据，1<=n<=300
对于80%的数据，1<=n<=1000
对于100%的数据，1<=n<=100000, k<=奇数区间的数
题目大意：定义一段奇数长度区间的值为它的中位数，求所有奇数区间值的第k大。
题解：二分答案
假设现在二分的答案为t，那么怎样统计比t大的区间的个数呢？设s[i]为1--i大于等于t的数的个数，
发现，如果一个区间的中位数的大小比t大，那么s[r]-s[l-1]>(r-l+1)/2,==> 2*s[r]-r>2*s[l-1]-(l-1)，
我们用树状数组统计一下s[r]>s[l]的个数，因为r,l的奇偶性不同，要维护两个树状数组。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define maxn 100009
using namespace std; int n,l,r,mid,ans,a[maxn],b[maxn],tree[maxn*][];
LL k; void add(int pos,int p){
if(pos<=)return;
for(;pos<=maxn*;pos+=pos&(-pos))tree[pos][p]++;
} LL getsum(int pos,int p){
LL all=;if(pos<=)return ;
for(;pos;pos-=pos&(-pos))all+=tree[pos][p];
return all;
} bool check(int p){
LL s=;
memset(tree,,sizeof(tree));
for(int i=;i<=n;i++)b[i]=a[i]>=p?:,b[i]+=b[i-];
for(int i=;i<=n;i++)b[i]=*b[i]-i+n;
add(n,);//???
for(int i=;i<=n;i++){
s+=getsum(b[i],(i&)^);
add(b[i],(i&));
}
return s>=k;
} int main(){
scanf("%d%lld",&n,&k);
for(int i=;i<=n;i++)scanf("%d",&a[i]),r=max(r,a[i]);
while(l<=r){
mid=(l+r)>>;
if(check(mid))ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
return ;
}
AC
3. 区间求和
（sum.cpp/c/pas）
时间限制：2s
内存限制：256MB
【问题描述】
有n个数，给定一个k，求所有长度大于等于k的区间中前k大数的总和。这样就比较简单相信大家都会，所以此题要求当k=1~n的总和，即求
【输入】
输入文件名为sum.in。
输入五个数n,a1,A,B,C。a1表示第一个数，A,B,C用来生成其余n-1个数。a(i)=(a(i-1)*A+B)mod C。1<=n<=1,000,000,0<=a1,A,B,C<=1,000,000,000
【输出】
输出文件名为sum.out。
一个数表示答案，最后答案对1,000,000,007取模。
【输入输出样例】
|
sum.in |
sum.out |
|
3 3 1 1 10 |
63 |
【样例解释】
三个数为3,4,5
K=1:[1,1]=3,[1,2]=[2,2]=4,[1,3]=[2,3]=[3,3]=5
(表示各个区间在k=1时的答案)
K=2:[1,2]=7,[2,3]=[1,3]=9
K=3:[1,3]=12
【数据说明】
对于30%的数据，1<=n<=100
对于60%的数据，1<=n<=300
对于80%的数据，1<=n<=1000
对于100%的数据，1<=n<=1000000
题解：树状数组...不会做...
首先我们讨论对于一个固定的区间[l,r]假设它的答案为ans，那么如果新增加一个数a[r+1]，
对于新的区间[l,r+1]，a[r+1]出现的次数为小于a[r+1]的数的次数+1。
所以我们要统计对于Ai<Aj &&i<j的个数，那么包含这两个数的区间为的个数为(n-j+1)*i,
Aj对答案的贡献为Aj*i*(n-j+1)。当Ai>Aj时同理，倒过来处理。
另外之前一直WA的原因是，离散化的时候应该双关键字查找，因为Ai<Aj时i<j。
还有模少了爆Int...
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define mod 1000000007
#define maxn 1000009
#define LL long long
using namespace std; LL n,ans,A,B,C,a[maxn],tree[maxn];
typedef pair<LL,int> PII;
PII b[maxn]; void add(int x,int p){
for(;x<=n;x+=x&(-x))tree[x]=(tree[x]+p)%mod;
} LL getsum(int x){
LL all=;
for(;x;x-=x&(-x))all=(all+tree[x])%mod;
return all;
} int main(){
scanf("%lld%lld%lld%lld%lld",&n,&a[],&A,&B,&C);
b[].first=a[];b[].second=;
for(int i=;i<=n;i++){
a[i]=(a[i-]*A+B)%C;
b[i].first=a[i];b[i].second=i;
}
sort(b+,b+n+);
for(int i=;i<=n;i++)
a[i]=lower_bound(b+,b+n+,make_pair(a[i],i))-b;
for(int i=;i<=n;i++){
add(a[i],i);
LL tmp=b[a[i]].first*1LL*(n-i+)%mod;
LL amp=getsum(a[i]);
ans=(ans%mod+tmp*amp%mod)%mod;
}
memset(tree,,sizeof(tree));
for(int i=n;i>=;i--){
LL tmp=(b[a[i]].first*1LL*i)%mod;
LL amp=getsum(a[i]);
ans=(ans%mod+tmp*amp%mod)%mod;
add(a[i],n-i+);
}
printf("%lld\n",ans);
return ;
}
AC