中秋欢乐赛#28 不正经题解
2024-09-23 13:35:04
发布于：上海
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
由于要总数最少又各不相同，我们可以为第一人安排 宝石，第二人安排 宝石……第 人安排 宝石。显然没有更优的解了。结果为从 到 的和，也就是 。可以化简为 。
证明：归纳法。
基本步：当 时，。
归纳步：当 时，
证毕。
int main(){
int n;scanf("%d",&n);
printf("%d\n",n*(n+1)/2);
return 0;
}
T5
瞪眼法得结果 为 。
证明：归纳法。
基本步：当 时，。
归纳步：当 时，
证毕。
int main(){
int n;scanf("%d",&n);
printf("%d\n",n*(n+1)*(n+2)/6);
return 0;
}
T6
代码入门，思维入门-，读题 IOI+
首先要知道的是硬盘大小是按照千进制算的，平常使用是按照 进制算的。而它给你的是硬盘大小，所以按千进制算。
接下来就很简单了：转换单位，比较，找最大值，保存过程性答案，输出。值得注意的是不开 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
给一个时间复杂度低于 的算法。
首先排序。有人问排序不就 了吗？答曰：基数排序更优。用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;
}
全部评论 8
什么数学大佬
暴论：题目能过就行要啥优化代码
我T4、T5我模拟法过的
然后T7是用python的re（正则表达式）库过的你这题解写的真的很棒！
（要不要来看看我的题解https://www.acgo.cn/discuss/study/27943）2024-09-16 来自 浙江
3我C我就说T6代码老改不对（用1024），我以为他跟我讲那么详细原来的二进制怎么弄十进制又是怎么奸商还以为会有个1或0给我标注一下是二进制还是十进制，发现没有索性用二进制，还甜美以为自己怪聪明，结果连测试二都跑不了，甜美的怎么就不告诉一声统一是用1024还是1000
2024-09-20 来自 江苏
0
有帮助，赞一个