A 一个美妙的旅程

思路

直接输出。

代码

#include <stdio.h>
int main()
{
    printf("Have a good day!");
    return 0;
}

B 最令人高兴的旅行计划

思路

简略发现两人都喜爱的景点对答案的奉献为 $2$ ，只要一个人喜爱的景点对答案的奉献为 $0$ ，二人都不喜爱的景点对答案的共享是 $- 2$ ，所以咱们只需要计算出有多少个两人都喜爱的景点 $c n t$ ，然后答案即为 $2cnt2\times cnt$ 。

代码

#include <stdio.h>
int n,x,y;
int cnt[200005];
int main()
{
	scanf("%d%d%d",&n,&x,&y);
	for (int a,i=1;i<=x;++i)
	{
		scanf("%d",&a);
		cnt[a]++;
	}
	for (int a,i=1;i<=y;++i)
	{
		scanf("%d",&a);
		cnt[a]++;
	}
	int ans=0;
	for (int i=1;i<=n;++i)
		if (cnt[i]==2) ans+=2;
	printf("%d\n",ans);
	return 0;
}

C 简略博弈游戏

思路

假如 $N$ 的个位值为 $0$ ，则先手必输，不然先手必胜。理由如下：

假如当时剩下的瓜子数的个位 $t$ 不是 $0$ ，就拿走 $t$ 个瓜子。这样的话假如对手还能进行操作，他操作后剩下瓜子数量的个位必定不是 $0$ ，还能够用同样的策略进行操作。直到对手不能进行操作为止。

数据规模较小，假如找不到上述的简略规律也能够用动态规划解决该问题。

代码

#include <stdio.h>
int main()
{
    int T,n;
    for (scanf("%d",&T);T--;)
        if (scanf("%d",&n),n%10==0) printf("Wumeinv\n");
        else printf("Ice_teapoy\n");
    return 0;
}

D 以fibonacci数列摆放的花

思路

奇数+奇数=偶数

奇数+偶数=奇数

所以斐波那契数列的奇偶性为
奇、奇、偶、奇、奇、偶、奇、奇、偶、奇、奇、偶……

所以本题的答案为 $n−⌊n3⌋n-\lfloor\frac{n}{3}\rfloor$ 。

代码

#include <stdio.h>
int main()
{
    int T;
    for (scanf("%d",&T);T--;)
    {
        long long n;
        scanf("%lld",&n);
        printf("%lld\n",n-n/3);
    }
    return 0;
}

E 博物馆门票

思路

小学数字题 qwq

输出 $min(1.6x,max(⌊kx⌋x,2x)2)min(1.6x,\frac{max(\lfloor\frac{k}{x}\rfloor\times x,2x)}{2})$ 。

简略发现买四张门票来打五折相当于不打折，所以咱们最多买三张票。所以可能挑选的计划有：

买两张学生票，答案能够取 $1.6 x$ 。
买两张成人票打五折，当 $2x≥k2x\ge k$ 时，答案能够取 $x$ 。
买三张成人票打五折，当 $3x≥k3x\ge k$ 时，答案能够取 $1.5 x$ 。

代码

#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
	int x,k;
	scanf("%d%d",&x,&k);
    if (2*x>=k) printf("%.2lf\n",x*1.0);
    else if (3*x>=k) printf("%.2lf\n",x*1.5);
    else printf("%.2lf\n",x*1.6);
	return 0;
}

F 爬山

思路

简略发现并不会来回走……

令 l[i] 表明第 i 座山往左最远能走到哪：

假如第 i 座山能去往第 i-1 座山，则 l[i]=l[i-1]+1
不然 l[i]=1。

同理求出第 i 座山往右最远能走到哪。两者中的最大值即为答案。

代码

#include <stdio.h>
const int N=200005;
int n,k,a[N];
int l[N],r[N]; 
int main()
{
	scanf("%d",&n);
	scanf("%d",&k);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	int ans=1;
	l[1]=r[n]=1;
	for (int i=2;i<=n;++i)
		if (a[i]+k>=a[i-1]) l[i]=l[i-1]+1;
		else l[i]=1;
	for (int i=n-1;i>=1;--i)
		if (a[i]+k>=a[i+1]) r[i]=r[i+1]+1;
		else r[i]=1;
	for (int i=1;i<=n;++i)
    {
        if (ans<l[i]) ans=l[i];
        if (ans<r[i]) ans=r[i];
    } 
	printf("%d\n",ans); 
	return 0;
}

G 祈福串珠

思路

性质一

一串串制造等价于一起制造多串。

具体来说，由于蓝桥 A 梦每次都是按序号把珠子给 Ity，当某个珠子不能串在第 $i$ 个珠串时，Ity 能够直接试图把它串在第 $i + 1$ 根绳子上，而不必把它还给蓝桥 A 梦等待下一轮制造。

性质二

一切的串串首不增串尾不减。

具体来说，记第 $i$ 个珠串最左边珠子的巨细为 $l_i$ ，最右边珠子的巨细为 $r_i$ 。则任一时间有

l1≥l2≥l3≥…r1≤r2≤r3≤…l_1\ge l_2\ge l_3\ge…\\ r_1\le r_2\le r_3\le…

不然不满意制造规矩。

解法

综上所述，关于第 $t(1≤t≤n)t(1\le t\le n)$ 颗珠子巨细为 $a_t$ ：

在 $l$ 数组中二分一个最小值 $i$ 满意 $l_i>a_t$ 。
在 $r$ 数组中二分一个最小值 $j$ 满意 $r_j<a_t$ 。
若 $i < j$ ，珠子 $t$ 应该串在第 $i$ 根绳子的左端，更新 $l_i$ ；若 $i > j$ ，珠子 $t$ 应该串在第 $j$ 根绳子的右端，更新 $r_j$ ；不然，珠子 $t$ 应该串在新的空绳子上。

简略发现更新不会影响数组 $l$ 和 $r$ 的单调性，思路类似于最长上升子序列的二分解法。顺便计算答案即可。

update：有群友说直接二分珠子第一个不被包括的珠串就能够了，我感觉非常对，可是代码是我的旧思路懒得改了（

代码

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=200005;
int n;
int a[N],b[N],tot,cnt[N];
int main()
{
	scanf("%d",&n);
	for (int i=1,x,aa,bb,l,r,mid;i<=n;++i)
	{
		scanf("%d",&x);
		if (tot==0)
		{
			cnt[++tot]=1;
			a[1]=b[1]=x;
			continue;
		}
		if (a[tot]>x)
		{
			for (l=1,r=tot;l!=r;)
			{
				mid=l+r>>1;
				if (a[mid]>x) r=mid;
				else l=mid+1;
			}
			aa=l;
		}
		else aa=tot+1;
		if (b[tot]<x)
		{
			for (l=1,r=tot;l!=r;)
			{
				mid=l+r>>1;
				if (b[mid]<x) r=mid;
				else l=mid+1;
			}
			bb=l;
		}
		else bb=tot+1;
		if (aa==bb)
		{
			cnt[++tot]=1;
			a[tot]=b[tot]=x;
		}
		else if (aa<bb) a[aa]=x,cnt[aa]++;
		else b[bb]=x,cnt[bb]++;
	}
	int maxx=1;
	for (int i=1;i<=tot;++i) maxx=max(maxx,cnt[i]);
	printf("%d %d",tot,maxx);
	return 0;
}

H 简略的问题

思路

全场最难的题，思路比较长且难想可是没什么超纲知识点所以还是放上来了 qwq

引理一

设 $A, B$ 是恣意两个不同的有限调集，则 $2∣A∩B∣∣A∪B∣≤∣A∣2+∣B∣2−12|A\cap B|\times|A\cup B|\le |A|^2+|B|^2-1$ 。当且仅当 A 和 B 存在包括关系，且两者元素个数相差 $1$ 时等号建立。下面给出证明：

令
$∣A∩B∣=x∣A∖(A∩B)∣=y∣B∖(A∩B)∣=z|A\cap B|=x\\ |A\setminus(A\cap B)|=y\\ |B\setminus(A\cap B)|=z$
则
$x,y,z∈Ny+z≥1∣A∣=x+y∣B∣=x+z∣A∪B=x+y+z∣x,y,z\in N\\ y+z \ge 1\\ |A|=x+y\\ |B|=x+z\\ |A\cup B=x+y+z|$
带入原式可得
$∣A∣2+∣B∣2−2∣A∩B∣∣A∪B∣=(x+y)2+(x+z)2−2x(x+y+z)=y2+z2≥1\begin{aligned} &|A|^2+|B|^2-2|A\cap B|\times|A\cup B|\\ =&(x+y)^2+(x+z)^2-2x(x+y+z)\\ =&y^2+z^2\ge 1 \end{aligned}$
当且仅当 $y$ 和 $z$ 分别为 $0$ 和 $1$ 时，等号建立。

引理二

记 $1,2,…,n{1,2,\dots,n}$ 的全部子集为 $A1,A2,…,A2nA_1,A_2,\dots,A_{2^n}$ ，则必定存在 ${A}$ 的一个摆放 $B1,B2,…,B2n{B_1,B_2,\dots,B_{2^n}}$ 使得 $Bi(1≤i≤n)B_i(1\le i\le n)$ 和 $B_{i \mod 2^n +1}$ 存在包括关系，且元素数量之差为 $1$ 。下面给出证明：

当 $n = 2$ 时，调集 ${1,2}$ 的四个子集摆放成 $∅,{1},{1,2},{2}\emptyset,\{1\},\{1,2\},\{2\}$ 即可满意条件。

假设出题对 $n$ 建立，且 $B1,B2,…,B2nB_1,B_2,\dots,B_{2^n}$ 是一个满意条件的摆放，则关于 $n + 1$ ，取以下摆放方式即可满意条件：
$B1,B2,…,B2n,B2n∪{n+1},B2n−1∪{n+1},…,B1∪{n+1}B_1,B_2,…,B_{2^n},B_{2^n}\cup \{n+1\},B_{2^n-1}\cup \{n+1\},\dots,B_1\cup \{n+1\}$
由数学归纳法，出题得证。

引理三

∑k=0nk2Cnk=n(n+1)2n−2\sum_{k=0}^n k^2 C_n^k=n(n+1)2^{n-2}

证明如下：

$∑k=0nk2Cnk=∑k=0nknCn−1k−1=n[∑k=0n(k−1+1)Cn−1k−1]=n[∑k=0n(k−1)Cn−1k−1+∑k=0nCn−1k−1]=n[∑k=0n(n−1)Cn−2k−2+2n−1]=n[(n−1)2n−2+2n−1]=n(n+1)2n−2\begin{aligned} &\sum_{k=0}^n k^2\times C_n^k\\ =&\sum_{k=0}^n k\times n\times C_{n-1}^{k-1}\\ =&n[\sum_{k=0}^n(k-1+1)\times C_{n-1}^{k-1} ]\\ =&n[\sum_{k=0}^n(k-1)\times C_{n-1}^{k-1} + \sum_{k=0}^nC_{n-1}^{k-1}]\\ =&n[\sum_{k=0}^n(n-1)\times C_{n-2}^{k-2} + 2^{n-1}]\\ =&n[(n-1)\times 2^{n-2}+2^{n-1}]\\ =&n\times(n+1)\times 2^{n-2} \end{aligned}$

综上所述：

由引理一可知

2n+1∣2−12=∑i=12n∣Ai∣2−2n−1=∑k=0nCnkk2−2n−1\begin{aligned} &\sum_{i=1}^{2^n} |A_i\cap A_{i\mod 2^n+1}|\times|A_i\cup A_{i\mod 2^n+1}|\\ \le&\sum_{i=1}^{2^n} \frac{|A_i|^2+|A_{i\mod 2^n+1}|^2-1}{2}\\ =&\sum_{i=1}^{2^n} |A_i|^2-2^{n-1}\\ =&\sum_{k=0}^n C_n^k\times k^2-2^{n-1} \end{aligned}

运用引理二中的摆放方法能够使得等号建立，又由引理三可知， $H_n$ 的最大值为

∑k=0nCnkk2−2n−1=n(n+1)2n−2−2n−1\sum_{k=0}^n C_n^k\times k^2-2^{n-1}=n(n+1)2^{n-2}-2^{n-1}

所以本题的答案为对每个问询的 $n$ ，输出 $(n2+n−2)2n−2(n^2+n-2)\times2^{n-2}$ 即可。

代码

#include <stdio.h>
using namespace std;
using LL=long long;
const LL mod=1e9+7;
LL poww(LL a,LL b)
{
	a%=mod;
	LL ans=1;
	for (;b;b>>=1,a=a*a%mod)
		if (b&1) ans=ans*a%mod;
	return ans;
}
int main()
{
	int T;
	LL n,t;
	for (scanf("%d",&T);T--;)
	{
		scanf("%lld",&n);
		if (n==1)
		{
			printf("0\n");
			continue;
		}
		t=poww(2,n-2);
		n%=mod;
		printf("%d\n",(n*n%mod+n+mod-2)%mod*t%mod);
	}
	return 0;
}

I 种瓜得瓜，种豆得豆

思路

第 $i(1≤i≤n)i(1\le i\le n)$ 棵气球当时的美味度是 $a_i$ ，咱们令 $b_i=k-a_i$ 表明第 $i$ 棵气球的最佳收成期限，一起也是最终收成期限。

从 $k - 1$ 到 $0$ 枚举当时时间 $t$ ，此时咱们能够挑选收成一切满意 $bi≥tb_i\ge t$ 的没有在未来被收成的气球。假设咱们挑选此时收成气球 $j$ ，那么对答案的奉献明显为 $k-b_j+t$ ，为了最大化答案，应该挑选收成 $b$ 值最小的气球。

对 $b$ 数组进行过排序，枚举当时时间 $t$ 的一起双指针将符合条件 $b_i>t$ 的气球压进栈里，每个时间收成栈顶的气球即可。

代码

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
const int N=200005;
using LL=long long;
LL ans;
int a[N],b[N],stk[N],n,p,k;
int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=k-a[i];
	sort(b+1,b+1+n);
	for (int t=k-1,j=n;t>=0;--t)
	{
		while (j>=1&&b[j]>=t) stk[++p]=b[j--];
		if (p) ans+=k-stk[p--]+t;
	}
	printf("%lld\n",ans);
	return 0;
}

J 数组划分

思路

对 $k$ 进行分类讨论：

若 $k = 1$ 则无法将任何元素别离成一个单独子段，故取一切元素最小值。
若 $k = 2$ 则能够将第一个元素或许最终一个元素别离成单独的一个子段，故取第一个和最终一个的较大值。
若 $\ge 3$ 则能够别离出任何一个元素作为单独的子段，故取一切元素最大值。

发现数据水了被一堆人直接输出数组最大值碾过（

代码

#include <stdio.h>
int a[200005];
int main()
{
	int n,k,minn=1e9+1,maxx=0;
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		if (a[i]>maxx) maxx=a[i];
		if (a[i]<minn) minn=a[i];
	}
	if (k>=3) printf("%d",maxx);
	else if (k==1) printf("%d",minn);
	else if (a[1]>a[n]) printf("%d",a[1]);
	else printf("%d",a[n]);
    return 0;
}

总结

榜单看上去不太丑，前排很有区分度 qwq

可是中档题略少，看起还还是让相当一部分同学在赛中感到无聊了对不起 orz

不太想出原题或许板子题，所以看起来可能会有点像是脑筋急转弯 orz

发现有部分同学彻底不理解多测（在一个测验点中输入 $T$ 组测验数据），导致原本能够做出的题写不出来，非战之罪，也很对不起（

原本以为昨天赛中没有什么锅的可是今日又查看代码才发现 J 数据弱了orz

【ZKNU】2023“华杉杯”ACM校赛题解

A 一个美妙的旅程

思路

代码

B 最令人高兴的旅行计划

思路

代码

C 简略博弈游戏

思路

代码

D 以fibonacci数列摆放的花

思路

代码

E 博物馆门票

思路

代码

F 爬山

思路

代码

G 祈福串珠

思路

代码

H 简略的问题

思路

代码

I 种瓜得瓜，种豆得豆

思路

代码

J 数组划分

思路

代码

总结

作者信息

【ZKNU】2023“华杉杯”ACM校赛题解

A 一个美妙的旅程

思路

代码

B 最令人高兴的旅行计划

思路

代码

C 简略博弈游戏

思路

代码

D 以fibonacci数列摆放的花

思路

代码

E 博物馆门票

思路

代码

F 爬山

思路

代码

G 祈福串珠

思路

代码

H 简略的问题

思路

代码

I 种瓜得瓜，种豆得豆

思路

代码

J 数组划分

思路

代码

总结

相关文章

Flutter 实现渐变弧形进度条

关于 Serverless 应用架构对企业价值的一些思考

NLP教程(3) | 神经网络与反向传播

AIGC的浪潮下，文本生成发展得怎么样了？

作者信息