本文主要是介绍2024.3.21|华北水利水电大学江淮校区ACM社团训练赛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
2024.3.21|华北水利水电大学江淮校区ACM社团训练赛
1.数字拆解
2.矩阵修改
3.因子数
4.回文数
5.中位数
心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。
数字拆解
题目:
小红拿到了一个偶数,她希望你将其切割成尽可能多的偶数。你能帮帮她吗?
输入描述:
一个偶数
1≤x≤105
输出描述:
输出若干行,从小到大输出每个偶数。
示例1
输入
1024
输出
2
4
10
说明
拆分成"10"+“2”+"4"三个偶数。
示例2
输入
999999999999999999999999990
输出
999999999999999999999999990
示例3
输入
202020
输出
0
0
0
2
2
2
注意:
自己看数据范围,用string吧孩子,然后还需要一个动态字符串t去切割、连接和存储,判断是不是偶数你就看这个数最末位能不能对2取余等不等于0就完了。对2取余为0的数有0,2,4,6,8。
实践代码:
bool cmp(string a,string b){if(a.size()!=b.size()) return a.size()<b.size();return a<b;
}
void solve(){string s;cin>>s;string t;vector<string> a;for(int i=0;i<s.length();i++){t+=s[i];int y=s[i]-'0';if(y%2==0) {a.push_back(t);t="";}}sort(a.begin(),a.end(),cmp);for(int i=0;i<a.size();i++) cout<<a[i]<<endl;
}
矩阵修改
题目:
小红拿到了一个字符矩阵,矩阵中仅包含"red"这三种字符。
小红每次操作可以将任意字符修改为"red"这三种字符中的一种。她希望最终任意两个相邻的字母都不相同。小红想知道,至少需要修改多少个字符?
输入描述:
第一行输入两个正整数n,m,代表矩阵的行数和列数。
接下来的n行,每行输入一个长度为m的、仅由"red"这三种字符组成的字符串。
1≤n≤4
1≤m≤1000
输出描述:
一个整数,代表需要修改的字母数量的最小值。
示例1
输入
2 3
ree
dee
输出
2
说明:
修改为:
red
dre
即可。
注意:
三进制状压dp。
实践代码:
因子数
题目:
给出一个质数 n,请求出一个质数 m,使得 n+m 不是质数。
其中,质数是指大于 1 的自然数,除了 1 和自身外,不能被其他自然数整除的数。
输入描述:
仅输入一行,包含一个整数 n(2≤n≤2⋅105 ),保证 n 是质数。
输出描述:
仅输出一行。包含一个质数 m(2≤m≤2⋅105 ),表示答案。
如果有多个可行的答案,请输出任意一个。
可以证明,在题目所给条件下一定有解。
示例1
输入
11
输出
3
void solve(){int x;cin>>x;if(x==1) {cout<<0;return;}int cnt=0;for(int i=2;i<x/i;i++){if(x%i==0){cnt++;while(x%i==0) x/=i;//排除9=3*3这种质因子相同情况}}if(x>1) cnt++;cout<<cnt;
}
回文数
如果一段序列区间是回文的,有两种情况:
1.长度为偶数时,证明区间里的数字是一一对应的,即里面的数字0-9中的每个数的数量是偶数个。
2.长度是奇数时,证明除了中间那个数字之外的数字是一一对应的,即对于数字0-9来说里面有且仅有一个数字的数量是奇数,剩下都必须是偶数个。
题目:
小红定义一个整数是“好数”,当且仅当该整数通过重排之后可以形成回文数。(可以包含前导零)
现在小红拿到了一个正整数x,小红想截取一段连续区间得到好数,她想知道有多少种不同的方案?
输入描述:
输入一个正整数1≤x≤105
输出描述:
得到“好数”的方案数。
示例1
输入
110
输出
5
说明
长度为 1 的区间,三个都是合法的。
长度为 2 的区间,"11"是合法的,"10"是不合法的。
长度为 3 的区间, "110"是合法的。
实践代码:
map<vector<int>,int> mp;
vector<int> cnt(10,0);//cnt[i] - i(0~9)这个数字出现了几次(这里只需记录奇/偶个) 1-奇数个 0-偶数个
void solve(){string s;cin>>s;mp[cnt]++;//初始化为0,即0~9的数字都没出现过,都是偶数int ans = 0;for(int i=0;i<s.length();i++){cnt[s[i]-'0']^=1;//开始为0 异或1为1(奇数个) 之后再出现异或1为0(偶数个)ans+=mp[cnt];//加上和它完全一样的区间数for(int j=0;j<10;j++){//统计只有一个数字出现次数不一样的区间vector<int> tmp;tmp=cnt;tmp[j]^=1;ans+=mp[tmp];}mp[cnt]++;//每次结束之后 这个区间数+1}
中位数
计算中位数的步骤如下:
首先,将所有数据按照大小顺序排列。
如果数据数量是奇数,那么中位数就是排序后的中间数值。
如果数据数量是偶数,那么中位数是排序后中间两个数的平均值。
题目:
小红拿到了一个数组:a1 ,a2 ,…,an。她定义 f(i) 为,删除第i个元素后,数组的中位数。现在小红想让你求出f(1),f(2)…f(n)的值,你能帮帮她吗?
输入描述:
第一行输入一个正整数n,代表数组的大小。
第二行输入n个正整数ai,代表数组的元素。
2≤n≤105
1≤ai≤109
输出描述:
输出n行,每行输出一个浮点数,第i行代表f(i)的值。保留一位小数。
示例1
输入
4
2 5 8 1
输出
5.0
2.0
2.0
5.0
示例2
输入
3
1 2 3
输出
2.5
2.0
1.5
实践代码:
void solve(){int n;cin>>n;vector<int> a(n),b(n);for(int i=0;i<n;i++) {cin>>a[i];b[i]=a[i];}sort(b.begin(),b.end());if(n%2==0){//即删一个数后数列个数为奇数情况int t1=b[n/2-1],t2=b[n/2];for(int i=0;i<n;i++){if(a[i]<t2) printf("%.1f\n",t2*1.0);else printf("%.1f\n",t1*1.0);}}else{//即删一个数后数列个数为偶数的情况int t1=b[n/2-1];int t2=b[n/2];int t3=b[n/2+1];for(int i=0;i<n;i++){if(a[i]<t2) printf("%.1f\n",(t2+t3)/2.0);if(a[i]>t2) printf("%.1f\n",(t1+t2)/2.0);else if(a[i]==t2)printf("%.1f\n",(t1+t3)/2.0);}}
}
心有猛虎,细嗅蔷薇。再见了朋友~
这篇关于2024.3.21|华北水利水电大学江淮校区ACM社团训练赛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!