devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

ZZULI新生周赛(8)部分题题解

作者：IT小白 | 2024-07-26 07:58:51

赞

踩

ZZULI新生周赛(8)部分题题解

问题 A: 一道简单题 

题目描述

ZYZ老师正在热情的准备着给大家发放的冰墩墩（是我雪容融不配了），在每一个包裹里都有一定数量的冰墩墩，现在ZYZ老师为了提前给大家发放，他想找到包裹中数量最多的那一个，但是准备发放时ZYZ老师想了想，感觉可能不太够，于是他就想从剩下的那些中再找到装有最多冰墩墩的包裹，即一共会发放两个包裹。现在ZYZ老师想知道，他一共可以提前发放多少数量的冰墩墩。

输入

第一行包括一个整数n(2 <= n <= 107)，代表现有的包裹数量。

第二行包括n个整数，a1,a2,...an(1 <= ai <= 1018),代表每一个包裹中冰墩墩的数量。

输出

输出一个整数，代表ZYZ老师一共可以提前发放的冰墩墩的数量。

样例输入 Copy 
3

2 1 3
样例输出 Copy 

5
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. void work()
  5. {
  6.     ll n;
  7.     scanf("%lld", &n);
  8.     ll m1;
  9.     ll m2;
  10.     ll a;
  11.     scanf("%lld", &a);
  12.     m1 = a;
  13.     scanf("%lld", &a);
  14.     m2 = a;
  15.     if (m1 < m2)
  16.     {
  17.         ll t = m1;
  18.         m1 = m2;
  19.         m2 = t;
  20.     }
  21.     for (int i = 1; i <= n - 2; i++)
  22.     {
  23.         scanf("%lld", &a);
  24.         if (a > m1)
  25.         {
  26.             m2 = m1;
  27.             m1 = a;
  28.         }
  29.         else if (a > m2)
  30.         {
  31.             m2 = a;
  32.         }
  33.     }
  34.     cout << m1 + m2 << endl;
  35. }
  36. int main()
  37. {
  38.     work(); return 0;
  39. }

问题 B: 传送站

题目描述

现宇宙中有两家转送站公司，小洛克想要从洛克星球a去往希望星球b。

我们把这些星球都简化到一条直线上，标号为1 - n，并且规定从星球i传送到星球j，如果其分别属于两家公司，那么他将花费|i - j|元，如果是同一家公司那么将没有任何费用,现在请你帮忙算一下其其前往希望星球至少需要多少元。
 

输入

第一行一个整数n(1 <= n <= 1000)。

第二行一个只含01的字符串。如果i位置上为0代表第i个星球使用第一家公司的传送站，为1代表其使用第二家公司的传送站。

第三行两个整数a , b(1 <= a,b <= n)代表出发地和目的地。
 

输出

输出一个整数，代表最小费用。
 

样例输入 Copy 
8
00000001
1 8
样例输出 Copy 

1

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. char s[1010];
  5. void work()
  6. {
  7.     int n;
  8.     cin >> n;
  9.     cin >> s;
  10.     int a, b;
  11.     cin >> a >> b;
  12.     if (s[a - 1] != s[b - 1])cout << 1 << endl;
  13.     else cout << 0 << endl;
  14. }
  15. int main()
  16. {
  17.     work(); return 0;
  18. }

问题 C: 收集魔卡

题目描述

小樱正在辛苦的收集魔卡，我们把每一个地点的魔卡简化到一条直线上，下标从1-n,小樱可以选择从某个地点开始往后连续的搜集（走到某格将代表拾取此处的魔卡），并且在某一地点停止而去战斗（走一格也可以），但是为了在战斗时拥有更多的选择，她想要至少搜集到k个正义的魔卡，同时要避免搜集到召唤恶灵的魔卡，现在小樱想要知道她一共可以有多少个搜集的方案。
 

输入

第一行输入两个正整数n(1 <= n <= 200000) 和 k(1 <= k <= 15),

第二行输入一行字符串，字符串仅包含大写字母（A到Z）。

E代表正义的魔卡，G代表召唤恶灵的魔卡。
 

输出

输出小樱的有效搜索的方案数。
 

样例输入 Copy 
5 1
EAEGE
样例输出 Copy 
6
提示
合法的方案：
s[1,1] = E
s[1,2] = EA
s[1,3] = EAE
s[2,3] = AE
s[3,3] = E
s[6,6] = E

一开始找了好长时间规律才AC了，后来队友告诉我可以暴力，我**，像个沙雕。 

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. char s[200005];
  5. ll res[200005];
  6. ll cnt[200005];
  7. struct node
  8. {
  9.     int w;
  10. }q[200005];
  11. void work()
  12. {
  13.     ll n, k;
  14.     cin >> n >> k;
  15.     cin >> s;
  16.     ll len = strlen(s);
  17.     ll ccnt = 0;
  18.     ll ans = 0;
  19.     if (s[0] == 'E')
  20.     {
  21.         res[0] = 1, cnt[0] = 0, q[ccnt++].w = 0;
  22.         if (k == 1)ans++;
  23.     }
  24.     ll youxiao = 0;
  25.     ll wuxiao = -1;
  26.     for (ll i = 1; i < len; i++)
  27.     {
  28.         if (s[i] == 'G')wuxiao = i, cnt[i] = 0, res[i] = 0, youxiao = i, ccnt = 0;
  29.         else if (s[i] == 'E')
  30.         {
  31.             res[i] = res[i - 1] + 1;
  32.             if (youxiao == wuxiao)youxiao = i;
  33.             q[ccnt++].w = i;
  34.             if (res[i] >= k)ans += q[ccnt - k].w - youxiao + 1;
  35.         }
  36.         else
  37.         {
  38.             res[i] = res[i - 1];
  39.             if (youxiao == wuxiao)youxiao = i;
  40.             if (res[i] >= k)
  41.             {
  42.                 ans += q[ccnt - k].w - youxiao + 1;
  43.             }
  44.         }
  45.     }
  46.     cout << ans << endl;
  47. }
  48. int main()
  49. {
  50.     work();
  51.     return 0;
  52. }

问题 D: 四六级成绩

题目描述

四六级成绩出来了，几家欢喜几家愁，裸考好几次的小明这次又没有过，他发誓要好好学习，决定从听力抓起（谁听听力呀）。
但他现在只能听学校放出的英语录音来进行练习，并且学校规定每50分钟播放一套英语录音，然后间隔10分钟停止播放，
我们假设从第一分钟开始播放第一个套录音，现在他想知道如果从t1分钟学习到t2分钟，他一共可以听多长时间的录音呢？

输入

第一行输入测试用例T,

每个测试用例输入两个整数t1,t2。

数据范围：

1<=T<=10,1<=t1<=t2<=1018 。

输出

如果小时数是整数，请输出：h小时

如果不是，请输出：h小时m分钟

样例输入 Copy

2
1 70
80 265

样例输出 Copy

1小时
2小时36分钟

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main()
  5. {
  6.     int t;
  7.     cin >> t;
  8.     while (t--)
  9.     {
  10.         ll h = 0, m = 0;
  11.         ll t1, t2;
  12.         cin >> t1 >> t2;
  13.         ll yu1 = t1 % 60;
  14.         ll yu2 = t2 % 60;
  15.         ll zheng1 = t1 / 60;
  16.         ll zheng2 = t2 / 60;
  17.         if (zheng2 > zheng1)
  18.         {
  19.             m += yu1 > 50 ? 0 : (50 - yu1 + 1);
  20.             m += 50 * (zheng2 - zheng1 - 1);
  21.             m += yu2 > 50 ? 50 : yu2;
  22.         }
  23.         else
  24.         {
  25.             if (yu2 > 50)
  26.             {
  27.                 if (yu1 <= 50)m += 50 - yu1 + 1;
  28.             }
  29.             else m += yu2 - yu1 + 1;
  30.         }
  31.         h = m / 60;
  32.         m %= 60;
  33.         if (m == 0)printf("%lld小时\n", h);
  34.         else printf("%lld小时%lld分钟\n", h, m);
  35.     }
  36.     return 0;
  37. }

问题 E: 剪彩带

题目描述

小明和自己的一群伙伴去帮助老师剪裁彩带。

每个人发到手中的彩带的长度都不是完全相同的，每次小明会说，裁到x的位置，那么每个人都会从自己彩带1位置往后找到x的地方剪下然后上交给小明（即彩带x+1到 彩带末尾的这一段）。如果不够长小命就会接着再说出一个x大家照做。

其实小明只是想一共裁出总和至少长为m的彩带，但是每次比较太慢了，现在小明相向你请教，请你告诉小明让所有人从x处裁减就能获得长至少为m的彩带，并且保证x最大，也就是从x+1处的话就不够了。
 

输入


 

第一行两个整数n(1 <= n <= 106)和m(1 <= m <= 106),n代表裁剪彩带及裁剪人的个数，m代表彩带的总需求长度。

第二行n个整数代表每条彩带的长度（1 <= 彩带长度 <= 109）。
 


 

输出

输出一个整数代表最大的x的值

样例输入 Copy 
4 7
20 15 10 17
样例输出 Copy 
15

与C问题一样，写了一些需要思维的地方，结果队友告诉我暴力能过，，，，说多了都是泪 

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll a[1000006];
  5. void work()
  6. {
  7.     ll n, m;
  8.     cin >> n >> m;
  9.     ll aans = 0;
  10.     for (int i = 0; i < n; i++)
  11.     {
  12.         cin >> a[i]; aans += a[i];
  13.     }
  14.     sort(a, a + n);
  15.     ll ans = 0;
  16.     ll res = 0;
  17.     int f = 0;
  18.     for (int i = n - 1; i >= 1; i--)
  19.     {
  20.         res++;
  21.         ans += (a[i] - a[i - 1])*res;
  22.         if (ans > m)
  23.         {
  24.             ans -= (a[i] - a[i - 1])*res;
  25.             ll cnt = (m - ans) / res;
  26.             if ((m - ans) % res)cnt++;
  27.             cout << a[i] - cnt << endl;
  28.             f = 1;
  29.             break;
  30.         }
  31.     }
  32.     if (!f)
  33.     {
  34.         ll z = (aans - m) / n;
  35.         if ((aans - m) % n)z++;
  36.         cout << z << endl;
  37.     }
  38. }
  39. int main()
  40. {
  41.     work(); return 0;
  42. }

问题 I: 勇士之力

题目描述

勇士一斗为了拯救九条裟罗，他必须要穿越一片迷宫。一斗每次只能向东或者向南走，不能向西或者向北走。这个迷宫的入口位于西北角，而迷宫的出口位于东南角。

迷宫的每个道路交叉点都存在一个丘丘人，丘丘人的种类不同，他们的攻击力也不同。丘丘人的种类有很多种，列如可能会有木盾丘丘人，冰盾丘丘人，爆弹丘丘人，雷弹丘丘人，射手丘丘人，冰箭丘丘人，风丘丘萨满，草丘丘萨满，和一斗最讨厌的冰丘丘萨满等等多种丘丘人。我们会给出每种丘丘人的攻击力，并且用数字来代表位于迷宫道路交叉点的丘丘人是什么种类。

一斗有一个初始血量W，他每经过一个道路交叉点就会与位于哪里的丘丘人交战，虽然一斗有着斗战岩牛，但还是要不可避免的扣除一次丘丘人的攻击力大小的血量。请问一斗是否能在血量大于0的情况下在迷宫的出口处遇到九条裟罗，如果可以的话就输出剩余的最大血量，否则输出-1。

注意：起点西北角和出口东南角不存在丘丘人，也就是说值为0。

输入

第一行是两个整数n,m分别代表迷宫的行数和列数。

第二行是一斗的初始血量W。

第三行是丘丘人的种类数量k

第四行是k个丘丘人的攻击力x，以空格隔开。注意我们认为丘丘人的种类编号是1~k。0默认为没有丘丘人。

接下来是n行数据每行数据有m个数，从左向右顺序描述了每个道路交叉点的丘丘人种类y。

数据范围:

2<=n,m<=100

1<=W<=5000

1<=k<=15

1<=x<=200

1<=y<=k

输出

输出一斗到达迷宫出口时剩余的最大血量，如果小于等于0则输出-1.

样例输入 Copy 
3 3
10
3
2 1 3
0 3 3
2 2 3
2 1 0
样例输出 Copy 
6

一开始用dfs一直***超时过不去，后来用dp成功AC 

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int n, m;
  5. int w;
  6. int k;
  7. int gj[20];
  8. int dp[105][105];
  9. int main()
  10. {
  11.     scanf("%d%d", &n, &m);
  12.     scanf("%d", &w);
  13.     scanf("%d", &k);
  14.     for (int i = 1; i <= k; i++)scanf("%d", &gj[i]);
  15.     for (int i = 1; i <= n; i++)
  16.         for (int j = 1; j <= m; j++)
  17.         {
  18.             scanf("%d", &dp[i][j]);
  19.             int t = dp[i][j];
  20.             dp[i][j] = gj[t];
  21.         }
  22.     for (int i = 2; i <= n; i++)
  23.     {
  24.         dp[i][1] += dp[i - 1][1];
  25.     }
  26.     for (int i = 2; i <= m; i++)
  27.     {
  28.         dp[1][i] += dp[1][i - 1];
  29.     }
  30.     for (int i = 2; i <= n; i++)
  31.         for (int j = 2; j <= m; j++)
  32.         {
  33.             dp[i][j] += min(dp[i - 1][j], dp[i][j - 1]);
  34.         }
  35.     int ans = w - dp[n][m];
  36.     if (ans > 0)cout << ans << endl;
  37.     else cout << -1 << endl;
  38.     return 0;
  39. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/884280
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号