GwOI Round1/ZhimaOI Round #9 CSP入门组模拟赛赛后总结

GwOI Round1 题解

~~比赛终于结束了，相信大家都 AK 了~~
本 $\texttt{solution}$ 由 $\texttt{Ghosted}$ 编写。

A.小黑与统计

$\texttt{Author:Ghosted}$
签到题，考虑直接爆搜。

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
#define MAX 21
int N,M,A[MAX],B[MAX],C[MAX],S[MAX],Ans;
bool Used[100001];
inline void Dfs(int X,int Sum)
{
    if(X==M+1)
    {
        if(!Used[Sum])Used[Sum]=true,Ans++;
        return;
    }
    S[X]=1,Dfs(X+1,Sum+A[X]);
    S[X]=2,Dfs(X+1,Sum+B[X]);
    S[X]=3,Dfs(X+1,Sum+C[X]);
    S[X]=0;
}
int main(void)
{
    BetterIO;
    register int i;cin>>N>>M;
    for(i=1;i<=M;i++)cin>>A[i]>>B[i]>>C[i];
    Dfs(1,0);
    if(N%Ans)cout<<N/Ans+1<<endl;
    else cout<<N/Ans<<endl;
    return 0;
}

B.小黑与飞竹

$\texttt{Author:Xcc}$
不难想到二分答案。
我们不妨把每一个飞竹看作是一个半径为 $R$ 的圆，但是这些圆不能影响到小黑从 $(1,1)$ 走到 $(N,N)$ 。
我们考虑二分半径 $R$ 的值，然后对于每一个答案考虑并查集判断。
不妨假设 $A_0$ 为底边， $A_{K+1}$ 为顶边。
将所有两个圆圆心距离小于等于 $2R$ 的圆合并。
如果与底边或顶边相切或相交就合并这个圆和底边或顶边。
加入最后底边和顶边不在同一集合，说明肯定有路径可以不被这些圆所影响。
~~可是为什么没人有分啊~~

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
usingnamespace std;
struct Struct{int X,Y;}A[5001];
int Total,N,M,Fa[5001];
inline void Init(){register int i;for(i=0;i<=Total+1;i++)Fa[i]=i;}
inline int Find(int X){return X==Fa[X]?X:Fa[X]=Find(Fa[X]);}
inline void Merge(int X,int Y){Fa[Find(X)]=Find(Y);}
inline bool Check(int X,int Y){return Find(X)==Find(Y);}
inline double Dist(int X1,int X2,int Y1,int Y2){return sqrt(1.0*(X1-X2)*(X1-X2)+1.0*(Y1-Y2)*(Y1-Y2));}
inline bool Check(double X)
{
	register int i,j;Init();
	for(i=1;i<=Total;i++)
	{
		for(j=1;j<i;j++)if(Dist(A[i].X,A[j].X,A[i].Y,A[j].Y)<=X*2)Merge(i,j);
		if(A[i].X-X<=1||A[i].Y+X>=M)Merge(0,i);
		if(A[i].X+X>=N||A[i].Y-X<=1)Merge(i,Total+1);
	}
	return Check(0,Total+1);
}
int main(void)
{
	BetterIO;
	register int i;cin>>N>>Total,M=N;
	for(i=1;i<=Total;i++)cin>>A[i].X>>A[i].Y;
	register double Left(0),Right(min(N,M));
	while(fabs(Right-Left)>1e-6)
	{
		register double Mid((Left+Right)/2);
		if(Check(Mid))Right=Mid;
		else Left=Mid;
	}
	cout<<fixed<<setprecision(2)<<Left<<endl;
	return 0;
}

C.小黑与龙焰

$\texttt{Author:Xcc}$
因为我们只关心数之间的相对大小关系，我们不妨做如下处理：

a_i= \left\{ \begin{aligned} 1\ \ \ \ \ &a_i>k\\ -1\ \ \ \ \ &a_i<k\\ 0\ \ \ \ \ &a_i=k\\ \end{aligned} \right.

然后即求覆盖 $k$ 且和为 $0$ 的子序列个数。
我们不妨设中位数 $k$ 出现的位置为 $pos$ 。
记 $pre_i$ 为 $i$ 到 $pos$ 中间的 $a_i$ 的和。
再记 $l_{pre_i}$ 为 $pos$ 左侧 $pre_i$ 出现的次数， $r_{pre_i}$ 为 $pos$ 右侧 $pre_i$ 出现的次数。
因为这样下标会变成负数，所以不妨统一都加一个 $n$ 。
答案即为：

\sum_{i=0}^{2n-1}l_i\times r_{2n-i}

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
#define MAX 400001
int N,Aim,S,A[MAX],L[MAX],R[MAX],Prefix[MAX];
int main(void)
{
    BetterIO;
    register int i;cin>>N>>Aim;
    register int S;
    for(i=1;i<=N;i++)
    {
        register int X;cin>>X;
        if(X>Aim)A[i]=1;
        else if(X<Aim)A[i]=-1;
        else A[S=i]=0;
    }
    register int Ret(0);L[N]=R[N]=1;
    for(i=S-1;i>=1;i--)L[(Prefix[i]=Prefix[i+1]+A[i])+N]++;
    for(i=S+1;i<=N;i++)R[(Prefix[i]=Prefix[i-1]+A[i])+N]++;
    for(i=0;i<2*N;i++)Ret+=L[i]*R[2*N-i];
    cout<<Ret<<endl;
    return 0;
}

D.小黑与剑气

$\texttt{Author:Ghosted}$
最后一题，原意为防 $\texttt{AK}$ 题，~~但是相信大家都爆切了~~。
不难想到二分答案 $x$ ，验证是否有 $k$ 个及以上个受到的伤害小于 $x$ 。
对于这个问题，我们考虑 $\texttt{dp}$ 。
不妨设 $dp_{i,j}$ 表示前 $i$ 个点已经选择了 $j$ 条剑气。
转移考虑要么直接与上一个段重叠，要么不重叠（忽略包含的情况，因为这只意味着可以选择少于 $m$ 段）。
重叠的情况下，选择上一个段显然是最优的。
不重叠的情况下，直接找包含这个点的左端点最左显然是最优的。

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
int N,M,S,K,A[10001],L[10001],R[10001],Dp[5001][5001];
inline bool Check(int X)
{
	register int i,j;memset(Dp,0,sizeof(Dp));
	for(i=1;i<=N;i++)
	{
		register int Last(i+1),Sum(0);
		for(j=1;j<=M;j++)if(L[j]<=i&&R[j]>=i)Last=min(Last,L[j]);
		for(j=Last;j<=i;j++)Sum+=(A[j]<=X);
		for(j=1;j<=S;j++)Dp[i][j]=max(Dp[i-1][j],Dp[Last-1][j-1]+Sum);
	}
	return Dp[N][S]>=K;
}
int main(void)
{
	BetterIO;
	register int i;cin>>N>>M>>S>>K;
	for(i=1;i<=N;i++)cin>>A[i];
	for(i=1;i<=M;i++)cin>>L[i]>>R[i];
	register int Left(1),Right(1000000000),Ans=-1;
	while(Left<=Right)
	{
		register int Middle=Left+Right>>1;
		if(Check(Middle))Ans=Middle,Right=Middle-1;
		else Left=Middle+1;
	}
	cout<<Ans<<endl;
	return 0;
}

GwOI Round1/ZhimaOI Round #9 CSP入门组模拟赛赛后总结

A.小黑与统计

B.小黑与飞竹

C.小黑与龙焰

D.小黑与剑气

CF492D题解