1035 插入与归并 (25 分)
题意
给出n与两行含n个数的序列 分别代表原始序列和经过几步排序步骤后的序列
要求判断这是插入排序还是归并排序 并输出下一步操作后的序列
思路
主要是用STL的sort函数模拟两种排序方式 对原序列分别进行处理进行每一步判断当先序列是否与给出的
序列相同 那哪种排序方式有相同结果就是哪种排序方式 然后再进一步用该种排序输出下一步结果
用到了STL的equal()函数 用法 equal(a.begin(), a.end(), b.begin());
代码
#include <cstdio>
#include <iostream>
#include <algorithm>//equal()被包含在algorithm中
using namespace std;
int n;
int a[110], b[110], c[110];
void getin(int a[], int b[]){
for(int i=2; i<=n; i++){
sort(a, a+i);//sort模拟插入排序
if(equal(a, a+n, b)){
sort(a, a+i+1);//若相等再进行一次该排序
printf("Insertion Sort\n");
for(int j=0; j<n; j++){
if(j == n-1) printf("%d\n", a[j]);
else printf("%d ", a[j]);
}
break;
}
}
}
void merge(int a[], int b[]){
int i;
for(i=2; i<=n; i*=2){
for(int j=0; j<n; j+=i){
if(j + i < n)
sort(a+j, a+j+i);//边界要小心
else sort(a+j, a+n);
}
if(equal(a, a+n, b)){
i*=2;
for(int j=0; j<n; j+=i){
if(j + i < n)
sort(a+j, a+j+i);//边界要小心
else sort(a+j, a+n);
}
printf("Merge Sort\n");
for(int j=0; j<n; j++){
if(j == n-1) printf("%d\n", a[j]);
else printf("%d ", a[j]);
}
break;
}
}
}
int main()
{
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d", &a[i]);
c[i] = a[i];
}
for(int i=0; i<n; i++){
scanf("%d", &b[i]);
}
getin(a, b);
merge(c, b);//注意要新开一个与原数组一样的c数组 因为a数组已不再是原数组
return 0;
}
1060 爱丁顿数 (25 分)
题意
给你n个数 求最大的E 满足这n个数中至少有E个数比E大（E<=n）不存在输出0
这题题意容易理解错 应理解为至少 题目不存在的情况没说处理 做题人容易以为不存在就输出空格（这是题目的锅）
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int const maxn = 100010;
int a[maxn];
int n;
bool comp(int a, int b){
return a > b;
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
sort(a+1, a+n+1, comp);
int flag = 1;
for(int i = 1; i <= n; i++){
if(a[i] <= i){//如果第i个数大于i，说明i是满足的，再继续循环下去看有没有更大值
flag = 0; //如果第i个<=i就是不符合，最大值就是前一个即i-1
printf("%d\n", i-1);
break;
}
if(i == n) {//E为n的情况要单独考虑
printf("%d\n",n);
flag = 0;
}
}
if(flag) printf("%d",0);
return 0;
}
主要是题目理解错了，其实想到了还是很简单的。
1073 多选题常见计分法 (20 分)
题意
思路
没什么特殊做法， 就暴力模拟就好了（也也能是我的水平不够，没想到技巧）
总之这题挺麻烦，数据输入就很烦
真要说那个地方有特别之处 就是我直接用两个二维数组aa 和 bb 分别记入每个题目正确答案和当前这个人题目每题的的答案（有该选项就记入为1， 第一维小标为选项+1-'a'）后续比较两数组对应选项是否相等 ，不相等贡献++（正确答案有学生答案没或学生答案有正确答案没该选项的错误次数都要+1）
还要注意下一次循环开始bb要清空
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct problem {
int score,amount,ncorrect;
};
double student[1010];
int bb[110][6], aa[110][6];//aa记入题目的正确答案 bb记入当前同学题目的答案
void clearb(int x){
for(int i = 1; i <= 6; i++){
bb[x][i] = 0;
}
}
int main(void)
{
struct problem arr[110];
int npeople,nproblem,err[110][10]={0};
scanf("%d %d",&npeople,&nproblem);
for(int i=1;i<=nproblem;i++){
scanf("%d %d %d",&arr[i].score,&arr[i].amount,&arr[i].ncorrect);
for(int j=1;j<=arr[i].ncorrect;j++){
char cc;
scanf(" %c",&cc);
aa[i][cc+1-'a']++;//记入i题cc选项存在
}
}
getchar();//注意回车影响
for(int i=1;i<=npeople;i++){
for(int j=1;j<=nproblem;j++){
clearb(j);//清空bb
int n,flag=1;
char ch;
scanf("(");
scanf("%d",&n);
for(int k=1;k<=n;k++){
scanf(" %c",&ch);
bb[j][ch+1-'a']++;//当前同学j题ch选项是否存在
}
for(int k = 1; k <= 6; k++){//同学答案与正确答案对比
if(bb[j][k] != aa[j][k]){
err[j][k]++;
if(aa[j][k]==0 && bb[j][k]==1)//该同学选了正确答案没有的答案不得分
flag = 0;
}
}
if(flag==1){//能得分也分为两种情况
if(n == arr[j].ncorrect)
student[i]+=arr[j].score;
else if(n < arr[j].ncorrect)
student[i]+=arr[j].score/2.0;
}
scanf(")");
getchar();
}
}
for(int i=1;i<=npeople;i++){
printf("%.1f\n",student[i]);
}
int maxn=0,f=1;
for(int i=1;i<=nproblem;i++){
for(int j = 1; j <= 6; j++){
if(err[i][j]>0) f=0;
maxn=max(maxn, err[i][j]);//找出最大错误数
}
}
if(f) {
printf("Too simple\n");
return 0;
}
else {
for(int i=1;i<=nproblem;i++){
for(int j = 1; j <= 6; j++){
if(err[i][j]==maxn) printf("%d %d-%c\n", maxn, i, j-1+'a');
}
}
}
return 0;
}
1074 宇宙无敌加法器
题意
输入第一个数有n位 分别对应每位进制
随后输入两个小于n位数 求相加后的结果
思路
坑点比较多
1.数据比较大 需用字符串储存数据
2.当相加和的位数比给出的第一个数大时的情况
3.两数都为零时要输出0
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
int a[25], b[25], c[25], d[25];
char n[25], m[25], k[25];
int main()
{
cin >> n >> m >> k;
int i1=0, i2=0, i3=0;
int len1 = strlen(n);
int len2 = strlen(m);
int len3 = strlen(k);
for(int l = len1-1; l >= 0; l--){
a[++i1] = n[l] - '0';
if(a[i1] == 0) a[i1] = 10;
}
for(int l = i1+1; l<=21; l++){
a[l] =10;
}
for(int j = len2-1; j >= 0; j--){
b[++i2] = m[j] - '0';
}
for(int j = len3-1; j >= 0; j--){
c[++i3] = k[j] - '0';
}
int i;
for(i = 1; i <= 21; i++) {
d[i] = (b[i] + c[i])%a[i];
b[i+1] += (b[i] + c[i]) / a[i];
}
int flag = 1;
for (int x = i; x >= 1; x--) {
if(d[x] == 0 && flag && x!=1){
continue;
}
else{
printf("%d",d[x]);
flag = 0;
}
}
return 0;
}
1079 延迟的回文数
题意
思路
用c++的string 注意使用string的细节点 （注释有标注）
因为位数可达到1000 所以普通类型无法存下 要用字符串解决
可以用函数reverse求反字符串
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
using namespace std;
string a;
int ishw(string a) {
for(int i = 0; i < a.length()/2; i++){
if(a[i] != a[a.length()-1-i]) return 0;
}
return 1;
}
string add(string a, string b) {
string c = a;
int x = 0;
for(int i = a.length()-1; i >= 0; i--){
c[i] = (a[i] -'0' + (b[i] - '0') + x) % 10 + '0';//不要忘了后面还要加个'0'
x = (a[i] -'0' + (b[i] - '0') + x)/10;
}
if(x > 0) c = "1" + c;// string类型相加要注意左加还是右加 "1"+c 和 c+"1" 不一样
return c ;// string类型可当做函数返回值直接输出
}
int main()
{
cin >> a;
if(ishw(a)) cout << a << " is a palindromic number.\n";
else {
int nn = 10;
while(nn--){
string b;
b = a;
reverse(b.begin(), b.end());//reverse 包含在<algorithm>中
string cc = add(a, b);
cout << a << " + " << b << " = " << cc << '\n';
if(ishw(cc)) {
cout << cc << " is a palindromic number.\n";
return 0;
}
a = cc;
}
cout << "Not found in 10 iterations.\n";
}
return 0;
}
1080 MOOC期终成绩
思路
创建一个结构体数组stu 储存每个同学各成绩信息 其中学号用string类型表示
用两个map mp 和mmp
mp 记录该同学对应结构体的位置（后续再出现直接查找位置将数据存入对应结构体中若是第一次出现就再新加一个结构体）
mmp 记录数据是否合法（不合法后续得去除）
有几个坑点：
-
数组要开3倍10000+ 因为题目说是每种成绩给的人数<=10000 可能三块输入的人都不一样
-
可能存在非法输入 题目说了程序成绩不大于900 期中末不大于100 （且也不能为负）
-
当期中和期末成绩为零时 而 没成绩未赋值也默认为零冲突
做这道题时 还发现一个易错点：用cin流输入像cin >> a[++j] >> b[j]的表达时 后面的那个j是自加前的值
例如：输入 2 3 j 一开始是 2 那么a[3]被赋值为2 b[2]的值为3（应该流输入的影响吧）
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <map>
using namespace std;
map<string, int> mp, mmp;
struct node{
string id;
int mooc, mid, end;
int final;
}stu[30010];// 开3倍
int n, m, k;
bool comp(node a, node b){
if(a.final == b.final) return a.id < b.id;
else return a.final > b.final;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
int j = 0;
for(int i = 1; i <= n; i++){
j++;
cin >> stu[j].id >> stu[j].mooc;
if(stu[j].mooc > 900 || stu[j].mooc < 0) mmp[stu[j].id] = 1;
mp[stu[j].id] = j;
}
for(int i = 1; i <= m; i++){
string a;
int score;
cin >> a >> score;
if(score > 100 || score < 0) {
mmp[a] = 1;//记入不合法
}
if(mp[a]) {
stu[mp[a]].mid = score+1;//都加1避免与mid和end值为1冲突
}
else {
stu[++j].id = a;
stu[j].mid = score+1;
mp[stu[j].id] = j;
}
}
for(int i = 1; i <= k; i++){
string b;
int sco;
cin >> b >> sco;
if(sco > 100 || sco < 0) {
mmp[b] = 1;
}
if(mp[b]) {
stu[mp[b]].end = sco+1;
}
else {
stu[++j].id = b;
stu[j].end = sco+1;
mp[stu[j].id] = j;
}
}
for(int i = 1; i <= j; i++){
if(stu[i].mooc < 200) stu[i].final = 0;
else if(stu[i].mid <= stu[i].end) stu[i].final = stu[i].end-1;
else stu[i].final = 0.4*(stu[i].mid-1) + 0.6*(stu[i].end-1) + 0.5;
}
sort(stu+1, stu+j+1, comp);
for(int i = 1; i <= j; i++){
if(stu[i].final < 60) break;
if(mmp[stu[i].id]) continue;//不合法就跳过
else {
cout << stu[i].id << " " << stu[i].mooc << " ";
if(stu[i].mid) cout << stu[i].mid-1 << " ";
else cout << "-1 ";
if(stu[i].end) cout << stu[i].end-1 << " ";
else cout << "-1 ";
//int final = (int)(stu[i].final + 0.5);
cout << stu[i].final << "\n";
}
}
return 0;
}