心态爆炸，打出gg。。。
A 爆long long fst了，B看错题半天然后又写挂一个细节
原地爆炸，差点炸出div1了qwq
A.
考虑枚举走了几个完整段，分情况讨论一下
然后就是一个gcd
注意写的不好可能会爆long long
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 ll n,k,a,b; 5 ll gcd(ll a,ll b) 6 { 7 if(!b)return a; 8 return gcd(b,a%b); 9 } 10 int main() 11 { 12 cin>>n>>k>>a>>b; 13 ll x=n*k,y=0; 14 for(int i=1;i<=n;++i) 15 { 16 x=min(x,n*k/gcd(a+b+k*i,n*k)); 17 y=max(y,n*k/gcd(a+b+k*i,n*k)); 18 x=min(x,n*k/gcd(a-b+k*i,n*k)); 19 y=max(y,n*k/gcd(a-b+k*i,n*k)); 20 x=min(x,n*k/gcd(b-a+k*i,n*k)); 21 y=max(y,n*k/gcd(b-a+k*i,n*k)); 22 x=min(x,n*k/gcd(k-a-b+k*i,n*k)); 23 y=max(y,n*k/gcd(k-a-b+k*i,n*k)); 24 } 25 cout<<x<<" "<<y<<endl; 26 return 0; 27 }
B.
维护每个元素按排列循环走下去的下一个元素是什么
然后对每个左端点倍增出离他最近的右端点
然后倒着扫一下取个后缀min
每次询问看是否超过最近的右端点就行了
1 #include<bits/stdc++.h> 2 #define maxn 200005 3 using namespace std; 4 int n,m,q; 5 int p[maxn],a[maxn]; 6 int Ans[maxn]; 7 int to[maxn],nxt[maxn][22],lst[maxn]; 8 int minr[maxn]; 9 int main() 10 { 11 scanf("%d%d%d",&n,&m,&q); 12 for(int i=1;i<=n;++i)scanf("%d",&p[i]); 13 for(int i=1;i<=m;++i)scanf("%d",&a[i]); 14 for(int i=1;i<n;++i)to[p[i]]=p[i+1]; 15 to[p[n]]=p[1]; 16 for(int i=1;i<=n;++i)lst[i]=m+1; 17 nxt[m+1][0]=m+1; 18 for(int i=m;i>=1;--i) 19 { 20 nxt[i][0]=lst[to[a[i]]]; 21 lst[a[i]]=i; 22 } 23 for(int j=1;j<=19;++j) 24 for(int i=1;i<=m+1;++i)nxt[i][j]=nxt[nxt[i][j-1]][j-1]; 25 for(int i=1;i<=m;++i) 26 { 27 int x=n-1,r=i; 28 for(int j=19;j>=0;--j)if(x-(1<<j)>=0)x-=(1<<j),r=nxt[r][j]; 29 minr[i]=r; 30 } 31 for(int i=m-1;i>=1;--i)minr[i]=min(minr[i],minr[i+1]); 32 for(int i=1;i<=q;++i) 33 { 34 int l,r; 35 scanf("%d%d",&l,&r); 36 if(r>=minr[l])Ans[i]=1; 37 } 38 for(int i=1;i<=q;++i)printf("%d",Ans[i]); 39 return 0; 40 }
C.
考虑下方的点基本上是不太行的
所以应该是上方的那些点
模仿凸包的过程，判断改成判是否在抛物线里就行了
1 #include<bits/stdc++.h> 2 #define vec point 3 #define maxn 200005 4 #define pdd pair<double,double> 5 #define mp(a,b) make_pair(a,b) 6 using namespace std; 7 const double eps=1e-7; 8 int n; 9 struct point 10 { 11 double x,y; 12 point(double x=0,double y=0):x(x),y(y){} 13 }a[maxn],p[maxn],ch[maxn]; 14 bool operator < (point A,point B) 15 { 16 if(A.x==B.x)return A.y<B.y; 17 return A.x<B.x; 18 } 19 pdd getu(point A,point B) 20 { 21 double b=((A.y-A.x*A.x)-(B.y-B.x*B.x))/(A.x-B.x); 22 double c=A.y-A.x*A.x-b*A.x; 23 return pdd(b,c); 24 } 25 bool in(point A,pdd u) 26 { 27 double b=u.first,c=u.second; 28 if(A.y-(A.x*A.x+b*A.x+c)>-eps)return 1; 29 return 0; 30 } 31 int main() 32 { 33 scanf("%d",&n); 34 for(int i=1;i<=n;++i)scanf("%lf%lf",&a[i].x,&a[i].y); 35 sort(a+1,a+n+1); 36 int cnt=0; 37 for(int i=1;i<n;++i)if(fabs(a[i].x-a[i+1].x)>eps)p[++cnt]=a[i]; 38 p[++cnt]=a[n]; 39 int top=0; 40 for(int i=cnt;i;i--) 41 { 42 while(top>1&&in(p[i],getu(ch[top],ch[top-1])))top--; 43 ch[++top]=p[i]; 44 } 45 printf("%d ",top-1); 46 return 0; 47 }