电子科技大学-经济与管理学院-SME杯-ACM竞赛解题报告(1)

2023-10-23 13:50
文章标签 管理 报告 竞赛 学院 经济 acm 解题 大学 电子科技 sme

本文主要是介绍电子科技大学-经济与管理学院-SME杯-ACM竞赛解题报告(1)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

电子科技大学-经济与管理学院-SME杯-ACM竞赛解题报告

摘要

先说一下个人感受吧。
首先所有的题目确实不难，几乎全是模拟题，也就是说不需要任何NOIP的知识就能够解题，只要你能够找到比较好的解题思路，再把它用程序写出来就行。最多最多就考察了一个读入优化和一个单调队列。
然后就是…
既然题目这么简单怎么我的成绩还是那么惨不忍睹啊orz（很久没练了完全不会审题了）
好了下面是真经报告：

题目讲解

A题

  1. 题意分析：
    本题要求我们从一个数列中选择至少一个数出来 ，并且选出的数的和最少为X，极差最大为d，询问最少有多少种选法。
  2. 解题思路：
    很明显这道题用DFS是最快最简单的算法：首先让数组从小到大排列再依次枚举数，DFS时记录这个最开始枚举的数并同时计算和和极差，满足则继续向后枚举，不满足则退回起点枚举下一个数。
    BFS也可以做，但是懒得打代码了（X）
  3. 注意事项：
    注意此题要用long long，不要头铁全用int
  4. AC代码：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;int n,ans=0;
long long minv,maxd;
int num[20];
int jud[20];void getans(int pos,long long sum,long long mnn)//通过子函数嵌套实现DFS，保存当前位置pos，本次枚举总和sum，起始数mnn
{if(sum>=minv)ans++;for(int i=pos+1;i<=n;i++)if(num[i]-mnn<=maxd)getans(i,sum+num[i],mnn);
}int main()
{cin >> n >> minv >> maxd;for(int i=1;i<=n;i++)cin>>num[i];sort(num+1,num+n+1);for(int i=1;i<=n;i++)getans(i,num[i],num[i]);cout << ans << endl;
}

B题

  1. 题意分析：
    本题要求我们计算从一个坐标移动到另一个坐标所需要的最小步数。
  2. 解题思路：
    很明显直接横坐标之差加上纵坐标之差就行了
    没有人用BFS吧
  3. 注意事项：
    如果要用stl的abs（）函数记得引用头文件cmath
  4. AC代码：
#include<iostream> 
#include<cstdio>
#include<cmath>
using namespace std;int t;
int xx1,yy1,xx2,yy2;int main()
{cin >> t;while(t--){cin >> xx1 >> yy1 >> xx2 >> yy2;cout << abs(xx2-xx1)+abs(yy2-yy1) << endl;}
}

C题

  1. 题意分析：
    本题要求我们计算从一个坐标移动到另一个坐标所需要的Z最简指令及步数。
  2. 解题思路：
    这个题可以算一道有点难度的模拟题了。
    为了简化判断，我选择先把机器人统一朝向北面。（如果不这么干而是直接解对于我来说不仅想着头大，代码实现也头大）然后再统一处理当终点分别在机器人的8个方位上如何走，如何输出答案。最后你会发现对于一个方向最简指令的格式与步数是唯一的。
  3. 注意事项：
    第一个是这里：
    【N for North, S for South, E for East, or O for West】
    注意O才是朝西，不是W也不是0。
    第二个是当终点在机器人左上方的时候最简指令是先向前走，而不是先转三圈。这样最长只需要5个指令而不是六个。
    （在这两处跌倒了无数次orz）
  4. AC代码：
#include<iostream> 
#include<cstdio>
#include<cmath>
using namespace std;char d;
int xx1,yy1,xx2,yy2;
int x,y;void getposition()
{if(d=='N'){x=xx2-xx1;y=yy2-yy1;}else if(d=='S'){x=xx1-xx2;y=yy1-yy2;}else if(d=='O'){x=yy2-yy1;y=xx1-xx2;}	else if(d=='E'){x=yy1-yy2;y=xx2-xx1;}		
}int main()
{cin >> xx1 >> yy1 >> d >> xx2 >> yy2;getposition();if(x>0){if(y>0){cout<<3<<endl<<"A "<<y<<endl<<"D"<<endl<<"A "<<x;}else if(y<0){cout<<4<<endl<<"D"<<endl<<"A "<<x<<endl<<"D"<<endl<<"A "<<-y;}else {cout<<2<<endl<<"D"<<endl<<"A "<<x;}}else if(x<0){if(y>0){cout<<5<<endl<<"A "<<y<<endl<<"D"<<endl<<"D"<<endl<<"D"<<endl<<"A "<<-x;}else if(y<0){cout<<5<<endl<<"D"<<endl<<"D"<<endl<<"A "<<-y<<endl<<"D"<<endl<<"A "<<-x;}else {cout<<4<<endl<<"D"<<endl<<"D"<<endl<<"D"<<endl<<"A "<<-x;}		}else{if(y>0){cout<<1<<endl<<"A "<<y;}else if(y<0){cout<<3<<endl<<"D"<<endl<<"D"<<endl<<"A "<<-y;}else {cout<<0<<endl;}	}
}

D题

  1. 题意分析：
    本题要求我们判断一个字符串是否是一个环形字符串的子串（或者说是否按字母顺序排列）
  2. 解题思路：
    因为在ASCII码中小写字母的编码是连续的，所以很明显直接判断字符是否连续即可，最多再特判一下za。
  3. 注意事项：
    字符，字符串的输入输出操作可能对初学者而言比较难。
  4. AC代码：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;int t,jd=0;
char p[1050];int main()
{cin>>t;while(t--){cin>>p;for(int i=1;i<strlen(p);i++)if(p[i]!=p[i-1]+1)if(p[i-1]!='z'||p[i]!='a'){jd=1;continue;}(jd)?(cout<<"NO"<<endl):(cout<<"YES"<<endl);jd=0;}return 0;
}

E题

  1. 题意分析：
    本题要求我们对一个数组中的数进行有限次的求反操作，使得数组中数的总和尽可能大。
  2. 解题思路：
    很明显，我们要尽可能让负数越少越好，负数的和越少越好，这样才能使总和尽可能大。所以一开始一定是从大（绝对值大）到小对负数进行求反，能变多少是多少。
    如果变完后还有剩余的操作步数，接着要特判是否有0存在。有零意味着不用对正数进行求反，于是数组的值在负数被转化完后就已经是最大值了。
    如果没有0，那么就从正数中找一个最小数再根据剩余操作步数进行求反，从而保证总和最大。
  3. 注意事项：
    在选正数最小值时不要忘了前面的负数，这里的求最小正数要考虑之前的负数。（在这里死了好几次orz）
  4. AC代码：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;int t,n,k,a,ans;
int neg[10050];
int numpos,numneg,numzro;int main()
{cin >> t;while(t--){cin >> n >> k;int jud=999;numpos=numneg=numzro=0;	ans=0;for(int i=1;i<=n;i++){cin >> a;	ans+=a;//	cout << a << " " << ans << endl;if(a>0){jud=min(a,jud);numpos++;}if(a<0)neg[++numneg]=-a;//cout<<neg[numneg]<<" ";if(a==0)numzro++;}if(numneg)sort(neg+1,neg+numneg+1);//		cout<<endl;
//		for(int i=1;i<=numneg;i++)cout<<neg[i]<<" ";
//		cout<<endl;while(k--){if(numneg){ans+=2*neg[numneg];jud=min(neg[numneg],jud);numneg--;continue;}if(numzro)break;ans-=2*jud;jud=-jud;}cout << ans << endl;}}

F题

  1. 题意分析：
    两个人分别在两个区间内往返运动，本题要求我们算这两人会相遇几次，
  2. 解题思路：
    模拟就可以做，用变量对应的数的变化模拟人的移动，用几个变量记录方向，但要注意细节。
  3. 注意事项：
    一开始若两人在同一点视为相遇了一次。
  4. AC代码：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;int t,k;
int l1,r1,p1,d1;
int l2,r2,p2,d2;void simulate()
{cin >> k;	int ans=0;    if(p1==p2)ans++;for(int i=1;i<=k;i++){if(p1==l1)d1=1;	if(p1==r1)d1=0;if(p2==l2)d2=1; if(p2==r2)d2=0;if(d1&&p1!=r1)p1+=1;	else if(!d1&&p1!=l1)p1-=1;if(d2&&p2!=r2)p2+=1;	else if(!d2&&p2!=l2)p2-=1;			if(p1==p2)ans++;}cout<<ans<<endl;
}int main()
{cin >> t;while(t--){cin >> l1 >> r1 >> p1 >> d1;cin >> l2 >> r2 >> p2 >> d2;simulate();}
}

G题

  1. 题意分析：
    本题询问我们能否通过将一个数减一，其余数加一的操作，将一个数列中的所有数变为一个值
  2. 解题思路：
    注意这道题中数列中数的值并不重要
    注意到每次操作该数与其他数相差2
    考虑奇偶性。。。
    然后你会发现这道题判断所有数是否同奇偶就完了
  3. 注意事项：
    主要是从题目中发现考点是奇偶性这点不一定想得到
    哦还有这道题竟然还卡cin，将cin解绑或进行读入优化就行。
  4. AC代码：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
using namespace std;int n,t,h;int main()
{scanf("%d",&t);while(t--){int odd=0,eve=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&h);if(h%2)	odd++;else	eve++;}if(odd&&eve) cout << "no" << endl;else 		 cout << "yes" << endl;}return 0;
}

I题

  1. 题意分析：
    本题询问我们一个奇数项字符串能不能通过翻转变为另一个奇数项字符串，如果有，最少需要多少步
  2. 解题思路：
    字符串处理题，暴力判断就行。我是用变量side判断此时a字符串剩余项的正反，再判断其是否与b字符串相符，步数是否加一。
  3. 注意事项：
    这道题是这次比赛几乎最坑的一道题。以至于我做出来后别人叫我看他代码哪里错了我都答不出来orz 好像只通过判断相邻字符来判断答案是否加一是会炸的，具体原因我有空再想想。。。
  4. AC代码：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
using namespace std;int n,t;
int ans=0,jud=0,side=1;
char a[100500],b[100500];int judge(int i)
{if     ((a[i]==b[n-1-i]&&a[n-1-i]==b[i])&&(a[i]==b[i]&&a[n-1-i]==b[n-1-i]))return 0;else if((a[i]==b[i]&&a[n-1-i]==b[n-1-i]))return 1;else if((a[i]==b[n-1-i]&&a[n-1-i]==b[i]))return 2;                                           else return -1;
}int main()
{cin >> t;while(t--){cin>>a>>b;	n=strlen(a);  ans=jud=0; side=1;//cout<<n<<endl;if(n==1){if(a[0]==b[0])cout<<0<<endl;else cout<<"-1"<<endl;continue;}if(judge(0)==2){ans+=1;side=2;}for(int i=1;i<(n-1)/2;i++){if((judge(i))==-1){jud=1;break;}else if(side!=judge(i))if(judge(i)!=0){ans++;}if(judge(i)==1)side=1;	if(judge(i)==2)side=2;					//cout<<i<<endl;}if(!jud&&(judge(0)!=-1)&&(a[(n-1)/2]==b[(n-1)/2]))cout<<ans<<endl;else   cout<<"-1"<<endl;//	for(int i=0;i<(n-1)/2;i++)cout<<judge(i);}return 0;
}

J题

  1. 题意分析：
    本题要求我们判断一个数列中某个数是否是某个区间内的最小数（实际上那个区间的中项就是它）
  2. 解题思路：
    本题终于与NOIP沾了点边。。。考了单调队列的维护。
    首先建一个单调队列，然后就不断存入数，剔除超出区间的数，输出第一项，完了
    然而尴尬的是单调队列当时我学的并不怎么好。。。当时我一般用的STL的单调队列。
    这次我也用了。
    然后我就炸了。
    这里写图片描述
    最后找的网上一个单调队列的轮子才过的。。。
  3. 注意事项：
    单调队列最好自己写，除非你试过很多遍很可靠（像Dijkstra小根堆优化）否则。。。

不要信任STL！！！

  1. AC代码：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
using namespace std;int n,t,x,y;
struct node
{int rain,date;
};const int maxn = 100050;
int num[maxn];typedef pair<int, int> P; 
struct priority_queue {P q[maxn];int head, tail;void clear() { head = tail = 0;}void pop(int pos) {while (head < tail && pos > q[head].second) ++head;}void push(int val, int pos) {while (head < tail && val < q[tail - 1].first) --tail;q[tail++] = make_pair(val, pos);}bool empty() { return head == tail;}node top() { node f;f.rain = q[head].first;f.date = q[head].second;return f;}
}que;int main()
{
//	ios::sync_with_stdio(0); 
//	cin.tie(0);	cout.tie(0);cin >> n >> x >> y;for(int i=1;i<=n;i++)cin >> num[i];for(int i=1;i<=min(y,n);i++)que.push(num[i],i);for(int i=1;i<=n;i++){node jud;que.pop(i-x);jud=que.top();			if(i+y<=n)que.push(num[i+y],i+y);jud=que.top();if(jud.date==i){cout<<i<<endl;break;}}return 0;
}

K题

  1. 题意分析：
    本题要求我们判断一个二维字符串能否在经过若干列平移后使得字符串中的‘#’联通，如果有求出一种可能的答案。
  2. 解题思路：
    首先可以判断如果出现‘##’那么一定能够联通
    接着可以判断出没有‘##’又同时有‘#.’，‘.#’那么就不会联通
    最后得出除了上面那种情况其他的情况都是联通的。
    输出就让‘##’在中间‘…’在最后就行
  3. 注意事项：
    字符串的读入，输出与统计可能对初学者有些难度
  4. AC代码：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;int s1,s2,s3,s4;
int jd[1050];
char s[1050];int main() {cin >> s;for(int i=0;i<strlen(s);i++)(s[i]=='#')?(jd[i+1]=1):(jd[i+1]=0);cin >> s;for(int i=0;i<strlen(s);i++){if(s[i]=='#'){if(jd[i+1])s2++;else	 s3++;}else{if(jd[i+1])s1++;else	 s4++;}}	if(s1&&s3&&!s2)cout << "NO" << endl;else {cout << "YES" << endl;for(int i=1;i<=s1+s2;i++)cout<<"#";	for(int i=1;i<=s3+s4;i++)cout<<".";cout << endl;for(int i=1;i<=s1;i++)cout<<".";		for(int i=1;i<=s2+s3;i++)cout<<"#";	for(int i=1;i<=s4;i++)cout<<".";	}return 0;
}// s1   s2   s3   s4
// #    #    .    .
// .    #    #    .

L题

  1. 题意分析：
    经典的过桥问题。
  2. 解题思路：
    注意过桥问题实际上有两种局部4人解
    第一种是由第一个人一直带着后面的人过桥，是最简单但也是接触过此题的同学最容易忘的一种。
    第二种就是经典的（1,2）（1）（3,4）（2）（1,2）的过法了，做过这类题的同学容易想到，一开始不容易想到。
    然后就很简单了，运用分治的思想，对于三个人以上的情况都拆成2+2n+m（m<2）的形式，对于每四个人（最快的两个人和还没过桥的最慢的两个人）判断哪个方案用时最小，然后把用时短的加入ans就完了。
  3. 注意事项：
    不容易想到有两种局部解。
  4. AC代码：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;int n;
long long ans;
long long t[120000];int main() {cin >> n;	for(int i=1;i<=n;i++)cin>>t[i];sort(t+1,t+n+1);while(n>3){if(2*t[2]>=t[1]+t[n-1])ans+=2*t[1]+t[n-1]+t[n];if(2*t[2] <t[1]+t[n-1])ans+=2*t[2]+t[1]+t[n];n-=2;		}if(n==1)ans+=t[1];else if(n==2)ans+=t[2];else if(n==3)ans+=t[1]+t[2]+t[3];cout << ans;return 0;
}

赛后总结

  1. 审题 很，重，要！（数据范围，是否要解绑cin或使用读入优化）
  2. 题目数据 很，不，靠，谱！ 一定要 手，造，样，例！
  3. 不，要，过，分，信，任，STL !
  4. 多，练，大，模，拟！
  5. 多，记，好，轮，子！
  6. Practice Makes Perfect !

这篇关于电子科技大学-经济与管理学院-SME杯-ACM竞赛解题报告(1)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/268263。

相关文章

认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

原文链接： https://tecdat.cn/?p=37628 6月16日，小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞，这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示，公司准备量产，并计划今年四季度开启预售小鹏汇天分体式飞行汽车，探索分体式飞行汽车城际通勤。阅读原文，获取专题报告合集全文，解锁文末271份飞行汽车相关行业研究报告。 据悉，业内人士对飞行汽车行业
阅读更多...
软考系统规划与管理师考试证书含金量高吗？

软考系统规划与管理师考试证书含金量高吗？

2024年软考系统规划与管理师考试报名时间节点： 报名时间：2024年上半年软考将于3月中旬陆续开始报名 考试时间：上半年5月25日到28日，下半年11月9日到12日 分数线：所有科目成绩均须达到45分以上（包括45分）方可通过考试 成绩查询：可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间：预计在11月左右 证书领取时间：一般在考试成绩公布后3~4个月，各地领取时间有所不同
阅读更多...
安全管理体系化的智慧油站开源了。

安全管理体系化的智慧油站开源了。

AI视频监控平台简介 AI视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒，省去繁琐重复的适配流程，实现芯片、算法、应用的全流程组合，从而大大减少企业级应用约95%的开发成本。用户只需在界面上进行简单的操作，就可以实现全视频的接入及布控。摄像头管理模块用于多种终端设备、智能设备的接入及管理。平台支持包括摄像头等终端感知设备接入，为整个平台提
阅读更多...
计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者：计算机编程-吉哥 🍊简介：专业从事JavaWeb程序开发，微信小程序开发，定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事，生活就是快乐的。 🍊心愿：点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能
阅读更多...
从状态管理到性能优化：全面解析 Android Compose

从状态管理到性能优化：全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动
阅读更多...
每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目： 牛牛发明了一种新的四舍五入应用于整数，对个位四舍五入，规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数
阅读更多...
Sentinel 高可用流量管理框架

Sentinel 高可用流量管理框架

Sentinel 是面向分布式服务架构的高可用流量防护组件，主要以流量为切入点，从限流、流量整形、熔断降级、系统负载保护、热点防护等多个维度来帮助开发者保障微服务的稳定性。 Sentinel 具有以下特性: 丰富的应用场景：Sentinel 承接了阿里巴巴近 10 年的双十一大促流量的核心场景，例如秒杀（即突发流量控制在系统容量可以承受的范围）、消息削峰填谷、集群流量控制、实时熔断下游不可用应
阅读更多...
Python：豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣，数据处理过程，数据分析，可视化，以及完整PPT报告】

Python：豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣，数据处理过程，数据分析，可视化，以及完整PPT报告】

**爬取豆瓣电影信息，分析近年电影行业的发展情况** 本文是完整的数据分析展现，代码有完整版，包含豆瓣电影爬取的具体方式【附带爬虫豆瓣，数据处理过程，数据分析，可视化，以及完整PPT报告】   最近MBA在学习《商业数据分析》，大实训作业给了数据要进行数据分析，所以先拿豆瓣电影练练手，网络上爬取豆瓣电影TOP250较多，但对于豆瓣电影全数据的爬取教程很少，所以我自己做一版。 目
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2