欢乐赛#34全题解
2024-11-18 18:09:57
发布于：四川
第一次写题解，如有不好的地方，望多多包含多多指教
许愿成为优秀题解
T1 数组
先看范围
数据：都在1e5之内，所以可以用数组（甚至题目名称就叫数组）
时间复杂程度：O（n）
思路：用一个数组记录每次给出的数，如果没被记录则a++
代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+50;
bool Bool[N];
int a=0;
int main(){
int T;
for(cin>>T;T;T--){
int h;
cin>>h;
if(Bool[h]==0){
a++;
Bool[h]++;
}
}
cout<<a;
}
T2 走路
一道简单的模拟
数据：指令数是1e5，字母4个
时间复杂度： O（n）
思路：模拟就行
代码：
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int a,x=0,y=0;
string str;
cin>>a>>str;
for(int i=0;i<a;i++){
if(str[i]=='D') y--;
if(str[i]=='U') y++;
if(str[i]=='R') x++;
if(str[i]=='L') x--;
}
cout<<"("<<x<<","<<y<<")";
}
T3 休息日
哔哔：一道题占了1/3的分数，然后默认cout<<1骗分，结果一看，哇，ioi赛制，被自己整笑了
言归正传，先分析一下，数据量是1e9，所以要么是O（n），要么是数学方法某人以为是递推，推了半天，被推死到沙滩上了
但是我研究了半天，发现解出来太费时间了，故放弃，选择打表大法
先用暴力算法解（大概是O（n方））出10到20
然后我惊奇的发现
抛开重复的不谈，
取12，2 和15，3可得y=x/3-2
将18代入验证，成立，所以答案就出来了
代码：
#include <iostream>
#include <stdio.h>
#define LL long long
using namespace std;
int main()
{
int n;
cin>>n;
cout<<n/3-2;
return 0;
}
没错就是这么简单
然后附上我的数学思路
设选的两天为a，b，可得
d1=2a-b-1
d2=b-a-1
d3=n-b-1
然后设min里的三项为X,Y,Z；
可得
X=abs(2a-b)
Y=abs(n-2b+a)
Z=abs(n-a-b)
在分别假设X，Y，Z最小，然后根据所得的n与a，b的关系求出最大值在进行比较，就可以证明了
如：当n>2b,n>3a时
X最小，Xmax=1/3n+2/1n
理论上可行，所以仅供参考，如有误求轻骂
T4 质数个数
数据 1e6，所以可以暴力
时间复杂程度：O（根号n*n）暴力是因为数据支持，用筛法会更快
思路：函数zs：先特判，然后根据质数的特性分别对每个数使用试除法
main 依次遍历直到n，记录质数个数
代码：
#include <iostream>
#include <stdio.h>
#define LL long long
#include <vector>
#include <cmath>
using namespace std;
bool zs(int n) {
if (n<=1) return 0;
if (n==2) return 1;
if (n%2==0) return 0;
for (int i=3; i<=sqrt(n);i+=2) {
if(n%i==0) {
return 0;
}
}
return 1;
}
int main()
{
int n;
cin>>n;
if(n==1){
cout<<0;
return 0;
}
int h=0;
for (int i=2;i<=n;i++) {
if (zs(i)){
h++;
}
}
cout<<h;
return 0;
}
T5 好串
数据：T在100以内，n在1e4以内，所以可以使用数组来记录
时间复杂度 O（T*n）
思路：多询问题目
单次询问：把两个字符串按位把字符存进Book数组，然后遍历查看是Book是否一样
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=127;
int main(){
int T;
for(cin>>T;T;T--){
int book[2][N]={0};
int len;
string str1,str2;
cin>>len>>str1>>str2;
for(int i=0;i<len;i++){
book[0][int(str1[i])]++;
book[1][int(str2[i])]++;
}
bool l=1;
for(int i=33;i<=126;i++){
if(book[0][i]!=book[1][i])
l=0;
}
if(l==1){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
return 0;
}
T6 期中考试
继续祝大家期中考试高分but我已经寄了
本人没有什么实力，如有错误望大佬多多指教
许愿成为优秀题解
全部评论 3
sqrt(n)虽然也是O(1)，但是常数巨大（时间是一次普通运算的数十倍甚至上百倍），所以建议你用
for(int i=3; i*i<=n; i++)11小时前 来自 广东
0
有帮助，赞一个