中秋欢乐赛#28 不正经题解

userId_undefined

暑 假 神（开学祭

秩序白银

2024-09-23 13:35:04

发布于：上海

135阅读
0回复
0点赞

23:59:00。

T1

按照题意模拟即可。根据 C++11 的新语法，max 函数可以传一个大括号包裹的初始化列表了，这样写会方便很多。注意包含 <algorithm> 头文件。

int main(){
	int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
	printf("%d\n",max({a,b,c,d}));
	
	return 0; 
}

T2

按照题意模拟即可。对于提到的三种运算，我们可以用 C++ 内置的函数实现。注意包含 <cmath> 头文件。

int main(){
	char s[10];double n;
	scanf("%s%lf",s,&n);
	int ans=0;
	switch(s[0]){
		case 'c':ans=ceil(n);break;
		case 'f':ans=floor(n);break;
		case 'r':ans=round(n);break;
	}
	printf("%d\n",ans);
	
	return 0; 
}

T3

按照题意模拟即可。买一个东西，我们就从余额中扣除相应费用。如果结果非负，说明我们买得起，反之不足。

int main(){
	int n,x,y;scanf("%d%d",&n,&x);
	for(int i=1;i<=n;i++){
		scanf("%d",&y);
		x-=y;
	}
	puts(x>=0?"YES":"NO");
	
	return 0; 
}

T4

由于要总数最少又各不相同，我们可以为第一人安排 11 宝石，第二人安排 22 宝石……第 nn 人安排 nn 宝石。显然没有更优的解了。结果为从 11 到 nn 的和，也就是 ∑i=1ni\sum\limits_{i=1}^ni。可以化简为 n×(n+1)2\dfrac{n\times(n+1)}2。

证明：归纳法。

基本步：当 n=1n=1 时，∑i=1ni=n×(n+1)2=1\sum\limits_{i=1}^ni=\dfrac{n\times(n+1)}{2}=1。

归纳步：当 n>1n>1 时，

∑i=1ni=∑i=1n−1i+n=(n−1)×n2+n=(n−1)×n+2n2=n×(n+1)2\begin{aligned}{} &\sum_{i=1}^ni\\ =&\sum_{i=1}^{n-1}i+n\\ =&\frac{(n-1)\times n}2+n\\ =&\frac{(n-1)\times n+2n}2\\ =&\frac{n\times(n+1)}2 \end{aligned}

证毕。

int main(){
	int n;scanf("%d",&n);
	printf("%d\n",n*(n+1)/2);
	
	return 0; 
}

T5

瞪眼法得结果 ∑i=1n∑j=1ij\sum\limits_{i=1}^n\sum\limits_{j=1}^ij 为 n×(n+1)×(n+2)6\dfrac{n\times(n+1)\times(n+2)}6。

证明：归纳法。

基本步：当 n=1n=1 时，∑i=1n∑j=1ij=n×(n+1)×(n+2)6=1\sum\limits_{i=1}^n\sum\limits_{j=1}^ij=\dfrac{n\times(n+1)\times(n+2)}6=1。

归纳步：当 n>1n>1 时，

∑i=1n∑j=1ij=∑i=1ni×(i+1)2(T4结论)=∑i=1n−1i×(i+1)2+n×(n+1)2=(n−1)×n×(n+1)6+n×(n+1)2=(n−1)×n×(n+1)6+3n×(n+1)6=n×(n+1)×(n+2)6\begin{aligned}{} &\sum_{i=1}^n\sum_{j=1}^ij\\ =&\sum_{i=1}^n\frac{i\times(i+1)}2\qquad\text{(T4结论)}\\ =&\sum_{i=1}^{n-1}\frac{i\times(i+1)}2+\frac{n\times(n+1)}2\\ =&\frac{(n-1)\times n\times(n+1)}6+\frac{n\times(n+1)}2\\ =&\frac{(n-1)\times n\times(n+1)}6+\frac{3n\times(n+1)}6\\ =&\frac{n\times(n+1)\times(n+2)}6 \end{aligned}

证毕。

int main(){
	int n;scanf("%d",&n);
	printf("%d\n",n*(n+1)*(n+2)/6);
	
	return 0; 
}

T6

代码入门，思维入门-，读题 IOI+

首先要知道的是硬盘大小是按照千进制算的，平常使用是按照 2102^{10} 进制算的。而它给你的是硬盘大小，所以按千进制算。

接下来就很简单了：转换单位，比较，找最大值，保存过程性答案，输出。值得注意的是不开 long long 见祖宗。

int main(){
	int n;ll xx,x=-1;char k;
	scanf("%d",&n);
	while(n--){
		char s[5];
		ll y,yy;
		scanf("%lld%s",&y,s);
		yy=y;
		switch(s[0]){
			case 'G':y*=1000;
			case 'M':y*=1000;
			case 'K':y*=1000;
		}
		if(y>=x){
			x=y;
			xx=yy;
			k=s[0];
		}
	}
	printf("%lld %c",xx,k);
	if(k!='B')putchar('B');
	
	return 0; 
}

T7

正常写法有手就能写，这里给一个不太正常的。（锻炼大家的 CSP 初赛阅读程序，包不准它真的给你这样马蜂氢锌的代码呢）

int main(){
	int cnt=0;char ch;
	while(((ch=getchar())!='a')||((cnt++)&0))if(ch==EOF)goto end;
	while(((ch=getchar())!='c')||((cnt++)&0))if(ch==EOF)goto end;
	while(((ch=getchar())!='g')||((cnt++)&0))if(ch==EOF)goto end;
	while(((ch=getchar())!='o')||((cnt++)&0))if(ch==EOF)goto end;
	end:puts(!(cnt^4)?"YES":"NO");
	
	return 0; 
}

我们可以拆开看：（见注释）

int main(){
	int cnt=0;char ch; // 定义
	while(((ch=getchar())!='a') // 字符不为 a
          ||((cnt++)&0) // 短路到 cnt 自增，与 0 保证退出循环
         )
      if(ch==EOF) // 输入结束了，离开
        goto end;
	while(((ch=getchar())!='c')||((cnt++)&0))if(ch==EOF)goto end;
	while(((ch=getchar())!='g')||((cnt++)&0))if(ch==EOF)goto end;
	while(((ch=getchar())!='o')||((cnt++)&0))if(ch==EOF)goto end;
  // 以上三份不一一解释
	end:puts(!(cnt^4) // cnt^4可以视为cnt!=4，取反就是cnt==4
             ?"YES": // 相同就是YES
             "NO"); // 否则就是NO 
	
	return 0; 
}

这样就好理解多了。

T8

给一个时间复杂度低于 O(nlog⁡n)O(n\log n) 的算法。

首先排序。有人问排序不就 O(nlog⁡n)O(n\log n) 了吗？答曰：基数排序更优。用2^8 做基数，可以吃到位运算和 Cache 的双重优化，见 [WC 2017] 挑战。

然后去重。用快慢指针（物理）即可， std 函数同款。

最后在所有里面，去掉出现过的，就是没出现过的（和）。

卡卡常，开个火车头。78ms，最优解榜一。基数排序就不放了，赛事 5KB 的长度限制恶心到了我，给代码来了极限压行。

u32 a[200005];
void unique(int& n){
	u32*slow=a+1,*to=a+1+n,*fast=a+1;
	while(fast!=to)++fast,((*slow)^(*fast))&&(*++slow=*fast);
	n=slow-a;
}

int main(){
	int n;ll k;read(n);read(k);
	int kk=k;
	k=k*(k+1)/2;
	for(register int i=1;i<=n;i++)read(a[i]);
	sort(a+1,n),unique(n);
	for(register int i=1;i<=n&&a[i]<=kk;i++)k-=a[i];
	printf("%lld\n",k);
	return 0; 
}
userId_undefined
去预览
0/2000

全部评论 8

热门讨论