2021 CCPC 桂林站

链接

gym

题解

A. Hero Named Magnus

输出 $2x-1$。

B. A Plus B Problem

直接模拟加法即可。

使用线段树二分或者二分+线段树找到第一个 $9$ 或者 $0$ 即可。

使用线段树二分，时间复杂度 $O(n\log n)$。

C. AC Automaton

好毒瘤啊，不会。

D. Assumption is All You Need

注意到，从小到大将数移到原来的位置后，就可以当做这个数字消失，也就是不再管它的位置。

大概是因为按照从小到大，没有归位的数都可以跨过去。

那么直接模拟即可。时间复杂度 $O(n^2)$。

E. Buy and Delete

最多只可能删除两次。

一次删掉 $x<y$ 的，另一次删掉 $x>y$ 的。

那么找到最小环即可。

时间复杂度 $O(nm\log n)$。

F. Illuminations II

题意

大凸包里包着小凸包，从大凸包的周长上任意选择一点作为光源，问小凸包期望被照亮的长度。

$n,m\le 2\times 10^5$。

题解

考虑反面，枚举小凸包的每一条边，看大凸包中有多长的线中的点能照到这条边。

这相当于求一条直线切一个凸包，问切成两部分后在直线右侧的长度和。

扫描线，维护直线切到凸包中的两条线段即可。

注意几乎平行的线段可能会有精度问题，判断点关于线的位置时需要注意。

程序

#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())

const db eps=1e-8;
const db pi=acos(-1.);
const db inf=1e20;
int sgn(db x)
{
	if(fabs(x)<eps) return 0;
	if(x<0) return -1;
	return 1;
}
inline db sqr(db x){return x*x;}

struct Point{
	db x,y;
	Point(){x=y=0;}
	Point(db _x,db _y){x=_x,y=_y;}
	void input(){scanf("%Lf%Lf",&x,&y);}
	friend inline bool operator==(Point A,Point B){return sgn(A.x-B.x)==0&&sgn(A.y-B.y)==0;}
	friend inline bool operator<(Point A,Point B){return sgn(A.x-B.x)==0?sgn(A.y-B.y)<0:A.x<B.x;}
	friend inline Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
	friend inline Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
	friend inline Point operator*(Point A,db k){return Point(A.x*k,A.y*k);}
	friend inline Point operator/(Point A,db k){return Point(A.x/k,A.y/k);}
	friend inline db operator^(Point A,Point B){return A.x*B.y-A.y*B.x;}
	friend inline db operator*(Point A,Point B){return A.x*B.x+A.y*B.y;}
	inline db len2(){return sqr(x)+sqr(y);}
	inline db len(){return sqrt(len2());}
	inline db angle(){return atan2(y,x);}
};
struct Line{
	Point s,e;
	Line(){}
	Line(Point _s,Point _e){s=_s,e=_e;}
	void adjust(){if(e<s) swap(e,s);}
	friend inline bool operator==(Line A,Line B){return A.s==B.s&&A.e==B.e;}
	inline db len(){return (e-s).len();}
	int relation(Point p)//1->left,2->right,3->on it.
	{
		int c=sgn((p-s)^(e-s));
		return !c?3:(1+(c>0));
	}
	bool parallel(Line v){return sgn((e-s)^(v.e-v.s))==0;}
	int linecrossline(Line v)//0 parallel,1 same,2 inter
	{
		if((*this).parallel(v)) return v.relation(s)==3;
		return 2;
	}
	Point Intersection(Line v)
	{
		db a1=(v.e-v.s)^(s-v.s);
		db a2=(v.e-v.s)^(e-v.s);
		return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
	}
};
const int N=200010;
int n,m;
Point a[N],b[N];
db sum,s[N];
Line li[N];

inline db ask(int l,int r)
{
	if(l<r) return s[r-1]-s[l];
	else return s[n-1]-s[l]+(r?s[r-1]:0);
}

int main()
{
	n=read(); m=read();
	ff(i,0,n) a[i].input();
	ff(i,0,m) b[i].input();
	Line now=Line(b[0],b[1]);
	ff(i,0,n) li[i]=Line(a[i],a[(i+1)%n]),sum+=li[i].len();
	ff(i,0,n) s[i]=li[i].len()+(i?s[i-1]:0.0);
	int l,r;
	ff(i,0,n)
		if(now.relation(a[i])==1&&now.relation(a[(i+1)%n])!=1)
		{
			l=i; break;
		}
	ff(i,0,n)
		if(now.relation(a[i])==2&&now.relation(a[(i+1)%n])!=2)
		{
			r=i; break;
		}
	db ans=(ask(l,r)+(now.Intersection(li[l])-a[(l+1)%n]).len()+(now.Intersection(li[r])-a[r]).len())/sum*now.len();
	ff(i,1,m)
	{
		now=Line(b[i],b[(i+1)%m]);
		for(;;)
			if(now.relation(a[l])!=2&&now.relation(a[(l+1)%n])!=1)
				break;
			else
				l=(l+1)%n;
		for(;;)
			if(now.relation(a[r])!=1&&now.relation(a[(r+1)%n])!=2)
				break;
			else
				r=(r+1)%n;
		ans+=(ask(l,r)+(now.Intersection(li[l])-a[(l+1)%n]).len()+(now.Intersection(li[r])-a[r]).len())/sum*now.len();
	}
	printf("%.12Lf",ans);
	return 0;
}

G. Occupy the Cities

一个比较好写的方法是：二分，然后贪心判断是否可行。

I. PTSD

从后往前贪心，看能否找到一个更大的去匹配即可。

J. Suffix Automaton

SAM

对反串建立SAM，每个节点的贡献是 $[len_{fa_x}+1,len_x]$。

为了满足字典序，我们找出每个点相对于父节点第一个多出来的字符，这个就相当于是原串的某个前缀再加一个字符。对于树中每个点，按照这个字符进行排序，就能按照字典序的要求来了。

找原串中第一个出现的字符串相当于找反串最后一次出现的字符串，在parent-tree中进行一遍dfs就可以找到right集合中最大的那个数。

SA

每个点的贡献是 $[height_x+1,n-sa_x+1]$。

SA本身就满足字典序。

找原串中第一个出现的字符串可以通过倍增找到。

对于以上两个算法，剩下的就是找到答案。

对询问离线，然后对若干条线段在数轴上从左到右扫描线，变成若干次单点修改，查找第 $k$ 小的值。用线段树维护即可。

时间复杂度 $O(n\sum+n\log n)$ 或 $O(n\log n)$。

K.Tax

建出最短路图后，直接dfs即可。

时间复杂度 $O(x^{\frac{n}{x}})$。

设 $f(x)=x^{\frac{n}{x}}$，则 $\ln f(x)=\frac{n}{x}\ln x$，$\frac{f’(x)}{f(x)}=n\times \frac{1-\ln x}{x^2}$。

易知 $x$ 取 $e$ 时，$f(x)$ 取得最大值。