Comet OJ CCPC－Wannafly & Comet OJ 夏季欢乐赛（2019）

Preface

在一个月黑风高的夜晚我这个蒟蒻正踌躇着打什么比赛好

是继续做一场AGC，还是去刷一场CF

然后，一道金光闪过（滑稽），我们的红太阳bzt给我指明了方向：

你太菜了，我知道有一场很水的比赛，你快来做吧

然后我就点进比赛，看到了排行榜上Minamoto旁大大的AK二字，不禁心生敬意

同时对于它一人狂得两题一血，身穿两条小裙子的事迹有不免心生敬佩

然后我就开始了刷水之旅（被水题狂虐）

以下题目按照编号顺序排列（怎么感觉在说废话）

A 完全k叉树

一眼发现可以处理出这棵树的深度和最后一层的节点数，然后分类讨论路径的拼法即可

要注意细节，同时还有\(k=1\)的情况要特判

#include<cstdio>

using namespace std;

int t,n,k;

int main()

{

	for (scanf("%d",&t);t;--t)

	{

		scanf("%d%d",&k,&n); int dep=0; long long cur=1,lst=1;

		if (k==1) { printf("%d\n",n-1); continue; }

		if (n==1) { puts("0"); continue; }

		while (cur<n) ++dep,cur=cur+(lst*=k);

		cur-=lst; int left=n-cur;

		if (left>(lst/k)) printf("%d\n",dep<<1); else printf("%d\n",(dep<<1)-1);

	}

	return 0;

}

B 距离产生美

比A题简单，发现原序列的数据范围是\(10^5\)，\(k\le 10^9\)，所以我们要修改就直接改到\(10^{18}\)即可

随便DP一下即可

#include<cstdio>

#include<iostream>

#include<algorithm>

#define RI register int

using namespace std;

const int N=100005;

int n,k,a[N],f[N][2];

int main()

{

	RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i)

	{

		scanf("%d",&a[i]); if (abs(a[i]-a[i-1])>=k)

		f[i][0]=min(f[i-1][0],f[i-1][1]); else f[i][0]=f[i-1][1];

		f[i][1]=min(f[i-1][0],f[i-1][1])+1;

	}

	return printf("%d",min(f[n][0],f[n][1])),0;

}

C 烤面包片

首先我们肯定容易发现，对于\(x! \operatorname{mod} y\)，若\(x>=y\)值一定为\(0\)

然后我们掏出计算器一算就发现\(4!!\)已经大到天上去了（好吧也就\(10^{24}\)级别）

所以我们要考虑的只有\(n=0,1,2,3\)的情况，注意下细节即可（PS：\(0!=1\)）

#include<cstdio>

#define RI register int

using namespace std;

int n,mod;

int main()

{

	scanf("%d%d",&n,&mod); if (n==0||n==1||n==2) return printf("%d",(n?n:1)%mod),0;

	if (n>3) return puts("0"),0; int ret=1;

	for (RI i=1;i<=720;++i) ret=1LL*ret*i%mod; return printf("%d",ret),0;

}

D 茶颜悦色

首先我们转化问题，把一个点化为一个矩形，表示若把正方形的某个定点放置在这个矩形内能覆盖到这个点

所以现在问题就变成了平面矩形覆盖次数最多的点，直接扫描线+树状数组即可

#include<cstdio>

#include<iostream>

#include<algorithm>

#define RI register int

#define CI const int&

using namespace std;

const int N=400005;

struct line

{

	int x,y1,y2,tp;

	inline line(CI X=0,CI Y1=0,CI Y2=0,CI Tp=0)

	{

		x=X; y1=Y1; y2=Y2; tp=Tp;

	}

	friend inline bool operator < (const line& A,const line& B)

	{

		return A.x<B.x;

	}

}l[N]; int n,k,x,y,rst[N],num,ans;

class Segment_Tree

{

	private:

		struct segment

		{

			int mx,tag;

		}node[N<<2];

		#define M(x) node[x].mx

		#define T(x) node[x].tag

		#define TN CI now=1,CI l=1,CI r=num

		inline void apply(CI now,CI mv)

		{

			M(now)+=mv; T(now)+=mv;

		}

		inline void pushup(CI now)

		{

			M(now)=max(M(now<<1),M(now<<1|1));

		}

		inline void pushdown(CI now)

		{

			if (T(now)) apply(now<<1,T(now)),apply(now<<1|1,T(now)),T(now)=0;

		}

	public:

		inline void modify(CI beg,CI end,CI mv,TN)

		{

			if (beg<=l&&r<=end) return apply(now,mv); int mid=l+r>>1; pushdown(now);

			if (beg<=mid) modify(beg,end,mv,now<<1,l,mid);

			if (end>mid) modify(beg,end,mv,now<<1|1,mid+1,r); pushup(now);

		}

		inline int query(void)

		{

			return M(1);

		}

		#undef M

		#undef T

		#undef TN

}SEG;

inline int find(CI x)

{

	return lower_bound(rst+1,rst+num+1,x)-rst;

}

int main()

{

	RI i,j,k; for (scanf("%d%d",&n,&k),i=1;i<=n;++i)

	{

		scanf("%d%d",&x,&y); x<<=1; y<<=1; rst[i]=y-k; rst[n+i]=y+k;

		l[i]=line(x-k,y-k,y+k,1); l[n+i]=line(x+k+1,y-k,y+k,-1);

	}

	sort(rst+1,rst+(n<<1)+1); num=unique(rst+1,rst+(n<<1)+1)-rst-1;

	for (i=1;i<=(n<<1);++i) l[i].y1=find(l[i].y1),l[i].y2=find(l[i].y2);

	for (sort(l+1,l+(n<<1)+1),i=1;i<=(n<<1);i=j+1)

	{

		for (j=i;j<(n<<1)&&l[j+1].x==l[i].x;++j);

		for (k=i;k<=j;++k) SEG.modify(l[k].y1,l[k].y2,l[k].tp);

		ans=max(ans,SEG.query());

	}

	return printf("%d",ans),0;

}

E 飞行棋

有点套路的期望题。首先我们考虑倒推，即用\(f_i\)表示距离终点\(i\)步时的期望步数

显然\(f_0=0\)，然后我们考虑对于\(f_i(i\in [1,k])\)，它们的答案是什么

发现对于它们任何一个位置，直接走到终点的概率就是\(\frac{1}{k}\)，否则就会落入另一个状态

而我们发现这些状态的问题和原问题等价，我们可以很容易地从概率推出它们的期望都是\(k\)

PS：如果你不想观察出这个结论的话你也可以大力列出方程然后高斯消元

然后我们发现接下来的转移由于没有走到终点再走回的这样一个过程，转移就比较单一，即为\(f_i=\frac{1}{k}\cdot \sum_{j=i-k}^{i-1} f_j+1\)，我们可以容易的使用矩阵快速幂来优化复杂度到\(O(k^3\cdot\log n)\)

#include<cstdio>

#include<cstring>

#define RI register int

#define CI const int&

using namespace std;

const int N=25,mod=1e9+7;

long long d,k; int invk;

inline void inc(int& x,CI y)

{

	if ((x+=y)>=mod) x-=mod;

}

inline int quick_pow(int x,int p=mod-2,int mul=1)

{

	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;

}

struct Matrix

{

	int mat[N][N],n,m;

	inline Matrix(CI N=0,CI M=0)

	{

		n=N; m=M; memset(mat,0,sizeof(mat));

	}

	inline int* operator [] (CI x) { return mat[x]; }

	friend inline Matrix operator * (Matrix A,Matrix B)

	{

		Matrix C(A.n,B.m); for (RI i=0;i<C.n;++i)

		for (RI j=0;j<C.m;++j) for (RI k=0;k<A.m;++k)

		inc(C[i][j],1LL*A[i][k]*B[k][j]%mod); return C;

	}

	friend inline Matrix operator ^ (Matrix A,long long p)

	{

		Matrix T(A.n,A.m); for (RI i=0;i<A.n;++i) T[i][i]=1;

		for (;p;p>>=1,A=A*A) if (p&1) T=T*A; return T;

	}

};

int main()

{

	scanf("%lld%lld",&d,&k); Matrix S(k+1,1),P(k+1,k+1);

	RI i; for (invk=quick_pow(k%mod),i=0;i<k;++i) S[i][0]=k; S[k][0]=1;

	for (i=0;i<k-1;++i) P[i][i+1]=1; for (i=0;i<k;++i) P[k-1][i]=invk;

	P[k-1][k]=P[k][k]=1; P=P^(d-k); S=P*S; return printf("%d",S[k-1][0]),0;

}

F 三元组

我们考虑把\(\min,\max\)去掉，那么我们强制\(a_i+a_j\)是\(\min\)，这样题目就变成求\(2\cdot(a_i+a_j)\le b_i+b_j\)的\(c_i\cdot c_j\)的和

把式子拆开并移项就得到了\((2\cdot a_i-b_i)+(2\cdot a_j-b_j)\le 0\)，这个我们记\(2\cdot a_i-b_i\)为\(d_i\)，然后把\(d_i\)排序后two points扫一下用前（后）缀和算答案即可

若\(b_i+b_j\)是\(\min\)的话就交换所有\(a_i,b_i\)再做一次即可

#include<cstdio>

#include<algorithm>

#include<iostream>

#define RI register int

#define CI const int&

using namespace std;

const int N=100005,mod=1e9+7;

struct data

{

	int a,b,c,v;

	friend inline bool operator < (const data& A,const data& B)

	{

		return A.v<B.v;

	}

}p[N]; int n,suf[N],ans;

inline void inc(int& x,CI y)

{

	if ((x+=y)>=mod) x-=mod;

}

inline int calc(int ret=0)

{

	RI i,j; for (i=1;i<=n;++i) p[i].v=p[i].b-2*p[i].a;

	for (sort(p+1,p+n+1),i=n;i;--i) suf[i]=suf[i+1],inc(suf[i],p[i].c);

	for (i=n,j=1;i;--i)

	{

		while (j<=n&&p[i].v+p[j].v<0) ++j;

		if (j<=n) inc(ret,1LL*p[i].c*suf[max(i,j)]%mod);

	}

	return ret;

}

int main()

{

	RI i; for (scanf("%d",&n),i=1;i<=n;++i)

	scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);

	for (ans=calc(),i=1;i<=n;++i) swap(p[i].a,p[i].b);

	return inc(ans,calc()),printf("%d",ans),0;

}

G 篮球校赛

律师函警告（不是）

首先我们很容易发现我们对于\(5\)个位置每个位置挑出前\(5\)的队员然后最优解一定在它们之中（否则要它有什么用？）

然后还愣着干什么，直接\(O(5^5)\)甚至\(O(2^{25})\)大暴力就过了啊

#include<cstdio>

#include<iostream>

#include<algorithm>

#define RI register int

#define CI const int&

using namespace std;

const int N=100005;

struct data

{

	int val,id,tp;

	friend inline bool operator < (const data& A,const data& B)

	{

		return A.val>B.val;

	}

}a[5][N],t[30]; int n,cnt; long long ans; bool cs[N];

inline void DFS(CI nw=1,CI ct=0,CI st=0,const long long& sum=0)

{

	if (nw>cnt) { if (ct==5) ans=max(ans,sum); return; }

	if (!cs[t[nw].id]&&!((st>>t[nw].tp)&1))

	cs[t[nw].id]=1,DFS(nw+1,ct+1,st|(1<<t[nw].tp),sum+t[nw].val),cs[t[nw].id]=0; DFS(nw+1,ct,st,sum);

}

int main()

{

	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)

	for (j=0;j<5;++j) scanf("%d",&a[j][i].val),a[j][i].id=i,a[j][i].tp=j;

	for (i=0;i<5;++i) for (sort(a[i]+1,a[i]+n+1),j=1;j<=5;++j) t[++cnt]=a[i][j];

	return DFS(),printf("%lld",ans),0;

}

H 分配学号

首先容易发现最后修改的学号序列在排序后是唯一的，只不过有些人可以被改动到的数字不一样

我们考虑先扫一遍求出目标序列，然后将原序列和目标序列都排序，然后two points维护下每个数能从多少个数变过来，然后乘起来就好了

#include<cstdio>

#include<algorithm>

#define RI register int

using namespace std;

const int N=100005,mod=1e9+7;

int n,ans=1; long long a[N],tar[N];

int main()

{

	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);

	for (sort(a+1,a+n+1),i=1;i<=n;++i)

	if (a[i]<=tar[i-1]) tar[i]=tar[i-1]+1; else tar[i]=a[i];

	for (sort(tar+1,tar+n+1),i=j=1;i<=n;++i)

	{

		while (j<=n&&a[j]<=tar[i]) ++j;

		ans=1LL*ans*(j-i)%mod;

	}

	return printf("%d",ans),0;

}

I Gree的心房

整场比赛最水的题，容易发现最少步数一定是\(n+m-2\)，所以判断\(k\)和它的关系即可

注意起点和终点不能被占用了以及计算剩下多少个无用位置时要开long long

#include<cstdio>

using namespace std;

int n,m,k;

int main()

{

	scanf("%d%d%d",&n,&m,&k); long long left=1LL*n*m-(n+m-1);

	if (k>left) puts("-1"); else printf("%d",n+m-2); return 0;

}

Postscript

当我做完这场比赛，看着自己每道题都WA上三四遍的提交，再看着现场AK并拿两题一血的bzt，我流下了蒟蒻的泪水

巴特西