这是本文档旧的修订版！

A. Magical Sticks

有 $1 \le i \le n$ 的小棍各一根。问能变成相同长度的小棍最多多少根。

偶数 $\frac n2$ ，奇数 $\lceil\frac n2\rceil$ (以 $n$ 为 $1$ 根， $[1,n-1]$ 首尾两两合并)。

点击以显示 ⇲

点击以隐藏 ⇱

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		if(n&1)printf("%d\n",n/2+1);
		else printf("%d\n",n/2);
	}
	return 0;
}

B. Magical Calendar

一周可以有 $1$ 至 $r$ 天，在格子日历上涂色连续 $n$ 天（要求形状是联通的），问可以有多少形状

一周 $k$ 天， $k < n$ 时可以贡献 $k$ 个方案， $k=n$ 时 $1$ 个， $k > n$ 时无。

点击以显示 ⇲

点击以隐藏 ⇱

#include<bits/stdc++.h>
#define ll __int64
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		ll n,r,res;
		cin>>n>>r;
		if(r<n)res=(1+r)*r/2;
		else res=n*(n-1)/2+1;
		cout<<res<<endl;
	}
	return 0;
}

C. A Cookie for You

小甜饼， $a$ 个香草味， $b$ 个巧克力味。 $n$ 个第一种客人，香草味严格多时吃香草，否则吃巧克力。 $m$ 个第二种客人，香草味严格多时吃巧克力，否则吃香草。能否安排顺序使得每个顾客吃个小甜饼。

首先 $a+b < n+m$ 说明供不应求完全没可能。然后可以直接把缺什么要什么的第二类刁钻客人处理完，这样肯定更优，第一类客人是总能满足的。

点击以显示 ⇲

点击以隐藏 ⇱

#include<bits/stdc++.h>
#define ll __int64
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		ll a,b,n,m;
		cin>>a>>b>>n>>m;
		if(a+b<n+m){puts("NO");continue;}
		if(min(a,b)>=m)puts("YES");
		else puts("NO");
	}
	return 0;
}

D. Grid-00100

构造 $n\times n~01$ 矩阵，最小化 $f(A) = (\max(R)-\min(R))^2 + (\max(C)-\min(C))^2$ 其中 $R,C$ 分别是行、列元素的和。

随便幻想一下就会差不多知道是对角线方向螺旋式填充的那种，最大值与最小值的差都不会超过 $1$

点击以显示 ⇲

点击以隐藏 ⇱

#include<bits/stdc++.h>
#define ll __int64
#define sqr(x) ((x)*(x))
using namespace std;
int a[303][303],r[303],c[303];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,k,tot=0;
		scanf("%d%d",&n,&k);
		for(int turn=0;turn<n&&tot<k;turn++)
		{
			for(int i=0,j=turn;i<n&&tot<k;i++,j=(j+1<n)?j+1:0)
			a[i][j]=1,tot++,r[i]++,c[j]++;
		}
		int maxr=0,minr=500,maxc=0,minc=500;
		for(int i=0;i<n;i++)
		{
			maxr=max(maxr,r[i]),minr=min(minr,r[i]);
			maxc=max(maxc,c[i]),minc=min(minc,c[i]);
		}
		printf("%d\n",sqr(maxr-minr)+sqr(maxc-minc));
		for(int i=0;i<n;i++)
		{
			r[i]=c[i]=0;
			for(int j=0;j<n;j++)printf("%d",a[i][j]),a[i][j]=0;
			puts("");
		}
	}
	return 0;
}

E1. Asterism (Easy Version)

给定数组 $a_i$ ，可以指定一个排列作为顺序。Yuzu有一个数 $x$ ， $x\ge a_i$ 的情况下才能打过第 $i$ 关，并且进入下一关时 $x$ 增加 $1$ 。 $f(x)$ 表示初始数字 $x$ 时有多少种排列Yuzu能打完所有关卡 $n$ 。问有多少 $f(x)$ 不能被素数 $p$ 整除，输出这些数字。

当 $x>=\max_{a_i}$ 时，所有排列都可以， $n!$ 必能被小于 $n$ 的 $p$ 整除。故不考虑

当 $x<\max_{a_i-i+1}$ 时所有排列都不可以， $0$ 也可以被整除，故不考虑。

其余情况下我们考虑用乘法原理计算 $f(x)$ 。

$b_i$ 为 $a$ 中小于等于 $i$ 的元素数量。则对于第 $i$ 个位置，可选元素的个数是 $b_{x+i-1}-(i-1)$ 。

$f(x)=\prod_1^nb_{x+i-1}-(i-1)$

E2. Asterism (Hard Version)

数据范围增大后不能再暴力计算。但观察一下可以发现在上述有效范围内如果 $f(x_0)$ 可以被整除，那对于 $x > x_0,f(x)$ 也可以被整除。于是就可以二分一下位置。

简述为什么：设 $C_i(x)=b_{x+i-1}-(i-1)$ 。可以发现 $i$ 每次增加，它最多只能减少 $1$ 。对于同个 $x$ ，所有 $C_i(x)$ 的值必然填满一个区间，且当 $i=n$ 它是必然减少到 $1$ 的，另只要存在 $C_i(x)\ge p$ 那 $f(x)$ 必可被整除。而 $C_i(x)$ 是随 $x$ 的增大而增大的，故二分条件成立。

点击以显示 ⇲

点击以隐藏 ⇱

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,p,a[100005];
bool check(int k)
{
	for(int i=1,j=1;j<=n;j++)
	{
		while(i<=n&&a[i]<=k+j-1)i++;
		if(i-j>=p)return 1;
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	int st=0;
	for(int i=1;i<=n;i++)st=max(st,a[i]-i+1);
	int l=st,r=a[n],res;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))r=mid-1,res=mid;
		else l=mid+1;
	}
	printf("%d\n",res-st);
	for(int i=st;i<res;i++)printf("%d ",i);
	puts("");
	return 0;
}

CVBB ACM Team

目录

A. Magical Sticks

B. Magical Calendar

C. A Cookie for You

D. Grid-00100

E1. Asterism (Easy Version)

E2. Asterism (Hard Version)

CVBB ACM Team

用户工具

站点工具

目录

A. Magical Sticks

B. Magical Calendar

C. A Cookie for You

D. Grid-00100

E1. Asterism (Easy Version)

E2. Asterism (Hard Version)

页面工具