蒟蒻的省选模拟自闭祭
上周省里发了一套模拟题
本来弱省历届省选都是什么高精度、dp原题、模拟之类的balabala的水题
今年这个模拟题突然就做自闭了。。。。
D1T1 余弦
题目描述
给定长度为的实数序列 , 你需要在数列上进行两类操作：
- 把中的每个加上实数。
- 求中的和 。
说明
对于 100%的数据，1 ≤ N M ≤ 200000
T1还是比较水的，推推式子线段树维护
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long lt;
typedef double dd;
int read()
{
int f=1,x=0;
char ss=getchar();
while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
return f*x;
}
const int maxn=400010;
int T,n,m;
dd a[maxn];
dd Scos[maxn<<2],Ssin[maxn<<2],add[maxn<<2];
void pushup(int p)
{
int lc=p<<1,rc=p<<1|1;
Scos[p]=Scos[lc]+Scos[rc];
Ssin[p]=Ssin[lc]+Ssin[rc];
}
void build(int s,int t,int p)
{
add[p]=0.0;
if(s==t){
Scos[p]=cos(a[s]);
Ssin[p]=sin(a[s]);
return;
}
int mid=s+t>>1;
build(s,mid,p<<1);build(mid+1,t,p<<1|1);
pushup(p);
}
void pushd(int s,int t,int mid,int p)
{
if(add[p]==0) return;
int lc=p<<1,rc=p<<1|1;
add[lc]+=add[p]; add[rc]+=add[p];
dd tc=Scos[lc],ts=Ssin[lc];
Scos[lc]+=(cos(add[p])-1.0)*tc-sin(add[p])*ts;
Ssin[lc]+=(cos(add[p])-1.0)*ts+sin(add[p])*tc;
tc=Scos[rc],ts=Ssin[rc];
Scos[rc]+=(cos(add[p])-1.0)*tc-sin(add[p])*ts;
Ssin[rc]+=(cos(add[p])-1.0)*ts+sin(add[p])*tc;
add[p]=0;
}
void update(int ll,int rr,int s,int t,int p,dd val)
{
if(ll<=s&&t<=rr){
dd tc=Scos[p],ts=Ssin[p];
Scos[p]+=(cos(val)-1.0)*tc-sin(val)*ts;
Ssin[p]+=(cos(val)-1.0)*ts+sin(val)*tc;
add[p]+=val;
return;
}
int mid=s+t>>1;
pushd(s,t,mid,p);
if(ll<=mid) update(ll,rr,s,mid,p<<1,val);
if(rr>mid) update(ll,rr,mid+1,t,p<<1|1,val);
pushup(p);
}
dd qsum(int ll,int rr,int s,int t,int p)
{
if(ll<=s&&t<=rr) return Scos[p];
int mid=s+t>>1; dd res=0;
pushd(s,t,mid,p);
if(ll<=mid) res+=qsum(ll,rr,s,mid,p<<1);
if(rr>mid) res+=qsum(ll,rr,mid+1,t,p<<1|1);
return res;
}
int main()
{
T=read();
for(int cs=1;cs<=T;++cs)
{
n=read();m=read();
for(int i=1;i<=n;++i)
scanf("%lf",&a[i]);
build(1,n,1);
printf("Case #%d:\n",cs);
while(m--)
{
int opt=read(),ll=read(),rr=read();
if(opt==1)
{
dd x; scanf("%lf",&x);
update(ll,rr,1,n,1,x);
}
else if(opt==2)
printf("%.3lf\n",qsum(ll,rr,1,n,1));
}
}
return 0;
}
D1T2 续一秒
题目描述
蛤先生是一位著名的科学家，不久前他得到了一种名叫“熵破坏者”的药剂。
这种药保存在个瓶子中，其中第个瓶子盛有升药剂。为了让“熵破坏者”发挥魔力，他必须把所有保存在瓶子中的药剂混合在一起。由于混合药剂是一件危险的工作，蛤先生取出了他珍藏已久的大容器，并打算把药剂以整瓶为单位，全部倒进大容器中。
大容器的容量可以看作无穷大。若大容器中已有升药剂，则再倒入升药剂后，大容器中剩余药剂的体积是（神奇的混合方法！）。最初，大容器是空的，蛤先生可以以任意一种顺序把每瓶药剂倒入大容器。
最终，若大容器中还剩余升药剂，则蛤先生就可以使用一次魔法，把自己的生命周期续秒。请帮蛤先生求出可能混合成的最大的，即蛤先生这次最多可以续几秒。
输入格式
输入包含多组数据，在数据开头有一个整数 T(T≤5)，表示组数。对于每组数据：第一行一个整数 N，第二行 N 个整数Vi。
说明
对于 20%的数据，，
对于 60%的数据，，
对于 100%的数据，,
啥啥啥这都啥???背包???贪心???
算了不会。。。写个模拟退火好了
最后提交的时候只有80pts，还算比较欧了吧
//模拟退火
#include<iostream>
#include<cstdio>
#include<cmath>
#include<set>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long lt;
typedef double dd;
#define T 100
#define eps 1e-8
#define delta 0.997
int read()
{
int f=1,x=0;
char ss=getchar();
while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
return f*x;
}
const int maxn=1010;
int Q,n,m;
int a[maxn],ans;
int calc()
{
int p=0;
for(int i=1;i<=n;++i)
p=abs(p-a[i]);
return p;
}
void SA()
{
dd t=T;
while(t>eps)
{
int x=0,y=0;
while(x==y) x=rand()%n+1,y=rand()%n+1;
swap(a[x],a[y]);
int tt=calc(),dE=tt-ans;
if(dE>=0) ans=tt;
else if( exp(dE/t) > (dd)rand()/(dd)RAND_MAX );
else swap(a[x],a[y]);
t*=delta;
}
}
int main()
{
Q=read(); srand(19260817);
for(int cs=1;cs<=Q;++cs)
{
n=read();
for(int i=1;i<=n;++i) a[i]=read();
if(n==1){ printf("Case #%d: %d\n",cs,abs(a[1])); continue;}
ans=calc();
for(int i=1;i<=3;++i) SA();
printf("Case #%d: %d\n",cs,ans);
}
return 0;
}
std给的好像确实是贪心，负数都最后加没问题，但正数的贪心真的没看懂，我好菜=_=
//std
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[210], f[100010], T, N, n, m, ans, sum;
int main()
{
freopen("second.in","r",stdin);
freopen("second.out","w",stdout);
cin >> T;
for (int t = 1; t <= T; t++)
{
cin >> n; N += n;
ans = m = sum = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if(a[i] > 0) sum += a[i];
}
for (int j = 0; j <= sum; j++) f[j] = 0;
f[0] = 1;
sort(a + 1, a + n + 1);
for (int i = 1; i < n; i++)
{
if (a[i] <= 0)
{
ans -= a[i];
continue;
}
for (int j = m; j >= 0; j--)
f[j + a[i]] |= f[j];
m += a[i];
}
int delta = m + 1;
for (int j = 0; j <= m; j++)
if (f[j] && abs(j - (m - j)) < delta)
delta = abs(j - (m - j));
if (a[n] > 0) ans += a[n] - delta; else ans -= a[n];
printf("Case #%d: %d\n", t, ans);
}
//cout << N << endl;
}
D1T3 松鼠与坚果
题目描述
小取酒是小 Cat Rainbow 的好朋友，它们一起到森林里玩。这片森林里住着一群松鼠。小取酒很喜欢松鼠，所以它对其中三只松鼠的活动习性进行了详细的跟踪观察。
在这三只松鼠中，第一只喜欢吃榛子，第二只喜欢吃松果，第三只喜欢吃栗子。有一天，它们收集了 N 个篮子的食物，其中每个篮子里恰好装了 1 个榛子、1 个松果和 1 个栗子，但是不同的篮子里的食物有不同的美味度。
现在它们邀请小取酒把这 N 个篮子分成三堆，第 1 只松鼠会吃掉第 1 堆每个篮子里的榛子，它获得的美味度就是第 1 堆篮子里美味度最大的榛子的美味度。同样地，第 2 只松鼠会吃掉第 2 堆篮子里的松果，获得第 2 堆篮子里美味度最大的松果的美味度。第 3 只松鼠会吃掉第 3 堆篮子里的栗子，获得第 3 堆篮子里美味度最大的栗子的美味度。
可是，小取酒还没有吃东西！于是它打算采取适当的方式把篮子分成三堆，使得三只松鼠获得的美味度之和最小。当然，它也有可能不分给某些松鼠食物，也就是说空堆是允许的，它甚至可以把这 N 个篮子全部分给某一只松鼠。没有获得篮子的松鼠获得的美味度是 0。
输入格式
第一行一个数 N，表示 N 个篮子。
接下来 N 行，每行三个数 ai, bi, ci 表示一个篮子里榛子、松果和栗子的美味度。
说明
对于 20%的数据，1 ≤ n ≤ 1000。
对于另外 30%的数据，1 ≤ ai ≤ 10。
对于 100%的数据，1 ≤ n ≤ 100000, 1 ≤ ai, bi, ci ≤ 100000000。
自闭了。。又不会
写到这题的时候已经花了两个小时，省选总时长4h，模拟我给自己限定3h
想了20分钟没有思路，部分分也不会拿，于是心力憔悴的我开始写暴搜。。最后10pts。。。
std又没有看懂，应该也是贪心吧，变量名全是a,b,c,d毒瘤的hin
//std
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
using namespace std;
set<int> b;
map<int,int> c;
struct rec{int x,y,z;}a[100010];
int n,m,p,d[100010];
set<pair<int,int> > f;
priority_queue<pair<int,int> > q;
bool operator <(rec a,rec b)
{
return a.x>b.x;
}
int main()
{
freopen("squirrel.in","r",stdin);
freopen("squirrel.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
b.insert(a[i].y);
}
sort(a+1,a+n+1);
for(set<int>::iterator it=b.begin();it!=b.end();it++)
c[*it]=++p,d[p]=*it;
int ans=a[1].x;
f.insert(make_pair(p+1,0));
f.insert(make_pair(0,1<<30));
q.push(make_pair(0,0));
for(int i=1;i<=n+1;i++)
{
int j=c[a[i].y];
set<pair<int,int> >::iterator it,it2;
while(q.size())
{
it=f.lower_bound(make_pair(q.top().second+1,0));
if(-q.top().first==d[q.top().second]+it->second) break;
q.pop();
}
ans=min(ans,a[i].x-q.top().first);
if(i==n+1) break;
it=f.lower_bound(make_pair(j,a[i].z));
if(a[i].z<=it->second) continue;
q.push(make_pair(-a[i].y-it->second,j));
it--;
while(it->second<=a[i].z)
{
it2=it--;
f.erase(it2);
}
f.insert(make_pair(j,a[i].z));
q.push(make_pair(-d[it->first]-a[i].z,it->first));
}
cout<<ans<<endl;
}
最后D1模拟愉快地只有190pts。。。
大概加回那一个小时最后一题还能再多骗点分吧
D2T1传销组织
题目描述
传销组织 GPLT 的宗旨是“有志者事竟成”，他们最近在执行一项宏伟的 N 人计划，以构建科学有效的情报网。换句话说，GPLT 组织希望组建一个由 N 个人和若干单向私有电话线构成的情报网，并使得情报网满足一系列要求。这些要求分成两类：
① 从第 a 个人通过 1 条或多条电话线可以联系到第 b 个人。
② 从第 a 个人通过 1 条或多条电话线不能联系到第 b 个人。
现在 GPLT 组织的首脑 gluo 请你帮忙给出一个满足所有要求的情报网，或者告诉他这样的情报网是不可能存在的。
输入格式
第一行 1 个整数 N，表示情报网的人数。
第二行 1 个整数 M，表示①类要求的个数，接下来 M 行每行 2 个整数 a, b
第 M+3 行 1 个整数 T，表示②类要求的个数，接下来 T 行每行 2 个整数 a, b
输出格式
若不存在这样的情报网，输出 NO。否则在第一行输出 YES，在第二行输出情报网中话线的数量 P，接下来 P 行每行 2 个整数描述电话线。由于资源有限，要求 P<=N+M+T。
说明
对于 20%的数据，1 ≤ N ≤ 100。
对于 60%的数据，1 ≤ N ≤ 25000。
对于 100%的数据，1 ≤ N, M, T ≤ 100000，1 ≤ a, b ≤ N，a≠b，要求输出的 P<=N+M+T。
怎么第一题就自闭了。。。。又是部分分都没拿
D2写完看了std前半思路和我一样，后面的维护方法是什么鬼???压位+分块???
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <bitset>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int N=100002;
int ver[N],Next[N],head[N],c[N],dfn[N],low[N],s[N],ins[N],du[N],a[N],b[N],deg[N];
int n,m,t,qu,tot,num,p;
vector<int> go[N];
bitset<8192> d[N];
template<typename T> inline void R(T &x) {
char ch = getchar(); x = 0;
for (; ch < '0'; ch = getchar());
for (; ch >= '0'; ch = getchar()) x = x * 10 + ch - '0';
}
void add(int x,int y)
{
ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x)
{
dfn[x]=low[x]=++num;
s[++p]=x,ins[x]=1;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])
low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x])
{
t++; int y;
do{y=s[p--]; ins[y]=0; c[y]=t;}while(x!=y);
}
}
bool topsort(int l,int r)
{
//cout<<l<<' '<<r<<endl;
queue<int> q;
for(int i=1;i<=t;i++)
{
deg[i]=du[i];
d[i].reset();
}
for(int i=1;i<=t;i++)
if(!deg[i]) q.push(i);
while(q.size())
{
int x=q.front(); q.pop();
if(x>=l&&x<=r) d[x][x-l]=1;
for(int i=0;i<go[x].size();i++)
{
int y=go[x][i];
d[y]|=d[x];
if(--deg[y]==0) q.push(y);
}
}
for(int i=1;i<=qu;i++)
if(b[i]>=l&&b[i]<=r&&d[a[i]][b[i]-l]==1)
return 0;
return 1;
}
int main() {
freopen("gplt.in","r",stdin);
freopen("gplt.out","w",stdout);
while(cin>>n>>m)
{
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(c,0,sizeof(c));
memset(du,0,sizeof(du));
tot=num=p=t=0;
for(int i=1;i<=n;i++) go[i].clear();
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int x=1;x<=n;x++)
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(c[x]==c[y]) continue;
go[c[y]].push_back(c[x]);
du[c[x]]++;
}
cin>>qu;
for(int i=1;i<=qu;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[i]=c[x],b[i]=c[y];
}
bool flag=0;
for(int l=1;l<=t;l+=8192)//这啥???压位??分块??
{
int r=min(t,l+8191);
if(!topsort(l,r)) {flag=1; break;}
}
if(flag) {puts("NO"); continue;}
puts("YES");
cout<<m<<endl;
for(int x=1;x<=n;x++)
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
printf("%d %d\n",x,y);
}
}
return 0;
}
D2T2 Zhizhang Snake
题目描述
Zhizhang Snake 是一个新型物种，它的身体是由 N 个点和 N-1 条线段构成的折线，其中第 i 个点的坐标为(xi, yi)，折线不会自交。Zhizhang Snake 可以平移或旋转自己的身体，但是在移动过程中，身体形状不能发生任何改变（即构成它身体的每条线段的长度和它们之间的夹角都保持不变），否则它就会挂掉……
直线 y=0 是一堵墙，坐标(0,0)处开有一个洞，洞与蛇身的宽度都是一个可以忽略不计的小量。现在 Zhizhang Snake 完全处于墙的上方(y>0)，它想知道它自己的整个身体能否活着穿过墙洞，到达墙的下方(y<0)。
输入格式
每个测试点包含 5 组数据，以 EOF 结尾，对于每组数据：
第一行有 1 个整数 N，表示 Zhizhang Snake 折线顶点的个数。
接下来 N 行每行 2 个整数(xi, yi)，描述这条折线。折线不会自交，折线上任意三个顶点都不共线。
输出格式
对于每组数据，输出 Possible 或 Impossible，表示 Zhizhang Snake 能否到达墙的下方。
说明
对于 20%的数据，1 ≤ N ≤ 10
对于 60%的数据，1 ≤ N ≤ 1000。
对于 100%的数据，1 ≤ N ≤ 100000, 0 ≤ xi ≤10^9，1 ≤ yi ≤10^9, 折线不会自交，折线上任意三个顶点都不共线。
看到这题内心十分复杂。。。心态崩了。。计算几何只会求裸凸包。。。直接跳了
std又没看懂系列
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
using namespace std;
struct poi { long double x, y; };
poi a[100010];
set<pair<long double, int> > f;
int n;
long double eps = 1e-10;
long double mul(poi a, poi b, poi c)
{
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
void insert(poi ct, int i)
{
set<pair<long double, int> >::iterator it, l, r;
long double z = atan2(a[i].y - ct.y, a[i].x - ct.x);
l = r = f.lower_bound(make_pair(z, i));
if (r == f.end()) r = f.begin();
if (l == f.begin()) l = --f.end(); else l--;
if (mul(a[i], a[l->second], a[r->second]) < -eps)
{
if (l == f.begin()) it = --f.end(); else it = l, it--;
while (f.size() > 2 && mul(a[i], a[l->second], a[it->second]) > -eps)
{
f.erase(l);
l = it;
if (l == f.begin()) it = --f.end(); else it = l, it--;
}
if (r == --f.end()) it = f.begin(); else it = r, it++;
while (f.size() > 2 && mul(a[i], a[r->second], a[it->second]) < eps)
{
f.erase(r);
r = it;
if (r == --f.end()) it = f.begin(); else it = r, it++;
}
f.insert(make_pair(z, i));
}
}
long double dist(poi a, poi b)
{
return sqrt((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y));
}
bool in(poi ct, poi p)
{
long double th = atan2(p.y - ct.y, p.x - ct.x);
set<pair<long double, int> >::iterator it, l, r;
l = r = f.lower_bound(make_pair(th, n + 1));
if (r == f.end()) r = f.begin();
if (l == f.begin()) l = --f.end(); else l--;
if (fabs(th - l->first) < eps)
return dist(ct, p) + eps < dist(ct, a[l->second]);
if (fabs(th - r->first) < eps)
return dist(ct, p) + eps < dist(ct, a[r->second]);
return mul(a[l->second], p, a[r->second]) < -eps;
}
bool check1()
{
poi ct;
ct.x = ct.y = 0;
for (int i = 1; i <= 3; i++)
ct.x += a[i].x, ct.y += a[i].y;
ct.x /= 3, ct.y /= 3;
f.clear();
for (int i = 1; i <= 3; i++)
f.insert(make_pair(atan2(a[i].y - ct.y, a[i].x - ct.x), i));
for (int i = 4; i <= n; i++)
{
insert(ct, i);
if (in(ct, a[i])) return 0;
}
return 1;
}
bool check2()
{
poi ct;
ct.x = ct.y = 0;
for (int i = n; i > n - 3; i--)
ct.x += a[i].x, ct.y += a[i].y;
ct.x /= 3, ct.y /= 3;
f.clear();
for (int i = n; i > n - 3; i--)
f.insert(make_pair(atan2(a[i].y - ct.y, a[i].x - ct.x), i));
for (int i = n - 3; i; i--)
{
insert(ct, i);
if (in(ct, a[i])) return 0;
}
return 1;
}
int main() {
freopen("snake.in","r",stdin);
freopen("snake.out","w",stdout);
while (cin >> n)
{
for (int i = 1; i <= n; i++)
{
double x, y;
scanf("%lf%lf", &x, &y);
a[i].x = x, a[i].y = y;
}
if (n < 4)
{
puts("Possible");
continue;
}
if (!check1() || !check2())
{
puts("Impossible");
continue;
}
puts("Possible");
}
return 0;
}
D2T3 分子配对
题目描述
一次偶然的机会，Haibara 得到了一粒 APTX4869 毒药。为了研究其成分以制作解药，Haibara 在显微镜下对 APTX4869 进行了详细的观察。APTX4869 的分子结构是一条链，链上的每个部位宽窄不一，形成了锯齿的形状。
Haibara 在这条分子链上选择了 N 个具有代表性的节点，并用一个整数表示每个节点处的宽度。
APTX4869 进入活生物体后，分子链将会在体内环境下带动机能细胞一起折叠、扭曲，引起生物体各系统的紊乱而致死。但在特殊的情况下，APTX4869 的分子链重叠时，部分锯齿刚好整齐地“咬合”在一起，避免了紊乱的发生，却造成了生物体细胞全面变小或恢复为以前某时刻的状态。
我们说 APTX4869 分子链的 n 个代表节点中，第 la~ra 个节点与 lb~rb个节点是“咬合”的，当且仅当节点区间[la,ra]，[lb,rb]满足下列条件：
- [la,ra]与[lb,rb]不重叠，即 la ≤ ra < lb ≤ rb 或 lb ≤ rb < la ≤ ra；
- [la,ra]与[lb,rb]的长度相等，即 ra-la = rb-lb；
- 对应节点的高度和相等，即对于任意的 0 ≤ i ≤ ra - la，有 w[la+i]+w[lb+i]=w[la]+w[lb]，其中 w[x]表示第 x (1 ≤x ≤n) 个节点处的宽度。
现在 Haibara 给出 m 段区间，请你帮她统计一下对于每段区间，有多少段区间与它是“咬合”的。
输入格式
第一行一个整数 n。
第二行包含 n 个整数，第 i 个数表示 w[i]，即第 i 个节点处的宽度。
第三行一个整数 m。接下来 m 行，每行有两个整数 l,r，表示询问有多少段区间与[l,r]是“咬合”的。
说明
对于 20%的数据，1<=n,m<=100。
对于另 30%的数据，询问区间的长度不超过 10。
对于 100%的数据，1<=n,m<=100000，1<=w[i]<=10^9，1<=l<=r<=n。
本来到这里已经打算自暴自弃不测了然而突然发现T3反而比较简单???十分钟左右有了思路
只要两端区间差分序列正好是对应的相反数就是"咬合的"
差分序列取反接在原差分序列后面求后缀数组，st表维护height，主席树查找区间个数
思路想的挺快但码了好久。。。差不多一小时50分钟吧才调好。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long lt;
int read()
{
int f=1,x=0;
char ss=getchar();
while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
return f*x;
}
const int inf=2e9;
const int maxn=1000010;
int n,m,Q;
int val[maxn],a[maxn];
int b[maxn],pos[maxn],cnt;
int rak[maxn],tp[maxn];
int sa[maxn],tax[maxn],height[maxn];
int mi[maxn][30];
int rt[maxn],size[maxn<<5],ch[maxn<<5][2],sz;
void rsort()
{
for(int i=0;i<=m;++i) tax[i]=0;
for(int i=1;i<=n;++i) tax[rak[i]]++;
for(int i=1;i<=m;++i) tax[i]+=tax[i-1];
for(int i=n;i>=1;--i) sa[tax[rak[tp[i]]]--]=tp[i];
}
void ssort()
{
m=cnt;
for(int i=1;i<=n;++i)
rak[i]=a[i],tp[i]=i;
rsort();
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(int i=n-k+1;i<=n;++i) tp[++p]=i;
for(int i=1;i<=n;++i) if(sa[i]>k) tp[++p]=sa[i]-k;
rsort();
swap(rak,tp);
rak[sa[1]]=p=1;
for(int i=2;i<=n;++i)
rak[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?p:++p;
if(p>=n)break;
m=p;
}
}
void getH()
{
int k=0;
for(int i=1;i<=n;++i)
{
if(k) k--;
int j=sa[rak[i]-1];
while(a[i+k]==a[j+k]) k++;
height[rak[i]]=k;
}
}
void RMQ()
{
for(int i=1;i<=n;++i) mi[i][0]=height[i];
for(int j=1;(1<<j)<=n;++j)
for(int i=1;i+(1<<j)-1<=n;++i)
mi[i][j]=min(mi[i][j-1],mi[i+(1<<j-1)][j-1]);
}
int qmin(int ll,int rr)
{
int k=0;
while((1<<k+1)<=rr-ll+1) k++;
return min(mi[ll][k],mi[rr-(1<<k)+1][k]);
}
int update(int pre,int ll,int rr,int x)
{
int tt=++sz; size[tt]=size[pre]+1;
ch[tt][0]=ch[pre][0]; ch[tt][1]=ch[pre][1];
int mid=ll+rr>>1;
if(ll<rr)
{
if(x<=mid) ch[tt][0]=update(ch[pre][0],ll,mid,x);
else ch[tt][1]=update(ch[pre][1],mid+1,rr,x);
}
return tt;
}
int query(int u,int v,int ll,int rr,int s,int t)
{
if(ll<=s&&t<=rr) return size[v]-size[u];
int res=0,mid=s+t>>1;
if(ll<=mid) res+=query(ch[u][0],ch[v][0],ll,rr,s,mid);
if(rr>mid) res+=query(ch[u][1],ch[v][1],ll,rr,mid+1,t);
return res;
}
int qpos1(int ll,int rr,int x)
{
int L=ll,R=rr,res=rr;
while(L<R){
int mid=L+R>>1;
if(qmin(mid+1,rr)>=x) R=mid,res=mid;
else L=mid+1;
}
return res;
}
int qpos2(int ll,int rr,int x)
{
int L=ll,R=rr,res=ll;
while(L<R){
int mid=L+R>>1;
if(qmin(ll+1,mid)>=x) L=mid+1,res=mid;
else R=mid;
}
return res;
}
lt solve(int ll,int rr)
{
int len=rr-ll+1;
int L=qpos1(1,rak[ll],len);
int R=qpos2(rak[ll],n,len);
lt res1=query(rt[L-1],rt[R],rr+(n>>1)+2,n,1,n);
lt res2=query(rt[L-1],rt[R],(n>>1)+1,ll+(n>>1)-len-1,1,n);
return res1+res2;
}
int main()
{
n=read();
for(int i=1;i<=n;++i) val[i]=read();
for(int i=1;i<n;++i)
{
a[i]=b[i]=val[i+1]-val[i];
a[i+n]=b[i+n]=-(val[i+1]-val[i]);
}
a[n]=a[n<<1]=b[n]=b[n<<1]=inf; n=n<<1;
sort(b+1,b+1+n);
for(int i=1;i<=n;++i)
if(i==1||b[i]!=b[i-1])
pos[++cnt]=b[i];
for(int i=1;i<=n;++i)
a[i]=lower_bound(pos+1,pos+1+cnt,a[i])-pos;
ssort(); getH(); RMQ();
for(int i=1;i<=n;++i)
rt[i]=update(rt[i-1],1,n,sa[i]);
Q=read();
while(Q--)
{
int ll=read(),rr=read();
if(ll==rr) printf("%lld\n",(n>>1)-1);
else printf("%lld\n",solve(ll,rr-1));
}
return 0;
}
最后D2只做了两个半小时就自暴自弃了，100pts滚粗吧
完了去看std也确实证明我再想两个小时也没用。。。
于是蒟蒻省选模拟290pts自闭滚粗。。。
后来拿到的题解。。。看完之后觉得自己已经拿到能拿的分了。。我好菜:)