A. The Beatles
time limit per test1 second memory limit per test256 megabytes
Recently a Golden Circle of Beetlovers was found in Byteland. It is a circle route going through \(n \cdot k\) cities. The cities are numerated from 1 to \(n \cdot k\), the distance between the neighboring cities is exactly 1 km.
Sergey does not like beetles, he loves burgers. Fortunately for him, there are n fast food restaurants on the circle, they are located in the 1-st, the (k + 1)-st, the (2k + 1)-st, and so on, the ((n-1)k + 1)-st cities, i.e. the distance between the neighboring cities with fast food restaurants is k km.
Sergey began his journey at some city s and traveled along the circle, making stops at cities each l km (l > 0), until he stopped in s once again. Sergey then forgot numbers s and l, but he remembers that the distance from the city s to the nearest fast food restaurant was a km, and the distance from the city he stopped at after traveling the first l km from s to the nearest fast food restaurant was b km. Sergey always traveled in the same direction along the circle, but when he calculated distances to the restaurants, he considered both directions.
Now Sergey is interested in two integers. The first integer x is the minimum number of stops (excluding the first) Sergey could have done before returning to s. The second integer y is the maximum number of stops (excluding the first) Sergey could have done before returning to s.Input
The first line contains two integers n and \(k (1 \le n, k \le 100\,000)\) — the number of fast food restaurants on the circle and the distance between the neighboring restaurants, respectively.
The second line contains two integers a and \(b (0 \le a, b \le \frac{k}{2}) \)— the distances to the nearest fast food restaurants from the initial city and from the city Sergey made the first stop at, respectively.Output
Print the two integers x and y.ExamplesinputCopy
2 3 1 1
outputCopy
1 6
inputCopy
3 2 0 0
outputCopy
1 3
inputCopy
1 10 5 3
outputCopy
5 5
Note
In the first example the restaurants are located in the cities 1 and 4, the initial city s could be 2, 3, 5, or 6. The next city Sergey stopped at could also be at cities 2, 3, 5, 6. Let's loop through all possible combinations of these cities. If both s and the city of the first stop are at the city 2 (for example, l = 6), then Sergey is at s after the first stop already, so x = 1. In other pairs Sergey needs 1, 2, 3, or 6 stops to return to s, so y = 6.
In the second example Sergey was at cities with fast food restaurant both initially and after the first stop, so l is 2, 4, or 6. Thus x = 1, y = 3.
In the third example there is only one restaurant, so the possible locations of s and the first stop are: (6, 8) and (6, 4). For the first option l = 2, for the second l = 8. In both cases Sergey needs x=y=5 stops to go to s.
暴力枚举，读懂题意之后就挺好做了，只需要枚举l然后扫一遍更新答案即可
#include<bits/stdc++.h>
using namespace std;
#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 pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
ll n,k,a,b,mn=1e18,mx=0;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void check(ll l){
ll a=gcd(n*k,l);
mn=min(mn,a);mx=max(mx,a);
}
int main(){
scanf("%lld%lld%lld%lld",&n,&k,&a,&b);
if(a<b) swap(a,b);
ll l=a-b;
rep(i,1,n) check(l),l+=k;
l=k-a-b;
rep(i,1,n) check(l),l+=k;
printf("%lld %lld\n",n*k/mx,n*k/mn);
}
B. Lynyrd Skynyrd
time limit per test2 seconds memory limit per test256 megabytes
Recently Lynyrd and Skynyrd went to a shop where Lynyrd bought a permutation p of length n, and Skynyrd bought an array a of length m, consisting of integers from 1 to n.
Lynyrd and Skynyrd became bored, so they asked you q queries, each of which has the following form: "does the subsegment of a from the l-th to the r-th positions, inclusive, have a subsequence that is a cyclic shift of p?" Please answer the queries.
A permutation of length n is a sequence of n integers such that each integer from 1 to n appears exactly once in it.
A cyclic shift of a permutation \((p_1, p_2, \ldots, p_n)\) is a permutation \((p_i, p_{i + 1}, \ldots, p_{n}, p_1, p_2, \ldots, p_{i - 1})\) for some i from 1 to n. For example, a permutation (2, 1, 3) has three distinct cyclic shifts: (2, 1, 3), (1, 3, 2), (3, 2, 1).
A subsequence of a subsegment of array a from the l-th to the r-th positions, inclusive, is a sequence \(a_{i_1}, a_{i_2}, \ldots, a_{i_k} for some i_1, i_2, \ldots, i_k such that l \leq i_1 < i_2 < \ldots < i_k \leq r\).Input
The first line contains three integers \(n, m, q (1 \le n, m, q \le 2 \cdot 10^5)\) — the length of the permutation p, the length of the array a and the number of queries.
The next line contains n integers from 1 to n, where the i-th of them is the i-th element of the permutation. Each integer from 1 to n appears exactly once.
The next line contains m integers from 1 to n, the i-th of them is the i-th element of the array a.
The next q lines describe queries. The i-th of these lines contains two integers \(l_i\) and \(r_i (1 \le l_i \le r_i \le m)\), meaning that the i-th query is about the subsegment of the array from the l_i-th to the r_i-th positions, inclusive.Output
Print a single string of length q, consisting of 0 and 1, the digit on the i-th positions should be 1, if the subsegment of array a from the l_i-th to the r_i-th positions, inclusive, contains a subsequence that is a cyclic shift of p, and 0 otherwise.ExamplesinputCopy
3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5
outputCopy
110
inputCopy
2 4 3
2 1
1 1 2 2
1 2
2 3
3 4
outputCopy
010
Note
In the first example the segment from the 1-st to the 5-th positions is 1, 2, 3, 1, 2. There is a subsequence 1, 3, 2 that is a cyclic shift of the permutation. The subsegment from the 2-nd to the 6-th positions also contains a subsequence 2, 1, 3 that is equal to the permutation. The subsegment from the 3-rd to the 5-th positions is 3, 1, 2, there is only one subsequence of length 3 (3, 1, 2), but it is not a cyclic shift of the permutation.
In the second example the possible cyclic shifts are 1, 2 and 2, 1. The subsegment from the 1-st to the 2-nd positions is 1, 1, its subsequences are not cyclic shifts of the permutation. The subsegment from the 2-nd to the 3-rd positions is 1, 2, it coincides with the permutation. The subsegment from the 3 to the 4 positions is 2, 2, its subsequences are not cyclic shifts of the permutation.
首先我们可以对于a数组的每个点，将其和和对应permutation前面的那个点连一条边，就假设样例一的2，1，3这个排列，我对于a数组值位3的数，应该去和这个位置之前最近的一个1去连边；
这样处理完之后，我们需要判断的就是，对于一个给定的l和r，是否能找到一个小于等于r位置，在此位置往前跳n-1步之后到达的位置大于等于l，显然暴力的话是\(n^2\)的，看到这个跳n-1步马上想起了倍增，套上去就好了
#include<bits/stdc++.h>
using namespace std;
#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 pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,m,q,p[maxn],pos[maxn],f[maxn],pre[maxn],now[maxn];
int main(){
scanf("%d%d%d",&n,&m,&q);
rep(i,1,n) scanf("%d",&p[i]),pos[p[i]]=i;
rep(i,1,m){
int x;scanf("%d",&x);pre[i]=i;
f[i]=now[p[(pos[x]+n-2)%n+1]];
now[x]=i;
}
for(int x=n-1;x;x>>=1){
if(x&1) rep(i,1,m) pre[i]=f[pre[i]];
dep(i,m,1) f[i]=f[f[i]];
}
rep(i,2,m) pre[i]=max(pre[i],pre[i-1]);
while(q--){
int l,r;scanf("%d%d",&l,&r);
printf(pre[r]>=l?"1":"0");
}
}
C. U2
time limit per test1 second memory limit per test256 megabytes
Recently Vasya learned that, given two points with different x coordinates, you can draw through them exactly one parabola with equation of type \(y = x^2 + bx + c\), where b and c are reals. Let's call such a parabola an U-shaped one.
Vasya drew several distinct points with integer coordinates on a plane and then drew an U-shaped parabola through each pair of the points that have different x coordinates. The picture became somewhat messy, but Vasya still wants to count how many of the parabolas drawn don't have any drawn point inside their internal area. Help Vasya.
The internal area of an U-shaped parabola is the part of the plane that lies strictly above the parabola when the y axis is directed upwards.Input
The first line contains a single integer \(n (1 \le n \le 100\,000)\) — the number of points.
The next n lines describe the points, the i-th of them contains two integers \(x_i\) and \(y_i\) — the coordinates of the i-th point. It is guaranteed that all points are distinct and that the coordinates do not exceed\( 10^6\) by absolute value.Output
In the only line print a single integer — the number of U-shaped parabolas that pass through at least two of the given points and do not contain any of the given points inside their internal area (excluding the parabola itself).ExamplesinputCopy
3 -1 0 0 2 1 0
outputCopy
2
inputCopy
5 1 0 1 -1 0 -1 -1 0 -1 -1
outputCopy
1
Note
On the pictures below all U-shaped parabolas that pass through at least two given points are drawn for each of the examples. The U-shaped parabolas that do not have any given point inside their internal area are drawn in red.
The first example.
The second example.
突破口其实在这个抛物线的表达式上；
题给条件中抛物线形如\(y = x^2 + bx + c\)，于是我们可以用二元组(b,c)表示一条抛物线；
又根据题目要求，符合条件的抛物线对于每个点，都要满足 \(x^2 + bx + c \geq y\)
移项之后就变成了 \(bx + c \geq y - x^2\)
很显然\(bx+c\)是一条直线，我们将\((x,y - x^2)\)看成一个点，那么就是说要这条直线在这个点上方；
此时事情就很明了了，维护每个\((x,y - x^2)\)点的一个上凸壳，凸壳上的边数(也就是点数-1)就是答案了
#include<bits/stdc++.h>
using namespace std;
#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 pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n;
struct point{
ll x,y;
bool operator<(const point &b)const{return x==b.x?y<b.y:x>b.x;}
}p[maxn];
point operator+(point a,point b){return {a.x+b.x,a.y+b.y};}
point operator-(point a,point b){return {a.x-b.x,a.y-b.y};}
point operator*(point a,ll b){return {a.x*b,a.y*b};}
ll operator*(point a,point b){return a.x*b.y-a.y*b.x;}
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%lld%lld",&p[i].x,&p[i].y),p[i].y-=p[i].x*p[i].x;
sort(p+1,p+1+n);
int top=1;
rep(i,2,n){
if(p[i].x==p[top].x) top--;
while(top>1&&(p[top]-p[top-1])*(p[i]-p[top-1])<=0) top--;
p[++top]=p[i];
}
printf("%d\n",top-1);
}
