# Codeforces#549 div1 solution

## 正经的Div 1场

Posted by yjjr's blog on April 3, 2019

# A. The Beatles

## 分析

• $L=m\times k +b-a$
• $L=m\times k -b-a$

## 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;
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;
}
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(){
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

## 题意

e.g. 循环移位：比如$(2,1,3)$，那么它存在三个等价的循环$(2,1,3)(1,3,2)(3,2,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;
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;
}
const int maxn=2e5+6;
int n,m,Q,p[maxn],a[maxn],fi[maxn],nxt[maxn][26],lst[maxn],minr[maxn];
int main(){
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--){
if(r>=minr[l])printf("%d",1);else printf("%d",0);
}
return 0;
}


# C. U2

## 分析

$(x,y)->(x,y-x^2)$

## 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;
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;
}
#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(){
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!