A. The Beatles
题意
给一个有n×k个点的环，环上从1开始，每k个点有一个餐厅，每次可以单向移动L个点，现在给出n和k以及a,b（分别表示初始位置离最近的餐厅的距离和第一次移动后离最近的餐厅的距离），询问最少和最多要移动多少次才能够回到初始位置
分析
考虑L存在的两种情况
- L=m×k+b−a
- L=m×k−b−a
其中m∈[1,n]
那么移动的次数ans=lmc(n×k,l)l=n×kgcd(n×k,l)
可以直接暴力枚举
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//******head by yjjr******
ll n,k,l1,l2,a,b,mn=6e18,mx=0;
inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
int main(){
n=read(),k=read(),a=read(),b=read();
l1=b-a,l2=k-b-a;
if(l1<=0)l1+=k;
if(l2<=0)l2+=k;
rep(i,0,n-1){
mn=min(mn,min(n*k/gcd(n*k,l1),(n*k/gcd(n*k,l2))));
mx=max(mx,max(n*k/gcd(n*k,l1),(n*k/gcd(n*k,l2))));
l1+=k,l2+=k;
}
cout<<mn<<' '<<mx<<endl;
return 0;
}
B. Lynyrd Skynyrd
题意
给出长度为m的序列p，和长度为n的序列a
给出Q次询问，每次询问序列a的区间[li,ri]中是否存在子序列为序列p的循环移位
e.g. 循环移位：比如(2,1,3)，那么它存在三个等价的循环(2,1,3)(1,3,2)(3,2,1)
分析
维护每个元素按照循环排列的下一个元素
之后对每个左端点求出离其最近的右端点位置
但如果暴力查询的话时间复杂度为O(n×m)
可以使用倍增进行优化（因为是连续寻找前驱的操作）
需要倒着循环一遍取后缀最小值
每次询问可以直接O(1)判断是否超过最近的右端点即可
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//******head by yjjr******
const int maxn=2e5+6;
int n,m,Q,p[maxn],a[maxn],fi[maxn],nxt[maxn][26],lst[maxn],minr[maxn];
int main(){
n=read(),m=read(),Q=read();
rep(i,1,n)p[i]=read();
rep(i,1,m)a[i]=read();
rep(i,1,n-1)fi[p[i]]=p[i+1];fi[p[n]]=p[1];
rep(i,1,n)lst[i]=m+1;
nxt[m+1][0]=m+1;
dep(i,m,1)nxt[i][0]=lst[fi[a[i]]],lst[a[i]]=i;
rep(j,1,19)rep(i,1,m+1)
nxt[i][j]=nxt[nxt[i][j-1]][j-1];
rep(i,1,m){
int now=n-1,r=i;
dep(j,19,0)if(now-(1<<j)>=0)now-=(1<<j),r=nxt[r][j];
minr[i]=r;
}
dep(i,m-1,1)minr[i]=min(minr[i],minr[i+1]);
while(Q--){
int l=read(),r=read();
if(r>=minr[l])printf("%d",1);else printf("%d",0);
}
return 0;
}
C. U2
题意
给出形如y=x2+bx+c的二次函数图象（注意没有a）
给出n个点的坐标，任意两个点可以确定一个二次函数图像
询问在构成的图像中有多少个图像其内部没有顶点
分析
(x,y)−>(x,y−x2)
转化之后可以求凸包了
或者可以直接魔改凸包，改成判断是否在抛物线内部即可
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//******head by yjjr******
#define eps 1e-7
const int maxn=2e5+6;
int n,tot=0;
struct P{double x,y;}a[maxn],p[maxn],s[maxn];
inline bool cmp(P a,P b){return a.x==b.x?a.y<b.y:a.x<b.x;}
inline P operator - (P a,P b){P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}
inline ll operator * (P a,P b){return a.x*b.y-a.y*b.x;}
inline ll dis(P a,P b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
/*inline bool operator < (P a,P b){
ll t=(a-p[1])*(b-p[1]);
if(t==0)return dis(p[1],a)<dis(p[1],b);else return t>0;
}
*/
int main(){
n=read();
rep(i,1,n){
scanf("%lf%lf",&a[i].x,&a[i].y);
a[i].y=a[i].y-1ll*a[i].x*a[i].x;
}
sort(a+1,a+1+n,cmp);
rep(i,1,n-1)if(fabs(a[i].x-a[i+1].x)>eps)p[++tot]=a[i];
p[++tot]=a[n];
int top=0;
dep(i,tot,1){
while(top>1&&((s[top]-s[top-1])*(p[i]-s[top-1])<=0))top--;
s[++top]=p[i];
}
cout<<top-1<<endl;
return 0;
}
皮一下
Wo sind Aufgabe D und E????
Kein Ahnung!
剩下的D和E咕了
本文可以转载，但必须附上原文链接，否则你会终生找不到妹子！！！欢迎关注我的CSDN: ahyjjr