锐客网

  1. 首页 > it技术 > >

“九韶杯”河科院程序设计协会第一届程序设计竞赛题目分析以及总结

还是有很多不足的，模拟思维还需加强，还有一直被诟病的图论
一：6的个数；
水题，没有过多的花里胡哨，手算（不太建议）或者代码模拟即可
参考代码如下：

1 #pragma GCC optimize(3) 2 #include 3 using namespace std; 4 int n=2021, num = 0; 5 int main() 6 { 7ios::sync_with_stdio(false); 8for (register int i = 1; i <= 2021; i++) 9{ 10int num1=i; 11while (num1) 12{ 13if (num1 % 10==6)num++; 14num1 /= 10; 15} 16} 17cout<
二：小明的作业；
不好意思，错了，我是弱鸡；
三：斐波那契（模拟思维的具体体现）
提供两种思路
1.常见的gcd写法，即gcd的递归写法，也有相应的辗转相除法，不在赘叙；
1 #pragma GCC optimize(3) 2 #include 3 using namespace std; 4 int a[100]={0,1,1}; 5 int b[100]; 6 long longfenzi; 7 long longfenmu; 8 long longgcd(long longa,long longb)//手写gcd函数 9 { 10if(b==0) return a; 11return gcd(b,a%b); 12 } 13 int main() 14 { 15for(register int i=3; i<=18; i++) 16{ 17a[i]=a[i-1]+a[i-2]; 18} 19for(int i=1; i<=13; i++) 20{ 21b[i]=a[i]*a[i+1]; //分母 22} 23fenzi=1; //分子 24fenmu=1; //分母 25for(int i=2; i<=13; i++) 26{ 27fenzi=fenzi*b[i]+1*fenmu; 28fenmu=fenmu*b[i]; 29long longtemp=gcd(fenzi,fenmu); //两者的最大共约数 30fenzi=fenzi/temp; //通分 ,不通分的后果就是程序不走或者直接爆 31fenmu=fenmu/temp; //通分 32} 33cout<
还要一种是关于STL库里好像是直接能写一种gcd函数，具体请看这篇https://blog.csdn.net/qq_44731019/article/details/109478391（转载），然后网上给出的代码思路也是和手写gcd大致的，这个相较于手写省去了很多麻烦，学到了；
摘自网上代码：
1 #include 2 #include 3 using namespace std; 4 int main() 5 { 6long long f[14]; 7f[0]=1; 8f[1]=1; 9for(int i=2; i<=13; i++) 10{ 11f[i]=f[i-1]+f[i-2]; 12} 13long long up=1,down=1; 14for(int i=1; i<13; i++) 15{ 16long long x=f[i]*f[i+1]; 17long long k=__gcd(x,down); 18down*=(x/k); 19up=up*(x/k)+down/x; 20} 21long long k=__gcd(up,down); 22up/=k; 23down/=k; 24cout<
四：数列重组；
全排列肯定是少不了了，久违的next_permutation()肯定是要用的，
大体思路即是，在按照字典序的情况下，先判断是否升序还是降序，并且对他们进行标记，然后满足了三个开始重新标记，即进行下一轮的升序或者降序判断，并且在满足条件的时候加一
参考代码如下:
1 #pragma GCC optimize(3) 2 #include 3 using namespace std; 4 int a[20] = {2, 3, 3, 3, 5, 6, 6, 7, 7, 8}; 5 int ans; //放结果 6 int main(){ 7ios::sync_with_stdio(false); 8do{//next_permutaion()一般搭配do-while使用 9bool flag1 = false, flag2 = false; //flag1表示之前是否出现递增，flag2表示之前是否出现递减 10int cnt = 0; //计数器 11for(register int i = 0; i<9; i++){//为社么是小于9呢？因为有i+1,那这样最后一个会越界，然后结果减半 12if(a[i + 1] > a[i]){ 13flag1 = true; 14if(flag2){ 15cnt ++; 16flag2 = false; 17flag1 = false; //flag1也要，因为当出现分割点后每次要从新的起点开始算，不受之前的区间影响了 18 19} 20 21} 22else if(a[i + 1] < a[i]){ 23flag2 = true; 24if(flag1){ 25cnt ++; 26flag1 = false; 27flag2 = false; 28} 29 30} 31} 32if(cnt <= 2) ans ++; 33}while(next_permutation(a, a + 10)); //按字典序排序 34cout << ans; 35return 0; 36 }

五：三角形个数
妥妥的好题，模拟思维的具体体现，这个题我是最后才做的，刚开始确实没想到是等差数列；不过网上大多数人说用前缀和求，我是弱鸡，我不会(●ˇ?ˇ●)
具体思路：
其实是找倒三角和正三角的个数，很不好找的其实
如果三角形的边长是i
对于大三角形来说，如果正三角形是以1开始，到n-i+1结束的等差数列
而对于倒三角来说，是从1开始，到n-2i+1结束的；
1 #pragma GCC optimizee(3) 2 #include 3 using namespace std; 4 const long longM=1e9+7; 5 int main() 6 { 7ios::sync_with_stdio(false); 8long long d=20210411,n; 9long long sumz=0; 10for(n=d; n>=1; n--) 11sumz=(sumz+n*(n+1)/2)%M; 12long long sumd=0; 13for(n=d-1; n>=1; n-=2) 14sumd=(sumd+n*(n+1)/2)%M; 15printf("%lld\n",(sumz+sumd)%M); 16return 0; 17 }

此外，本题特别鸣谢我身旁的zhy同学，如果他不和我说这个题是等差并且一直在坚持这个题，或许我就give up了；
六：字符串
没有什么特殊的技巧，值得注意的是关于如何接受空格符的问题，这里有两种方法：
1.getline函数：http://c.biancheng.net/view/1345.html（转载）
2.输入的正则用法：https://blog.csdn.net/weixin_43469047/article/details/83753526（转载）；
不得不说长见识了
七：不会
八：友谊纽带
唉，bfs我是很不擅长的，主要是用太多了STL关于队列的操作，我当时都不知道怎么做出来的，并且我的代码和网上标准答案大相径庭，还是学习大佬的代码把
1 /*1.这题一开始我读题目了，我以为的是把这些点全部连接起来所需要的最小边数； 2于是我用了并查集，只过了两个点~ 3 2.后来发现题目是要求找出一个连通块里的任意两点的距离，也就是连通块的最大长度； 4这样的话我们就可以用BFS暴力搜索所有节点，找出它们距其他节点的最远距离`的最大值`； 5当一次广搜之后仍有节点未被访问的则说明该图不只有一个连通块，输出-1； 6 */ 7 #include 8 using namespace std; 9 vectorG[2005]; 10 int vis[2005]; 11 int BFS(int x){ 12memset(vis,0,sizeof(vis)); 13queueq; 14q.push(x); 15int ans=0; 16while(!q.empty()){ 17int f=q.front(); 18q.pop(); 19ans=max(ans,vis[f]); 20for(int i=0; i>n>>m; 33for(int i=0; i>a>>b; 36G[a].push_back(b); 37G[b].push_back(a); 38} 39int ans=0; 40bool flag=true; 41for(int j=1; j<=n; j++){ 42ans=max(ans,BFS(j)); 43for(int i=1; i<=n; i++) 44if(vis[i]==0){ 45flag=false; break; 46} 47} 48if(flag) 49cout
转载自：https://blog.csdn.net/alpha_xia/article/details/115703564?spm=1001.2101.3001.6650.2&utm_medium=distribute.pc_relevant.none-task-blog-2~default~OPENSEARCH~Rate-2.pc_relevant_antiscanv2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~OPENSEARCH~Rate-2.pc_relevant_antiscanv2&utm_relevant_index=4；
九：传送门
这题我知道是克鲁斯卡尔啊，我没板子不会写，太难了，寒假的时候最小生成树就不会，主要是图论太难了；
十：最后一个小时的时光，我当时脑子已经一片混沌了，这题我没记错的话应该是直接爆搜了，毕竟我也没啥技巧了，只能搜了，唉；
思路是：枚举出每种获胜情况，并且用check函数检验
然后接下来就是搜了
利用dfs来搜接下来下的一步棋的所有情况
当x==10是结束条件，其实在某一定程度上很像2n皇后，但又不像；
难度较高，高级的思维模拟题，如果没有技巧建议深搜，毕竟搜可以混一部分的分数，运气好的话还可以过
1 #pragma GCC optimize(3) 2 #include 3 using namespace std; 4 int p[100]; 5 int n; 6 int ans; 7 int check(int u)//检查函数 8 { 9if(p[0]+p[4]+p[8]==3*u||p[2]+p[4]+p[6]==3*u) 10return 1; 11if(p[0]+p[3]+p[6]==3*u||p[1]+p[4]+p[7]==3*u||p[2]+p[5]+p[8]==3*u) 12return 1; 13if(p[0]+p[1]+p[2]==3*u||p[3]+p[4]+p[5]==3*u||p[6]+p[7]+p[8]==3*u) 14return 1; 15else 16return 0; 17 } 18 int dfs(int x)//深搜 19 { 20if(x==10)//边界条件 21{ 22if(check(1)) return 1; //正常返回 23if(check(-1)) return -1; //异常返回，此处也可以用bool判断 24return 0; 25} 26//开始模拟，怎么这么多模拟题 27int t,lost=0,win=0,d=0; 28if(x&1) t=1; 29else t=-1; 30for(int i=0; i<9; i++) 31{ 32if(p[i]==0) 33{ 34p[i]=t; 35if(check(t)) win++; 36else 37{ 38int p=dfs(x+1); 39if(p==t) 40win++; 41else if(p==0) d++; 42else lost++; 43} 44p[i]=0; 45} 46} 47if(win!=0) 48return t; 49else if(d!=0) 50return 0; 51else 52return (-1*t); 53 } 54 int main() 55 { 56ios::sync_with_stdio(false); 57int t; 58cin>>t; 59while(t--) 60{ 61ans=0; 62memset(p,0,sizeof(p)); 63cin>>n; 64for(int i=1; i<=n; i++) 65{ 66int x,y; 67cin>>x>>y; 68x--; 69y--; 70if(i&1) p[x*3+y]=1; //按位与运算，取 2进制整数 i 的最低位，如果最低位是1 则得1，如果最低位是0 则得0。 奇数 i 的最低位 是1，偶数i 的最低位 是0。 71else p[x*3+y]=-1; 72} 73ans=dfs(n+1); 74if(ans==1) cout<<'X'<
总结：
通过这次模拟赛，很明确的是，对于难题，思维题，较难的模拟题，还有图论尤其是最小生成树方面还是有很多的不足
但是也得到了一些经验：做不出来或者没思路的时候搜也是一种不错的选择；
下一步加强搜索的优化和训练，学习一些自己在图论上知识的空缺，加强模拟题以及思维题的训练，即使难，多练，也会熟能生巧的；
道阻且长，兴则将至，戒骄戒躁，任重道远，早日成为自己想成为的人。
【“九韶杯”河科院程序设计协会第一届程序设计竞赛题目分析以及总结】奔向远方，加油加油！

    推荐阅读


    上一篇：2023年考研人数预测

    下一篇：awk讲义-1-快速入门