模拟
既约分数
1、题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
例如 1/7 , 3/4 , 1/8 都是既约分数。
请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1和 2020）？
运行限制
最大运行时间：2s
最大运行内存: 128M
题目分析：
题目类型：枚举
解题思路：分别枚举分子分母在 1-2020 范围，判断是否最大公约数为 1，如果是就是既约分数，计数代码
#include<iostream>
#include<algorithm>
using namespace std;
int my_gcd(int a,int b){
if(b == 0) return a;
return my_gcd(b, a%b);
}
int main(){
int ans = 0;
for(int i=1;i<=2020;i++){
for(int j=1;j<=2020;j++){
if(my_gcd(i,j) == 1)ans++;
}
}
cout<<ans<<'\n';
return 0;
}
改进：质数筛等数学方法。
数的分解
1、题目描述
- 题目分析：
题目类型：枚举
解题思路：分别枚举三个数，如果他们满足和为 2019 的条件和不包含 2 和 4则计数，最后答案除以 6 则为最终答案。因为排列组合同个答案有 6 次呈现。
优化 1：用数组来进行不包含 2 和 4 的判断。
优化 2：添加 i<j<k 的约束保证只有一种答案
优化 3：利用 i 和 j 的枚举来计算 k
- 代码
#include<iostream>
using namespace std;
int flag[2020];
int check(int i){
while(i){
if(i%10==2||i%10==4)return 0;
i/=10;
}
return 1;
}
signed main(){
int res = 0;
for(int i=1;i<=2019;i++)if(check(i))flag[i]=1;
for(int i=1;i<=2019;i++){
for(int j=i+1;j<2019-i-j;j++){
if(flag[i]&&flag[j]&&flag[2019-i-j])res++;
}
}
cout<<res<<'\n';
return 0;
}
改进：数位 dp
小蓝和小桥的挑战
2. 题目分析：
题目类型：枚举
解题思路：先求 0 的个数z，在求 z 的过程中求总和 sum，如果 sum 为 0，则答案为 z+1，否则则为 z。调整过程是先把为 0 的+1，然后如果总和为 0 把一个正整数+1.
- 代码
#include<iostream>
using namespace std;
int tmp,t,n;
signed main(){
cin>>t;
while(t--){
cin>>n;
int sum = 0,z = 0;
for(int i=1;i<=n;i++){
cin>>tmp;
if(tmp == 0){
z++;tmp++;}
sum+=tmp;
}
if(sum==0)cout<<z+1<<'\n';
else cout<<z<<'\n';
}
return 0;
}
DNA序列修正
- 题目
- 样例输出为 2
思路分析：贪心，枚举。操作次数最少说明交换操作尽可能多。遍历第一条 DNA，判断是否配对，如果不配对，遍历第二条 DNA 后面位置看是否能进行交换来满足。如果不能交换就进行替换。
代码
#include<iostream>
#include<map>
using namespace std;
map<char,int> mp{
{
'A',0},
{
'C',1},
{
'G',2},
{
'T',3}
};
signed main(){
int N;cin>>N;
string a,b;
cin>>a>>b;
int cnt = 0;
for(int i = 0;i<N;i++){
if(mp[a[i]]+mp[b[i]]!=3){
for(int j = i+1;j<N;j++){
if(mp[a[i]]+mp[b[j]]==3&&mp[a[j]]+mp[b[i]]==3){
swap(b[i],b[j]);
break;
}
}
cnt++;
}
}
cout<<cnt;
}
无尽的石头
解题思路：模拟
读题可知行走路径是唯一的，先求出路径存在数组中，然后再查询。代码
#include<iostream>
#include<vector>
#include<algorithm>//find
using namespace std;
#define ll long long
const ll MAX = 1e6;
vector<ll> stones;
ll sum_digits(ll digit){
ll sum = 0;
while(digit){
sum += digit%10;
digit/=10;
}
return sum;
}
void preprocess(){
stones.push_back(1);
while(true){
ll next = *--stones.end() + sum_digits(*--stones.end());
if(next<=MAX)stones.push_back(next);
else break;
}
}
int main(){
preprocess();
int t;cin>>t;
while(t--){
int n;cin>>n;
auto it = find(stones.begin(), stones.end(), n);
if(it!=stones.end())cout<<it - stones.begin()<<'\n';
else cout<<-1<<'\n';
}
return 0;
}
