1. T1
1.1 知识点: 字符串，模拟，分类讨论
1.2 题意概述：给定一个学生某一年的年级 判定 某一次csp竞赛 这个学生是否能够参加
1. Csp-X 自 2017 年开始 只有 小学 3 年级 ~ 小学 6 年级 可以参加
2. csp-J 自 2000 年开始 只有 小学 3 年级 ~ 初中 3 年级 可以参加
3. csp-S 自 2000 年开始 只有 小学 3 年级 ~ 高中 3 年级 可以参加
1.3 做题思路
1. 转换 字符串 对应级别的大小写
2. 获取 比赛的年份 year
3. 根据 年份 x 将 年级y 换算为 year 当年的年级 grade
4. 根据不同的级别进行判断
1. 小学组 s[4]=='X'
1. year>=2017
2. grade>=3&&grade<=6 2. 初中组 1. year>=2000
2. grade>=3&&grade<=9 3. 高中组 1. year>=2000
2. grade>=3&&grade<=12
1.4 参考代码
#include
#include
using namespace std;
int main() {
int x,y;
string s;
cin>>x>>y;
cin>>s;
//1. 如果是小学组
//1.1 年份应该在2017之后
//1.2 比赛年份应该在三年级~六年级之间
//2 如果是初中组
//2.1 年份应该在 2000年后
//2.2 比赛年份应该在三年级 ~九年级之间
//3 如果是 高中组
//3.1 年份 应该在2000年后
//3.2 年级应该在 三年级~12年级之间
//因此我们发现 1. 判断级别 2 获取年份根据级别 判断年份是否合法 3 计算比赛年份 明明的年级 然后进行判断
int year = 0;
for(int i = 5;i<9;i++) { year*=10; year+=(s[i]-'0'); } if(x>year)
{
for(int i = year;i<x;i++)
{
y--;
}
}
else{
for(int i = x;i<year;i++) { y++; } } if(s[4]>='a'&&s[4]<='z') s[4] = s[4]-'a'+'A';//转换 大写
if(s[4]=='S')
{
if(year<2000)
{
cout<<"Not exis"; } else if(y>=3&&y<=12)
{
cout<<"Yes";
}
else if(y<3) cout<<"You are too young!";
else cout<<"You are older";
}
else if(s[4]=='J')
{
if(year<2000)
{
cout<<"Not exist"; } else if(y>=3&&y<=9)
{
cout<<"Yes";
}
else if(y<3) cout<<"You are too young!";
else cout<<"You are older";
}
else
{
if(year<2017)
{
cout<<"Not exist"; } else if(y>=3&&y<=6)
{
cout<<"Yes";
}
else if(y<3) cout<<"You are too young!";
else cout<<"You are older";
}
return 0;
}
2. T2
2.1 知识点：数组，循环嵌套，枚举
2.2 题意概述：
n个点 编号 1 ~ N, 对于每个节点找到一个离他距离最近的点，如果存在多个则找到编号最小的。
欧式距离公式：$$d(<x_1,y_1>,<x_2,y_2>) = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$
2.3 做题思路
1. 本题数据范围较小 只有100 所以 $$O(n^2)$$ 只有10000 次所以可以直接使用暴力解
2. 每次选择一个点 x ,距离 x 最近坐标在 1 ~ N 中。
1. 记录 最大值下标为 k
2. 初始化 k 为 1(或者 1 ~ N 任意值 每个坐标必然存在一个最远坐标，因此 无论如何都可以更新到最大值)
3. 如果选取坐标 y 如果 $$d(x,y)>d(x,k)$$ 更新 k 为 y(保证下标最小 )
1. 如果 下标最大 则 $$d(x,y)>=d(x,k)$$
2.4 参考代码
- pair<type,type> 是用于 存储序对 坐标的特殊数据类型 或stl
- pair<int,int> 存储两个为 int 类型的数据
- pair<int,string> 存储第一个为 int 类型的数据 第二个为 string 类型的数据
- pair<double,char> 存储第一个为 double 第二个为 char 的数据
- pair<string,pair<int,double>> 存储 第一个为 string 第二个 为 pair<int,double> 的数据
- pair具有两个元素 或者说成员 其中第一个元素为 first 第二个元素为 second
- pair<int,int> x = {1,2} 可以通过大括号进行初始化
- x.first = 3
- x.second = 5
- cout<<x.first<<" "<<s.second;
#include<bits/stdc++.h>
using namespace std;
pair<int,int> num[200];
double dis(int x,int y);
int main()
{
int n;
cin>>n;
for(int i = 1;i<=n;i++) { cin>>num[i].first>>num[i].second;
/*
int x,y;
cin>>y;
num[i] = {x,y};
*/
}
for(int i = 1;i<=n;i++)
{
int k = 1;
for(int j = 1;j<=n;j++) { if(dis(i,j)>dis(i,k)) k = j;
}
cout<<k<<endl; } return 0; } double dis(int x,int y) { int dx = num[x].first - num[y].first; int dy = num[x].second - num[y].second; return sqrt(dx*dx+dy*dy); } 3. T3 3.1 知识点 桶排序 模拟 3.2 题意概述 1. 一共初始有 n 块地 每一块地初始都有一颗萝卜 2. 每颗萝卜 都有对应的能量 3. 兔子一共要进行 q 次操作 4. 每次 选择 一个编号为 x 的菜地 做以下两种操作 - 如果当前 有一颗萝卜 消耗 y 的能量 把他拔出 并获得这颗萝卜的能量 - 如果当前 没有萝卜 种植一颗 能量为 y 的萝卜 3.3 做题思路 1. 建立 一个长度 为 1000000 的数组 作为桶 以及记录剩余能量 m 2. 输入 n 次 初始化 n 块 菜地 3. 重复 q 次操作 1. 如果 当前菜地 非空 则判定 当前 m 是否大于 y 1. 大于 说明能量充足 进行拔出 并获得对应的能量 2. 小于 能量不足 不进行拔出 2. 如果菜地为空 种植萝卜 对应位置能量等于 y 4. 1~n 遍历 n 块菜地 求出 n 的个数 3.4 参考代码 1. Scanf与cin的读入 1. 本题 (x,y) 的读入格式处理比较麻烦 2. 第一种使用char作为占位符 将符号作为char类型读入 char c; int x,y; cin>>c>>x>>c>>y>>c;
3. 使用scanf做格式化读入 但 按字符读入时scanf需要处理换行字符问题 所以在scanf之前需要加一个getchar吸收换行符
int x,y;
getchar();
scanf("(%d,%d)",&x,&y);
2. 数组必须开在全局变量
- 局部变量: 在任意大括号的变量 特别的 在内存 大括号内的变量称为 外层 同名变量的局部变量
- 局部变量 最多只能开到10000 的大小
- 全局变量 最大一维数组可以开到 1e8=>100000000
3. #define (x) (y) 可以将所有代码中的单词 x 替换为 y
- 如 #define x cout<<100; 则 x 就是输出100的意思
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N int(2e5+10)
int num[N];
int main()
{
int n,q,m;
cin>>n>>q>>m;
for(int i = 1;i<=n;i++) { cin>>num[i];
}
while(q--)//q下标用不到
{
int x,y;
getchar();
scanf("(%d,%d)",&x,&y);
if(num[x]>0)
{
if(m>=y)
{
m -=y;
m +=num[x];
num[x] = 0;
}
}
else num[x] = y;
}
int cnt = 0;
for(int i = 1;i<=n;i++) { cnt+=(num[i]>0);
}
cout<<m<<" "<<cnt<<endl;
return 0;
}
4. T4
4.1 知识点：高斯公式 排序
4.2 题意概述&&做题思路
根据题意其实这道题是想要 求出 $$P = \{num[i]|num[i]<=k~and~1<=i<=n\}$$,并对P去掉所有全部重复的元素，然后求和 在于 1~k之和取反。
- 首先，容易想到 这道题思路上好像可以用桶排序解决
1. 数组 大小最多可以开到 1e9 所以显然开不了这么大的数组
2. 但退而求其次 数组 开到 1e8 可以求出对应的 暴力解
- 这里 对于数据范围太大的元素 我们需要使用离散化 去重的方法
- 方法一：使用排序
- 方法二：使用unordered_set
4.3 参考代码
4.3.1 暴力小数据 50分
1. 对每个元素 打表 由于范围 太大 使用桶排枚举查询 次数太多 可以利用 元素个数2e5
2. 对于每个元素 x
1. 如果 出现过1次 直接跳过
2. 如果元素大小大于 k 直接 跳过(对于 k 小于 1e8的情况 桶排不会越界)
3. 否则说明当前元素出现一次 进行累加
#include<bits/stdc++.h>
using namespace std;
#define N int(1e8)
int num[N];
int main()
{
long long n,k;
cin>>n>>k;
long long sum = 0;
for(int i = 1;i<=n;i++) { int x; cin>>x;
if(num[x]||x>k) continue;
num[x]=1;
sum+=x;
}
cout<<(1+k)*k/2-sum;
return 0;
}
4.3.2 排序离散化
- 作为常用的基本去重手段 一般是对数组进行排序 每当相邻元素 不同 则对其中一个元素进行了去重
1. 1~N 进行排序
2. 首先计数第一个元素
3. 向后遍历 如果[x]!=[x+1] 则对[x+1]元素计数
1. n个元素 有n-1 个连续子段
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N int(3e5+10)
int num[N];
int main()
{
ll n,k;
cin>>n>>k;
ll sum = 0;
for(int i = 1;i<=n;i++) { cin>>num[i];
}
sort(num+1,num+1+n);
if(num[1]<=k) sum+=num[1];
for(int i = 1;i<n;i++) { if(num[i+1]>k) break;
if(num[i]==num[i+1]) continue;
sum+=num[i+1];
}
cout<<(1+k)*k/2-sum;
return 0;
}
4.3.3 unordered_set 离散化
unordered_set 是竞赛里常用的离散化方法
#include<bits/stdc++.h>
using namespace std;
#define ll long long
unordered_set num;
int main()
{
ll n,k;
cin>>n>>k;
ll sum = 0;
for(int i = 1;i<=n;i++) { int x; cin>>x;
if(x<=k) num.insert(x);
}
for(auto i: num)
{
sum+=i;
}
cout<<(1+k)*k/2-sum;
return 0;
}
5. T5
5.1 知识点：数学 桶排序
5.2 题意概述
题目给定若干跟 长度不一的火柴棒 只能用其中相同长度的 拼搭出来 正多边形
比如 1 2 1 1 2 2 2 就可以用长度 为1的火柴棒 拼接一个 正三角形 和 用长度 为2的火柴棒 拼接一个正四边形。
题目想要求出 最多可以组合多少个正多边形
5.3 做题思路
通过分析我们发现 对于一个长度 为x的木棒来说 尽量多的组成正多边形 其实就是去组成正三角形。
1. 求解出每种长度木棒的个数
2. 对于每种木棒 拼出的最多个数 为 num[x]/3
5.4 参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N int(1e6+10)
int num[N];
int main()
{
int n;
cin>>n;
for(int i = 1;i<=n;i++) { int x; cin>>x;
num[x]++;
}
ll sum = 0;
for(int i = 1;i<=N;i++)
{
sum+=num[i]/3;
}
cout<<sum;
return 0;
}