CF#549 div1

Source

CF#549div1

A

请先思考后再展开

阅读理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ll gcd(ll x,ll y) {return y==0?x:gcd(y,x%y);}
ll n,k;
ll mi=LLINF,mx=0;
void check(ll x,ll y)
{
if(x>y) y+=n*k;
ll tmp=y-x;
chmin(mi,n*k/gcd(n*k,tmp));
chmax(mx,n*k/gcd(n*k,tmp));
}
ll gg(ll x){return (x+n*k)%(n*k);}
void main()
{
n=qread(),k=qread();
ll a=qread(),b=qread();
for(ll t=0;t<=n*k-1;t+=k)
{
check(a,gg(t-b));check(k-a,gg(t-b));
check(a,gg(t+b));check(k-a,gg(t+b));
}
printf("%lld %lld",mi,mx);
}

B

请先思考后再展开

显然先把排列转化为求递增的序列
一直在想怎么处理这个shift,想过复制到后面、从n向左右考虑,然后都搞不动
但其实只要直接考虑每个位置作为开头就好了(我以为一般不能这么直接地考虑……)
时间复杂度 $O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int a[MAX_N],num[MAX_N];
int lst[MAX_N],nxt2[MAX_N];
int bin[30],mm[MAX_N][20],nxt[MAX_N][20];
int jump(int x,int k){for(int t=19;t>=0;t--) if(k&bin[t]) x=nxt[x][t];return x;}
void main()
{
bin[0]=1;for(int i=1;i<30;i++) bin[i]=bin[i-1]<<1;
int n=qread(),m=qread(),q=qread();
for(int i=1;i<=n;i++) a[qread()]=i;
for(int i=1;i<=m;i++) num[i]=a[qread()];
for(int i=1;i<=n+1;i++) lst[i]=m+1;nxt[m+1][0]=m+1;
for(int i=m;i>=1;i--) {lst[num[i]]=i,nxt[i][0]=lst[num[i]+1];if(num[i]==n) nxt2[i]=lst[1];}
for(int t=1;t<20;t++) for(int i=1;i<=m+1;i++) nxt[i][t]=nxt[nxt[i][t-1]][t-1];
for(int i=1;i<=m;i++)
{
int to=jump(i,n-num[i]);
if(num[i]==1) mm[i][0]=to;
else if(nxt2[to]) mm[i][0]=jump(nxt2[to],num[i]-2);
else mm[i][0]=INF;
}
for(int t=1;t<20;t++) for(int i=1;i<=m-bin[t]+1;i++) mm[i][t]=min(mm[i][t-1],mm[i+bin[t-1]][t-1]);
while(q--)
{
int l=qread(),r=qread();
int t=log2(r-l+1),ans=min(mm[l][t],mm[r-bin[t]+1][t]);
write(ans<=r);
}
}

C

题意补充:如果抛物线重合,只算一条;如果上面恰好有其他点,也合法

请先思考后再展开

$y_3>x_3^2+bx_3+c$
$y_3-x_3^2>bx_3+c$
故把点 $(x,y)->(x,y-x^2)$
然后就是求多少个直线(重叠算一个),上面是没有点的
维护上凸壳即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,ll>
#define PB push_back
#define vc vector
void chmax(ll &x,const ll y) {x=x>y?x:y;}
void chmin(ll &x,const ll y) {x=x<y?x:y;}
const int MAX_N=1e5+10;
const ll MOD=1e9+7;
void add(ll &x,ll y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
double slope(pr a,pr b){return (double)(b.SE-a.SE)/(b.FR-a.FR);}
pr p[MAX_N];bool cmp(pr a,pr b){return a.FR<b.FR or (a.FR==b.FR and a.SE>b.SE);}
int sta[MAX_N];
void main()
{
int n=qread();for(int i=1;i<=n;i++){ll x=qread(),y=qread();p[i]=MP(x,y-x*x);}
sort(p+1,p+n+1,cmp);
int top=1;sta[top]=1;
for(int i=2;i<=n;i++) if(p[i-1].FR!=p[i].FR)
{
while(top>1 and slope(p[sta[top-1]],p[sta[top]])<=slope(p[sta[top]],p[i])) top--;
sta[++top]=i;
}
write(top-1);
}
};
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
srand(time(0));
mine::main();
}

咕咕咕

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a12f.html
转载请注明出处,谢谢!