欢乐赛#26题解

暑假神（开学祭

2024-08-05 11:36:44

发布于：上海

201阅读

0回复

0点赞

本次欢乐赛挺简单的nia~
第一次抢到欢乐赛首 AK，真棒。

T1

模拟即可。如果 $n\geq 99$ ，输出 99+；否则输出 $n$ 。

#include <cstdio>
using namespace std;

int main(){
	int n;scanf("%d",&n);
	if(n>=99) puts("99+");
	else printf("%d",n);
	
	return 0;
}

T2

模拟即可*2。如果 $n>0$ ，输出 YES，否则输出 NO。

#include <cstdio>
using namespace std;

int main(){
	int n;scanf("%d",&n);
	puts(n>0?"YES":"NO");
	
	return 0;
}

T3

模拟即可*3，但是更复杂了。仔细读题：

那么他会给你这 $k$ 杯奶茶中的每一杯打 $7$ 折（向下取整）哦~

也就是说，打折后的单价为 $\lfloor0.7\times v\rfloor$ ，这 $k$ 杯的总价是 $k\times\lfloor0.7\times v\rfloor$ 而不是 $\lfloor k\times0.7\times v\rfloor$ ，单价要先取整再乘数量！
然后我们要买 $n$ 杯奶茶，这 $n$ 杯奶茶中有几个 $k$ 杯奶茶呢？当然是 $\lfloor \dfrac nk\rfloor$ 。剩下的 $n \bmod k$ 杯奶茶就需要按原价 $v$ 元购买。总价即为 $\lfloor\dfrac nk\rfloor\times k\times\lfloor0.7\times v\rfloor+(n \bmod k)\times v$ 。

最后与 $m$ 比较输出即可。

#include <cstdio>
using namespace std;
#define abs(X) ((X)>=0?(X):(-(X)))

int main(){
	#define int long long
	int n,m,k,v;scanf("%lld%lld%lld%lld",&n,&m,&k,&v);
	int cost;
	if(n>=k) cost=(int)(0.7*v)*(n/k*k)+n%k*v;
	else cost=n*v;
	puts(cost<=m?"YES":"NO");
	printf("%lld",abs(cost-m));
	
	return 0;
}

T4

疑为错题。输入数据量最大约为 $10^9$ 字节的数量级。

当然数据水，我们的普通程序优化一下就过了，注释在代码里。

#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
// 臭名昭著的火车头，NOI 系列赛事不可用

#include <cstdio>
#include <cctype>
using namespace std;

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
// 极快的 fread 字符快读

inline void rd(int& x) { // 整形快读，引用参数比返回值快
	x=0;register char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
}

signed main(){
	register int n,x,ans=-1;rd(n),rd(x);
	for(register int i=1,t;i<=n;i++)
        rd(t),
		x>=t&&!(t&1)  && // 判断条件：比 x 小，偶数
			(ans=t); // 相当于 if(x>=t&&t%2==0)ans=t;
	
	printf("%d\n",ans); // 输出量小不用快写
		
	return 0;
}

T5

可以任意次交换字符串中任意两个字符的位置，换句话说就是可以随意重排这个字符串。因此考虑把两个字符串变为有序，相同即为 YES，不同即为 NO。

实现时可以考虑使用桶计数字符。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;

int buc[256];
int main(){
	char s[1005];scanf("%s",s);
	int l=strlen(s);
	for(int i=0;i<l;i++) buc[s[i]]++;
	scanf("%s",s);
	l=strlen(s);
	for(int i=0;i<l;i++) buc[s[i]]--;
	for(int i=32;i<=128;i++){
		if(buc[i]!=0){
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	
	return 0;
}

T6

吐槽在前，数据过水。考虑这份显然错误的桶计数的代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;

unordered_map<int,int>mp;

int buc[256];
int main(){
	char s[1005];scanf("%s",s);
	int l=strlen(s);
	for(int i=0;i<l;i++) buc[s[i]]++;
	scanf("%s",s);
	l=strlen(s);
	for(int i=0;i<l;i++) buc[s[i]]--;
	
	for(int i=32;i<=128;i++){
		if(buc[i]>0){
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	
	return 0;
}

输入：

yp
npy

代码的输出：YES，显然错误。~~最离谱的还是这份代码能 AC，所以数据确实应该加强。~~

本题正解应为循环与双指针。初始 ps 与 pt 分别取 $s$ 与 $t$ 的串首，每一次循环贪心地移动 pt 至下一个 $t$ 中与 ps 指向的字符相同的位置，随后 ps 与 pt 均需自增。若 pt 已经指向串尾，ps 仍失配，则 $s$ 不是 $t$ 的子序列，否则是。时间复杂度 $O(n)$ 。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;

int main(){
	char s[1005],t[1005];
    scanf("%s%s",s,t);
	int ls=strlen(s),lt=strlen(t);
	int ps=0,pt=0;
    while(ps<ls&&pt<lt){
        //printf("%d %d %d %d\n",ps,pt,ls,lt);
        while(pt<lt&&s[ps]!=t[pt])pt++;
        ps++,pt++;
    }
    //printf("%d %d %d %d",ps,pt,ls,lt);
	if(pt==lt&&ps!=ls||pt>lt)puts("NO");
    else puts("YES");
	return 666; // 不要复制哦
}

T7

某人刚想开始打十六进制转十进制，忽然看见这句话：

如果你知道某些技巧的话，这道题会非常简单。

某人快速思索，想起了 C 风格输入输出有一个神奇的类型限定符：%X。这个限定符可以输入输出十六进制数，真神奇！

于是这就变成了 a+b problem。

#include <cstdio>
using namespace std;

int main(){
	int a,b;
	scanf("%X%X",&a,&b);
	printf("%X",a+b);
	return 0;
}

某人试了样例，发现输出少了前缀 0X。这好办，输出时多加一个 0X 前缀就行了。

所以这仍然是 a+b problem。

#include <cstdio>
using namespace std;

int main(){
	int a,b;
	scanf("%X%X",&a,&b);
	printf("0X%X",a+b);
	
	return 666; // 不要复制哦
}

T8

本次欢乐赛的压轴题，还是挺有难度的。暴力显然不行，因为 $O(n)$ 在 $n=10^{18}$ 下会超时。看起来是数学题，所以直接去想 $O(1)$ 。

首先问题好像很吓人，可以先容斥一波。 $[x,y]$ 中不能被 $a$ 整除且也不能被 $b$ 整除的数的个数，即为 $[x,y]$ 中数的个数，去掉能被 $a$ 整除的，再去掉能被 $b$ 整除的。这时能同时被 $a$ 和 $b$ 整除的就被算了两遍，要再加一遍，即再加上能同时被 $a$ 和 $b$ 整除的。小学数学告诉我们能同时被 $a$ 和 $b$ 整除相当于能被 $\operatorname{lcm}(a,b)$ 整除。所以问题分为四部分：

$[x,y]$ 中数的个数
$[x,y]$ 中能被 $a$ 整除的个数
$[x,y]$ 中能被 $b$ 整除的个数
$[x,y]$ 中能被 $\operatorname{lcm}(a,b)$ 整除的个数

第一个问题的答案显然是 $y-x+1$ 。现在考虑后面三个问题。

提示：接下来的这一段讨论中诸变量的意义与前文不同，请不要混淆。

要知道，一个连续区间中，一个数 $x$ 的倍数分布是等差的，公差为 $x$ 。所以使用等差数列的性质，我们需要的答案项数即为（首末项之差） $\div x+1$ 。而首项就是大于等于左端点的最小的 $x$ 的倍数，末项就是小于等于右端点的最大的 $x$ 的倍数。令左端点为 $l$ ，右端点为 $r$ ，首项为 $a$ ，末项为 $b$ ，根据倍数的定义，则有：

$\begin{cases} \lceil\frac lx\rceil x=a\\ \lfloor\frac rx\rfloor x=b \end{cases}$

可以试着去理性理解一下这个式子，应该可以理解。

由此得出结论：在 $[l,r]$ 中，能被 $x$ 整除的数有 $(\lfloor\frac rx\rfloor x-\lceil\frac lx\rceil x)\div x+1$ 个。可继续化简，当然不化简也没问题。

有了这个结论，后三问便可解决。相信写代码就不是难事了，接下来说几个坑。

1.不开 ____ ____ 见祖宗。不用我说罢。
2.过程中涉及浮点运算。而数据范围是 $10^{18}$ ，最大有效位数达到了 $19$ ，此时使用 double 类型会导致丢精度，然后听取 WA 声一片。正确的做法是使用 long double 类型，当然将过程中的浮点运算全部化为整形运算也不失为一种好的选择。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define int long long
int lcm(int a,int b){
	return a*b/__gcd(a,b);
}

signed main(){
    long long x,y,a,b;
    scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
    int len=y-x+1;
    int la=ceil(1.0l*x/a)*a,ra=floor(1.0l*y/a)*a;
    int cnta=(ra-la)/a+1;
    int lb=ceil(1.0l*x/b)*b,rb=floor(1.0l*y/b)*b;
    int cntb=(rb-lb)/b+1;
    int ab=lcm(a,b);
    int lab=ceil(1.0l*x/ab)*ab,rab=floor(1.0l*y/ab)*ab;
    int cntab=(rab-lab)/ab+1;
    printf("%lld",len-cnta-cntb+cntab);
    return 666; // 不要复制哦
}

后记

T4 数据范围什么鬼？如果想卡空可以改空间限制吧。

有帮助，赞一个

去预览

0/2000

全部评论 9

我是垃圾
最简
a, b = input().split()
print(f"0X{(int(a, 16) + int(b, 16)):X}")

2024-07-29 来自上海
1
- 暑假神（开学祭
  回复我是垃圾
  print(hex(sum(map(lambda x:int(x,16),input().split()))).upper())
  
  更简
  2024-07-30 来自上海
  0
暑假神（开学祭
再顶

2024-07-29 来自上海
1
- 复仇者_必胜啊（不加团队
  回复暑假神（开学祭
  快写能优化吗？
  
  void write(int x){ if(x>9) write(x/10); putchar(x%10+'0'); }
  6天前来自广东
  0
小ZUZU_童瑞琪专属奴隶
我就比你慢了3分钟

2024-07-29 来自广东
1
- 复仇者_ドラゴンコア
  回复小ZUZU_童瑞琪专属奴隶
  +1
  
  2024-07-29 来自浙江
  0
- 小ZUZU_童瑞琪专属奴隶
  回复复仇者_ドラゴンコア
  ?
  
  2024-07-29 来自广东
  0
大香蕉
我和“大香蕉树”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1815619424530272256

2024-07-31 来自浙江
0
大香蕉
我和“大香蕉树”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1815619424530272256

2024-07-30 来自浙江
0
复仇者_ドラゴンコア
只慢三分钟就发出来了

2024-07-29 来自浙江
0
- 复仇者_ドラゴンコア
  回复复仇者_ドラゴンコア
  破电脑该换了
  
  2024-07-29 来自浙江
  0
‮队团加不）ด้้童帅_者仇复
Wow

2024-07-29 来自湖南
0
小ZUZU_童瑞琪专属奴隶
召唤acjun

2024-07-29 来自广东
0
暑假神（开学祭
顶，卡时在九点发的：）

2024-07-29 来自上海
0

T1

T2

T3

T4

T5

T6

T7

T8

后记

全部评论 9

热门讨论