哈理工新生赛热身赛解题报告

2024-09-07 18:58
文章标签 报告 解题 新生 理工 热身赛

本文主要是介绍哈理工新生赛热身赛解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本次热身赛6道题目，由于没有官方解题报告，自己写了一个山寨版的解题报告，希望对学弟学妹有所帮助

期中两到签到题该校OJ上没有挂出，我在田大神的帮助下a掉了其它四题，解题报告如下所示

线段
Time Limit: 1000 MSMemory Limit: 32768 K
Total Submit: 10(6 users)Total Accepted: 7(6 users)Rating: Special Judge: No
Description

坐标轴上有一些点，依次给出。点与点之间要求用一个半圆的直径连接，即把这两个点作为连接他们的半圆的直径的两个端点。第一个点与第二个点连，第二个与第三个连。半圆不能在坐标轴下面。问最后连出的图形，是否存在两个半圆他们是交叉的。

Input

多组测试数据。

每组测试数据的第一行有一个数n(1 ≤ n ≤ 1000)，表示有n个点。

之后一行有n个数x1, x2, ..., xn ( - 10^6 ≤ xi ≤ 10^6)，每个数表示该点在坐标轴的位置。
Output

如果最后的图形有交叉，输出yes,如果没有，输出no。

Sample Input

4

0 10 5 15

4

0 15 5 10

Sample Output

yes

no

Source
2014.11.29新生赛-热身赛


要考虑多种情况，注意两个半圆有一点重合的地方那种情况就行

然后这题我用c++写的，如果要转化成c，只要把sort()排序函数，自己手写一个就行

就是按照x从小到大排序结构体，如果x1相同，按照从小到大排x2就行

比如数据0 15 5 10

排序后

0 15

5 10

5 15

然后每次往前比较，如有交叉的标记下

AC代码

[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. #include <iostream>  
  2. #include <algorithm>  
  3. #include <cstdio>  
  4. using namespace std;  
  5. const int maxn = 1e6+10;  
  6. struct Node  
  7. {  
  8.     int x,y;  
  9. }node[maxn];  
  10.   
  11. bool cmp(Node a, Node b)  
  12. {  
  13.     if(a.x == b.x) return a.y < b.y;  
  14.      return a.x < b.x;  
  15. }  
  16. int main()  
  17. {  
  18.   
  19.    int n;  
  20.    while(scanf("%d",&n) != EOF)  
  21.    {  
  22.        int a[1000];  
  23.        for(int i = 0; i < n; i++)  
  24.        {  
  25.            scanf("%d",&a[i]);  
  26.        }  
  27.        int cent = 0;  
  28.        for(int i = 1; i < n; i++)  
  29.        {  
  30.            node[cent].x = a[i-1] < a[i] ? a[i-1] : a[i];  
  31.            node[cent++].y = a[i-1] < a[i] ? a[i] : a[i-1];  
  32.   
  33.        }  
  34.   
  35.        sort(node,node+cent,cmp);  
  36.        int flag = 1;  
  37.   
  38.        for(int i = 0; i < cent; i++)  
  39.         for(int j = 0; j < i; j++)  
  40.        {  
  41.            if( node[i].x  == node[j].x && node[i].y >= node[j].y) continue;  
  42.            if(node[i].x < node[j].y && node[i].y > node[j].y)  
  43.             {  
  44.               flag = 0;  
  45.            }  
  46.        }  
  47.   
  48.        if(flag) printf("no\n");  
  49.        else printf("yes\n");  
  50.    }  
  51.    return 0;  
  52. }  
组合
Time Limit: 1000 MSMemory Limit: 32768 K
Total Submit: 7(5 users)Total Accepted: 6(5 users)Rating: Special Judge: No
Description

给出一个正整数N，从集合{1,2,3..N} 中找出所有大小为k的子集, 并按照字典序从小到大输出。

Input

第一行是一个整数T,代表T组测试数据。

接下来T行，每行是两个正整数n(1<=n<=10), k(1<=k<=n)。

Output

对于每组数据按字典序输出所有符合条件的子集。

Sample Input

1

5 3

Sample Output

1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

2 3 4

2 3 5

2 4 5

3 4 5

Source
2014.11.29新生赛-热身赛

这题用深搜解决，如果不会深搜就理解成不断的递归求解，自己最好拿样例手动在纸上面模拟一下代码就清楚了

[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. #include <stdio.h>  
  2. #include <string.h>  
  3.   
  4. int a[11];  
  5. int visit[11];  
  6. int n,k;  
  7. void dfs(int d, int q)  
  8. {  
  9.     if(d == k)  
  10.     {  
  11.         printf("%d",a[0]);  
  12.         for(int i = 1; i < k; i++)  
  13.             printf(" %d",a[i]);  
  14.         printf("\n");  
  15.         return;  
  16.     }  
  17.   
  18.     for(int i = q; i <= n; i++)  
  19.     {  
  20.         if(!visit[i])  
  21.         {  
  22.             visit[i] = 1;  
  23.             a[d] = i;  
  24.             dfs(d+1,i+1);  
  25.             visit[i] = 0;  
  26.         }  
  27.     }  
  28. }  
  29. int main()  
  30. {  
  31.     int T;  
  32.     scanf("%d",&T);  
  33.     while(T--)  
  34.     {  
  35.         memset(a,0,sizeof(a));  
  36.         scanf("%d%d",&n,&k);  
  37.         dfs(0,1);  
  38.     }  
  39.     return 0;  
  40. }  

一个整数的正反面
Time Limit: 3000 MSMemory Limit: 32768 K
Total Submit: 9(4 users)Total Accepted: 5(4 users)Rating: Special Judge: No
Description

给定一个整数n，和一个整数k。求比n小的，并且在k进制和 -k进制下表示出来的形式是一样的非负整数的个数，例如：

2 :

3进制下：

2 = 2*(30) ， 所以2 用3进制表示的形式是2

-3 进制下：

2 = 2*(-3)0， 所以2 用-3 进制表示的形式是2

所以2 在 3 进制和-3进制下的形式是一样的。

 

再例如：

7：

3进制下：

7 = 1*(30) + 2*(31)， 所以7用3进制表示的形式是21

-3进制下：

7 = 0*(-3)0+2*(-3)1+1*(-3)2，所以7用-3进制表示的形式是120

所以7在3进制和-3进制下的形式不一样。

                                                 p

k进制：一个整数序列a0, a1, ..., ap，0 <= ai < |k| 并且 ∑(ai*ki)=x 。

                                                i=0

Input

每组输入包括一行，每行包括两个整数n和k。1 <= n <= 1e15, 2 <= k <= 1000。

Output

每组输出包括一个整数，表示答案。

Sample Input

21 3

21 2

Sample Output

9

8

Hint

第一组满足条件的非负整数：0 1 2 9 10 11 18 19 20

第二组满足条件的非负整数：0 1 4 5 16 17 20 21

Source
2014.11.29新生赛-热身赛

这题是思维题目，要明白当所有的奇数位为0的时候才会满足要求

那如果求个数呢？

举个例子：

比如 101 十进制（n = 101, k = 10）
所有的答案就是 000 001 002 …… 009 100 101 
中间那位永远都是零要不然就不是答案
所以去掉中间那位之后
0 1 2 …… 9 10 11 也就是12个
那么我们将101缩成11，那答案就是1*10^0+1*10^1 = 11，但是要加1，因为0也算一个
所以我们只需要求出比n小的数的奇数为置0，偶数为另它为k(注意是最高不为0的奇数位以后的位置)

[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. #include <stdio.h>  
  2. typedef long long  LL;  
  3. int a[65];  
  4. LL n,k;  
  5. int main()  
  6. {  
  7.    while(scanf("%lld%lld",&n,&k) != EOF)  
  8.    {  
  9.        int len = 0,pos = 0,ans,pow;  
  10.        while(n)  
  11.        {  
  12.            a[len++] = n%k;  
  13.            n /= k;  
  14.        }  
  15.        for(int i = len-1; i >= 0; i--)  //我们记录最高不为0的奇数位置
  16.        {  
  17.            if(i%2 == 1 && a[i] != 0)  
  18.            {  
  19.                pos = i;  
  20.                break;  
  21.            }  
  22.        }  
  23.   
  24.        for(int i = 0; i < pos; i += 2)  //然后把pos之前的偶数位置全部置为k-1
  25.        {  
  26.            a[i] = k-1;  
  27.        }  
  28.        ans = 0,pow = 1;  
  29.        for(int i = 0; i < len; i += 2)  
  30.        {  
  31.           ans += a[i]*pow;  
  32.           pow *= k;  
  33.        }  
  34.   
  35.        printf("%d\n",ans+1);  
  36.   
  37.    }  
  38.    return 0;  
  39. }  

无聊的小明
Time Limit: 3000 MSMemory Limit: 32768 K
Total Submit: 4(4 users)Total Accepted: 4(4 users)Rating: Special Judge: No
Description

小明想用两个字母a和b创造一个长度为n的单词，但是他又不希望连续的a超过p个，同时也不希望连续的b超过q个。那么小明有能创造出多少个不用的单词呢？

Input

每组数据包括一行，三个整数n，p，q分别对应题意。

其中max(a, b) <= n <= 50000，1 <= a, b <= 300。

Output

输出不同的单词的个数。个数要对1000000007取模。

Sample Input

3 2 1

Sample Output

4

Source
2014.11.29新生赛-热身赛

dp[i][j]表示长度为i 结尾数是j 的方案数量

ans[len]=dp[len][0]+dp[len][1]（用0,1代替a,b）
状态转移方程：
dp[i][1]+=dp[i-j][0];
dp[i][0]+=dp[i-j][1];

举例子说明：
比如0最多只能连续不超过3个
xxxxxxxxxx10
xxxxxxxxx100
xxxxxxxx1000 
这就表示结尾零的可能情况，
最后一个x必须是1
所以 dp[i][0]=dp[i-1][1]+dp[i-2][1]+dp[i-3][1]

[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. #include <stdio.h>  
  2. #include <string.h>  
  3. const int N = 50005;  
  4. const int mod = 1e9+7;  
  5.   
  6. int dp[N][2];  
  7. int main()  
  8. {  
  9.     int n,a,b;  
  10.     while(scanf("%d%d%d",&n,&a,&b)!=EOF)  
  11.     {  
  12.         memset(dp,0,sizeof(dp));  
  13.         dp[0][1]=1;  
  14.         dp[0][0]=1;  
  15.         for(int i=1;i<=n;i++)  
  16.         {  
  17.             for(int j=1;j<=i&&j<=a;j++)  
  18.             {  
  19.                 dp[i][1]+=dp[i-j][0];  
  20.                 dp[i][1]%=mod;  
  21.             }  
  22.             for(int j=1;j<=i&&j<=b;j++)  
  23.             {  
  24.                 dp[i][0]+=dp[i-j][1];  
  25.                 dp[i][0]%=mod;  
  26.             }  
  27.         }  
  28.         printf("%d\n",(dp[n][0]+dp[n][1])%mod);  
  29.     }  
  30.   
  31.     return 0;  
  32. }  

这四个题目分链接地址：

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblemVolume

第一个简单的计算机几何可以A掉，还有就是组合那题也可以递归求出，其它两题有兴趣可以看看


这篇关于哈理工新生赛热身赛解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

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

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

原文链接： https://tecdat.cn/?p=37628 6月16日，小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞，这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示，公司准备量产，并计划今年四季度开启预售小鹏汇天分体式飞行汽车，探索分体式飞行汽车城际通勤。阅读原文，获取专题报告合集全文，解锁文末271份飞行汽车相关行业研究报告。 据悉，业内人士对飞行汽车行业
阅读更多...
计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

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

🍊作者：计算机编程-吉哥 🍊简介：专业从事JavaWeb程序开发，微信小程序开发，定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事，生活就是快乐的。 🍊心愿：点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能
阅读更多...
Python：豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣，数据处理过程，数据分析，可视化，以及完整PPT报告】

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

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

开题报告中的研究方法设计：AI能帮你做什么？

AIPaperGPT，论文写作神器~ https://www.aipapergpt.com/ 大家都准备开题报告了吗？研究方法部分是不是已经让你头疼到抓狂？ 别急，这可是大多数人都会遇到的难题！尤其是研究方法设计这一块，选定性还是定量，怎么搞才能符合老师的要求？ 每次到这儿，头脑一片空白。 好消息是，现在AI工具火得一塌糊涂，比如ChatGPT，居然能帮你在研究方法这块儿上出点主意。是不
阅读更多...
【干货分享】基于SSM的体育场管理系统的开题报告（附源码下载地址）

【干货分享】基于SSM的体育场管理系统的开题报告（附源码下载地址）

中秋送好礼 中秋佳节将至，祝福大家中秋快乐，阖家幸福。本期免费分享毕业设计作品：《基于SSM的体育场管理系统》。 基于SSM的体育场管理系统的开题报告 一、课题背景与意义 随着全民健身理念的深入人心，体育场已成为广大师生和社区居民进行体育锻炼的重要场所。然而，传统的体育场管理方式存在诸多问题，如资源分配不均、预约流程繁琐、数据统计不准确等，严重影响了体育场的使用效率和用户体验。
阅读更多...
[SWPUCTF 2021 新生赛]web方向(一到六题) 解题思路，实操解析，解题软件使用，解题方法教程

[SWPUCTF 2021 新生赛]web方向(一到六题) 解题思路，实操解析，解题软件使用，解题方法教程

题目来源 NSSCTF | 在线CTF平台因为热爱，所以长远！NSSCTF平台秉承着开放、自由、共享的精神，欢迎每一个CTFer使用。https://www.nssctf.cn/problem   [SWPUCTF 2021 新生赛]gift_F12 这个题目简单打开后是一个网页  我们一般按F12或者是右键查看源代码。接着我们点击ctrl+f后快速查找，根据题目给的格式我们搜索c
阅读更多...
【中国国际航空-注册/登录安全分析报告】

【中国国际航空-注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击，存在如下安全问题： 1. 暴力破解密码，造成用户信息泄露 2. 短信盗刷的安全问题，影响业务及导致用户投诉 3. 带来经济损失，尤其是后付费客户，风险巨大，造成亏损无底洞 所以大部分网站及App 都采取图形验证码或滑动验证码等交互解决方案， 但在机器学习能力提高的当下，连百度这样的大厂都遭受攻击导致点名批评， 图形验证及交互验证方式的安全性到底如
阅读更多...
hdu1879(解题报告)

hdu1879(解题报告)

继续畅通工程                                   Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
阅读更多...
hdu2033(解题报告)

hdu2033(解题报告)

人见人爱A+B                                   Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
阅读更多...
HDU3791(解题报告)

HDU3791(解题报告)

二叉搜索树                      Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)                                          Total Subm
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2