牛客OI周赛7-提高组OI(A BB 题线段树orRMQ)
第一次打OI赛制的比赛。
首先看A题，签到题，暴力即可，牛客OI发现一个特色，同份代码可能是80分，有时是100分，我交了第一发是80分，赛后同份代码100分
链接：https://ac.nowcoder.com/acm/contest/371/A
来源：牛客网
题目描述
小睿睿在游戏开始时有n根火柴棒，他想知道能摆成形如“A+B=n”的等式且使用的火柴棒数也恰好等于n/k的等式有多少种(B+A=n与A+B=n看作一种)
注：
“=”与“+”分别需要使用2根火柴棒
输入描述:
一行2个整数n,k，保证n取模k为0输出描述:
一行一个整数，表示答案示例1
输入
60 2输出
4说明
11+49=60
13+47=60
17+43=60
19+41=60示例2
输入
100000 1250输出
3092备注:
对于30%的数据，0<=n<=100
对于50%的数据，0<=n<=1000000
对于100%的数据，0<=n<=50000000;A,B>=0直接贴代码了，不解释了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[10]={6,2,5,5,4,5,6,3,7,6},n,k,num,ans,s1;
int cal(int num)
{
int sum=0;
if(num==0)
{
sum+=a[0];
return sum;
}
while(num>0)
{
int d=num%10;
sum+=a[d];
num/=10;
}
return sum;
}
int main()
{
cin>>n>>k;
num=n/k-4;
ans=0;
s1=cal(n);
num-=s1;
for(int i=0;i<=n/2;++i)
{
int j=n-i;
int s1=cal(i);
int s2=cal(j);
if(s1+s2==num)
{
ans++;
}
}
printf("%d\n",ans);
return 0;
}B题：
链接：https://ac.nowcoder.com/acm/contest/371/B
来源：牛客网
题目描述
小睿睿的n个妹纸排成一排，每个妹纸有一个颜值val[i]。有m个询问，对于每一个询问，小睿睿想知道区间[L,R]颜值最高而编号最小的妹纸是哪一个
对于妹纸们的颜值val[i]，其生成函数为：
void generate_array(int n,int seed)
{
unsigned x = seed;
for (int i=1;i<=n;++i)
{
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
val[i]=x%100;
}
}对于每一组询问，区间[L,R]的生成函数为：
void generate_ask(int n,int m,int seedx,int seedy)
{
unsigned x=seedx,y=seedy;
for (int i=1;i<=m;++i)
{
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
y ^= y << 13;
y ^= y >> 17;
y ^= y << 5;
L=(x^lastans)%n+1,R=(y^lastans)%n+1;
if (L>R)swap(L,R);
//解决询问
}
}
其中lastans为上个询问的答案，对于第一个询问，lastans为0
输入描述:
第1行2个整数n,m，分别表示序列长度和询问次数
第2行3个整数seed,seedx,seedy，意义如题所示输出描述:
一行一个整数，表示所有询问的答案的异或和示例1
输入
10 5
3 5 7输出
2说明
生成序列：
7 11 47 53 3 7 63 36 55 55
各组询问及答案：
询问：4 6
该询问答案：4
询问：2 6
该询问答案：4
询问：2 2
该询问答案：2
询问：4 8
该询问答案：7
询问：1 9
该询问答案：7
所有询问的答案的异或和：2示例2
输入
100000 10000000
1 2 3输出
5042备注:
对于30%的数据，n,m<=1000
对于50%的数据，m<=1000000
对于100%的数据，n<=100000,m<=10000000,seedx,seedy,seed<=1000这题刚开始是想线段树做，处理nlogn（n最大1e5），查询mlogn（10000000*log（1e5）/log(2））顶多就是2e8不会超时。
不知道哪里分析错了，交上去居然超时了，还是乖乖用RMQ吧。
先贴线段树：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll val[N],L,R,lastans,ans;
struct node
{
ll v;
int idx;
}a[N*4];
void build(int id,int l,int r)
{
if(l==r)
{
a[id].v=val[l];
a[id].idx=l;
return ;
}
int mid=l+r >>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
if(a[id<<1].v<a[id<<1|1].v) a[id]=a[id<<1|1];
else a[id]=a[id<<1];
}
node qu(int id,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)
{
return a[id];
}
node ans;
ans.v=-1;
ans.idx=10000+10;
int mid=(l+r)>>1;
if(ql<=mid)
{
node t=qu(id<<1,l,mid,ql,qr);
if(ans.v<t.v) ans=t;
}
if(qr>mid)
{
node t=qu(id<<1|1,mid+1,r,ql,qr);
if(ans.v<t.v) ans=t;
}
return ans;
}
void generate_array(int n,int seed)
{
unsigned x = seed;
for (int i=1;i<=n;++i)
{
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
val[i]=x%100;
}
}
void generate_ask(int n,int m,int seedx,int seedy)
{
unsigned x=seedx,y=seedy;
for (int i=1;i<=m;++i)
{
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
y ^= y << 13;
y ^= y >> 17;
y ^= y << 5;
L=(x^lastans)%n+1,R=(y^lastans)%n+1;
if (L>R)swap(L,R);
node t=qu(1,1,n,L,R);
ans^=t.idx;
lastans=t.idx;
// printf("%d\n",t.idx);
}
}
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
} while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
int main()
{
int n,m,seed,seedx,seedy;
n=read();
m=read();
seed=read();
seedx=read();
seedy=read();
generate_array(n,seed);
build(1,1,n);
ans=0;
lastans=0;
generate_ask(n,m,seedx,seedy);
printf("%lld\n",ans);
}再贴RMQ。之所以开始不用RMQ呢，是因为我的RMQ需要板子才能打出来，觉得麻烦。之前分析不会超时，又想要快，就敲了线段树，没想到，唉
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll val[N],L,R,lastans,ans;
struct node
{
ll v;
int idx;
}a[N*2][32];
node max_(node a,node b)
{
if(a.v<b.v) return b;
else if(a.v==b.v)
{
if(a.idx<b.idx) return a;
else return b;
}
else return a;
}
void build(int n)
{
for(int i=1;i<=n;i++) a[i][0].v=val[i],a[i][0].idx=i;
for(int i=1;(1<<i)<=n;i++)
{
for(int j=1;j-(1<<i)-1<=n;j++)
{
a[j][i]=max_(a[j][i-1],a[j+(1<<(i-1))][i-1]);
}
}
}
node qu(int l,int r)
{
int k=log(1.0*(r-l+1))/log(2.0);
return max_(a[l][k],a[r-(1<<k)+1][k]);
}
void generate_array(int n,int seed)
{
unsigned x = seed;
for (int i=1;i<=n;++i)
{
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
val[i]=x%100;
}
}
void generate_ask(int n,int m,int seedx,int seedy)
{
unsigned x=seedx,y=seedy;
for (int i=1;i<=m;++i)
{
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
y ^= y << 13;
y ^= y >> 17;
y ^= y << 5;
L=(x^lastans)%n+1,R=(y^lastans)%n+1;
if (L>R)swap(L,R);
node t=qu(L,R);
ans^=t.idx;
lastans=t.idx;
// printf("l:%d r:%d\n",L,R);
// printf("idx:%d v:%d\n",t.idx,t.v);
}
}
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
} while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
int main()
{
int n,m,seed,seedx,seedy;
n=read();
m=read();
seed=read();
seedx=read();
seedy=read();
generate_array(n,seed);
// for(int i=1;i<=n;i++) printf("%d ",val[i]);
// puts("");
build(n);
ans=0;
lastans=0;
generate_ask(n,m,seedx,seedy);
printf("%lld\n",ans);
}